本项目是炸飞机（又称飞机大战）游戏的AI。
https://mathmonkeyliu.github.io/zfj/
可以参考https://mp.weixin.qq.com/s/ni7TqwWlA7PldDzgUsAL8w
简单来说，游戏棋盘是一个 10x10 的方格表，其上放置着 3 架飞机，每一架飞机的形状都一样，为“士”字行。每个飞机占据10个格子，有1个格子是机头（红色），9个格子是机身。飞机可以朝上、下、左、右四个方向放置，但是不能重叠。比如下面是一个符合规则的布局：
游戏分为两个阶段，布局阶段和攻击阶段
- 布局阶段：将自己的三架飞机按符合要求的方式布局。
- 攻击阶段：双方布局完成后进入攻击阶段，攻击阶段双方点击对方的棋盘中的格子，并可以得到这个格子所属飞机的部分的反馈，包括不属于飞机、属于飞机的机身、属于飞机的机头。
获胜条件：先击中对方三个机头的人获得胜利。
游戏没有先后手之分，同一回合先下手为强。
可以在https://game.hullqin.cn/zfj游玩。
项目依赖位于 requirements.txt 文件中。
如果使用 uv，则直接运行以下命令即可：
uv sync在这个游戏中，我们假设布局的先验概率是均匀分布。
首先，你要先运行python layout_generater.py生成所有可能的布局。
经典的决策树信息熵增益的算法。可以枚举出有66816种布局方式和33344种机头的排列。每一步，我们遍历所有没有点击的格子（也就是未知状态的格子），计算点击他们之后的信息增益。然后选择信息增益最大的那个格子（这里注意，如果信息增益相同，选择这个格子正好击中机头概率最大的格子）。
算法实现在id3.py里。
可以使用evaluate.py遍历所有布局，计算步数进行评估。
python evaluate.py --method id3 --out evaluation_id3.png评估结果如下：
在所有布局情况下，id3算法的平均数步数为12.851，中位数步数为13.000。
由于id3选出的动作未必是最优的，所以我们每一步选取id3信息增益最高的topk个格子（旋转对称的格子会被排除在外），搜索使得全局平均步数最低的那个策略。
当然，当topk=1时，就退化为id3算法。
算法实现在min_avg.py里。
可以通过以下命令计算并保存策略：
python min_avg.py --out topk_1.json --topk 1评估可使用
python evaluate.py --method min_avg --checkpoint topk_1.json --out evaluation_min_avg_topk_1.png这样的搜索计算量是十分大的，复杂度大概为$O((3\times\text{topk})^{depth})$，其中$depth$为搜索树的深度，也就是所花的步数。
于是，我实现了一个CPU并行计算的脚本min_avg_cpu.py，会自动读取你的CPU核心数并进行并行计算。
python min_avg_cpu.py --out topk_2.json --topk 2以上topk=2的命令在一个64核心的Intel(R) Xeon(R) Gold 6326 CPU @ 2.90GHz上大概需要八个小时。
使用
min_avg_cpu的时候需要注意！如果你对你的内存不是非常有自信，请调低config.py中的MAX_EXPAND_NODES。比如我运行的时候服务器就死机了，这时候由于有temp_policies文件夹，可以从断点继续算。当然，如果你不想继续死机的话，建议把之前计算的策略删除，并且提高MAX_EXPAND_NODES，或者运行dealing_tricky_nodes.pydivide and conquer那些计算量极大的节点。
topk=2的实验结果如下：
在所有布局随机选取的先验下，topk=2的平均数步数达到了12.657，中位数步数为13.000。
这个是我之前做过的尝试，感兴趣的可以翻一翻之前的commit。方法同样是使用id3选出topk个动作，但这一次是只搜索最坏情况下的最大步数，因此可以使用alpha-beta剪枝，在topk=3的配置下计算到的最坏步数是19步。这意味着无论是什么样的游戏策略，在最坏的情况下，都至少需要19步。
19，又让你想起了什么呢？你想起的是一个年份，一个年纪，一个班级，还是一个学号呢？算了，我不想再猜了，就像她不想去猜你的内心一样。
欢迎读者设计其它方法超越我的性能。可以通过mathmonkeyliu@mail.ustc.edu.cn联系我。
刘泽睿，来自中国科学技术大学(USTC)