ConnectFour的Minmax

Question

我正在尝试实现一个最小最大算法来创建一个连接四的人工智能。我在这方面遇到了很多麻烦，因为我觉得我有一些过于复杂的事情(而且它不能正常工作)，也许这里的人能帮上忙。我将首先发布我的代码，然后我将在下面讨论它的问题。

这是对minmax算法的初始调用。

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

这是一个初始的minimax方法(它在ConnectFour类中，它不是在单独的AI类中调用初始方法的地方)，是一个子类，它保存着用户移动到的每一列，以及如果它移动到该列中，则包含min/max‘’ed得分。

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调用的一种方法，它可以从极小极大地增加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[][] state，因此对它的任何修改都将适用于这两种状态。你想要的是

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

Answer 2

我只想谈谈一个问题。您应该尽量不要有太多的每个问题，并包括与您的问题相关的代码，如您的ConnectFour类这里。

如果您想要在不更改原件的情况下修改板的副本，则需要创建一个深拷贝，而不是引用的副本。要对你的房子做浅薄的复制，你要复制你的房子钥匙。如果你把它给了某人，当你回到家的时候，你不应该惊讶地看到变化。要对你的房子做一个深刻的复制，你可以得到第二批土地，然后根据你房子的蓝图和照片建造一座新房子。如果你把新房子的钥匙给了某个人，他/她可能不会立即注意到这一点，但是任何改变都不应该直接影响到你，而且你所做的改变不会影响收信人。

“深度复制”实际上是模棱两可的，因为您的对象可能包含具有对象成员的对象成员。在进行深度复制时，必须决定是对任何成员对象进行深拷贝还是浅层复制。如果ConnectFour类包含移动对象的ArrayList (每个对象都是表示列的int的包装器)，则有3个选择：

• 您可以复制对ArrayList的引用。
• 您可以使用对同一组移动的引用来创建一个新的ArrayList。
• 您可以使用对移动副本的引用创建一个新的ArrayList。

无论如何，我的猜测是，您还没有嵌套的成员对象，因此深度复制方法可以如下所示：

public class ConnectFour{
    private int[][] board = new int[6][7];

    public setCurrentGameState(int[][] state){ 
        for(int i = 0; i<6; i++)
            for(int j=0; j<7; j++)
                board[i][j] = state[i][j];
    }
    ...