CODEWITHSUNDEEP
javascripttic-tac-toeminmax
user9044844
user9044844

Reputation:

TicTacToe MinMax Algorithm Not Returning Optimal Move

When playing against the AI ("O"), there are many times where it is not making the optimal move.

I believe it has to do something with the evaluation between boards within the MinMax() function, but I don't see anything wrong, and was hoping another set of eyes can catch something I missed.

compare_winning(board, winningPlayer, depth, checkTie)
   {
       const winning_combos = [
       [0,1,2],
       [3,4,5],
       [6,7,8],
       [0,3,6],
       [1,4,7],
       [2,5,8],
       [0,4,8],
       [2,4,6]
       ];
       
       for (let i = 0; i < winning_combos.length; i++)
       {
           if (board[winning_combos[i][0]].color === "x" && board[winning_combos[i][1]].color === "x" && board[winning_combos[i][2]].color === "x")
           {
               winningPlayer.win = -100 + depth;
               return true;
           }
           if (board[winning_combos[i][0]].color === "ai" && board[winning_combos[i][1]].color === "ai" && board[winning_combos[i][2]].color === "ai")
           {
               winningPlayer.win = 100 - depth; // '- depth' to choose a move that will lead to a sooner win.
               return true;
           }
       }

       if(checkTie){
           for (let i = 0; i < board.length; i++)
               if (board[i].color === "w")
                   return false;
           winningPlayer.win = 0;
           return true;
       }
       return false;
   }

MinMax(board, depth, player, bestSuccessor)
   {
       // When reaches a leaf node.
       let winningPlayer = {};
       if (this.compare_winning(board, winningPlayer, depth, true)){
           return winningPlayer.win;
       }

       // Returns an array filled with different boards with every possible move 'player' can move.
       let successors = this.Successors(board, player);

       if (player === "ai"){
           let result_value = Number.NEGATIVE_INFINITY;
           
           for (let i = 0; i < successors.length; i++){
               let value = this.MinMax(successors[i], depth + 1, "x", bestSuccessor);
               
               if (value > result_value){
                   result_value = value;
                   bestSuccessor.move = successors[i];
               }

           }
           return result_value;
       }

       else{
           let result_value = Number.POSITIVE_INFINITY;

           for (let i = 0; i < successors.length; i++){
               let value = this.MinMax(successors[i], depth + 1, "ai", bestSuccessor);
               
               if (value < result_value){
                   result_value = value;
                   bestSuccessor.move = successors[i];
               }
               
           }
           return result_value;
       }
   }

I am calling MinMax() in my handleClick() function immediately after I set this.state.board with the Users move ("X").

...
    let bestMove = {};
    this.MinMax(this.state.board.flat(), 0, "ai", bestMove)
...

Upvotes: 0

Views: 95

Answers (1)

user9044844
user9044844

Reputation:

Instead of having an object bestMove = {} passed into the MinMax() Function, rather returning the board state along with the minmax value in the MinMax() Function together as an object/list seemed to return the appropriate board. (aka. one of the next successor boards)

Before, with passing an object bestMove = {} into the MinMax() Function, it returned the board state at the leaf node. Instead I wanted the board state with the next optimal move played.

MinMax(board, depth, player)
    {
        // When reaches a leaf node.
        let winningPlayer = {};
        if (this.compare_winning(board, winningPlayer, depth, true)){
            return [winningPlayer.win, board];
        }

        let successors = this.Successors(board, player);
        let bestBoard; 

        if (player === "ai"){
            let result_value = Number.NEGATIVE_INFINITY;
            for (let i = 0; i < successors.length; i++){
                let value = this.MinMax(successors[i], depth + 1, "x")[0];
                
                if (value > result_value){
                    result_value = value;
                    bestBoard = successors[i];
                }
            }
            return [result_value, bestBoard];
        }
        else{
            let result_value = Number.POSITIVE_INFINITY;
            for (let i = 0; i < successors.length; i++){
                let value = this.MinMax(successors[i], depth + 1, "ai")[0];
                
                if (value < result_value){
                    result_value = value;
                    bestBoard = successors[i];
                }
            }
            return [result_value, bestBoard];
        }
    }

//let bestMove = {};
let bestBoard = this.MinMax(newBoard.flat(), 0, "ai");

Upvotes: 0

Related Questions