java - Java - 极小极大算法问题

Question

我正在制作一个用于练习制作课程的 tictactoe 板，但我的算法遇到了问题。它似乎在返回最好的移动进攻，但它并没有起到防守作用。我不知道我在哪里搞砸了，似乎找不到它。我在这里查看了很多关于它的东西，并将它与类似的项目进行了比较，但似乎仍然无法理解。这是我的代码。

package TicTacToe;

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


public class Solution {

private static GameBoard currentBoard; 
private static Player botPlayer; 

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    String player;
    System.out.println("ENTER bot: ");
    player = in.next();

    if(player.equalsIgnoreCase("X")) {
        botPlayer = Player.X;}
    else {botPlayer = Player.O;}

    String board[] = new String[3];
    for(int i = 0; i < 3; i++) {
        System.out.println("ENTER board: ");
        board[i] = in.next();
    }

        currentBoard = new GameBoard(3,3, board);
        List<Space> OpenSpaces = getOpenSquares(currentBoard);
        MakeMove(OpenSpaces);

    System.exit(-1);
}

public static List<Space> getOpenSquares(GameBoard GB) {
    List<Space> OpenSpaces = new ArrayList<Space>();
    for(int r = 0; r < 3; r++) {
        for(int c = 0; c < 3; c++) {
            if(GB.squares[r][c] == Player.Open) {
                OpenSpaces.add(new Space(r,c));
            }
        }
    }
    return OpenSpaces;
}

private static Space bestMove;
private static Space currentMove;
private static Space previousMove;


private static void MakeMove(List<Space> OpenSpaces) {
    if(OpenSpaces.size() == currentBoard.Size) {
        Random random = new Random();
        bestMove = new Space(random.nextInt(2),2);
    } else {
        for(Space child: OpenSpaces) {
            currentMove = GetBestMove(currentBoard,botPlayer);
            if (currentMove != null){

            }else{
                continue;}
            if(previousMove != null && previousMove.Rank < currentMove.Rank ||
                    previousMove == null && currentMove != null) {
                bestMove = currentMove;
            }
            previousMove = currentMove;
        }   
    }
    if (bestMove != null) {
        currentBoard.squares[bestMove.X][bestMove.Y] = botPlayer;
        System.out.println("the best move is: " + currentMove.X + " " + currentMove.Y);
    } 
}

private static Space GetBestMove(GameBoard gb, Player p) {
    Space bestSpace = null;
    List<Space> cloneOpenSpaces = getOpenSquares(gb);
    GameBoard cloneBoard = null;
    cloneBoard = gb.Clone();
        for(Space Open: cloneOpenSpaces) {
            cloneBoard = gb.Clone();
            Space newSpace = Open;
            cloneBoard.squares[newSpace.X][newSpace.Y] = p;
            if(cloneBoard.Winner == Player.Open && cloneOpenSpaces.size() > 0) {
                Player InP;
                if(p == Player.X) {
                    InP = Player.O;
                }else {
                    InP = Player.X;
                    }

                Space tempMove = GetBestMove(cloneBoard, InP);
                if(tempMove != null){
                    newSpace.Rank = tempMove.Rank;
                }


            } else {
                if(cloneBoard.Winner == Player.Open) {
                    newSpace.Rank = 0;
                }else if(cloneBoard.Winner == Player.O) {
                    newSpace.Rank = -1;
                }else if(cloneBoard.Winner == Player.X) {
                    newSpace.Rank = 1;
                }

            }
            System.out.println(newSpace.Rank);
            if(bestSpace == null || 
                    (p == Player.X && newSpace.Rank < ((Space)bestSpace).Rank)||
                    (p == Player.O && newSpace.Rank > ((Space)bestSpace).Rank)) {
                bestSpace = newSpace;
            }               
        }
    return (Space)bestSpace;
}

public static enum Player {
    X (1),
    O (-1),
    Open (0);

    private final double value;
    Player(double value){
        this.value = value;
    }
}

public static class Space {
    public int X;
    public int Y;
    public double Rank;

