'Minimax Algorithm - Tic Tac Toe AI not selecting best move
I've been working on writing a minimax algorithm for my tictactoe game, but it doesn't seem to be choosing the correct move. It is possible to win against the computer, so I must have something mixed up here.
I based my algorithm off this article (I had to alter my minimax code since my code was different from the example in the article)
// Checking if there are any moves remaining on the board. Returns false if there are no moves left to play
const isMovesLeft = function () {
if (gameBoard._moves === 9) {
return false;
} else {
return true;
}
};
// Evaluates if the maximiser or minimiser has won or draw - returns a number if there is a win or draw
const evaluate = function () {
if (gameBoard._roundWon && gameBoard._currentPlayer === gameBoard._player1)
return +10;
if (gameBoard._roundWon && gameBoard._currentPlayer === gameBoard._player2)
return -10;
if (gameBoard._roundTie) return 0;
};
// Minimax function - considers all the possible ways the game can go and returns the value of the board
const minimax = function (board, depth, isMax) {
let score = evaluate();
// If maximiser has won the game - return evaluated score
if (score === 10) return score;
// If minimiser has won the game - return evaluated score
if (score === -10) return score;
// If there are no moves left and there is no winner - then return as a tie
if (isMovesLeft() === false) return 0;
// If it is the maximiser's turn
if (isMax) {
let bestScore = -1000;
let availableTiles = [];
// Looping through all tiles
tile.forEach((tile, index) => {
// Check if cell is empty
if (tile.textContent === '') {
availableTiles.push(index);
}
});
// Make the move
const chosenEmptyTile =
availableTiles[Math.floor(Math.random() * availableTiles.length)];
renderAITile(tile, chosenEmptyTile);
addPlayerMoves(chosenEmptyTile);
// Calling minimax recursively and choose the maximum value
bestScore = Math.max(bestScore, minimax(board, depth + 1, false));
console.log(bestScore);
// Undo the move
undoAIMove(tile, chosenEmptyTile);
return bestScore;
} else {
let bestScore = 1000;
let availableTiles = [];
// Looping through all tiles
tile.forEach((tile, index) => {
// Check if cell is empty
if (tile.textContent === '') {
availableTiles.push(index);
}
});
// Make the move
const chosenEmptyTile =
availableTiles[Math.floor(Math.random() * availableTiles.length)];
renderAITile(tile, chosenEmptyTile);
addPlayerMoves(chosenEmptyTile);
// Calling minimax recursively and choose the maximum value
bestScore = Math.min(bestScore, minimax(board, depth + 1, false));
// Undo the move
undoAIMove(tile, chosenEmptyTile);
return bestScore;
}
};
const undoAIMove = function (tile, chosenEmptyTile) {
tile[chosenEmptyTile].textContent = '';
tile[chosenEmptyTile].classList.remove(`playerX`);
tile[chosenEmptyTile].classList.remove(`playerO`);
gameBoard._board[chosenEmptyTile] = '';
gameBoard._moves -= 1;
};
// Return the best possible move for the AI
const findBestMove = function (board) {
let bestVal = -1000;
let bestMove = [];
let availableTiles = [];
// Traverse all cells, evaluate minimax function for all empty cells. And return the cell with optimal value.
tile.forEach((tile, index) => {
if (tile.textContent === '') {
availableTiles.push(index);
}
});
// Make the move
console.log(`Empty Tile: ${availableTiles}`);
const chosenEmptyTile =
availableTiles[Math.floor(Math.random() * availableTiles.length)];
console.log(`Chosen tile: ${chosenEmptyTile}`);
renderAITile(tile, chosenEmptyTile);
addPlayerMoves(chosenEmptyTile);
console.log(gameBoard._board);
// Compute evaluation function for this move
let moveVal = minimax(board, 0, false);
// Undo the move
undoAIMove(tile, chosenEmptyTile);
// If value of the current move is more than the best value, then update best
if (moveVal > bestVal) {
bestVal = moveVal;
bestMove.push(chosenEmptyTile);
gameBoard._board[chosenEmptyTile] = 'X';
renderAITile(tile, bestMove);
}
return bestMove;
};
const startGameAI = function () {
if (gameBoard._aiTurn && gameBoard._opponent === 'AI') {
// Finding best move
findBestMove(gameBoard._board);
// Store AI moves in data
addPlayerMoves();
console.log(gameBoard._moves);
// Check if game over or tie
checkGameOver();
// Switch players
switchPlayers();
renderScoreBoard();
}
};
// Renders the tile AI selects
const renderAITile = function (tile, randomEmptyTileIndex) {
if (gameBoard._roundWon || gameBoard._roundTie || !gameBoard._isGameActive)
return;
if (gameBoard._aiTurn) {
tile[randomEmptyTileIndex].textContent = 'X';
tile[randomEmptyTileIndex].classList.add(
`player${gameBoard._currentPlayer}`
);
}
};
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
