我正试图使用minimax算法在javaScript中制作Tic-Tac-Toe,但似乎我做错了什么,minimax算法没有检测到最佳动作。这是代码:
const board = ["X", null, null, null, null, "X", "X", "O", "O"];
/*
X _ _
_ _ X
X O O
*/
// duplicate passed board and return the new board state
const makeAIMove = (currentBoard, square, player) => {
const nextBoard = [...currentBoard];
nextBoard[square] = player;
return nextBoard;
};
// find empty squares
const emptySquares = (sqBoard) =>
sqBoard
.map((sq, idx) => (sq === null ? idx : null))
.filter((sq) => sq !== null);
// check if no empty squares are available
const isFinished = (sqBoard) => (emptySquares(sqBoard).length ? false : true);
// check winner
const checkWinner = (sqBoard) => {
const winConditions = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[0, 4, 8],
[2, 4, 6],
];
for (const winCondition of winConditions) {
[a, b, c] = winCondition;
if (sqBoard[a] && sqBoard[a] === sqBoard[b] && sqBoard[a] === sqBoard[c])
return sqBoard[a];
}
return false;
};
// minimax algorithm
const minimax = (sqBoard, depth, isMaximizer) => {
// terminal checker
const theWinner = checkWinner(sqBoard);
// we have a winner
if (theWinner) {
return theWinner === "X" ? -10 : 10;
}
// it's a tie
if (isFinished(sqBoard)) {
return 0;
}
let bestScore;
if (isMaximizer) {
bestScore = -1000;
emptySquares(sqBoard).forEach((square) => {
// make a sample move
let nextBoard = makeAIMove(sqBoard, square, "O");
// recursion
let score = minimax(nextBoard, depth + 1, false);
bestScore = Math.max(bestScore, score);
});
} else {
bestScore = 1000;
emptySquares(sqBoard).forEach((square) => {
let nextBoard = makeAIMove(sqBoard, square, "X");
let score = minimax(nextBoard, depth + 1, true);
bestScore = Math.min(bestScore, score);
});
}
return bestScore;
};
// find the best move
const nextBestMove = (sqBoard) => {
let nextMoveArray = [];
let remainedSquares = emptySquares(sqBoard);
remainedSquares.forEach((square) => {
let nextBoard = makeAIMove(sqBoard, square, "O");
let theScore = minimax(nextBoard, 0, true);
nextMoveArray.push({
sq: square,
sc: theScore,
});
});
nextMoveSorted = nextMoveArray.sort((a, b) => (a.sc < b.sc ? 1 : -1));
return nextMoveSorted[0].sq;
};
console.log(nextBestMove(board));
在上述情况下,最好的移动是通过在棋盘[3]上填一个“0”来阻止X获胜,但是它总是检测到另一个得分更高的移动。
有人能帮助我理解我的代码出了什么问题吗?
非常感谢。
从你的代码中,我了解到 X 是最小化,O 是最大化玩家。但是后来我看到这段代码:
let nextBoard = makeAIMove(sqBoard, square, "O");
let theScore = minimax(nextBoard, 0, true);
因此,在O移动后,您调用minimax
,其中isMaximizer
设置为true。但这将使<code>minimax</code>在O已经玩过的情况下玩另一个O招式。你想得到X的最佳回复,所以你应该在这里传递false
:
let theScore = minimax(nextBoard, 0, false);
现在,这将为每一次这样的呼叫返回-10(所以对于O的每一次移动),因为游戏对于O已经处于失败状态,无论它做什么,X都会赢。如果O在3移动,那么X将以双重攻击玩2。
如果你想区分快赢和慢赢,那么你应该在每次回溯时调整分数。
例如,您可以将< code>return bestScore语句替换为返回一个更接近零的值。例如-10变成了-9,5变成了4,而0仍然是0:
return bestScore - Math.sign(bestScore);
通过此更改,O 将在 3 处播放,因为它的分数是 -7(仍然输),而其他移动都得分为 -9(从 X 开始一步立即失败)。