    public Space(int x, int y) {
        this.X = x;
        this.Y = y;
        Rank = 0;
    }


    public Space() {
    }
}

public static class GameBoard {

    public int Rows;
    public int getRows() {
        return this.Rows;
    }
    public void setRows(int rows) {
        Rows = rows;
    }

    public int Columns;
    public int getColumns() {
        return this.Columns;
    }
    public void setColumns(int columns) {
        Columns = columns;
    }

    public Player[][] squares;

    //public Player[x][y] 
    public Player getPlayer(int x, int y) {
        return this.squares[x][y];
    }

    public void setPlayer(int x, int y, Player player) {
        squares[x][y] = player;
    }

    public boolean Full;

    public boolean isFull() {
        for(int r = 0; r < 2; r++) {
            for(int c = 0; c < 2; c++) {
                if (squares[r][c] != Player.Open) {return false;}
            }
        }
        return true;
    }

    public int Size;
    public int getSize() {
        return this.Size;
    }
    public void setSize(int size) {
        Size = size;
    }

    public List<Space> OpenSquares;
    public List<Space> getOpenSquares() {
        List<Space> OpenSquares = new ArrayList<Space>();
        for(int r = 0; r < Rows; r++) {
            for(int c = 0; c < Columns; c++) {
                if(squares[r][c] == Player.Open) {
                    OpenSquares.add(new Space(r,c));
                }
            }
        }
        return this.OpenSquares;
    }

    public Player Winner;
    public Player getWinner() {
        int count = 0; 

        //columns 
        for (int x = 0; x < Rows; x++) 
        { 
            count = 0;
            for (int y = 0; y < Columns; y++) {
                count += squares[x][y].value;
            }
            if (count == 3) {
                return Player.X; 
            }else if (count == -3) {
                return Player.O; 
            }
        } 

        //rows 
        for (int x = 0; x < Rows; x++) { 
            count = 0; 
            for (int y = 0; y < Columns; y++) {
                count += squares[y][x].value; 
            }
            if (count == 3) {
                return Player.X; 
            }else if (count == -3) {
                return Player.O; 
            }
        } 

        // Diagonals right to left 
        count = 0; 
        count += squares[0][0].value; 
        count += squares[1][1].value; 
        count += squares[2][2].value; 
        if (count == 3) {
            return Player.X; 
        }else if (count == -3) {
            return Player.O; 
        } 


        // Diagonals left to right 
        count = 0; 
        count += squares[0][2].value; 
        count += squares[1][1].value; 
        count += squares[2][0].value; 
        if (count == 3) {
            return Player.X; 
        }else if (count == -3) {
            return Player.O; 
        }
        return Player.Open; 
    }

    public GameBoard Clone() {
        GameBoard b = new GameBoard(Rows,Columns);
        b.squares = (Player[][])this.squares.clone();
        b.Winner = getWinner();
        return b;
    }

    // Class initializer 
    public GameBoard(int boardRows, int boardColumns, String[] board) {

        // Set the dimensions 
        Rows = boardRows;
        Columns = boardColumns;

        // Create game spaces 
        squares = new Player[Rows][Columns];
        for(int r = 0; r < Rows; r++) {
            for(int c = 0; c < Columns; c++) {
                //squares[i][n] = Player.Open;
                if(board[r].charAt(c) == 'X') {
                    squares[r][c] = Player.X;
                }
                if(board[r].charAt(c) == 'O') {
                    squares[r][c] = Player.O;
                }
                if(board[r].charAt(c) == '_') {
                    squares[r][c] = Player.Open;
                }
            }
        }
        this.Winner = getWinner();
        this.OpenSquares = getOpenSquares();
        //Size of the board
        this.Size = Rows * Columns;
    }

    // clone Class initializer
    public GameBoard(int boardRows, int boardColumns) {
        // Set the dimensions 
        Rows = boardRows;
        Columns = boardColumns;

        // Create game spaces 
        squares = new Player[Rows][Columns];
        for(int r = 0; r < Rows; r++) {
            for(int c = 0; c < Columns; c++) {
                squares[r][c] = Player.Open;
            }   
        }
        this.Winner = getWinner();
        this.OpenSquares = getOpenSquares();
        //Size of the board
        Size = Rows * Columns;
    }
}
}

