java - 连接四的极小极大

Question

我正在尝试实现一个 minmax 算法来为连接四创建一个 AI。尽管我觉得我的事情过于复杂(而且它不能正常工作)，但我遇到了很多麻烦，也许这里有人可以提供帮助。我将首先发布我的代码，然后在下面发布我遇到的问题。

这是对 minmax 算法的初始调用

public int getColumnForMove(ConnectFour game) 
{
    game.minimax(2, game.getCurrentPlayer(), game);
    int column = game.getBestMove();
    return column;
}

这是被调用的初始 minimax 方法(它在 ConnectFour 类中，而不是在单独的 AI 类中调用初始方法的地方)和一个包含用户移动到的每一列的子类如果它移动到该列，则作为最小/最大分数。

class ColumnsAndScores
{
    int column;
    int score;

    ColumnsAndScores(int column, int score)
    {
        this.column = column;
        this.score = score;
    }

}

List<ColumnsAndScores> cas = new ArrayList<>();

public void minimax(int depth, int turn, ConnectFour game)
{
    cas = new ArrayList<>();
    minimaxHelper(depth, depth, turn, game);
}

以下是从每组可能的移动中获取最小或最大分数的方法:

public int getMax(List<Integer> list)
{
    int max = Integer.MIN_VALUE;
    int index = -1;

    for (int i = 0; i < list.size(); i++)
    {
        if (list.get(i) > max)
        {
            max = list.get(i);
            index = i;
        }
    }

    return list.get(index);
}

public int getMin(List<Integer> list)
{
    int min = Integer.MAX_VALUE;
    int index = -1;

    for (int i = 0; i < list.size(); i++)
    {
        if (list.get(i) < min)
        {
            min = list.get(i);
            index = i;
        }
    }

    return list.get(index);
}

这是实际的 minimax 方法(它有一堆注释掉的代码，表明它应该返回一系列值，具体取决于棋盘的好坏，如果它不是明确的赢或输，但现在我只是试图让它根据输赢做出决定(如果在请求的深度内没有发生任何事情，它就会随机移动))。

public int minimaxHelper(int originalDepth, int depth, int turn, ConnectFour game) 
{   
    //holds future game states
    ConnectFour futureGameState;

    //holds the current scores
    List<Integer> scores = new ArrayList<>(); 

    //if (not at the lowest depth)
    if (depth !=0)
    {
        if (checkForWin(turn))
        {
            //return Integer.MAX_VALUE or Integer.MIN_VALUE respectively based on who's turn it is
            return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;

        }

        //recursively call getColumnForMove(depth--, otherTurn) for each column if the column isnt full
        for (int i = 1; i <= ConnectFour.NUM_OF_COLUMNS; i++)
        {
            futureGameState = new ConnectFour();
            futureGameState.setCurrentGameState(game.getCurrentGameState());
            futureGameState.setCurrentPlayer(game.getCurrentPlayer());
            if (futureGameState.isValidMove(i))
            {
                futureGameState.makeMove(i);
                futureGameState.switchPlayer();
                scores.add(minimaxHelper(originalDepth, depth - 1, futureGameState.getCurrentPlayer(), futureGameState));
            }
            else //if move isnt valid return the worst possible value so this column doesnt get chosen
            {
                return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            if (depth == originalDepth)
            {
                ColumnsAndScores newScore;
                if (turn % 2 == 0)
                    newScore = new ColumnsAndScores(i, getMax(scores));
                else
                    newScore = new ColumnsAndScores(i, getMin(scores));

                cas.add(newScore);
            }

        }

        if (turn % 2 == 0)
            return getMax(scores);
        else
            return getMin(scores);

    }
    else
    {
        if (checkForWin(turn))
        {
            //return Integer.MAX_VALUE or Integer.MIN_VALUE respectively based on who's turn it is
            return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;

        }
        else
        {
            return 0;
        }
        //else
            //if 3 in a row with 2 open spaces that have pieces under those spaces
                //return 100
            //else if 3 in a row with 1 open space that has a piece under that space
                //return 80;
            //else if 3 in a row
                //return 60;
            //else if 2 in a row 
                //return 40
            //else
                //return 0
    }

}

最后，这是一种由 AI 调用的方法，用于从 minimax 也添加了 ColumnAndScores 的列表中获得最佳着法。

public int getBestMove()
{
    int highestScore = Integer.MIN_VALUE;
  int best = -1;

  for (int i = 0; i < cas.size(); ++i) { 
      if (highestScore < cas.get(i).score) {
         highestScore = cas.get(i).score;
          best = i;
      }
  }

  if (highestScore == 0)
    return 1 + ((int) (Math.random() * 7));
  else
    return best;
}

虽然我认为存在一些逻辑错误，但我目前遇到的最大困难是当我执行futureGameState = new ConnectFour(); 时。
futureGameState.setCurrentGameState(game.getCurrentGameState());

这应该将它放入一个单独的实例中，这样当我随后进行移动时，它应该只持续到树的那个分支，而不会破坏正在玩的实际游戏，但事实并非如此。它正在改变正在传递的游戏的实际状态。

Answer 1

这个问题很可能是由 ConnectFour 的实现引起的，比如

private int[][] state;
public void setCurrentGameState(int[][] newState) {
    this.state = newState;
}

没关系，但会导致您的游戏状态“副本”实际引用相同 int[][] 状态，因此对它的任何修改都将应用于两个州。你想要的是

public class ConnectFour implements Cloneable<ConnectFour> {
    private static final int NUM_ROWS = 6;
    private static final int NUM_COLS = 7;
    private int[][] state = new int[NUM_ROWS][NUM_COLS];
    // ...
    public ConnectFour clone() {
        int[][] stateCopy = new int[NUM_ROWS][NUM_COLS];
        for (int i = 0; i < NUM_ROWS; i++)
            for (int j = 0; j < NUM_COLS; j++)
                stateCopy[i][j] = this.state[i][j];
        ConnectFour cloned = new ConnectFour();
        cloned.setCurrentGameState(stateCopy);
        // copy other fields over to cloned
        return cloned;
    }
}