Unbeatable Tic Tac Toe. Single-page HTML, CSS & JavaScript.
DEMO
Implementation of Minimax algorithm wrapped up in a neat chalkboard UI. The chalk effect is achieved using SVG turbulence filters.
Minimax algorithm:
|
function getComputerMoveData(tempPlaygroundState, depth) { |
|
const winCombinationIndex = getWinCombinationIndex(tempPlaygroundState); |
|
if (winCombinationIndex !== -1) { |
|
// we've got a winner in this hypothetical game! |
|
const wonMover = tempPlaygroundState[winCombinations[winCombinationIndex][0]]; |
|
return { |
|
index: -1, |
|
score: wonMover === 1 |
|
? -1 // user hypothetically won (bad) |
|
: 1 // computer hypothetically won (good) |
|
}; |
|
} else if (!tempPlaygroundState.some((mover) => mover === -1)) { |
|
// a tie |
|
return { index: -1, score: 0 }; |
|
} |
|
|
|
depth = (depth || 0) + 1; |
|
// 1 - user's hypothetical turn; 0 - computer's hypothetical turn. |
|
const mover = +!(depth % 2); |
|
|
|
const availableMoves = tempPlaygroundState |
|
.map((_, i) => i) |
|
.filter((boardIndex) => tempPlaygroundState[boardIndex] === -1); |
|
const scores = []; |
|
const moves = []; |
|
|
|
for (let i = 0; i < availableMoves.length; i++) { |
|
const move = availableMoves[i]; |
|
const iterationPlayground = [ ...tempPlaygroundState ]; |
|
iterationPlayground[move] = mover; |
|
const hypotheticalMoveData = getComputerMoveData(iterationPlayground, depth); |
|
scores.push(hypotheticalMoveData.score); |
|
moves.push(move); |
|
|
|
// rollback the hypothetical move |
|
tempPlaygroundState[move] = -1; |
|
} |
|
|
|
const func = mover === 1 |
|
? Math.min // we're looking for the min score if it's user's turn |
|
: Math.max; // and for the max score if it's computer's score |
|
const moveScore = func.apply(null, scores); |
|
const moveScoreIndex = scores.indexOf(moveScore); |
|
return { index: moves[moveScoreIndex], score: moveScore }; |
|
} |