tictactoe minmax递归导致混淆

Question

我读了很多使用minmax算法的tic tac toe例子，但是还没有找到一个好的来解释到底是怎么回事。我已经写了一个可以工作的程序，但需要帮助理解递归过程的一小部分。

如果你加载下面的代码，输入你的名字，O(不是零)和0(零)，你会得到我正在看的结果。在计算机移动之后，停止程序并查看console.log。

如果查看控制台输出，就会看到在返回语句之前出现的best 0 7 [[0, 7]]行。来自0 simulateMove = 6 scoreMove[1] = 7 depth = 2的下一行是什么？

另一个问题是为什么在第423行我需要scoreMoveAvailable[i][1] = simulateMove;而不是scoreMoveAvailable[i][1] = scoreMove[1];

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Random;
import java.util.Arrays;

public class TicTacToeV2{      
    private static final int boardRowDim = 3;    
    private static final int boardColDim = 3; 
    private String[][] board;
    private String playerName;
    private String playerMark;
    private String computerMark;
    private boolean humanGoes;
    private boolean winner;
    private boolean draw
    private int gameTargetScore;
    private boolean output = true;
    private boolean toSeed = true;    
    private ArrayList<Integer> availableMoves;

    public TicTacToeV2(String name, boolean whoGoesFirst){

        availableMoves = new ArrayList<Integer>();    
        board = new String[boardRowDim][boardColDim];        


        for (int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){               
                board[i][j] = ((Integer)(double2single(i,j))).toString();                
                availableMoves.add(double2single(i,j));
            }
        }
        playerName = name;
        humanGoes = whoGoesFirst;
        playerMark = "X";
        computerMark = "O";
        gameTargetScore = 15;
        if(!humanGoes){
            playerMark = "O";
            computerMark = "X";
            gameTargetScore = - 15;
        }
        winner = false;
        draw = false;        
    }

    public static void main(String[] args)throws Exception{
       System.out.println("\u000C");         
        Scanner kboard = new Scanner(System.in);
        printHeader();                   

        System.out.print("          Please enter your name ; ");
        String name = kboard.next();
        name = capitalize(name);

        System.out.print("\n\n          X's go first. " + name + ", please enter your mark ('X' or 'O')");
        String mark = kboard.next().toUpperCase();       
        boolean whoPlaysFirst = (mark.equals("X")) ? true : false;

        TicTacToeV2 myGame = new TicTacToeV2(name,whoPlaysFirst); 

        myGame.playGame(kboard);
    }

    public void playGame(Scanner kboard)throws Exception{   

        Integer move = null;
        boolean goodMove;
        String kboardInput = null;
        Scanner input;
        int[] cell2D = new int[2];
        Random random = new Random();
        int nextComputerMove;

        if(toSeed){
           board = seedBoard();          
           availableMoves = seedAvailable(board); 
           int x = 0;
           int o = 0;
           for(int i = 0; i < 3;i++){
              for(int j = 0;j < 3;j++){
                 if(board[i][j].equals("X"))x++;
                 else if(board[i][j].equals("O"))o++;

              }
           }

              if((x - o) == 1) humanGoes = true;
              else if((x - o) == 0) humanGoes = false;
              else{
                 System.out.println("Fatal Error: seed bad");
                 System.exit(0);
              }

          System.out.println("humangoes = " + humanGoes + x + o);
        }

        while(!winner && !draw){            
            printHeader();
            goodMove = false; 
            drawBoard(board);           

            if(!humanGoes && availableMoves.size() < 9){
                System.out.println("That's a great move, I'll have to think about this");
                Thread.sleep(2000);   
            }

            if(humanGoes){
                while(!goodMove){ 
                    System.out.print("\n\n          Please enter a number for your move : ");
                    kboardInput = kboard.next();
                    input = new Scanner(kboardInput);
                    if(input.hasNextInt()){
                        move = input.nextInt();
                        if(move == 99){
                            System.out.println("You found the secret exit code");
                            Thread.sleep(2000);
                            printHeader();
                            System.out.println("bye");
                            System.exit(0);
                        }
                        goodMove = checkMove(move);
                        if(!goodMove)System.out.println("          WARNING: Incorrect input, try again");
                    }else{
                        System.out.println("          WARNING: Incorrect input, try again");
                    }
                }
                cell2D = single2Double(move);
                board[cell2D[0]][cell2D[1]] = playerMark;

            }else{

                //nextComputerMove = random.nextInt(availableMoves.size());
                //move = availableMoves.get(nextComputerMove);               


                String[][] currentBoard = new String[boardRowDim][boardColDim];
                currentBoard = copyBoard(board);

                ArrayList<Integer> currentAvailableMoves= new ArrayList<Integer>();
                currentAvailableMoves = copyAvailableMoves(availableMoves);

                //System.out.println(System.identityHashCode(currentAvailableMoves));

                int[] bestScoreMove = new int[2];

                bestScoreMove = findBestMove(currentBoard,currentAvailableMoves,true,0,kboard); 
                move = availableMoves.get(availableMoves.indexOf(bestScoreMove[1]));

                cell2D = single2Double(move);
                board[cell2D[0]][cell2D[1]] = computerMark;
            }

            humanGoes = humanGoes ? false:true; 

            availableMoves = updateAvailableMoves(move,availableMoves);

            if (Math.abs(score(board)) == 15) winner = true;
            if (availableMoves.size() == 0) draw = true; 

            if(winner || draw){ 
                printHeader();             
                drawBoard(board); 
            }

            if(score(board) == gameTargetScore)System.out.println(playerName + " you are too good for me. \n" +
                    "Congratulations you won!!\n\n");
            else if(score(board) == -gameTargetScore)System.out.println("IWONIWONIWONohboyIWONIWONIWON");            
            else if(draw)System.out.println("Good game. It's a draw!");

        }  
    }

    public void drawBoard(String[][] someBoard){ 

        String mark = " ";
        Integer row,col;
        String type;



        for( int i = 0;i < 15; i++){ 
            System.out.print("          "); 
            for (int  j = 0; j < 27; j++){ 

                mark = " ";
                if(i==5 || i == 10)mark = "-";
                if(j==8 || j == 17)mark = "|";

                row = i/5;
                col = j/9;

                type = someBoard[row][col];

                if(type == "X"){
                    if( ((i%5 == 1 || i%5 == 3) &&
                        (j%9 == 3 || j%9 == 5)) ||
                    (i%5 == 2 && 
                        j%9 == 4))mark = "X";
                }else if(type == "O"){
                    if( ((i%5 == 1 || i%5 == 3) &&
                        (j%9 == 3 || j%9 == 4 || j%9 == 5)) ||
                    ((i%5 == 2) && 
                        (j%9 == 3 || j%9 == 5))) mark = "O";   
                }else{
                    if( i%5 == 2 && j%9 == 4){
                        mark = ((Integer)(row * 3 + col)).toString();                        
                    }
                }
                System.out.print(mark);
            } 
            System.out.println();
        }
        System.out.println("\n\n\n");
    }    

    public boolean checkMove(Integer move){
        /*
         * to sanitize user input we have to check if what
         * they entered is an available square
         */
        boolean goodMove = false;

        for(Integer available : availableMoves){
            if (available == move) goodMove = true;
        }       

        return goodMove;       
    }

    public int score(String[][] newBoard){

        int row;
        int newCol;
        int score = 0; 
        for (int strategy = 0; strategy < 8; strategy++){
            score = 0; 
            for (int col = 0; col < 3; col++){
                if(strategy < 3){  //rows
                    row = strategy ;
                    newCol = col;
                }else if (strategy < 6){ //cols
                    row = col;
                    newCol = strategy - 3;
                }else{//diag
                    int diag = strategy - 6;
                    row = col - 2 * diag * (col - 1);
                    newCol = col;                    
                }
                if(newBoard[row][newCol].equals("X")){
                    score+=5;                   
                }else if(newBoard[row][newCol].equals("O")){
                    score+=-5;                   
                }
            }
            score = (Math.abs(score)== 15) ? score : 0;            
            if(Math.abs(score) == 15) break;
        } 


        return score;         
    }

    public String[][] copyBoard(String[][] originalBoard){
        String[][] duplicateBoard = new String[boardRowDim][boardColDim];
        for (int i = 0;i < boardRowDim; i++){
            for(int j = 0; j < boardColDim; j++){                
                duplicateBoard[i][j] = originalBoard[i][j]; 
            } 
        }
        return duplicateBoard;
    }

    public String[][] updateBoard(Integer move, String mark, String[][]oldBoard){
        String[][] currentBoard = new String[boardRowDim][boardColDim];
        int[] cell2D = new int[2];

        currentBoard = copyBoard(oldBoard);
        cell2D = single2Double(move);
        currentBoard[cell2D[0]][cell2D[1]] = mark;

        return currentBoard;        
    }

    public ArrayList<Integer> copyAvailableMoves(ArrayList<Integer> originalAvailableMoves){
        ArrayList<Integer> duplicateAvailableMoves = new ArrayList<Integer>(); 
        for(int i = 0; i < originalAvailableMoves.size();i++){
            duplicateAvailableMoves.add(originalAvailableMoves.get(i));            
        }
        return duplicateAvailableMoves;        
    }

    public ArrayList<Integer> updateAvailableMoves(Integer move, ArrayList<Integer> oldAvailableMoves){
        ArrayList<Integer> currentAvailableMoves = new ArrayList<Integer>();
        currentAvailableMoves = copyAvailableMoves(oldAvailableMoves);
        currentAvailableMoves.remove(move);
        return currentAvailableMoves;

    }
    public String[][] seedBoard(){
       String[][] sampleBoard ={{"0","O","X"},{"X","4","O"},{"6","7","X"}}; 
       //String[][] sampleBoard ={{"X","O","O"},{"3","4","X"},{"6","7","8"}}; 
       return sampleBoard;
    }

    public ArrayList<Integer> seedAvailable(String[][] seedBoard){
        ArrayList seedMoves = new ArrayList<Integer>();
        int index = -1;
        for(int i = 0; i < 3;i++){
            for (int j = 0; j < 3; j++){
                if(!seedBoard[i][j].equals("X") && !seedBoard[i][j].equals("O")){
                    index = i*3 + j;
                    seedMoves.add(index);
                }
            }
        }
        //System.out.println(seedMoves);

        return seedMoves;

    }

    public int[] findBestMove(String[][] currentBoard, ArrayList<Integer> currentAvailableMoves,boolean currentComputerMoves,int depth,Scanner kboard){
        ArrayList<Integer> simulateAvailableMoves = new ArrayList<Integer>();
        String[][] simulateBoard = new String[boardRowDim][boardColDim];




        //System.out.println(System.identityHashCode(currentAvailableMoves));


        int[] scoreMove = new int[2]; //return array with score and associated move       
        int[] cell2D = new int[2];        //array holding i and j of board to place Mark (X or O)  
        int computerTargetScore = (computerMark.equals("X")) ? 15:-15;

        /*
         * scoreMoveAvailable is an array that holds scores for each available move 
         * inside loop.  The bestScoreMove will be the min or max of this array
         * depending on whether it's X's or O's turn to move 
         */       
        int[][] scoreMoveAvailable = new int[currentAvailableMoves.size()][2];        
        Integer simulateMove = null; //current move inside loop


        Boolean simulateComputerMoves = null;  


        for(int  i  = 0; i < currentAvailableMoves.size(); i++){
            scoreMoveAvailable[i][0] = 0; //score
            scoreMoveAvailable[i][1] = -1; // square 0 - 8
        }

        if(output)System.out.println("on enter available moves " + currentAvailableMoves);



        for (int i = 0; i <  currentAvailableMoves.size() ;i++){ 




            simulateAvailableMoves = copyAvailableMoves(currentAvailableMoves);
            simulateBoard = copyBoard(currentBoard);
            simulateComputerMoves = currentComputerMoves; 

            if(output)System.out.println("in loop available moves " + i + "  " + simulateAvailableMoves);


            simulateMove = simulateAvailableMoves.get(i); 

            simulateAvailableMoves = updateAvailableMoves(simulateMove,simulateAvailableMoves);
            cell2D = single2Double(simulateMove);

            if(simulateComputerMoves){ 
                if(output)System.out.println("computer moves " + simulateMove);


                simulateBoard[cell2D[0]][cell2D[1]] = computerMark;


                simulateComputerMoves = false; 

                if(score(simulateBoard) ==  computerTargetScore || simulateAvailableMoves.size() == 0){
                    scoreMove[0] = score(simulateBoard);
                    scoreMove[1] = simulateMove; 
                    if(output)System.out.println("score computer" + Arrays.toString(scoreMove) +" computer moves = " + simulateMove + " i = " + i);
                    if(output)drawBoard(simulateBoard);                    
                }else{                    
                    depth++;                                      
                    if(output)System.out.println("computer calling findbest " +simulateAvailableMoves);
                    if(output)drawBoard(simulateBoard);
                    scoreMove = findBestMove(simulateBoard,simulateAvailableMoves,simulateComputerMoves,depth,kboard);                    
                }
            }else{ 
                if(output)System.out.println("human moves" + simulateMove);


                simulateBoard[cell2D[0]][cell2D[1]] = playerMark;


                simulateComputerMoves = true;

                if(score(simulateBoard) == (-computerTargetScore) || simulateAvailableMoves.size() == 0){
                    scoreMove[0] = score(simulateBoard);
                    scoreMove[1] = simulateMove;
                    if(output)System.out.println("score human "+ Arrays.toString(scoreMove) +" human moves " + simulateMove + " i = " + i);
                    if(output)drawBoard(simulateBoard);                   
                }else{                    
                    depth++;  
                    if(output)System.out.println("human calling findbest " + simulateAvailableMoves);
                    if(output)drawBoard(simulateBoard);                
                    scoreMove = findBestMove(simulateBoard,simulateAvailableMoves,simulateComputerMoves,depth,kboard);                    
                }
            }



            if(output)System.out.println(i + " simulateMove =  " + simulateMove + " scoreMove[1] =  " + scoreMove[1] + " depth = " + depth);
            //  drawBoard(simulateBoard);

            scoreMoveAvailable[i][0] =  scoreMove[0] ;
            scoreMoveAvailable[i][1] =  simulateMove;
            if(output)System.out.println("score array =  " + i + "  " + Arrays.deepToString(scoreMoveAvailable));
        }

        int[] bestScoreMove = new int[2];
        bestScoreMove[0] = scoreMoveAvailable[0][0];  //set bestScoreMove to first element in arraylist
        bestScoreMove[1] = scoreMoveAvailable[0][1];


         if(output)System.out.println("****************************************");

        if( (currentComputerMoves && computerMark.equals("X") ) || (!currentComputerMoves && computerMark.equals("O") ) ) {

            for (int i = 0; i < scoreMoveAvailable.length;i++){
                if(scoreMoveAvailable[i][0]  > bestScoreMove[0]){
                   bestScoreMove[0] = scoreMoveAvailable[i][0] ;
                   bestScoreMove[1] = scoreMoveAvailable[i][1];
                }
                if(output)System.out.printf("MAX X scores and moves = %d   %d   %d %s\n",i,scoreMoveAvailable[i][0],scoreMoveAvailable[i][1],"XXX"); 
            }
            if(output)System.out.println("\n");
        }else{

            for (int i = 0; i < scoreMoveAvailable.length;i++){
                if(scoreMoveAvailable[i][0]  < bestScoreMove[0]){
                   bestScoreMove[0] = scoreMoveAvailable[i][0] ;
                   bestScoreMove[1] = scoreMoveAvailable[i][1];
                }
                if(output)System.out.printf("MIN O scores and moves =%d %d   %d %s\n",i,scoreMoveAvailable[i][0],scoreMoveAvailable[i][1],"OOO"); 
            }
            if(output)System.out.println("\n");
        }    

        if(output)System.out.println("best " + bestScoreMove[0] + "  " + bestScoreMove[1] + "  " + Arrays.deepToString(scoreMoveAvailable));
        return bestScoreMove;

    }

    /*
     * just some static methods to help make things easy
     */

    public static void printHeader(){
        System.out.println("u000C          Welcome to TicTacToe\n" +
            "        where you can match wits\n" +
            "          against the computer\n" +
            "(the real challenge is making it a draw)\n");
    }


    public static int double2single(int row, int col){
        int singleCell = 0; 
        singleCell = boardRowDim * row + col;
        return singleCell;
    }

    public static int[] single2Double(int cell){
        int[] cell2D = new int[2];

        cell2D[0] = cell / boardColDim;
        cell2D[1] = cell % boardColDim;

        return cell2D;
    }

    public static String capitalize(String word){
        word = word.substring(0,1).toUpperCase() + word.substring(1); 
        return word;    
    }

}

