After hours trying to implement minimax as an AI for tic tac toe, I jus't don't know what to do anymore. The AI won't make smart choices, it seems like it just chooses the first move that it can. This is my first time trying to implement something like that. I've used geeks for geeks articles on minimax algorithm, and some youtube videos as base for this.
'O' is the max or AI, while 'X' is the min or player. findBestMove takes the board array, and returns the best move as the index values to be used in the array and to be inserted in the visual board created on the web.
const check = (n1, n2, n3) => {
if (n1 === '') return;
if (n1 === n2 && n2 === n3) {
value = n1;
}
}
const checkResult = () => {
// Check all possible win scenarios
check(board[0][0], board[0][1], board[0][2]);
check(board[1][0], board[1][1], board[1][2]);
check(board[2][0], board[2][1], board[2][2]);
check(board[0][0], board[1][0], board[2][0]);
check(board[0][1], board[1][1], board[2][1]);
check(board[0][2], board[1][2], board[2][2]);
check(board[0][0], board[1][1], board[2][2]);
check(board[0][2], board[1][1], board[2][0]);
if (value === 'X') {
return -10;
} else if (value === 'O') {
return 10;
}
}
function findBestMove(board) {
let bestMove = {};
let bestVal = -Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
board[i][j] = 'O';
let moveVal = minimax(board, 0, false);
board[i][j] = '';
if (moveVal > bestVal) {
bestVal = moveVal;
bestMove = { i, j };
}
}
}
}
return bestMove;
}
function minimax(board, depth, maxPlayer) {
let score = GameBoard.checkResult();
if (!!score) {
if (score < 0) {
return score + depth;
} else {
return score - depth;
}
}
if (!isMovesLeft(board)) {
return 0;
}
if (maxPlayer) {
let maxEval = -Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
board[i][j] = 'O';
let eval = minimax(board, depth + 1, false);
board[i][j] = '';
maxEval = Math.max(maxEval, eval);
console.log(maxEval + ' ' + eval);
}
}
}
return maxEval;
} else {
let minEval = Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
board[i][j] = 'X';
let eval = minimax(board, depth + 1, true);
board[i][j] = '';
minEval = Math.min(minEval, eval);
}
}
}
return minEval;
}
}
function isMovesLeft(board) {
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
return true;
}
}
}
return false;
}
You need to reset value in checkResult:
let board = Array(3).fill().map(() => Array(3).fill(''));
let value;
const check = (n1, n2, n3) => {
if (n1 === '') return;
if (n1 === n2 && n2 === n3) {
value = n1;
}
}
const checkResult = () => {
value = '';
// Check all possible win scenarios
check(board[0][0], board[0][1], board[0][2]);
check(board[1][0], board[1][1], board[1][2]);
check(board[2][0], board[2][1], board[2][2]);
check(board[0][0], board[1][0], board[2][0]);
check(board[0][1], board[1][1], board[2][1]);
check(board[0][2], board[1][2], board[2][2]);
check(board[0][0], board[1][1], board[2][2]);
check(board[0][2], board[1][1], board[2][0]);
if (value === 'X') {
return -10;
} else if (value === 'O') {
return 10;
}
}
let GameBoard = {
checkResult,
};
function findBestMove(board) {
let bestMove = {};
let bestVal = -Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
board[i][j] = 'O';
let moveVal = minimax(board, 0, false);
board[i][j] = '';
if (moveVal > bestVal) {
bestVal = moveVal;
bestMove = { i, j };
}
}
}
}
return bestMove;
}
function minimax(board, depth, maxPlayer) {
let score = GameBoard.checkResult();
if (!!score) {
return score - depth * Math.sign(score);
}
if (!isMovesLeft(board)) {
return 0;
}
if (maxPlayer) {
let maxEval = -Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
board[i][j] = 'O';
let eval = minimax(board, depth + 1, false);
board[i][j] = '';
maxEval = Math.max(maxEval, eval);
}
}
}
return maxEval;
} else {
let minEval = Infinity;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
board[i][j] = 'X';
let eval = minimax(board, depth + 1, true);
board[i][j] = '';
minEval = Math.min(minEval, eval);
}
}
}
return minEval;
}
}
function isMovesLeft(board) {
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === '') {
return true;
}
}
}
return false;
}
let boardDisplay = document.getElementById('board-display');
for (let row = 0; row < 3; row++) {
let rowDisplay = boardDisplay.tBodies[0].appendChild(document.createElement('tr'));
for (let col = 0; col < 3; col++) {
let cellDisplay = rowDisplay.appendChild(document.createElement('td'));
let cellButton = cellDisplay.appendChild(document.createElement('button'));
cellButton.type = 'button';
cellButton.addEventListener('click', () => {
cellButton.remove();
board[row][col] = 'X';
cellDisplay.textContent = 'X';
if (!isMovesLeft(board) || GameBoard.checkResult()) {
return;
}
let {i, j} = findBestMove(board);
board[i][j] = 'O';
boardDisplay.tBodies[0].rows[i].cells[j].textContent = 'O';
if (GameBoard.checkResult()) {
for (let button of boardDisplay.querySelectorAll('button')) {
button.disabled = true;
}
}
});
}
}#board-display {
font-family: sans-serif;
font-size: 24px;
}
#board-display td {
border: 1px solid #ccc;
text-align: center;
width: 64px;
height: 64px;
}
#board-display button {
display: block;
margin: 0;
width: 100%;
height: 100%;
}<table id="board-display">
<tbody></tbody>
</table>