所有的类都在底部。提前感谢您的任何帮助和更正。:)

我在下面的代码中使它递归，虽然我仍然无法计算得分.. 如果值为 1、0 或 -1，那么如果有多个具有相同值的移动，它将只取第一个可能不是最好的举动“阻止。

private static Space GetBestMove(GameBoard gb, Player p) {
Space bestSpace = null;
List<Space> cloneOpenSpaces = getOpenSquares(gb);
GameBoard cloneBoard = null;
cloneBoard = gb.Clone();
    for(Space Open: cloneOpenSpaces) {
        cloneBoard = gb.Clone();
        Space newSpace = Open;
        cloneBoard.squares[newSpace.X][newSpace.Y] = p;
        if(cloneBoard.Winner == Player.Open && cloneOpenSpaces.size() > 0) {
            Player InP;
            if(p == Player.X) {
                InP = Player.O;
            }else {
                InP = Player.X;
                }

            ***Space tempMove = GetBestMove(cloneBoard, InP);***
            if(tempMove != null){
                newSpace.Rank = tempMove.Rank;
            }

测试结果如下

测试 1

ENTER bot: 
O

ENTER board: 
[ ][O][ ]

ENTER board: 
[ ][ ][ ]

ENTER board: 
[ ][X][X]

-1.0
-1.0
-1.0
-1.0
-1.0
-1.0
-1.0
-1.0
-1.0

the best move is: 0 2

测试 2

ENTER bot: 
O

ENTER board: 
[ ][X][X]

ENTER board: 
[ ][ ][ ]

ENTER board: 
[ ][O][ ]


1.0
1.0
1.0
1.0
1.0
-1.0
1.0
-1.0
-1.0
1.0
-1.0
1.0
1.0
-1.0
-1.0
the best move is: 1 1

score 2 · Accepted Answer

我没有运行你的代码，但我想我可能知道你为什么会遇到问题。极小极大算法本质上是递归的。您查看每个开放空间，并为每个空间确定某种分数。我在你的代码中看到了这一点。但是，我没有看到等同于逻辑的递归“如果我移到这里，那么我的对手在下一轮会有什么选择”。请注意，您可以继续调用相同的评分函数，但对两个玩家的选项进行评分。这是计算变得密集的地方，也是剪枝之类的东西发挥作用的地方。假设我想向前看 3 步。假设最初有 5 个开放空间。对于 5 个开放空间中的每一个，我都会检查我的选项并给每个选项打分。然后我假装移动到那里，通过计分功能发送新的棋盘，并假设我的对手将采取剩余 4 个可能的移动中得分最高的移动。然后我假装他移动到那里，然后我再次通过计分功能运行棋盘，现在上面有 2 个假设的移动。你继续这个设定的“深度”，或潜在移动的数量，并选择产生最高价值的移动，假设对手会按照你计算的那样做。

我意识到这是冗长的，但我希望在某个地方埋藏一点价值。看看你的代码，找出你在哪里得分（如果你看到胜利，接受它；如果你能阻止胜利，接受它；等等）。然后继续调用此函数，在其中不断添加虚假/潜在动作（得分函数中具有最高价值的动作），一旦达到深度，您就可以简单地选择可能给您带来最有价值结果的动作。

基本上，在您的代码中，您应该GetBestMove(...)从MakeMove(...). 但是，GetBestMove(...)应该反复调用自己，每次都用修改板；每次，它都会返回给定假设（或真实）棋盘的最佳棋步。我在您的代码中没有看到的是对的递归调用GetBestMove(...)，以及随之而来的必要维护。这就解释了为什么你只会出现攻击性行为；它只看最好的立即行动是什么，而不考虑如果你采取行动你的对手可能会做什么！

如果我的假设是错误的，请提供一个测试用例，您期望在其中出现一些行为，但会得到不同的结果。

java - Java - 极小极大算法问题

测试 1

测试 2

1 回答 1

Related

Reference