蒙特卡洛算法丈量亚马逊棋博弈边界

关于 MCTS 架构的亚马逊棋博弈程序的探索与实现
Bot Name: ZZmazon
日期： 2026 年 1 月 9 日

小注

本文是 pku 大一计概a大作业 Amazons项目中的我的设计框架，具体详见开源仓库

由于深度学习门槛过高遂采用介于纯α-β剪枝和纯MCTS模拟之间的 MCTS+UCT 算法框架，以下是学期小论文~~（十分官话）~~

1. 引言

亚马逊棋（Game of the Amazons）规则简洁但策略极深。本项目开发了两个版本：

• 逻辑层（竞技型）： 在 Botzone 平台有限算力下目前已达到前 8% 的水平。
• 界面层（体验型）： 拥有舒适的 UI 界面，支持双人对决、调试 Bot 及观察局势评估。

项目计划于本月底开源至 Github：The-Bot-of-Amazons。

2. 基于 MinMax 思想架构的 MCTS 决策模型

针对亚马逊棋单步约 2100 个分支因子的计算压力，程序采用以 MCTS 为核心、以 UCT 算法为决策准则的架构。

2.1 决策准则：基于 UCT 的数学平衡

引入 UCT 算法兼顾历史胜率（利用）与强制探索（探索）：

$$UCT(v_i) = \underbrace{\frac{Q(v_i)}{N(v_i)}}_{\text{Exploitation}} + C \cdot \underbrace{\sqrt{\frac{\ln N(p)}{N(v_i)}}}_{\text{Exploration}}$$

2.2 算法执行：MCTS 四阶段迭代逻辑

1. 选择 (Selection)：从根节点出发，依据 UCT 原则递归向下。
2. 扩展 (Expansion)：若非终止状态，则生成新子节点。
3. 模拟 (Simulation)：执行快速随机走子（Rollout）。海量的模拟试错是成功的关键，而非仅依赖人类模糊的经验。
4. 回溯 (Backpropagation)：模拟结果沿路径逆向、以极大极小方式更新 $Q$ 值与 $N$ 值。
   • 极大极小公式：$val = iscurrent ? val : 1 - val$。

3. 剪枝——搜索优化

通过下表所示的策略提升有限时间内的搜索效率：

维度	核心机制	优化目的与逻辑
高频扩展	Progressive Expansion	动态调整阈值 $T_{expand} \in [4, 20]$，确保仅高频验证路径继续搜索。
预测取优	Heuristic Pre-selection	引入评估函数 $f(s)$ 预扫描，仅保留高分动作。
随机采样	Stochastic Sampling	对深层节点进行 $n=200$ 子集采样，确保搜索覆盖度。
时间控制	Time-Aware	随剩余时间减少，单调锐减搜索宽度，聚焦核心。
深度渗透	Visit-Induced	随访问量增加压缩宽度至 4，强化深层探索。

4. 评估函数哲学

将态势抽象为多维特征向量，通过 Sigmoid 映射估计胜率：

• 双重距离场测度：利用 BFS 构建 Queen-Distance 与 King-Distance 场。
• 多维特征提取：整合领地占领、位置势能及 Super-Mobility 修正项。
• 自适应扰动 (Jitter)：引入随机因子 $[0.99, 1.01]$，规避启发式陷阱。
• 非线性概率映射：$P(win)=\sigma(V\cdot \alpha)=\frac{1}{1+e^{-V(s)\cdot 0.2}}$
• 参数优化：采用经过强化学习的 28 阶段参数。

5. UI 交互体验与存档

• 复盘与悔棋：基于 undoStack 支持任意跳转与悔棋。
• 增量式存档：利用 fstream 记录动作流，实现 100% 还原。
• 局势热力图：提供基于 Queen/King 距离的实时局势度量视图。
• 趣味交互：包含幽默超时提醒与逻辑纠错。

6. 战绩与展望

ZZmazon Bot 在 Botzone 平台表现优异，截止 2026 年 1 月 9 日排名位列 Top 8%（约 1616 分）。

未来路径：

1. 位棋盘 (Bitboard)
2. 哈希置换表
3. 神经网络估值

7. 结语

从零开始构建逻辑的纯粹感令人着迷。虽然算力有限，但通过策略剪枝和自研评估函数实现了“以弱胜强”，甚至开发者本人已近一个月无法战胜自己的 Bot。

在兴趣的彼岸划开实践的双桨，在算法的边界上写下自己的逻辑！

---

参考文献

• [1] J. Lieberum. An evaluation function for the game of Amazons. Theoretical Computer Science, 2005.
• [2] R. J. Lorentz. Amazons Discover Monte-Carlo. CG 2008, LNCS 5131.
• [3] J. Kloetzer, et al. The Monte-Carlo Approach in Amazons. Proceedings of the Computer Games Workshop, 2007.