xxxxxxxxxx
// Tic Tac Toe AI with Minimax Algorithm
// The Coding Train / Daniel Shiffman
// https://thecodingtrain.com/CodingChallenges/154-tic-tac-toe-minimax.html
// https://youtu.be/I64-UTORVfU
// https://editor.p5js.org/codingtrain/sketches/0zyUhZdJD
function bestMove() {
// AI to make its turn
let bestScore = -Infinity;
let minDepth = Infinity;
let move = {i: 0, j:0};
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// Is the spot available?
if (board[i][j] == '') {
board[i][j] = ai;
let r = minimax(board, 0, false)
let score = r.s;
let depth = r.d;
board[i][j] = '';
if (score > bestScore) {
bestScore = score;
minDepth = depth;
move = { i, j };
} else if (score == bestScore && depth < minDepth) {
minDepth = depth;
move = { i, j };
}
}
}
}
board[move.i][move.j] = ai;
currentPlayer = human;
}
let scores = {
X: 10,
O: -10,
tie: 0
};
function minimax(board, depth, isMaximizing) {
let result = checkWinner();
if (result !== null) {
return {s: scores[result], d: depth};
}
if (isMaximizing) {
let bestScore = -Infinity;
let bestDepth = Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// Is the spot available?
if (board[i][j] == '') {
board[i][j] = ai;
let r = minimax(board, depth + 1, false);
let score = r.s;
let d = r.d;
board[i][j] = '';
if(score > bestScore) {
bestScore = score;
bestDepth = d;
} else if (score == bestScore && d < bestDepth) {
bestDepth = d;
}
}
}
}
return {s: bestScore, d: bestDepth};
} else {
let bestScore = Infinity;
let bestDepth = Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// Is the spot available?
if (board[i][j] == '') {
board[i][j] = human;
let r = minimax(board, depth + 1, true);
let score = r.s;
let d = r.d;
board[i][j] = '';
if(score < bestScore) {
bestScore = score;
bestDepth = d;
} else if (score == bestScore && d < bestDepth) {
bestDepth = d;
}
}
}
}
return {s: bestScore, d: bestDepth};
}
}