As part of a course, I tried to implement minimax in a game of Tic-Tac-Toe in which the human player plays first (marker 'X', adds 1 to array) and the computer plays second (marker 'O', adds -1 to array). The minimax sort of works, in the sense that I cannot win the game except if I play middle row or middle column.
let main = (function() {
let currentPlayer;
let gameOver = false;
let boardArray = Gameboard();
const dialogElement = document.querySelector('[data-modal]');
const gameContainer = document.querySelector('[data-game-container]');
// gameboard array
function Gameboard() {
const board = [];
const columns = 3;
const rows = 3;
// create a 2d array and populate it with 0s
for (let i = 0; i < rows; i++) {
board[i] = [];
for (let j = 0; j < columns; j++) {
board[i][j] = 0;
}
}
return board;
}
//let boardArray = Gameboard();
const gameController = function(param) {
// defining and initializing variables
// the unary plus operator turns the string into an integer
const gameChoice = +param.choice;
const player1 = Players(param.playerX, 1);
const player2 = Players(param.playerO, -1);
const board = boardArray;
let gameboardCells = document.querySelectorAll('.board-cell');
currentPlayer = player1.marker;
// click and game logic for 2 player game
if (gameChoice === 0) {
gameboardCells.forEach(cell => {
cell.addEventListener('click', (event) => {
const index = event.target.dataset.index;
let arrayColumn = index % 3;
let arrayRow = (index - arrayColumn) / 3;
// add the marker of the current player in the array
if (board[arrayRow][arrayColumn] === 0 && gameOver === false) {
board[arrayRow][arrayColumn] = currentPlayer;
currentPlayer = currentPlayer === player1.marker ? player2.marker : player1.marker;
announceTurn(currentPlayer);
} else {
return
}
renderUI.addMarker(board);
checkWinningCombinations(board);
});
});
} else if (gameChoice === 1) {
playEasyAI(gameChoice, player1, board, gameboardCells);
} else if (gameChoice === 2) {
playUnbeatableAI(gameChoice, player1, board, gameboardCells)
}
}
function playEasyAI(choice, player, array, cells) {
board = array;
gameboardCells = cells;
player = 1;
// player vs. easy AI game
// human clicks + computer pushes in random available cell
// get available cells
gameboardCells.forEach(cell => {
cell.addEventListener('click', (event) => {
const index = event.target.dataset.index;
let arrayColumn = index % 3;
let arrayRow = (index - arrayColumn) / 3;
if (board[arrayRow][arrayColumn] === 0 && gameOver === false) {
board[arrayRow][arrayColumn] = player;
} else {
return
}
// checkWinningCombinations(board) to see if human player wins
// so that computer does not play after human won
checkWinningCombinations(board);
// get available cells
const availableCells = [];
for (let row = 0; row < board.length; row++) {
for (let col = 0; col < board[row].length; col++) {
if (board[row][col] === 0) {
availableCells.push({
row,
col
});
}
}
}
if (availableCells.length > 0 && gameOver === false) {
randomIndex = Math.floor(Math.random() * availableCells.length);
const easyAiMove = availableCells[randomIndex];
board[easyAiMove.row][easyAiMove.col] = -1;
}
renderUI.addMarker(board);
checkWinningCombinations(board);
});
});
}
function playUnbeatableAI(choice, player, array, cells) {
board = array;
gameboardCells = cells;
player = 1;
// player vs. easy AI game
// human clicks + computer pushes in random available cell
// get available cells
gameboardCells.forEach(cell => {
cell.addEventListener('click', (event) => {
const index = event.target.dataset.index;
let arrayColumn = index % 3;
let arrayRow = (index - arrayColumn) / 3;
if (board[arrayRow][arrayColumn] === 0 && gameOver === false) {
board[arrayRow][arrayColumn] = player;
renderUI.addMarker(board);
checkWinningCombinations(board);
const aiMove = getBestMove(board);
console.log(aiMove);
board[aiMove.row][aiMove.col] = -1; // Set the AI move on the board
} else {
return
}
renderUI.addMarker(board);
checkWinningCombinations(board);
});
});
}
function minimax(board, depth, isMaximizing) {
// Evaluate the board and return a score if the game is over
const result = evaluate(board);
const HUMAN_PLAYER = 1;
const AI_PLAYER = -1;
if (result !== 0) {
return result;
}
// If it's the AI's turn (maximizing player)
if (isMaximizing) {
let bestScore = -Infinity;
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
// If the cell is empty
if (board[row][col] === 0) {
board[row][col] = HUMAN_PLAYER;
const score = minimax(board, depth + 1, false);
board[row][col] = 0; // Undo the move
bestScore = Math.max(score, bestScore);
}
}
}
return bestScore;
} else {
// If it's the human's turn (minimizing player)
let bestScore = Infinity;
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
// If the cell is empty
if (board[row][col] === 0) {
board[row][col] = AI_PLAYER;
const score = minimax(board, depth + 1, true);
board[row][col] = 0; // Undo the move
bestScore = Math.min(score, bestScore);
}
}
}
return bestScore;
}
}
function getBestMove(board) {
let bestMove = {
row: -1,
col: -1
};
let bestScore = -Infinity;
const HUMAN_PLAYER = 1;
const AI_PLAYER = -1;
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
if (board[row][col] === 0 && gameOver === false) {
board[row][col] = AI_PLAYER;
const score = minimax(board, 0, true);
board[row][col] = 0; // Undo the move
if (score > bestScore) {
bestScore = score;
bestMove = {
row,
col
};
}
}
}
}
return bestMove;
}
function evaluate(board) {
for (let row = 0; row < 3; row++) {
if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
if (board[row][0] === 1)
return -10;
else if (board[row][0] === -1)
return +10;
}
}
for (let col = 0; col < 3; col++) {
if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
if (board[0][col] === 1)
return -10;
else if (board[0][col] === -1)
return +10;
}
}
if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
if (board[0][0] === 1)
return -10;
else if (board[0][0] === -1)
return +10;
}
if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
if (board[0][2] === 1)
return -10;
else if (board[0][2] === -1)
return +10;
}
return 0;
}
const checkWinningCombinations = function(array) {
const board = array;
for (let i = 0; i < 3; i++) {
// check rows and columns for a winner
const rowSum = board[i][0] + board[i][1] + board[i][2];
const colSum = board[0][i] + board[1][i] + board[2][i];
if (colSum === 3 || rowSum === 3) {
endGame(1);
return -10;
} else if (colSum === -3 || rowSum === -3) {
endGame(-1);
return +10;
}
}
// check diagonals for a winner
const diagonalSum1 = board[0][0] + board[1][1] + board[2][2];
const diagonalSum2 = board[0][2] + board[1][1] + board[2][0];
if (diagonalSum1 === 3 || diagonalSum2 === 3) {
endGame(1);
return -10;
} else if (diagonalSum1 === -3 || diagonalSum2 === -3) {
endGame(-1);
return +10;
}
// check for tie game
if (board[0].indexOf(0) === -1 && board[1].indexOf(0) === -1 && board[2].indexOf(0) === -1) {
endGame(0);
return 0;
}
}
const endGame = function(winner) {
gameOver = true;
announceWinner(winner);
}
const announceWinner = function(player) {
const announcementBox = document.querySelector('[data-game-announcement]');
const player1 = document.querySelector('[data-player-x]').value;
const player2 = document.querySelector('[data-player-o]').value;
if (player === 1) {
announcementBox.innerText = `${player1} won!`;
} else if (player === -1) {
announcementBox.innerText = `${player2} won!`;
} else if (player === 0) {
announcementBox.innerText = 'It\'s a tie';
}
}
const announceTurn = function(player) {
const announcementBox = document.querySelector('[data-game-announcement]');
const player1 = document.querySelector('[data-player-x]');
const player2 = document.querySelector('[data-player-o]');
if (player === 1) {
player = player1.value;
} else if (player === -1) {
player = player2.value;
}
announcementBox.innerText = `It's ${player}'s turn`;
}
const initialPlayerAnnouncement = function() {
const announcementBox = document.querySelector('[data-game-announcement]');
const player1 = document.querySelector('[data-player-x]').value;
announcementBox.innerText = `It's ${player1}'s turn`;
}
const clickReplay = function() {
const board = boardArray;
const cells = document.querySelectorAll('.board-cell');
const announcementBox = document.querySelector('[data-game-announcement]');
const player1 = document.querySelector('[data-player-x]').value;
let gameboardCells = document.querySelectorAll('.board-cell');
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
board[i][j] = 0;
}
}
cells.forEach(cell => {
cell.classList.remove('x', 'circle');
});
gameOver = false;
currentPlayer = 1;
announcementBox.innerText = `It's ${player1}'s turn`;
}
const clickReset = function() {
const board = boardArray;
const cells = document.querySelectorAll('.board-cell');
const announcementBox = document.querySelector('[data-game-announcement]');
let gameboardCells = document.querySelectorAll('.board-cell');
const form = document.querySelector('[data-add-names-form]');
const boardContainer = document.querySelector('[data-board-container]');
const player0 = document.querySelector('[data-player-o]');
const dialogElement = document.querySelector('[data-modal]');
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
board[i][j] = 0;
}
}
cells.forEach(cell => {
cell.classList.remove('x', 'circle');
});
gameOver = false;
gameContainer.classList.add('hidden');
form.reset();
announcementBox.innerText = '';
boardContainer.innerHTML = '';
player0.disabled = false;
dialogElement.showModal();
}
const openModal = function() {
dialogElement.showModal()
}
return {
board: Gameboard,
gameController: gameController,
initialPlayerAnnouncement: initialPlayerAnnouncement,
clickReplay: clickReplay,
clickReset: clickReset,
openModal: openModal
}
})();
main.openModal();
/**
* displays the board on form submit
* adds CSS classes matching 2d array elements
*/
let renderUI = (function() {
// displays the gameboard on form submit
const displayGameboard = function() {
const board = main.board();
const boardContainer = document.querySelector('[data-board-container]');
// create and append board cells
board.forEach((row, rowIndex) => {
row.forEach((cell, columnIndex) => {
// create a 'div' for each array element, add a CSS class, and a data-index value
const boardCell = document.createElement('div');
boardCell.classList.add('board-cell');
const index = rowIndex * 3 + columnIndex; // *3 comes from the number of columns
boardCell.dataset.index = index;
boardContainer.appendChild(boardCell);
})
})
}
// adds CSS classes matching array element
function addMarker(array) {
const board = array;
const cells = document.querySelectorAll('.board-cell');
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
if (board[row][col] === 1) {
cells[row * 3 + col].classList.add('x');
} else if (board[row][col] === -1) {
cells[row * 3 + col].classList.add('circle');
}
}
}
}
return {
displayGameboard: displayGameboard,
addMarker: addMarker
}
})();
/**
* Players factory function
*/
const Players = (name, marker) => {
return {
name,
marker
}
}
(function clickSubmit() {
const form = document.querySelector('[data-add-names-form]');
form.addEventListener('submit', returnFormInput);
})();
function returnFormInput(event) {
event.preventDefault();
const formData = new FormData(this);
const data = Object.fromEntries(formData);
const dialogElement = document.querySelector('[data-modal]');
const gameContainer = document.querySelector('[data-game-container]');
dialogElement.close();
gameContainer.classList.remove('hidden');
// displayGameboard hass to be before gameController
// because gameController needs to select already rendered cells
renderUI.displayGameboard();
main.initialPlayerAnnouncement();
main.gameController(data);
}
(function replayGame() {
// reset: board, CSS classes, text field, currentPlayer, gameOver
const replayButton = document.querySelector('[data-replay-game]');
replayButton.addEventListener('click', main.clickReplay);
})();
(function resetGame() {
const resetButton = document.querySelector('[data-reset-game]')
resetButton.addEventListener('click', main.clickReset);
})();
(function clickTwoPlayerGame() {
const radioButton = document.getElementById('pvp');
const xInput = document.querySelector('[data-player-x]');
const oInput = document.querySelector('[data-player-o]');
radioButton.addEventListener('click', () => {
xInput.value = '';
oInput.value = '';
oInput.disabled = false;
});
})();
(function clickPlayerEasyAI() {
const radioButton = document.getElementById('easyai');
const xInput = document.querySelector('[data-player-x]');
const oInput = document.querySelector('[data-player-o]');
radioButton.addEventListener('click', () => {
xInput.value = '';
oInput.value = 'EasyAI';
oInput.disabled = true;
});
})();
(function clickPlayerToughAI() {
const radioButton = document.getElementById('unbeatableai');
const xInput = document.querySelector('[data-player-x]');
const oInput = document.querySelector('[data-player-o]');
radioButton.addEventListener('click', () => {
xInput.value = '';
oInput.value = 'ToughAI';
oInput.disabled = true;
});
})();
:root {
--cell-size: 100px;
--mark-size: calc(var(--cell-size)* 0.9);
--pantone-honeysuckle: rgb(203, 101, 134);
--pantone-classic-blue: rgb(16, 76, 129);
--pantone-rose-quartz: #f7cac9;
--pantone-serenity: #92a8d1;
}
html {
font-size: calc(16px + (26 - 16) * ((100vw - 300px) / (2800 - 300)));
font-family: Roboto, Arial, sans-serif;
}
body {
display: flex;
align-items: center;
justify-content: center;
background-color: var(--pantone-rose-quartz);
padding-top: 25vh;
}
/* modal */
.modal {
border: none;
box-shadow: 0 0 #0000, 0 0 #0000, 0 25px 50px -12px rgba(0, 0, 0, 0.25);
background-color: var(--pantone-serenity);
}
input[type="radio"],
input[type="radio"]:checked {
accent-color: var(--pantone-rose-quartz);
}
.submit-form-button {
background-color: var(--pantone-rose-quartz);
padding: 10px;
}
/* game container */
.game-container {
display: flex;
flex-direction: column;
gap: 20px;
}
/* announcement area */
.game-announcement {
font-size: 2rem;
}
/* board container */
.board-container {
display: grid;
gap: 10px;
grid-template-columns: repeat(3, 1fr);
}
.board-cell {
background-color: var(--pantone-serenity);
height: var(--cell-size);
width: var(--cell-size);
display: flex;
justify-content: center;
align-items: center;
position: relative;
}
/* creating the X element */
.board-cell.x::before,
.board-cell.x::after {
content: '';
width: calc(var(--mark-size) * 0.15);
height: var(--mark-size);
background-color: black;
position: absolute;
}
.board-cell.x::before {
transform: rotate(45deg);
}
.board-cell.x::after {
transform: rotate(-45deg);
}
/* creating the 0 element */
.board-cell.circle::before,
.board-cell.circle::after {
content: '';
background-color: black;
position: absolute;
border-radius: 50%;
}
.board-cell.circle::before {
width: var(--mark-size);
height: var(--mark-size);
background-color: black;
}
.board-cell.circle::after {
width: calc(var(--mark-size) * 0.7);
height: calc(var(--mark-size) * 0.7);
background-color: var(--pantone-serenity);
}
/* game buttons */
.replay-game,
.reset-game {
font-size: 1.5rem;
padding: 10px;
display: inline-block;
}
.hidden {
display: none;
}
<dialog data-modal class="modal" autofocus data-keyboard="false">
<div class="modal-header">
<h2 data-enter-names-header class="players-names">Play Tic Tac Toe!</h2>
</div>
<form action="" method="get" data-add-names-form>
<div class="player-vs-player">
<label><input type="radio" id="pvp" name="choice" value="0" checked> Player 1 Vs. Player 2</label>
</div>
<div class="player-vs-easyai">
<label><input type="radio" id="easyai" name="choice" value="1"> Player 1 Vs. Easy AI</label>
</div>
<div class="player-vs-unbeatableai">
<label><input type="radio" id="unbeatableai" name="choice" value="2" > Player 1 Vs. Tough AI</label>
</div>
<p class="add-player-x">
<label>X <input type="text" name="playerX" data-player-x placeholder='Name of player X' required /></label>
</p>
<p class="add-player-o">
<label>O <input type="text" name="playerO" data-player-o placeholder='Name of player 0' required /></label>
</p>
<button class="submit-form-button" type="submit" data-submit-form-button>Let's Go!</button>
</form>
</dialog>
<div class='game-container hidden' data-game-container>
<div class='game-announcement' data-game-announcement></div>
<div class="board-container" data-board-container></div>
<div class='game-buttons'>
<button class="replay-game" data-replay-game>Replay!</button>
<button class="reset-game" data-reset-game>Reset Game</button>
</div>
</div>
I created a codepen https://codepen.io/aadriaan/pen/ExrvjxM and the relevant code for the Human Player vs Minimax starts at line 103. These are the functions where I think the problem is:
playUnbeatableAI
minimax
getBestMove
evaluate
To reproduce the issue, run the snippet, select "Player 1 Vs. Tough AI", type a name, and click "Let's go". Then play moves in the right column:
The AI answers in the first column, and doesn't prevent the win in the right column.
Where is the mistake in my minimax implementation?
There are the following problems in your getBestMove
, minimax
and evaluate
functions -- which are the contributing functions to your AI player:
As getBestMove
is maximizing the score (cf score > bestScore
), the call to minimax
should get false
for isMaximizing
-- but you have true, which means the minimax
call will take the maximum score after the opponent's move. That's wrong.
In minimax
the comments correctly say that AI is the maximizing player, but in the if (isMaximizing)
block, you have the HUMAN
player playing and maximize their scores. This is wrong. In this block, it should be the AI_PLAYER
that plays the moves, and in the else
block it should be the HUMAN
player playing.
In minimax
the base case is reached when result !== 0
, but when the game ends in a draw, result
is 0, so also then the base case should kick in. As this doesn't happen in your code, you get a bestScore
that is (-)Infinity, which is a wrong evaluation of a draw. To fix this, I would suggest adding logic to evaluate
, so that it only returns 0 when a draw is detected, but in all other non-winning cases, it should return something else, like null
.
Here are the corrected versions of the three involved functions. Comments indicate where changes were made:
function minimax(board, depth, isMaximizing) {
const result = evaluate(board);
const HUMAN_PLAYER = 1;
const AI_PLAYER = -1;
if (result !== null) { // *** Use distinct value for a non-determined value
return result;
}
if (isMaximizing) {
let bestScore = -Infinity;
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
if (board[row][col] === 0) {
board[row][col] = AI_PLAYER; // *** changed player. This is the maximizing player
const score = minimax(board, depth + 1, false);
board[row][col] = 0;
bestScore = Math.max(score, bestScore);
}
}
}
return bestScore;
} else {
let bestScore = Infinity;
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
if (board[row][col] === 0) {
board[row][col] = HUMAN_PLAYER; // *** changed player. This is the minimizing player
const score = minimax(board, depth + 1, true);
board[row][col] = 0;
bestScore = Math.min(score, bestScore);
}
}
}
return bestScore;
}
}
function getBestMove(board) {
let bestMove = {
row: -1,
col: -1
};
let bestScore = -Infinity;
const HUMAN_PLAYER = 1;
const AI_PLAYER = -1;
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
if (board[row][col] === 0 && gameOver === false) {
board[row][col] = AI_PLAYER;
const score = minimax(board, 0, false); // *** Must provide false as argument
board[row][col] = 0;
if (score > bestScore) {
bestScore = score;
bestMove = {
row,
col
};
}
}
}
}
return bestMove;
}
function evaluate(board) {
for (let row = 0; row < 3; row++) {
if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
if (board[row][0] === 1)
return -10;
else if (board[row][0] === -1)
return +10;
}
}
for (let col = 0; col < 3; col++) {
if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
if (board[0][col] === 1)
return -10;
else if (board[0][col] === -1)
return +10;
}
}
if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
if (board[0][0] === 1)
return -10;
else if (board[0][0] === -1)
return +10;
}
if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
if (board[0][2] === 1)
return -10;
else if (board[0][2] === -1)
return +10;
}
// *** Return null when the game is not over:
if (board[0].includes(0) || board[1].includes(0) || board[2].includes(0)) {
return null;
}
return 0; // *** Draw (game over)
}
Note that these types of problems can be found easily through debugging. This should better be done before spending time on the UI.