‹ 全部项目
搜索与博弈
Hinger 棋类博弈 AI:搜索、精确求解与对弈智能体
用图算法、可证明的启发函数与精确求解来研究 Hinger 棋局。
- 时间
- 2025.10 – 2026.11
- 技术栈
- Python
- pytest
- GitHub Actions
01 / 04制胜判定
01 · 制胜判定
把制胜位置归约为割点。
将制胜位置判定归约为棋盘图的割点问题,基于 Tarjan 算法实现线性时间检测。
02 · 搜索
推导并证明启发函数。
推导并证明可采纳且一致的 A* 启发函数。
03 · 精确求解
5×5 完整棋盘,精确求解。
基于记忆化 negamax 与对称性约简,精确求解 5×5 完整棋盘。
04 · 对弈智能体
以精确解为基准。
实现 minimax、alpha-beta 与蒙特卡洛树搜索对弈智能体,并以精确解为基准评估各算法的走法质量。
关键结果
5×5
基于记忆化 negamax 与对称性约简,精确求解完整棋盘。