极小极大算法的解释
5.00/5 (1投票)
如何在游戏应用程序中采用 Minimax 算法作为获胜策略。
引言
递归的概念，即一个方法调用自身的另一个实例，可能有点难以理解，因为它在某种程度上需要三维思考。需要同时考虑输入和输出参数以及递归调用的深度。因此，在深入研究更复杂的 Minimax 算法之前，考虑一个简单的例子可能会有所帮助。
递归算法
递归算法是自身内部调用同一函数的另一个实例的函数。它们都具有一些共同的特征，通过一个简单的例子可以最好地展示。这是一个计算 x 的 n 次幂的递归方法。
public int XPowerN( int x, int n)
{
if (n==0 )
{
return 1;
}
int nMinusOneResult=XPowerN( x, n-1 );
return nMinusOneResult * x;
}
该方法必须能够输出一个内部生成的结果，而无需进行递归调用，否则将创建一个无法返回的编码黑洞。在这种情况下，当 n=0 时，方法会跳出自身并返回 1。对于 n 的其他值，该方法依赖于对同一方法的其他调用逐步完成的工作。在这个例子中，该方法需要 n-1 作为参数的递归调用的结果，然后它只需将 x 乘以返回的值。对 n=4 的调用将涉及 4 次递归；这 4 个调用存储在堆栈上并形成一个先进后出的队列。因此，第一个完成的方法调用是当 n=0 时。最终结果随着对方法的每次调用完成而逐步建立。正是这种逐步方法往往会导致问题，因此在父方法和任何子递归调用之间保持良好的分离度非常重要。在将引用类型用作参数之前创建新的实例优于为每次调用提供相同的对象实例并希望它们在此过程中不会变得过于混乱。
Minimax
Minimax 是一种递归算法，常用于游戏玩法中，以选择玩家可以采取的最佳行动。它通过构建一个移动预判树来实现这一点，在该树中，所有相关移动和后续移动都会在多次游戏中进行探索，然后返回找到的最佳移动。有一种名为 Alpha-beta 剪枝的优化方法，用于阻止探索那些不可能返回比已发现的移动更好结果的移动。这里用作示例的游戏是井字游戏，其棋盘是一个 3x3 的方格矩阵，两名玩家中的一名每移动一步，就会有一个方格被该玩家的标记占据。一名玩家使用 X 作为标记，另一名玩家使用 O。获胜者是第一个将他们的 3 个标记放在一行、一列或对角线中的玩家。如果两名玩家都以最佳方式玩，结果总是平局。这是一个图表，显示了算法在构建和遍历预判树时所走的路径。此示例中的游戏从只剩下 3 步可玩且轮到 Max (X) 移动时开始。评分系统非常简单，Max 获胜得 +1 分，Min（另一个对手）获胜得 -1 分。平局得 0 分。算法所走的路径可以通过从左到右跟随箭头来追踪。
父子关系。
根节点在 Min1 级别有三个子节点，对应于 Max 的每个移动选项。子节点本身是节点的父节点，这些节点探索 Min 可以响应的所有移动。这种父子关系一直持续到出现赢家或没有更多移动可探索为止。
Minimax 使用的变量。
在每次递归调用中，两个变量 alpha 和 beta 从父节点传递到子节点。Alpha 记录 Max 在搜索中找到的最佳分数，beta 为 Min 做同样的事情。只有 Max 可以更新 alpha，只有 Min 可以更新 beta。分数作为从 Minimax 调用返回的值从子节点传递到父节点。Max 节点总是返回找到的最高分数，Min 节点总是返回最小分数，换句话说，两名玩家都做出他们最好的移动，并且禁止使用弃子策略。数据在父节点和子节点之间传递和更新的方式是理解算法如何工作的关键。
评估第一个子节点。
根节点的第一个子节点探索 Max 在零基索引 1 处放置 X 的所有可能移动。它的 2 个子节点依次考虑在索引 7 和索引 8 处放置 O 的选项。在 Min2 级别，递归结束并向其父节点返回 0 分。其在 Max2 处的父节点没有进一步的子节点，因此该递归调用结束并向其在 Min1 处的父节点返回 0。Min1 处的节点看到的最佳分数现在是 0，并且 beta 被更新为该值，此前该值是正无穷大的默认值。对于 Min 来说，分数越低越好。该节点记录其子节点返回的最低分数，因为这是该方法调用完成时该节点返回的值。它还会检查其父节点（根节点）是否已经返回了一个更好的分数。根节点看到的最佳分数是 alpha 值，它尚未从负无穷大的默认值更新，因此 Max 没有更好的选择，值得探索第二个子节点，看看它是否为 Min 节点返回一个更好（更低）的值。实际上它返回一个更高的分数 (+1)，因此 Min 节点将其最佳分数 (0) 返回给根节点，该节点将其 alpha 值更新为 0。这里有一些效率上的节省，因为树是同时构建和评估的。
Alpha Beta 剪枝。
Alpha Beta 剪枝发生在根节点的第二个和第三个子节点上。由于第一个子节点返回 0，根节点的 alpha 设置已更新为零。根节点的第二个和第三个子节点都从它们自己的第一个子节点接收到 -1。这会将 beta 更新为 -1，此前它被设置为正无穷大。Beta 现在小于 alpha。根节点已经找到了一个零选项，继续探索这两个节点可以为 Max 返回的最佳结果是 -1。如果找到一个更低的值，它们会返回一个更低的值，因为 Min 节点总是返回它们的最低值。因此，递归结束并将 -1 返回给根节点。这两个路径被剪枝，因为 Max 永远不会沿着它们走下去。请注意，根节点的 beta 值不会更新，因为它没有父 Min 节点。只有 Min 节点才能更改 beta 并将其传递给其子节点。
Minimax 算法。
下面显示的代码可以重构，但希望以目前的形式相对容易理解。IEnumerable<int> 用作表示棋盘的参数，而不是数组，这样如果需要进行更改，就需要创建一个新的数组实例，并且减少了多个方法迭代在同一数组实例上工作的机会。x=1 O=-1 和 Space=0 的数值用于代替字符符号，因为 Minimax 更关注计算值而不是显示它们。例如，匹配的行总值为 +3 或 -3。depth 参数用于限制移动搜索的深度，以给对手更好的获胜机会。
public int Minimax(IEnumerable<int> board,
int depth,
int alpha,
int beta,
bool isMaxingPlayer)
{
//check if previous move produced a winner
if (lineService.CheckForAWin(board, !isMaxingPlayer))
{
int eval = isMaxingPlayer ? -1 : 1;
return eval;
}
if (depth == 0)
{
return 0;
}
//An alternative that removes the need for the depth param
//if (board.Contains(0) is false)
//{
// return 0;
//}
if (isMaxingPlayer)
{
int maxScore = int.MinValue;
//explore the child boards recusively
foreach (var childBoard in lineService.GetChildBoards(board, isMaxingPlayer))
{
//Max calls Min
int score = Minimax(childBoard, depth - 1, alpha, beta, false);
if (score > maxScore)
{
maxScore = score;
}
// update the alpha score if necessary
alpha = score > alpha ? score : alpha;
//check if Min has already found a better node than this to visit
if (beta <= alpha)
{
//this Max node score is higher than another child's node score
//that Min has found consequently Min is not going to choose this path
//so prune it
break;
}
}
return maxScore;
}
//Minimising
int minScore = int.MaxValue;
foreach (var childBoard in lineService.GetChildBoards(board, isMaxingPlayer))
{
//Min calls Max
int score = Minimax(childBoard, depth - 1, alpha, beta, true);
if (score < minScore)
{
minScore = score;
}
beta = score < beta ? score : beta;
if (beta <= alpha)
{
//this Min node's score is lower than another child's node
//so Max is not going to choose this path so prune it
break;
}
}
return minScore;
}
单元测试 Minimax
在测试算法时，有一个陷阱，一个意想不到的预期值。该算法是无敌的，但它并不总是能找到最快的获胜方法。在以下 Min 输掉游戏的情况下，它会选择索引 4 处的方格，而不是索引 6 处的快速获胜。这是因为第一个子 Min 节点的评估在索引 4 处有一个 X，并且它为 Max 返回了最佳可能 (+1) 分数，因为 Min 的所有可用选项都导致 Max 获胜。因此，返回索引 4，因为 Minimax 输出找到的第一个最佳选项。
示例应用程序
示例应用程序非常简单。它输出结果，一个缓慢的平局，其中 Minimax 为双方都下，然后是一个快速获胜，当 Minimax 扮演 X 对抗随机 O 时。还有一个异步示例，其中在 Minimax 玩 500 场随机 0 游戏时报告进度。剧透警告！O 从未获胜，并且平局次数少于 5 次。
public async Task<(int xCount, int oCount)> LookForAWinner(int gamesToPlay)
{
//Progress expects a method that takes a string and returns void
var progressHandler = new Progress<string>(Console.WriteLine);
int totalGames = gamesToPlay;
int winnerCountX = 0;
int winnerCountO = 0;
for (int g = 1; g <= totalGames; g++)
{
int[] board = new int[9];
bool isMaxingPlayer = true;
for (int i = 0; i < 9; i++)
{
int moveIndex = isMaxingPlayer ? await GetBestMove(board, 0, isMaxingPlayer)
: lineService.GetRandomMove(board);
int symbol = isMaxingPlayer ? 1 : -1;
board[moveIndex] = symbol;
if (lineService.CheckForAWin(board, isMaxingPlayer))
{
winnerCountX = isMaxingPlayer ? winnerCountX + 1 : winnerCountX;
winnerCountO = isMaxingPlayer ? winnerCountO : winnerCountO + 1;
break;
}
//next turn
isMaxingPlayer = !isMaxingPlayer;
}
if (g % 50 == 0 && progressHandler is IProgress<string> progress)
{
string report=$"Games played {g} Winners found Player X= {winnerCountX} Player O = {winnerCountO}"
progress.Report(report);
}
}
return (winnerCountX, winnerCountO);
}
结论。
Minimax 算法在实现游戏策略方面非常有用，但在使用变量和递归调用的数量时需要谨慎，以避免出现虚假结果和可怕的堆栈溢出异常。