Here is a simple implementation of a minimax algorithm for Tic Tac Toe in JavaScript. The search tree deepens until a game-over state is detected. If a win is detected, then the current player cannot play, and so the static value is negative (-10). If a draw is detected the returned value is 0.
In all other cases the search deepens. This implementation uses a minimax algorithm where the value is maximised for both players. Therefore the sign of the value coming back from a deeper evaluation is always flipped (“what is good for my opponent is bad for me, and vice versa”).
If a board is found to have a winning position then the moves that lead to the shortest path to a win are prioritised. This is achieved by lowering the absolute value by 1 point every time we backtrack.
If there are several moves with an equal value, then a random one will be picked from those.
Here is the implementation, with some basic HTML:
class TicTacToe {
constructor() {
this.board = Array(9).fill(0); // 0 means "empty"
this.moves = [];
this.isWin = this.isDraw = false;
}
get turn() { // returns 1 or 2
return 1 + this.moves.length % 2;
}
get validMoves() {
return [...this.board.keys()].filter(i => !this.board[i])
}
play(move) { // move is an index in this.board
if (this.board[move] !== 0 || this.isWin) return false; // invalid move
this.board[move] = this.turn; // 1 or 2
this.moves.push(move);
// Use regular expression to detect any 3-in-a-row
this.isWin = /^(?:...)*([12])\1\1|^.?.?([12])..\2..\2|^([12])...\3...\3|^..([12]).\4.\4/.test(this.board.join(""));
this.isDraw = !this.isWin && this.moves.length === this.board.length;
return true;
}
takeBack() {
if (this.moves.length === 0) return false; // cannot undo
this.board[this.moves.pop()] = 0;
this.isWin = this.isDraw = false;
return true;
}
minimax() {
if (this.isWin) return { value: -10 };
if (this.isDraw) return { value: 0 };
let best = { value: -Infinity };
for (let move of this.validMoves) {
this.play(move);
let {value} = this.minimax();
this.takeBack();
// Reduce magnitude of value (so shorter paths to wins are prioritised) and negate it
value = value ? (Math.abs(value) - 1) * Math.sign(-value) : 0;
if (value >= best.value) {
if (value > best.value) best = { value, moves: [] };
best.moves.push(move); // keep track of equally valued moves
}
}
return best;
}
goodMove() {
let {moves} = this.minimax();
// Pick a random move when there are choices:
return moves[Math.floor(Math.random() * moves.length)];
}
}
(function main() {
const table = document.querySelector("#game");
const btnNewGame = document.querySelector("#newgame");
const btnCpuMove = document.querySelector("#cpumove");
const messageArea = document.querySelector("#message");
let game, human;
function display() {
game.board.forEach((cell, i) => table.rows[Math.floor(i / 3)].cells[i % 3].className = " XO"[cell]);
messageArea.textContent = game.isWin ? (game.turn == human ? "CPU won" : "You won")
: game.isDraw ? "It's a draw"
: game.turn == human ? "Your turn"
: "CPU is preparing move...";
table.className = game.isWin || game.isDraw || game.turn !== human ? "inactive" : "";
}
function computerMove() {
if (game.isWin || game.isDraw) return;
human = 3 - game.turn;
display();
setTimeout(() => {
game.play(game.goodMove());
display();
}, 500); // Artificial delay before computer move is calculated and played
}
function humanMove(i) {
if (game.turn !== human || !game.play(i)) return; // ignore click when not human turn, or when invalid move
display();
computerMove();
}
function newGame() {
game = new TicTacToe();
human = 1;
display();
}
table.addEventListener("click", e => humanMove(e.target.cellIndex + 3 * e.target.parentNode.rowIndex));
btnNewGame.addEventListener("click", newGame);
btnCpuMove.addEventListener("click", computerMove);
newGame();
})();#game { border-collapse: collapse }
#game td { border: 1px solid black; width: 30px; height: 30px; text-align: center; cursor: pointer }
#game td.X, #game td.O { cursor: default }
#game td.X { color: green }
#game td.O { color: red }
#game td.X:after { content: "X" }
#game td.O:after { content: "O" }
#game.inactive { background: silver }<table id="game">
<tr><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td></tr>
</table>
<h4 id="message"></h4>
<button id="newgame">New Game</button>
<button id="cpumove">Let CPU play a move</button>