javascript minimax algorithm tic tac toe, not always giving the best move

Question

I have been trying to use minimax algorithm for my tic tac toe game to make my AI unbeatable. However it doesn't always return the optimal move.

AI = X; human = "O"

var board =  ["x", "x", "-",
               "-", "o", "o",
               "-", "-", "-"]

It gives the board above index[2] as the optimal move which is correct.

However, with the board below, the answer it gives is index[3], which will allow the human player to win on its turn.

var boardB = ["x","x","o",
             "-","o","-",
             "-","_","-"];

var player = 'x';
var opponent = 'o';

function isMovesLeft(board){
    for (var i = 0; i<board.length; i++){
        if (board[i] =='-'){
            return 'true';
        }
        else{
            return 'false';
        }
    }
}



function evaluate(){
    for (var i = 0; i < board.length; i += 3) {
        if (board[i] === board[i + 1] && board[i + 1] === board[i + 2]) {
            if (board[i] == player){
                return +10;  
            }
            else if(board[i]== opponent){
                return -10;
            } 
        }
    }
    for (var j = 0; j < board.length; j++) {
        if (board[j] === board[j + 3] && board[j + 3] === board[j + 6]) {
            if (board[j] == player){
                return +10;  
            }
            else if(board[j] == opponent){
                return -10;
            } 
        }
    }


  if ((board[4]==board[0] && board[4]==board[8]) || (board[4]==board[2] && board[4]==board[6])) {
    if (board[4]==player){
        return +10;
    }
    else if (board[4]==opponent){
        return -10;
    }
 }

return 0;
}



function minimax(board, depth, isMax){
    var score = evaluate(board);

    if (score == 10){
        return score;
    }

    if (score == -10){
        return score;
    }

    if (isMovesLeft(board) =="false"){
        return 0;
    }

    if (isMax == "true"){
        var best = -1000;

        for (var i = 0; i< board.length; i++){
            if (board[i]=='-'){
                board.splice(i, 1, player);
                var value = minimax(board, depth+1, "false");
                best = Math.max(best, value);

                board.splice(i, 1, "-");
            }
         }
         return best;  
     }

    else if (isMax == 'false'){
        var best = 1000;
        for (var i = 0; i<board.length; i++){
            if (board[i]=='-'){
             board.splice(i, 1, opponent);
             var value = minimax(board, depth+1, "true");
             best = Math.min(best, value);

             board.splice(i, 1, "-");
            }
         }
        return best;
      }
}

function findBestMove(board){
    var bestVal = -1000;
    var bestMove= -1;

    for (var i = 0; i<board.length; i++){
        if (board[i]=='-'){
            board.splice(i, 1, player);
            var moveVal = minimax(board, 0, "false");

            board.splice(i, 1, "-");

            if (moveVal > bestVal)
            {
                bestMove = i;
                bestVal = moveVal;
            }
        }
    }
    alert("bestVal is : " + bestVal + "<br> best Move is : " + bestMove;)
}

I wonder what is wrong with my code. Below are some websites that I used as references:

http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/

https://blog.vivekpanyam.com/how-to-build-an-ai-that-wins-the-basics-of-minimax-search/

But I still can't figure out the reason why it's not always returning the optimal move. I hope someone can lead me to the right direction. Thanks in advance!

Answer 1

If you see the moveVal for each i you'll see that it's zero.
That's because in the minimax function you call isMovesLeft which when false returns 0.
The problem with your program is that isMovesLeft always returns false.
You should change it to :

function isMovesLeft(board){
    for (var i = 0; i<board.length; i++){
        if (board[i] =='-'){
            return 'true';
        }
    }
return false;
}  

This change should have your program get 6 as the best move.

The parameter depth is never used anywhere.
You can use it while returning the score: return score/depth
This will ensure that the short term consequences of losing/winning have more effect than long term.