使用Alpha-Beta搜索算法的Connect4
4.00/5 (17投票s)
MiniMax 算法的更新。以相同的结果实现更快的搜索。
引言
这是我们都玩过的传统 Connect4 游戏，目标是连接 4 个同色棋子（水平、垂直或对角线）。
这对于需要学习通用游戏 AI 的程序员非常有帮助，可以将 AI 应用于任何回合制策略游戏，如 Tic Tac Toe 甚至 Chess。
我两年前用 C++ 写了这个游戏。我将所有代码都转换成了 C#，以看看将 C++ 代码转换为 C# 有多容易。
实现
该项目包含 Form1 类，其中包含一个简单的用户界面和绘图函数。Form1.Draw 函数接收窗体的 Graphics 对象，根据保存的棋子值绘制棋盘。
Connect4Board 类是从 C++ 转换过来的，它包含了所有的 AI 代码以及游戏规则和函数。
游戏人工智能
游戏 AI 的代码可能看起来难以理解，因为它最初是用 C++ 编写的。我将尝试简要解释 AI 算法，这样您就不需要阅读代码了。
AlphaBeta 搜索基于 MiniMax 算法。它通过一个递归函数来工作，该函数检查计算机可以进行的 7 种可能走法。并尝试为每种走法打分，然后决定对计算机来说的最佳走法。
首先，我们需要一个函数，根据计算机和玩家的机会来计算棋盘局面的得分。在代码中，此函数称为 'int position()'。
机会是指一个空格（一个孔），其周围有 3 个同色棋子排成一行（水平、垂直或对角线）。如果周围只有 2 个棋子，则得分较低。棋盘局面的得分是计算机得分的总和减去玩家得分的总和。
然后我们需要确定何时检查棋盘的局面。一种可能的方法是在计算机的每一步之后都进行检查，在 Connect4 中，计算机有 7 种可能的走法。因此，我们为棋盘增加一步。计算棋盘的得分。然后移除此棋子。然后，我们继续添加其他走法，直到所有走法都获得得分。这样，计算机就会根据最高得分来决定最佳走法。
这种方法在计算得分的函数非常复杂，能为后续的每一步都打分的情况下会很好。但是，我们无法编写这样的函数。因此，更好的方法是在玩家也放置棋子后计算得分。这需要检查计算机和玩家所有可能的走法。这意味着，对于计算机的 7 种走法中的每一种，玩家都有 7 种走法。这将需要检查 49 种局面得分。然后，我们返回玩家每 7 种走法中的最差局面。然后，我们选择计算机每 7 种走法中的最佳局面。
虽然 MiniMax 算法效果很好，但需要大量的处理。我们对该算法进行了一些小的变动，并称之为 Alpha Beta Search。它基于这样的理念：如果你已经有一个你知道不错的选择，当你查看其他选择时，如果你发现一个和你已知的不错选择一样好甚至更差的，你就无需费力去精确计算它到底有多差。任何不比已知最佳选择好的选择都足够差了，所以你可以直接舍弃它，而无需完全理解它。你可以在证明它不比最佳选择好的那一刻就将其丢弃。
这个想法是在搜索中传递两个分数。第一个是 alpha，这是可以通过某种方式确定的最佳分数。任何低于此分数的值都没有用，因为存在一种策略可以确保得到 alpha 分数。任何等于或低于 alpha 的分数都算不上改进。
第二个分数是 beta。Beta 是对手的最坏情况。这是对手必须忍受的最糟糕的情况，因为已知对手有一种方法可以强制局面不再比 beta 更差（从对手的角度来看）。如果搜索发现返回 beta 或更好分数的局面，那么这个局面太好了，走法一方将没有机会利用这种策略。
在搜索走法时，每一步搜索返回的分数都与 alpha 和 beta 有某种关系，并且这种关系非常重要，它可能意味着搜索可以停止并返回一个值。
如果一个走法导致的分数小于或等于 alpha，那么它只是一个糟糕的走法，可以忽略，因为正如我在前面几段所述，已知存在一种策略可以为走法一方带来 alpha 价值的局面。
如果一个走法导致的分数大于或等于 beta，那么整个节点都毫无价值，因为对手不会让走法一方达到这个局面，因为对手可以选择一种方式来避免它。所以，如果我们发现一个分数等于 beta 或更高，那么可以证明整个节点都不会发生，因此不需要搜索其余的合法走法。
如果一个走法导致的分数大于 alpha 但小于 beta，那么这就是走法一方计划采取的走法，除非之后情况发生变化。所以 alpha 会增加以反映这个新值。
给算法的深度级别越多，它就能更好地预测未来最佳的走法。因此，我设置了简单模式的递归深度为 3 级（检查计算机回合、玩家下一回合和计算机下一回合），普通模式为 5 级，困难模式为 7 级递归，以做出更好的估计，同时处理时间更长。（不建议在 Pocket PC 模拟器上选择困难模式）。
这个算法可以用于任何回合制策略游戏，如 Chess 等。但游戏越复杂，你就需要一个更复杂的评分函数，并有更多的递归级别。最重要的是在每一层去除一些糟糕的走法以减少处理成本。因为，你不需要看到一个将导致你大量失分的走法的全部未来。
希望您喜欢这个游戏和这个算法。