连接四的极小极大
Minmax for ConnectFour
我正在尝试实现一个 minmax 算法来为连接四创建一个 AI。尽管我觉得我的事情过于复杂（而且它不能正常工作），但我遇到了很多麻烦，也许这里有人可以提供帮助。我将首先 post 我的代码，然后是我在下面遇到的问题。
这是对 minmax 算法的初始调用
public int getColumnForMove(ConnectFour game)
{
game.minimax(2, game.getCurrentPlayer(), game);
int column = game.getBestMove();
return column;
}
这是被调用的初始 minimax 方法（它在 ConnectFour class 内部，而不是在单独的 AI class 中调用初始方法的地方）和子class 包含用户移动到的每一列以及移动到该列时的 min/max 分数。
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 方法（它有一堆注释掉的代码表明它应该 return 一系列值取决于棋盘的好坏，如果它不是明确的赢或输但现在我只是想让它根据输赢做出决定（如果 none 发生在请求的深度，它会随机移动）。
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());
这应该将它放入一个单独的实例中，这样当我随后进行移动时，它应该只持续到树的那个分支并且不会破坏正在玩的实际游戏，但事实并非如此。它正在改变正在传递的游戏的实际状态。
我只想解决一个问题。每个问题你应该尽量不要太多，并包括与你的问题相关的代码，比如你的 ConnectFour class 这里。
如果你想复制电路板，你可以在不改变原件的情况下进行修改，你需要制作一个deep copy，而不是参考的副本。要对您的房屋进行浅表复制，您需要复制房屋钥匙。如果您将它送给某人，当您回到家时看到变化，您不应该感到惊讶。要对您的房子进行深度复制，您需要获得第二批土地，然后根据您房子的蓝图和照片建造一座新房子。如果您将新房的钥匙交给某人，he/she 可能不会立即注意到差异，但任何更改都不会直接影响您，您所做的更改也不会影响接收者。
"Deep copy" 实际上是有歧义的，因为你的对象可能包含有对象成员的对象成员。进行深拷贝时，您必须决定是对任何成员对象进行深拷贝还是浅拷贝。如果您的 ConnectFour class 包含一个 Move 对象的 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];
}
...
问题很可能是由 ConnectFour 的实施引起的，例如
private int[][] state;
public void setCurrentGameState(int[][] newState) {
this.state = newState;
}
没关系，但会使您的 "copy" 游戏状态实际引用 相同的 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;
}
}
我正在尝试实现一个 minmax 算法来为连接四创建一个 AI。尽管我觉得我的事情过于复杂（而且它不能正常工作），但我遇到了很多麻烦，也许这里有人可以提供帮助。我将首先 post 我的代码，然后是我在下面遇到的问题。
这是对 minmax 算法的初始调用
public int getColumnForMove(ConnectFour game)
{
game.minimax(2, game.getCurrentPlayer(), game);
int column = game.getBestMove();
return column;
}
这是被调用的初始 minimax 方法（它在 ConnectFour class 内部，而不是在单独的 AI class 中调用初始方法的地方）和子class 包含用户移动到的每一列以及移动到该列时的 min/max 分数。
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 方法（它有一堆注释掉的代码表明它应该 return 一系列值取决于棋盘的好坏，如果它不是明确的赢或输但现在我只是想让它根据输赢做出决定（如果 none 发生在请求的深度，它会随机移动）。
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());
这应该将它放入一个单独的实例中，这样当我随后进行移动时，它应该只持续到树的那个分支并且不会破坏正在玩的实际游戏，但事实并非如此。它正在改变正在传递的游戏的实际状态。
我只想解决一个问题。每个问题你应该尽量不要太多，并包括与你的问题相关的代码，比如你的 ConnectFour class 这里。
如果你想复制电路板，你可以在不改变原件的情况下进行修改，你需要制作一个deep copy，而不是参考的副本。要对您的房屋进行浅表复制，您需要复制房屋钥匙。如果您将它送给某人，当您回到家时看到变化，您不应该感到惊讶。要对您的房子进行深度复制，您需要获得第二批土地，然后根据您房子的蓝图和照片建造一座新房子。如果您将新房的钥匙交给某人，he/she 可能不会立即注意到差异，但任何更改都不会直接影响您，您所做的更改也不会影响接收者。
"Deep copy" 实际上是有歧义的，因为你的对象可能包含有对象成员的对象成员。进行深拷贝时，您必须决定是对任何成员对象进行深拷贝还是浅拷贝。如果您的 ConnectFour class 包含一个 Move 对象的 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];
}
...
问题很可能是由 ConnectFour 的实施引起的，例如
private int[][] state;
public void setCurrentGameState(int[][] newState) {
this.state = newState;
}
没关系，但会使您的 "copy" 游戏状态实际引用 相同的 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;
}
}