‹ 全部项目

搜索与博弈

Hinger 棋类博弈 AI:搜索、精确求解与对弈智能体

用图算法、可证明的启发函数与精确求解来研究 Hinger 棋局。

时间
2025.10 – 2026.11
技术栈
  • Python
  • pytest
  • GitHub Actions
01 / 04制胜判定
  1. 01 · 制胜判定

    把制胜位置归约为割点。

    将制胜位置判定归约为棋盘图的割点问题,基于 Tarjan 算法实现线性时间检测。

  2. 02 · 搜索

    推导并证明启发函数。

    推导并证明可采纳且一致的 A* 启发函数。

  3. 03 · 精确求解

    5×5 完整棋盘,精确求解。

    基于记忆化 negamax 与对称性约简,精确求解 5×5 完整棋盘。

  4. 04 · 对弈智能体

    以精确解为基准。

    实现 minimax、alpha-beta 与蒙特卡洛树搜索对弈智能体,并以精确解为基准评估各算法的走法质量。

关键结果

5×5

基于记忆化 negamax 与对称性约简,精确求解完整棋盘。