目前，我正在研究一个使用minimax + alpha-beta pruning的 Gomoku AI 实现。
在搜索时间和搜索深度方面，我从“可接受的实施”中针对这两个规则：
- 搜索时间（超过 0.5 秒是“坏”，少于 0.5 秒是可以的）
- 搜索深度（小于 10 个搜索深度级别是“不好的” ，超过 10 个搜索深度级别是可以的）
minimax 算法通过递归函数调用生成节点树，每个节点由具有特定游戏状态的函数调用表示。
增加深度搜索会增加树中节点的数量，从而增加搜索时间。
搜索时间和搜索深度之间存在折衷。
Alpha-beta 修剪倾向于通过修剪无用的节点搜索和减小树的大小来帮助这种妥协。修剪与评估/启发式函数直接相关。启发式的错误实现可能会导致 alpha-beta 修剪效率低下。
如果您正在开发或已经完成 Gomoku AI，在某些游戏步骤中分享您在实现中的树大小、搜索深度和时间搜索的统计数据，并解释您如何达到它可能有助于调查。
此时的实现不适合我的“不可接受”，在第一步搜索深度为 4 的搜索时间超过 1 秒......在 IntelCore i7 3.60GHz CPU 上......
以下是实际实现的属性：
- 板尺寸 19x19
- 在石头周围实现大小为 5x5 的搜索窗口以减少搜索节点
- 在棋子上的每个节点上实施启发式计算，而不是在叶节点数上计算所有棋盘大小。
- 实现 alpha-beta 修剪
- 没有多线程
以下是它在第一步中搜索深度为 4时达到的当前统计数据：
- 时序极小极大算法：1.706175 秒
- 构成树的节点数：2850
. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
o x . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x
糟糕的统计数据可能会导致错误的启发式方法，从而导致修剪效率低下。等待其他统计数据/回复来验证这一假设可能会有所帮助。
编辑 1
从关于这个问题的新搜索活动中回来。
该实现在每次启发式计算中都面临 19*19 循环索引......通过在特定索引（不是整个板）的启发式计算删除了这个
该实现面临一个 19*19 循环索引来检查获胜状态......通过仅检查播放索引周围的每个步骤的任何对齐来删除它。
该实现面临一个 19*19 循环索引，以检查它可以在哪里播放（即使在窗口中）......通过在每个步骤更新的递归传播有效索引的索引数组来删除。该数组是一个二分数组（与插入，搜索和按索引删除）
该实现缺少 Zobrist 哈希表，这是来自以下答案的一个非常好的主意。它现在通过单元测试来实现，以证明实现是有效的。在每个新节点处更新按哈希排序的数组，并具有哈希节点关联。该数组是一个二分数组（与插入，搜索和按索引删除）
实现是在每一步以随机方式尝试每个索引（不是计算顺序或评估分数顺序）。
编辑前的例子不是很好，因为它是在餐具柜上播放的，并且允许的索引窗口是最大尺寸的一半。
以下是新获得的表演：
关闭Zobrist 表并在 42 处播种，第一步搜索深度为 4
- 时序极小极大算法：0.083288 秒
- 组成树的节点数：6078
. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . x . . . . . . . . . 11
. . . . . . . . o . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x
使用 Zobrist 表，种子为 42，第一步搜索深度为 4
- 计时 minmax_algorithm：0.434098 秒
- 组成树的节点数：9320
. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . x . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . 11
. . . . . . . . o . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x
实际上，搜索深度 4 是可以的，但不能超过 6。节点数正在变成指数级（超过 20 000）......
在这里发现使用相同语言/技术的出色实现，可以在不到 1 秒的时间内达到 10 深度，无需 Zobrist 或智能技巧，并遵循逻辑。
问题一定出在其他地方，导致节点呈指数增长 - 修剪效率低下。