Алгоритм TicTacToe MinMax не возвращает оптимальное движение - PullRequest
Новая
       44

Алгоритм TicTacToe MinMax не возвращает оптимальное движение

0 голосов
/ 21 июня 2020

Когда вы играете против AI («O»), во многих случаях он не делает оптимального хода.

Я считаю, что он должен что-то делать с оценкой между досками в MinMax () функция, но я не вижу ничего плохого и надеялся, что другая пара глаз сможет уловить то, что я пропустил. 

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;
       }
   }

Я вызываю MinMax () в своей функции handleClick () сразу после того, как установил это .state.board с перемещением пользователей ("X"). 

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

1 Ответ

0 голосов
/ 28 июня 2020

Вместо объекта bestMove = {}, переданного в функцию MinMax (), вместо возврата состояния платы вместе со значением minmax в функции MinMax () вместе, как объект / список, казалось, возвращалась соответствующая плата. (также известная как одна из следующих плат-преемников)

Раньше, передавая объект bestMove = {} в функцию MinMax (), он возвращал состояние платы на листовом узле. Вместо этого я хотел состояние доски при следующем оптимальном ходе. 

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");
...