团队课程项目(2 人)
贡比涅技术大学 · 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 个半回合。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)上的粗略测量:
已知问题也很明确:
legals 多次线性扫描 state,实际复杂度接近 O(n⁴);(0,0),没有搜索最佳开局;仓库的 tp/ 目录同时保存了 IA02 的练习与 TD/TP 讲义:命题逻辑与一阶逻辑、SAT(含数独编码与 Gophersat 样例)、Prolog(亲属关系推理、Mastermind)、ASP(Clingo)以及 Minimax 井字棋。它们和 Gopher & Dodo 项目相互独立,作为完整的学习存档。