This is a continuation from my previous question.
So, I think I've made a lot of progress. The AI now seems to generally make the best move, and go for wins, but one last problem I'm having is that it doesn't seem to care about losing. That is, if it has a fork, or 4 in a row, it will go for the win, but if the HUMAN player has 3 (or 4) in a row, it won't make a move that would stop them from winning.
Even weirder, sometimes if I set the depth to a lower value, it will prevent the loss, but not if I increase the depth. Here's my current code, with an example board where it fails to find the best move (to prevent the loss next turn):
const ROWS = 9;
const COLS = 9;
const LEN = 5;
const EMPTY = 0;
const HUMAN = 1;
const COMP = 2;
const WINNING_MOVE = 100000;
function checkDirection(grid, who, currChain, sRow, sCol, incRow, incCol) {
let newChain = 0;
while (currChain + newChain < LEN) {
const row = sRow + (incRow * (newChain + 1));
const col = sCol + (incCol * (newChain + 1));
if (grid[row * COLS + col] !== who) {
break;
}
newChain++;
}
return newChain;
}
function lineCheck(grid, who, sRow, sCol, mRow, mCol) {
let chain = 1;
chain += checkDirection(grid, who, 0, sRow, sCol, mRow, mCol);
chain += checkDirection(grid, who, chain, sRow, sCol, -mRow, -mCol);
return chain >= LEN;
}
function isWinningMove(grid, who, row, col) {
return lineCheck(grid, who, row, col, 1, 0) ||
lineCheck(grid, who, row, col, 0, 1) ||
lineCheck(grid, who, row, col, 1, 1) ||
lineCheck(grid, who, row, col, -1, 1);
}
function getTile(grid, row, col) {
if (row < 0 || col < 0 || row >= ROWS || col >= COLS) {
return -1;
}
return grid[row * COLS + col];
}
function hasNeighbor(board, row, col) {
if (getTile(board, row - 1, col - 1) > 0) { return true; }
if (getTile(board, row - 1, col + 1) > 0) { return true; }
if (getTile(board, row + 1, col - 1) > 0) { return true; }
if (getTile(board, row + 1, col + 1) > 0) { return true; }
if (getTile(board, row - 1, col) > 0) { return true; }
if (getTile(board, row + 1, col) > 0) { return true; }
if (getTile(board, row, col - 1) > 0) { return true; }
if (getTile(board, row, col + 1) > 0) { return true; }
return false;
}
function minimax(board, depth, alpha, beta, player, latestRow, latestCol) {
if (depth === 0) {
const val = evaluateBoard(board, latestRow, latestCol);
return [ val, latestRow * COLS + latestCol ]; // returns a pair (value, move)
}
const opponent = player === COMP ? HUMAN : COMP;
// player argument should be opponent, and return statement should be different per player
if (isWinningMove(board, opponent, latestRow, latestCol)) {
const multiplier = player === COMP ? 1 : -1;
return [ WINNING_MOVE * multiplier, latestRow * COLS + latestCol ];
}
let bestMove = -1;
if (player === COMP) {
let maxEval = Number.MIN_SAFE_INTEGER;
for (let row = 0; row < ROWS; row++) {
for (let col = 0; col < COLS; col++) {
const idx = row * COLS + col;
const tileValue = board[idx];
if (tileValue > 0 || !hasNeighbor(board, row, col)) { continue; }
board[idx] = player;
const evaluation = minimax(board, depth - 1, alpha, beta, HUMAN, row, col)[0];
board[idx] = tileValue;
if (evaluation > maxEval) {
maxEval = evaluation;
bestMove = idx;
}
alpha = Math.max(alpha, evaluation);
if (beta <= alpha) {
return [ maxEval, bestMove ];
}
}
}
return [ maxEval, bestMove ];
} else {
let minEval = Number.MAX_SAFE_INTEGER;
for (let row = 0; row < ROWS; row++) {
for (let col = 0; col < COLS; col++) {
const idx = row * COLS + col;
const tileValue = board[idx];
if (tileValue > 0 || !hasNeighbor(board, row, col)) { continue; }
board[idx] = player;
const evaluation = minimax(board, depth - 1, alpha, beta, COMP, row, col)[0];
board[idx] = tileValue;
if (evaluation < minEval) {
minEval = evaluation;
bestMove = idx; // Also track best move for HUMAN.
}
beta = Math.min(beta, evaluation);
if (beta <= alpha) {
return [ minEval, bestMove ];
}
}
}
return [ minEval, bestMove ];
}
}
function evaluatePlayerBoard(grid, who, latestRow, latestCol) {
let idx = 0;
let score = 0;
if (isWinningMove(grid, who, latestRow, latestCol)) {
return WINNING_MOVE;
}
for (let row = 0; row < ROWS; row++) {
for (let col = 0; col < COLS; col++) {
if (grid[idx] !== who) { idx++; continue; }
if (getTile(grid, row - 1, col - 1) === who) { score++; }
if (getTile(grid, row - 1, col + 1) === who) { score++; }
if (getTile(grid, row + 1, col - 1) === who) { score++; }
if (getTile(grid, row + 1, col + 1) === who) { score++; }
if (getTile(grid, row - 1, col) === who) { score++; }
if (getTile(grid, row + 1, col) === who) { score++; }
if (getTile(grid, row, col - 1) === who) { score++; }
if (getTile(grid, row, col + 1) === who) { score++; }
// if (getTile(grid, row, col) === who) { score++; }
idx++;
}
}
return score;
}
function evaluateBoard(grid, latestRow, latestCol) {
return evaluatePlayerBoard(grid, COMP, latestRow, latestCol) // COMP is maximizing
- evaluatePlayerBoard(grid, HUMAN, latestRow, latestCol); // HUMAN is minimizing
}
function getBestMove(board, maxDepth) {
for (let depth = 1; depth <= maxDepth; depth++) {
const [ evaluation, move ] = minimax(board, depth, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, COMP, -1, -1);
// if we found a winning move already, return early
// otherwise, keep iterating until we reach max depth
if (evaluation > 10000 || depth === maxDepth) {
return move;
}
}
return 0; // should never run
}
const exampleBoard = [
0, 0, 0, 0, 0, 0, 0, 0, 0, // 0-8
0, 0, 0, 0, 0, 0, 0, 0, 0, // 9-17
0, 0, 0, 0, 0, 0, 2, 0, 0, // 18-26
0, 0, 2, 2, 0, 1, 0, 0, 0, // 27-35
0, 0, 0, 2, 1, 0, 0, 0, 0, // 36-44
0, 0, 0, 1, 0, 0, 0, 0, 0, // 45-53
0, 0, 1, 0, 0, 0, 0, 0, 0, // 54-62
0, 0, 0, 0, 0, 0, 0, 0, 0, // 63-71
0, 0, 0, 0, 0, 0, 0, 0, 0, // 72-80
];
console.log(getBestMove(exampleBoard, 3));I believe it should be logging 64 (to prevent the loss next turn), but it is instead logging 20
You have a logical error in this part of the code:
// player argument should be opponent, and return statement should be different per player
if (isWinningMove(board, opponent, latestRow, latestCol)) {
const multiplier = player === COMP ? 1 : -1;
return [ WINNING_MOVE * multiplier, latestRow * COLS + latestCol ];
}
When this block is entered, we know that it was the opponent that won, not player, and so the multiplier should be based on opponent. If the opponent is the maximizing player, we should multiply with 1, otherwise with -1.
Not an issue, but it makes no sense to return latestRow * COLS + latestCol as the best move, because the current player has no best move (they lost the game), and latestRow * COLS + latestCol is certainly not their move, so it is irrelevant. (The same remark can be made for the depth == 0 block)
Fix:
// player argument should be opponent, and return statement should be different per player
if (isWinningMove(board, opponent, latestRow, latestCol)) {
const multiplier = opponent === COMP ? 1 : -1;
return [ WINNING_MOVE * multiplier, -1 ];
}