团队课程项目(2 人)

Gopher & Dodo 六边形棋盘博弈 AI

贡比涅技术大学 · IA02 逻辑编程与问题求解(2024 春)

为 Mark Steere 的两款双人六边形棋 Gopher 与 Dodo 实现自动对弈 AI:轴向坐标棋盘、合法着法生成、机动性评估,以及带记忆化的 Minimax 搜索。

项目背景

这是 UTC IA02「逻辑编程与问题求解」 的期末项目。课程提供了一个裁判服务器 gndserver 和一个 HTTP 客户端 gndclient.py,负责注册、配对、计时、合法性校验和状态同步;我们需要实现的是 AI 主体 jeux.py——棋盘建模、合法着法生成、局面评估和搜索。

对局对象是 Mark Steere 设计的两款双人六边形棋:Gopher 与 Dodo。两者规则都不复杂,但“六边形邻接”和“无子可动即胜”这类反直觉规则,让合法着法和终局判断比普通棋类更容易写错。

游戏规则

Gopher

  • 棋盘初始全空,红方先手,第一子可以下在任意空格;
  • 此后每步必须与恰好一枚敌子相邻,且与零枚己子相邻;
  • 双方都不能跳过回合;
  • 最后成功落子的一方获胜。

尺寸为 n 的六边形棋盘有 3n(n-1)+1 个格子:n=4 是 37 格,n=6 是 91 格。

Dodo

  • 开局按服务器配置摆放棋子(corners 或 one_line);
  • 每步把己方一枚棋子向正前方或斜前方移动一格,目标格必须为空;
  • 轮到你行动时如果没有合法着法,你获胜——与大多数棋类“无子可动即输”相反。

实现

  • 棋盘:用轴向坐标 (x, y) 表示六边形网格,initialize_board 生成 n=4/6 的格子,并按规则摆放 Dodo 的初始棋子。
  • 合法着法 legals:Gopher 遍历敌子邻格,保留“恰好一个敌邻、零个己邻”的空格;Dodo 按颜色取三个前进方向,目标格在界内且为空。
  • 状态转移 apply_action:Gopher 直接把目标格设为当前玩家;Dodo 则清空起点、占用终点。
  • 评估 evaluation:当前版本用机动性启发式,-len(legals(...)),己方可选着法越少分越低。
  • 搜索:minmax + memoize,以完整棋盘、深度、当前最大化方、根玩家、棋盘尺寸和游戏名作为缓存 key;根节点枚举着法,每个着法向下搜索 4 层,共 5 个半回合。
  • 对局外壳:每回合打印 ASCII 棋盘;根据服务器返回的游戏名自动分派 Gopher / Dodo 策略;课程提供的 gndclient.py 未修改。

结果与局限

本地用 gndserver.exe -game gopher -random 启动服务器,再运行 test_client.py,可以完整下完一局并正确输出 Ending: 1 wins with a score of 1 与 Red wins!。

在本机(Windows 11 / Python 3.14)上的粗略测量:

  • Dodo 4×4 初始局面走一步(depth 4)约 4.5 秒;
  • Gopher 4×4 对随机对手完整一局约 1.7 秒。

已知问题也很明确:

  • 没有时间管理,固定搜索 depth 4,6×6 局面可能超时;
  • 评估函数只看机动性,且没有把“终局”纳入判断;
  • legals 多次线性扫描 state,实际复杂度接近 O(n⁴);
  • Gopher 空棋盘时固定下 (0,0),没有搜索最佳开局;
  • 记忆化缓存无上限,长时间运行会持续占内存;
  • 目前只有手工/脚本验证,缺少自动化测试。

课程存档

仓库的 tp/ 目录同时保存了 IA02 的练习与 TD/TP 讲义:命题逻辑与一阶逻辑、SAT(含数独编码与 Gophersat 样例)、Prolog(亲属关系推理、Mastermind)、ASP(Clingo)以及 Minimax 井字棋。它们和 Gopher & Dodo 项目相互独立,作为完整的学习存档。

源码与规则文档:https://github.com/yicongl1/Gopher-and-Dodo

技术文章

01 六边形棋盘的坐标、邻居与合法着法 轴向坐标、六个邻居、棋盘边界,以及 Gopher 与 Dodo 两条不同的合法着法规则。 02 带记忆化的 Minimax:缓存键、深度与评估函数 缓存键为什么包含深度、机动性评估的两个问题,以及这版为什么没用 alpha-beta。

相关技能

  • C++
  • Git