Почему мой алгоритм Minimax не дает правильных ходов?
Алгоритм работает без ошибок, но ИИ совсем не умен и, похоже, делает случайные шаги. Я работал над этим два дня и не могу понять, где я ошибся. Может кто-нибудь помочь найти ошибку, из-за которой он не может сделать правильный ход?
При запуске игры ИИ всегда должен делать ход по индексу 4 (средний квадрат), если только я не займу это место, но он этого не делает, а также вообще не пытается выиграть.
$(document).ready(function() {
let X = {
isComputer: false,
symbol: "x",
marker: "<img src='img/x.png'>",
winMarker: "<img src='img/xWin.png'>"
}
let O = {
isComputer: false,
symbol: "o",
marker: "<img src='img/o.png'>",
winMarker: "<img src='img/oWin.png'>"
}
let game = {
board: [0,1,2,3,4,5,6,7,8],
firstTurn: X,
xScore: 0,
oScore: 0,
turnNumber: 0,
started: false
}
let winningCombos = [
[0,1,2], [3,4,5], [6,7,8],
[0,3,6], [1,4,7], [2,5,8],
[0,4,8], [2,4,6]
];
let theWinningCombo;
let player = X;
let clearBoardTimeoutID;
let ai1;
let ai2;
function clearBoardForNextGame() {
clearBoardTimeoutID =
setTimeout(function() {
$('.square').empty();
game.firstTurn = game.firstTurn == X ? O : X;
game.turnNumber = 0;
game.board = [0,1,2,3,4,5,6,7,8];
game.started = true;
}, 1500);
}
function thisPlayerWon(board, symbol) {
for (let i = 0; i < winningCombos.length; i++) {
let counter = 0;
for (let j = 0; j < winningCombos[i].length; j++) {
if (board[winningCombos[i][j]] == symbol) {
counter++;
}
if (counter == 3) {
theWinningCombo = winningCombos[i];
return true;
}
}
}
return false;
}
function showWinnerAndUpdateScore(combo, player) {
game.started = false;
combo.forEach(index => $('#' + index).html(player.winMarker));
player == X ? (game.xScore++, $('#score1').text(game.xScore)) : (game.oScore++, $('#score2').text(game.oScore))
}
function AImove(AIplayer, board) {
AIplayer = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);
let opponent = AIplayer == X ? O : X;
let bestMove = minimax(AIplayer, board, 0);
board[bestMove] = AIplayer.symbol;
$('#' + bestMove).html(AIplayer.marker);
game.turnNumber++;
function minimax(player, board, depth) {
let spotsNotMarked = emptyBoardSpots(board);
if (thisPlayerWon(board, AIplayer.symbol)) {
return 10-depth;
}
else if (thisPlayerWon(board, opponent.symbol)) {
return depth-10;
}
else if (spotsNotMarked.length == 0) {
return 0;
}
let moves = [];
let scores = [];
for (let i = 0; i < spotsNotMarked.length; i++) {
let index = spotsNotMarked[i];
let score;
board[index] = player.symbol;
if (player == X) {
score = minimax(O, board, depth+1);
}
else {
score = minimax(X, board, depth+1);
}
scores.push(score);
board[index] = index;
moves.push(index);
}
if (player == AIplayer) {
return moves[scores.indexOf(Math.max(...scores))];
}
else {
return moves[scores.indexOf(Math.min(...scores))];
}
}
}
function emptyBoardSpots(board) {
return board.filter(square => !isNaN(square));
}
$('.AI-Switch').on('change', function() {
if (!game.started) {
this.id == "one" ? (X.isComputer = !(X.isComputer), ai1 = X) : (O.isComputer = !(O.isComputer), ai2 = O);
}
});
$('#resetButton').on('click', function() {
clearTimeout(clearBoardTimeoutID);
$('.square').empty();
$('.scores').text("0");
game.board = [0,1,2,3,4,5,6,7,8];
game.firstTurn = X;
game.xScore = 0;
game.oScore = 0;
game.turnNumber = 0;
game.started = false;
});
$('#startButton').on('click', function() {
game.started = true;
});
$('.square').on('click', function() {
if (game.started && !isNaN(game.board[this.id])) {
player = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);
this.innerHTML = player.marker;
game.board[this.id] = player.symbol;
game.turnNumber++;
if (game.turnNumber > 3 && thisPlayerWon(game.board, player.symbol)) {
showWinnerAndUpdateScore(theWinningCombo, player);
clearBoardForNextGame();
}
else if (game.turnNumber == 9) {
clearBoardForNextGame();
}
if (O.isComputer && player == X) {
AImove(player, game.board);
}
else if (X.isComputer && player == O) {
AImove(player, game.board);
}
}
});
});
1 ответ
Решение
Проблема заключается в возвращаемом значении minimax: это оценка или это движение?
Эта проблема
Вы полагаете, что рекурсивный вызов должен вернуть счет, за исключением первого вызова, когда он должен вернуть ход. Это действительно было бы удобно, но это не то, что происходит:
- Только при обнаружении выигрыша или ничьей функция возвращает счет
- Во всех (!) Других случаях ход возвращается
Это означает, что на полпути вниз по дереву рекурсии (еще не на листе) вы также получаете ходы назад... но вы рассматриваете их как баллы на один уровень выше в дереве рекурсии. Очевидно, что это делает любой результат бессмысленным.
Решение
Пусть ваш minimax Функция возвращает счет, а также ход (при необходимости) одновременно. Это можно сделать, вернув объект с двумя частями информации.
Вот твой AImove Функция с несколькими изменениями для реализации этой идеи. Измененные строки отмечены ***:
function AImove(AIplayer, board) {
AIplayer = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);
let opponent = AIplayer == X ? O : X;
let bestMove = minimax(AIplayer, board, 0).move; // *** Get move part of return value
board[bestMove] = AIplayer.symbol;
$('#' + bestMove).html(AIplayer.marker);
game.turnNumber++;
function minimax(player, board, depth) {
if (depth===2) console.log('step');
let spotsNotMarked = emptyBoardSpots(board);
if (thisPlayerWon(board, AIplayer.symbol)) {
return { score: 10-depth }; // *** Object with score (there's no move)
}
else if (thisPlayerWon(board, opponent.symbol)) {
return { score: depth-10 }; // *** idem
}
else if (spotsNotMarked.length == 0) {
return { score: 0 }; // *** idem
}
let moves = [];
let scores = [];
for (let i = 0; i < spotsNotMarked.length; i++) {
let index = spotsNotMarked[i];
let score;
board[index] = player.symbol;
if (player == X) {
score = minimax(O, board, depth+1).score; // *** Get score part
}
else {
score = minimax(X, board, depth+1).score; // *** idem
}
scores.push(score);
board[index] = index;
moves.push(index);
}
let score = (player == AIplayer ? Math.max : Math.min)(...scores); // *** Get score
return { score, move: moves[scores.indexOf(score)] }; // *** Return both move & score
}
}