CODEWITHSUNDEEP
javascriptalgorithmminimax
aclspy
aclspy

Reputation: 61

Why is my Minimax algorithm not producing correct moves?

The algorithm is running fine without any errors but the AI is not smart at all and seems to be making random moves. I've been working on this for two days and can't figure out where I went wrong. Can someone please help to find the bug thats causing it to not make the right move?

When starting the game, the AI should always make the move at index 4 (middle square) unless I take that spot, but it doesn't do that and also it doesn't try to win at all.

$(document).ready(function() {

let X = {
    isComputer: false,
    symbol: "x",
    marker: "<img src='img/x.png'>",
    winMarker: "<img src='img/xWin.png'>"
}
let O = {
    isComputer: false,
    symbol: "o",
    marker: "<img src='img/o.png'>",
    winMarker: "<img src='img/oWin.png'>"
}
let game = {
    board: [0,1,2,3,4,5,6,7,8],
    firstTurn: X,
    xScore: 0,
    oScore: 0,
    turnNumber: 0,
    started: false
}
let winningCombos = [
    [0,1,2], [3,4,5], [6,7,8],
    [0,3,6], [1,4,7], [2,5,8],
    [0,4,8], [2,4,6]
];
let theWinningCombo;
let player = X;
let clearBoardTimeoutID;
let ai1;
let ai2;

function clearBoardForNextGame() {

    clearBoardTimeoutID = 
    setTimeout(function() {
        $('.square').empty();
        game.firstTurn = game.firstTurn == X ? O : X;
        game.turnNumber = 0;
        game.board = [0,1,2,3,4,5,6,7,8];
        game.started = true;
    }, 1500);
}

function thisPlayerWon(board, symbol) {
    for (let i = 0; i < winningCombos.length; i++) {
        let counter = 0;
        for (let j = 0; j < winningCombos[i].length; j++) {
            if (board[winningCombos[i][j]] == symbol) {
                counter++;
            }
            if (counter == 3) {
                theWinningCombo = winningCombos[i];
                return true;
            }
        }
    }
    return false;
}

function showWinnerAndUpdateScore(combo, player) {
    game.started = false;
    combo.forEach(index => $('#' + index).html(player.winMarker));
    player == X ? (game.xScore++, $('#score1').text(game.xScore)) : (game.oScore++, $('#score2').text(game.oScore))
}

function AImove(AIplayer, board) {
    AIplayer = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);
    let opponent = AIplayer == X ? O : X;

    let bestMove = minimax(AIplayer, board, 0);

    board[bestMove] = AIplayer.symbol;
    $('#' + bestMove).html(AIplayer.marker);
    game.turnNumber++;

    function minimax(player, board, depth) {

        let spotsNotMarked = emptyBoardSpots(board);

        if (thisPlayerWon(board, AIplayer.symbol)) {
            return 10-depth;
        }
        else if (thisPlayerWon(board, opponent.symbol)) {
            return depth-10;
        }
        else if (spotsNotMarked.length == 0) {
            return 0;
        }

        let moves = [];
        let scores = [];

        for (let i = 0; i < spotsNotMarked.length; i++) {

            let index = spotsNotMarked[i];

            let score;

            board[index] = player.symbol;

            if (player == X) {
                score = minimax(O, board, depth+1);
            }
            else {
                score = minimax(X, board, depth+1);
            }

            scores.push(score);

            board[index] = index;

            moves.push(index);
        }

        if (player == AIplayer) {
            return moves[scores.indexOf(Math.max(...scores))];
        }
        else {
            return moves[scores.indexOf(Math.min(...scores))];
        }
    }
}

function emptyBoardSpots(board) {
    return board.filter(square => !isNaN(square));
}

$('.AI-Switch').on('change', function() {
    if (!game.started) {
        this.id == "one" ? (X.isComputer = !(X.isComputer), ai1 = X) : (O.isComputer = !(O.isComputer), ai2 = O);
    }
});

$('#resetButton').on('click', function() {
    clearTimeout(clearBoardTimeoutID);
    $('.square').empty();
    $('.scores').text("0");
    game.board = [0,1,2,3,4,5,6,7,8];
    game.firstTurn = X;
    game.xScore = 0;
    game.oScore = 0;
    game.turnNumber = 0;
    game.started = false;
});

$('#startButton').on('click', function() {
    game.started = true;
});

$('.square').on('click', function() {
    if (game.started && !isNaN(game.board[this.id])) {

        player = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);

        this.innerHTML = player.marker;
        game.board[this.id] = player.symbol;

        game.turnNumber++;

        if (game.turnNumber > 3 && thisPlayerWon(game.board, player.symbol)) {

            showWinnerAndUpdateScore(theWinningCombo, player);

            clearBoardForNextGame();
        }
        else if (game.turnNumber == 9) {
            clearBoardForNextGame();
        }

        if (O.isComputer && player == X) {
            AImove(player, game.board);
        }
        else if (X.isComputer && player == O) {
            AImove(player, game.board);
        }
    }
});
});

Upvotes: 0

Views: 291

Answers (1)

trincot
trincot

Reputation: 350137

The issue is the return value of minimax: is it a score or is it a move?

The problem

You reason that the recursive call should return a score, except for the first call when it should return a move. This would indeed be handy, but it is not what is happening:

  • Only when a win or draw is detected will the function return a score
  • In all (!) other cases a move is returned

This means that half way down the recursion tree (not yet at a leaf), you are also getting moves back, ... but you treat them as scores one level up inside the recursion tree. Obviously that makes any result meaningless.

The solution

Let your minimax function return a score, but also a move (when relevant) at the same time. This you can do by returning an object with the two pieces of information.

Here is your AImove function with just a few modifications to implement that idea. The modified lines are marked with ***:

function AImove(AIplayer, board) {
    AIplayer = !(game.turnNumber % 2) ? game.firstTurn : (game.firstTurn == X ? O : X);
    let opponent = AIplayer == X ? O : X;
    let bestMove = minimax(AIplayer, board, 0).move; // *** Get move part of return value
    board[bestMove] = AIplayer.symbol;
    $('#' + bestMove).html(AIplayer.marker);
    game.turnNumber++;

    function minimax(player, board, depth) {
        if (depth===2) console.log('step');
        let spotsNotMarked = emptyBoardSpots(board);
        if (thisPlayerWon(board, AIplayer.symbol)) {
            return { score: 10-depth }; // *** Object with score (there's no move)
        }
        else if (thisPlayerWon(board, opponent.symbol)) {
            return { score: depth-10 }; // *** idem
        }
        else if (spotsNotMarked.length == 0) {
            return { score: 0 }; // *** idem
        }
        let moves = [];
        let scores = [];
        for (let i = 0; i < spotsNotMarked.length; i++) {
            let index = spotsNotMarked[i];
            let score;
            board[index] = player.symbol;
            if (player == X) {
                score = minimax(O, board, depth+1).score; // *** Get score part
            }
            else {
                score = minimax(X, board, depth+1).score; // *** idem
            }
            scores.push(score);
            board[index] = index;
            moves.push(index);
        }

        let score = (player == AIplayer ? Math.max : Math.min)(...scores); // *** Get score
        return { score, move: moves[scores.indexOf(score)] }; // *** Return both move & score
    }
}

Upvotes: 2

Related Questions