我目前正在尝试在 flutter 中实现一个简单的井字游戏。我正在使用 minimax 函数来计算 AI 玩家的动作。对于最简单的 3x3 列表数组，minimax 函数可以完美运行。但是当我尝试对 4x4,5x5,6x6 列表数组使用相同的 minimax 函数（以使游戏更加复杂和有趣）时，minimax 函数似乎无限地运行而不返回移动，无论我做什么（我添加了 alpha-beta 修剪，但没有效果）。我究竟做错了什么。任何帮助将不胜感激。以下是我使用的主要功能：
int minimax(List<List<String>> board, bool isMaximizing, BuildContext context, int alpha, int beta) {
// Check for terminal states
if (checkWin(board, 'O', context)) {
return 1;
} else if (checkWin(board, 'X', context)) {
return -1;
} else if (checkDraw(board)) {
return 0;
}
// Recursively explore the game tree
if (isMaximizing) {
int bestScore = -1000;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j].isEmpty) {
board[i][j] = 'O';
int score = minimax(board, false, context, alpha, beta);
board[i][j] = '';
bestScore = max(score, bestScore);
alpha = max(alpha, score);
if (beta <= alpha) {
break; // Prune the subtree
}
}
}
}
return bestScore;
} else {
int bestScore = 1000;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j].isEmpty) {
board[i][j] = 'X';
int score = minimax(board, true, context, alpha, beta,);
board[i][j] = '';
bestScore = min(score, bestScore);
beta = min(beta, score);
if (beta <= alpha) {
break; // Prune the subtree
}
}
}
}
return bestScore;
}
}
bool checkWin(List<List<String>> board, String player, BuildContext context) {
for (int i = 0; i < 4; i++) {
if ((board[i][0] == player &&
board[i][1] == player && board[i][2] == player && board[i][3] == player) || (board[0][i] == player &&
board[1][i] == player && board[2][i] == player && board[3][i] == player)) {
//Testing for winning cells so as to add colors
if(context.read<SharedPrefProvider>().hardLevel % 2 != 0) {
checkWinColors(board, player, i, context);
}
return true;
}
}
if ((board[0][0] == player && board[1][1] == player && board[2][2] == player && board[3][3] == player) ||
(board[0][3] == player && board[1][2] == player && board[2][1] == player && board[3][0] == player)) {
//Testing for winning cells so as to add colors
if(context.read<SharedPrefProvider>().hardLevel % 2 != 0) {
checkWinColors(board, player, 0, context);
}
return true;
}
return false;
}
bool checkDraw(List<List<String>> board) {
// Check if every row has every cell filled
for (var row in board) {
for (var cell in row) {
if (cell.isEmpty) {
return false; // If any cell is empty, the game is not a draw
}
}
}
// If all cells are filled, the game is a draw
return true;
}
以下函数调用 minimax 函数来获取棋盘上最佳 AI 走法的索引
void makeAIMove(board) {
int bestScore = -1000;
int bestMoveRow = -1;
int bestMoveCol = -1;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j].isEmpty) {
board[i][j] = 'O';
int score = minimax(board, false, context, -1000, 1000);
board[i][j] = '';
if (score > bestScore) {
bestScore = score;
bestMoveRow = i;
bestMoveCol = j;
}else{
}
}
}
}
//Returns index of the next move on the board
if (bestMoveRow != -1 && bestMoveCol != -1) {
setState(() {
board[bestMoveRow][bestMoveCol] = "O";
});
}
}
4x4 版本的“问题”是游戏开始时要检查的棋盘状态数量从大约 9 个增加！到16！ （这里我忽略了早期的胜利，但他们代表了少数）。所以从 ~106 到 ~1013。再加上每个状态的工作量，即访问所有单元格以检查平局或获胜，您将获得大约 1015 数量级的操作。预计 minimax 不会很快从这样的任务中返回。
以下是一些提高性能的想法：
使用更快的数据结构来维护状态：使用位图。 X 玩家使用一张 16 位位图，O 玩家使用一张。
在此类位图上检查胜利会更快。有 10 条线可以获胜：每条线都可以由一个 4 位设置为 1 的位图表示。如果这样的获胜者位图与当前 X 位图的 AND 得到获胜者位图，则您会发现X 获胜。如果 X 位图与 O 位图的 OR 导致所有 16 位设置为 1，也可以检测到平局。
即使棋盘未满，您也可以检测棋盘是否不再有可能获胜。当两个玩家都在每条可能的线上都采取了行动时，就会发生这种情况。同样，您可以使用位图来检查这一点，并且它允许您使用值 0 提前回溯。
通过位图操作，您可以知道哪些方格仍然为空，并且再次通过智能位操作（请参阅：如何获取数字中最低有效位的值？）您可以避免 16 次迭代，并且只进行每个自由方块的迭代。
棋盘越大，您评估之前已经访问过的棋盘（通过交换棋步）的可能性就越大。因此，应用记忆化是值得的：使用先前评估的值维护一个字典（由这些位图对作为键）。
扩展上一点：在读取/写入该字典时，首先将镜像/旋转应用到其中“最少”的 8 个等效板之一（按任何选定的顺序，例如按位图顺序）。
为极小极大搜索设置最大搜索深度。当达到最大深度并且棋盘不代表胜利时，则返回棋盘的启发值。这可以像平局一样简单地返回 0。这个想法是，如果你在 4 步之内取得了胜利，那么就不值得深入研究，因为可以肯定的是（在这场比赛中）对手有足够的防守可能性来对抗你的动作并保持平局。同样的道理也适用于 4 步之内不输掉比赛。
因此，您可以采取很多措施来优化该算法。
最后（但这可能不是您的兴趣），4x4 连胜游戏在最佳玩法中是平局，比 3x3 井字游戏更微不足道。我发现应用极小极大对于这个游戏来说是大材小用。您可以在搜索深度 1 处设计一个静态评估函数，并偏向于最大化您在仍可获胜的行中所拥有的位置数量减去对手的相同度量之间的差异的移动。