This JS minimax code for playing tic-tac-toe isn’t finding the best moves, even when there is a win in one move. What is wrong with it?
/**
* Return a list of possible moves on the board.
*
* @param {string[]} board - The board.
* @returns {number[]}
*/
function actions(board) {
const acts = [];
for (let i = 0; i < board.length; i++) {
if(board[i] == " ") {
acts.push(i);
}
}
return acts;
}
/**
* Return number of occupied squares on the board.
*
* @param {string[]} board - The board.
* @returns {number}
*/
function occupied(board) {
return board.filter((pos) => pos != " ").length;
}
/**
* Decide whether the game is over.
*
* @param {string[]} board - The board.
* @returns {boolean} - true if there is a winner or all cells are occupied, otherwise false.
*/
export function terminal(board) {
return getWinner(board) || occupied(board) === 9;
}
/**
* Calculate the winner, if any.
*
* @param {string[]} board - The board.
* @returns {string} - The name of the winner, or null.
*/
export function getWinner(board) {
const lines = [
[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 winner = null;
for (let i = 0; i < lines.length; i++) {
const [a, b, c] = lines[i];
if (board[a] != " " && board[a] == board[b] && board[a] == board[c]) {
winner = board[a];
break;
}
}
return winner;
}
/**
* Calculate the value of a board.
*
* @param {string[]} board - The board.
* @returns {number} - 1 if the board is won by X, -1 if the board is won by O, otherwise 0.
*/
function utility(board) {
const w = getWinner(board);
if (w == 'X') {
return 1;
} else if (w == 'O') {
return -1;
} else {
return 0;
}
}
/**
* Return the board that results from taking a move.
*
* @param {string[]} board - The board.
* @returns {string[0]} - The new board.
*/
function result(board, move) {
const result = board.slice();
result[move] = player(board);
return result;
}
/**
* Calculate whose move it is.
*
* @param {string[]} board - The board.
* @returns {string} - The name of the next player.
*/
function player(board) {
return occupied(board) % 2 == 0 ? 'X' : 'O';
}
/**
* Implementation of the Minimax algorithm.
*
* @param {string[]} board - The board.
* @param {boolean} xIsNext - true if X is next.
* @returns {number} - The best move to take for the current player.
*/
export function minimax(board, isMaximizingPlayer) {
if (terminal(board)) {
return [utility(board), null]; // Return utility and null move for terminal states
}
let bestValue = isMaximizingPlayer ? -Infinity : Infinity;
let bestMove = null;
actions(board).forEach((move) => {
let newBoard = result(board, move);
let [value, _] = minimax(newBoard, !isMaximizingPlayer);
if (isMaximizingPlayer) {
if (value > bestValue) {
bestValue = value;
bestMove = move;
}
} else {
if (value < bestValue) {
bestValue = value;
bestMove = move;
}
}
});
return [bestValue, bestMove];
}