1. 简介
五子棋（Gomoku），又称连五棋，是一种两人轮流下棋的游戏，目标是将五枚棋子连成一线（横向、纵向或斜向）。谁先达成五子连线，谁就获胜。
为了应对各种棋类游戏，人们开发了多种人工智能策略。近年来，深度学习方法在许多复杂游戏中取得了成功。然而，这类方法通常较为复杂，而经典的AI方法也依然具有研究价值。
在本教程中，我们将介绍一种启发式搜索算法——威胁空间搜索（Threat Space Search, TSS），它最初在这篇论文中提出。我们将展示如何定义“威胁”，并说明如何通过搜索一系列威胁来显著减少原本庞大的搜索空间。
2. Alpha-Beta 搜索
传统的双人对弈游戏常用的方法是 Alpha-Beta 搜索，通常还会结合剪枝策略。否则，搜索空间会大到无法完整探索。
在这种回合制结构中，算法会构建一棵从当前状态出发的博弈树，直到达到指定深度或满足停止条件。一旦达到深度限制，每个局面都会被评估。玩家的目标是最大化自己的得分并最小化对手的得分。这是对 Minimax 算法 和 Alpha-Beta 搜索的高层介绍。
Alpha-Beta 搜索是一种完整的深度优先搜索，其时间复杂度呈指数增长，分支因子巨大。因此，完整搜索整棵树并不可行，我们必须引入一些启发式策略。人类玩家在下五子棋时往往关注威胁序列，所以我们也将这样做。
3. 威胁（Threats）
在五子棋中，某些棋子排列比其他排列更具威胁性。一些威胁必须立即应对，并迫使对手只能在有限的选项中回应。一个胜利策略就是一系列威胁的组合，最终导致对手无法防守。
我们先介绍几种常见的威胁结构，帮助我们建立直觉，理解威胁空间搜索的概念。
以下是几种典型的威胁结构（如图）：
- Four（四）：五个格子中已有四个被攻击方占据，第五个为空
- Straight Four（直四）：六个格子中中间四个被占据，两端为空
- Three（三）：七个格子中中间三个被占据，其余为空；或六个格子中占据中间四个中的任意三个
- Broken Three（断三）：六个格子中占据中间四个中的三个但不连续，其余为空
这些威胁之所以危险，是因为如果出现一个 Four，下一手就能赢；而 Three 如果不及时应对，就会变成 Straight Four，从而立即获胜。我们将在下一节中介绍如何利用这些威胁结构进行威胁空间搜索。
4. 威胁空间搜索（Threat Space Search）
在 TSS 中，我们只关注进攻，忽略防守。如果有多个可能的防守动作，我们将其视为同时发生。一旦发现一个潜在的威胁序列，我们会进一步验证该序列是否能真正导致胜利，即它是否能经受住任何防守动作的考验。
TSS 的设计是为了更贴近人类的下棋方式。人类玩家会快速评估并排除那些无法形成后续威胁的路径。TSS 算法通过识别可能通向胜利的威胁序列并验证其有效性，来模拟这种行为。
4.1 TSS 基本概念
为了构建威胁搜索树，我们需要定义几个关键术语：
- Gain Square（得子点）：攻击方落子的位置
- Cost Squares（代价点）：防守方回应的可能位置列表
- Rest Squares（剩余点）：与得子点一起构成威胁的其他位置
基于这些术语，我们可以定义一些用于构建搜索树的高级概念：
- 威胁 A 依赖于威胁 B，如果 A 的 Rest Square 是 B 的 Gain Square
- 威胁 A 的依赖树是以 A 为根节点，仅包含依赖于 A 的节点构成的树
- 两棵树冲突，如果其中一棵树的 Gain Square 是另一棵树的 Cost Square，或者 Cost Square 相互重叠
这些概念构成了 TSS 的理论基础，帮助我们高效地构建和评估威胁序列。
5. TSS 示例
下面是一个五子棋的局面，展示了多个威胁结构：
运行 TSS 后，我们识别出多个威胁树。我们只关注那些可能通向强制胜利的路径。以下是部分威胁树的结构：
| 深度 | 威胁类型 | 得子点 | 代价点 |
|---|---|---|---|
| 1 | Four | l15 | k15 |
| 1 | Four | k15 | l15 |
| 1 | Four | o12 | o11 |
| 1 | Four | o11 | o12 |
| 1 | Three | j5 | j4, j8, j9 |
| 2 | Four | f15 | i4 |
| 2 | Four | e15 | f15 |
| 3 | Five | e15 |
前四个深度为1的威胁树最终无法形成 Straight Four 或 Five，因此可被排除。我们也能看到一些树之间存在冲突，比如第一行和第二行的得子点互相是对方的代价点。
第三层的树中，有一条路径成功导向了 Five，而另一条路径在第二层就无法继续。这个例子展示了我们如何快速剪枝无效威胁树，并且无需精确模拟对手的每一步回应，从而大幅减少搜索空间。
6. 总结
威胁空间搜索（TSS）是一种启发式搜索方法，旨在将庞大的搜索空间压缩到可管理的规模，同时识别出潜在的胜利路径。
✅ 优点：
- 显著减少搜索空间
- 更贴近人类玩家的思维方式
- 可与其它启发式算法结合使用
❌ 局限：
- 不保证一定能找到胜利路径
- 对复杂局面可能遗漏关键威胁
⚠️ 建议：一个完整的五子棋 AI 应将 TSS 与其他启发式方法结合使用，以提升整体性能。例如可结合 Alpha-Beta 搜索、评估函数、模式识别等技术。
如果你正在开发一个五子棋 AI，TSS 是一个非常值得尝试的启发式策略，它能显著提升搜索效率，尤其在开局和中局阶段。