最快的 Connect 4 获胜检查方法
fastest Connect 4 win checking method
我正在尝试按照井字游戏的 alpha-beta pruning 方法制作 ai。我需要尽快检查胜利，因为人工智能会经历许多不同的可能游戏状态。目前我想到了2种方法，都不是很有效。
- 创建一个大元组，用于对连续 4 个可能的获胜条件进行评分，并循环遍历它。
- 使用for循环，水平检查，垂直检查，向左诊断，向右诊断。这似乎
#1. 会慢得多
有人建议怎么做？
从你的问题来看，你的方法将如何实施有点不清楚。但是从 alpha-beta 剪枝来看，好像你想看很多不同的游戏状态，并在递归中为每个状态确定一个 "score"。
一个非常重要的观察结果是，一旦找到 4 行，递归就会结束。这意味着在递归步骤开始时，游戏板没有任何 4-in-a-row 实例。
由此，我们可以直观地看出，在所述递归步骤中放置的新块必须是在递归步骤中创建的任何 4-in-a-row 实例的一部分。这大大减少了对解决方案的搜索 space，从总共 69 个（21 个垂直、24 个水平、12+12 个对角线）4 行位置减少到最多 13 个（3 个垂直、4 个水平、3 个+3 对角线）。
这应该是您第二种方法的基准。对于一个简单的实现，它最多需要 52 (13*4) 次检查，或者对于更快的算法需要 25 (6+7+6+6) 次检查。
我想说，现在很难通过 25 次布尔检查来完成这个获胜检查，但我猜你的 #1 方法会使用一些额外的内存使用量来减少每个递归步骤的计算量。最简单的方法是存储 8 个整数（单字节适合此应用程序），它们代表可以在 8 个方向中的任何一个方向上找到的最长的同色筹码链。
使用它，一次胜利检查可以减少到 8 次布尔检查和 4 次加法。只需获取新放置的筹码相对两侧的链长，检查它们是否与筹码颜色相同，如果是，则将它们的长度相加并加 1（对于新放置的筹码）。
从这个计算来看，您的 #1 方法似乎是最有效的。但是，它有更大的维护数据结构的开销，并且使用更多的内存，除非可以通过引用传递，否则应该避免这种情况。此外（假设布尔检查和加法的速度相似）即使忽略开销，更难的方法也只能以 2 倍的优势获胜。
我做了一些简化，有些解释可能crystal不清楚，如果您还有其他问题，请询问。
我正在尝试按照井字游戏的 alpha-beta pruning 方法制作 ai。我需要尽快检查胜利，因为人工智能会经历许多不同的可能游戏状态。目前我想到了2种方法，都不是很有效。
- 创建一个大元组，用于对连续 4 个可能的获胜条件进行评分，并循环遍历它。
- 使用for循环，水平检查，垂直检查，向左诊断，向右诊断。这似乎
#1. 会慢得多
有人建议怎么做？
从你的问题来看，你的方法将如何实施有点不清楚。但是从 alpha-beta 剪枝来看，好像你想看很多不同的游戏状态，并在递归中为每个状态确定一个 "score"。
一个非常重要的观察结果是，一旦找到 4 行，递归就会结束。这意味着在递归步骤开始时，游戏板没有任何 4-in-a-row 实例。
由此，我们可以直观地看出，在所述递归步骤中放置的新块必须是在递归步骤中创建的任何 4-in-a-row 实例的一部分。这大大减少了对解决方案的搜索 space，从总共 69 个（21 个垂直、24 个水平、12+12 个对角线）4 行位置减少到最多 13 个（3 个垂直、4 个水平、3 个+3 对角线）。
这应该是您第二种方法的基准。对于一个简单的实现，它最多需要 52 (13*4) 次检查，或者对于更快的算法需要 25 (6+7+6+6) 次检查。
我想说，现在很难通过 25 次布尔检查来完成这个获胜检查，但我猜你的 #1 方法会使用一些额外的内存使用量来减少每个递归步骤的计算量。最简单的方法是存储 8 个整数（单字节适合此应用程序），它们代表可以在 8 个方向中的任何一个方向上找到的最长的同色筹码链。
使用它，一次胜利检查可以减少到 8 次布尔检查和 4 次加法。只需获取新放置的筹码相对两侧的链长，检查它们是否与筹码颜色相同，如果是，则将它们的长度相加并加 1（对于新放置的筹码）。
从这个计算来看，您的 #1 方法似乎是最有效的。但是，它有更大的维护数据结构的开销，并且使用更多的内存，除非可以通过引用传递，否则应该避免这种情况。此外（假设布尔检查和加法的速度相似）即使忽略开销，更难的方法也只能以 2 倍的优势获胜。
我做了一些简化，有些解释可能crystal不清楚，如果您还有其他问题，请询问。