Answer 1

请注意，下图假设您不是在做"depth++"，而是在递归调用中使用"depth + 1“。前者是代码中的一个良性错误，它会导致打印错误。

当使用bestScoreMove = findBestMove...查找计算机的移动时，第一次调用findBestMove。基于种子板和人类采取的"0"，现在可用的移动是4，6和7。

首先，计算机模拟moving 4

• ，这会创建一个递归调用，将一个帧添加到函数堆栈中。人类现在有6个和7个可能的移动。因为6是第一个，所以人类首先“尝试”6。现在，在这个模拟中，它是computer/4 -> human /6

• 再次，一个框架被添加到函数栈中，用于从人类“运行模拟”的递归调用。现在，只剩下一步了:计算机取7，这是best 0 7 [[0, 7]] is printed.

• After，最后一个递归调用返回的地方，函数栈被弹出，我们又回到了人移动6的地方，这就是打印0 simulateMove = 6..的地方。

您可以使用调试器来显示有关堆栈的更多详细信息，但这里有一些额外的建议(主要是为了使函数更简短)，以使调试更容易：

，

• ，有很多Thread.sleep(2000);紧跟着println。您可以在许多但不是所有位置将这两行包含在函数
• 中，逻辑假定电路板大小为3x3，例如&& availableMoves.size() < 9)。这是不一致的，而且这种逻辑可能会令人困惑。为了清楚起见，你可以创建一个函数"noMovesMade()“，它基于可用的variables.
• Additionally，来计算这个值，它可以简单地放在"else”块中(因为这已经意味着它是计算机的turn)
• if((x - o) == 1) humanGoes = true;正在假设人类在玩"O“，而其余的代码不是这样假设的)。
• 在很多情况下，变量被初始化，赋值，然后重新赋值，而不使用。例如，String[][] currentBoard = new String[boardRowDim][boardColDim]; currentBoard = copyBoard(board);是冗余的，bestScoreMove也是如此。可以使用
• Arrays.copyOf来复制数组(在copyBoard的内循环中，可以使用for来代替迭代数组在checkMove
• humanGoes = humanGoes ? false:true;中可以缩写为humanGoes = !humanGoes