javascriptarraysrecursiontic-tac-toeminimax
Tic-Tac-Toe with minimax can be beaten in middle row or middle column. How to fix it so it becomes unbeatable?
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?
Solution
There are the following problems in your getBestMove, minimax and evaluate functions -- which are the contributing functions to your AI player:
As
getBestMoveis maximizing the score (cfscore > bestScore), the call tominimaxshould getfalseforisMaximizing-- but you have true, which means theminimaxcall will take the maximum score after the opponent's move. That's wrong.In
minimaxthe comments correctly say that AI is the maximizing player, but in theif (isMaximizing)block, you have theHUMANplayer playing and maximize their scores. This is wrong. In this block, it should be theAI_PLAYERthat plays the moves, and in theelseblock it should be theHUMANplayer playing.In
minimaxthe base case is reached whenresult !== 0, but when the game ends in a draw,resultis 0, so also then the base case should kick in. As this doesn't happen in your code, you get abestScorethat is (-)Infinity, which is a wrong evaluation of a draw. To fix this, I would suggest adding logic toevaluate, so that it only returns 0 when a draw is detected, but in all other non-winning cases, it should return something else, likenull.
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.
- How do I display epub format book in pure HTML5/CSS/Jquery
- Can you render a html file into a container?
- Web Assembly (WASM) errors in a Vite + Vue app using Realm Web SDK
- JavaScript mapping touch events to mouse events
- How can I make a yup number accept nullable values?
- Why is requestAnimationFrame better than setInterval or setTimeout
- Remove last item from array
- How to search for and highlight matching text/phrases within the entire document-body's text-content?
- React markdown - how to get nth-element and append another element using react-markdown or dangerouslySetInnerHTML?
- Get the size of the screen, current web page and browser window
- Refresh / Reload page on pause youtube iframe api
- Aligning vertical scroll positions of related parts between main block and gutter
- How to make react-hook-form work with multiple forms in one page?
- How can I set Date object to null in Javascript?
- Detect multiple keypresses and trigger an action once in p5.js
- Refresh Page for interval using js
- Javascript callback for two functions
- Disable table pagination in Material-UI
- how to make password textbox value visible when hover an icon
- Tomtom API search by street
- window.postMessage to script.google.com as popup
- MQTT describe function outside the handler
- How to distinguish between left and right mouse click with jQuery
- Stop on a network request in browser dev tools
- Skip arguments in JS
- Autocomplete filter in react ant-design
- Javascript Like "Promise.all" on Java 8 (maybe with lambdas)
- How to change main content when sidebar item is clicked
- 'File name differs from already included file name only in casing' on relative path with same casing
- How to solve error "Unexpected template string expression: no-template-curly-in-string"