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

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

关于 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(vi)=Q(vi)N(vi)⏟Exploitation+C⋅ln⁡N(p)N(vi)⏟ExplorationUCT(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)：模拟结果沿路径逆向、以极大极小方式更新 QQ 值与 NN 值。
    • 极大极小公式：val=iscurrent?val:1−valval = iscurrent ? val : 1 - val。

3. 剪枝——搜索优化

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

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

4. 评估函数哲学

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

  • 双重距离场测度：利用 BFS 构建 Queen-Distance 与 King-Distance 场。
  • 多维特征提取：整合领地占领、位置势能及 Super-Mobility 修正项。
  • 自适应扰动 (Jitter)：引入随机因子 [0.99,1.01][0.99, 1.01]，规避启发式陷阱。
  • 非线性概率映射：P(win)=σ(V⋅α)=11+e−V(s)⋅0.2P(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.