AI四国大战

本人是一名四国军旗爱好者，虽然水平不高，但是很喜欢下，我决定开发一个AI四国军旗，名字叫AI四国大战。

支持版本：

• Android
• iPad/iPhone
• Qt for PC/MAC

主要特征包括：

• 个性化AI角色
• 分级别AI能力
• 支持触摸操作和行棋，简介的UI
• 支持基本的复盘，布局管理
• Android/iPad 版本支持应用内付费选择更多的个性角色

系统设计

本游戏核心AI算法包括如下部分:

• 表示一个棋局的数据结构，这个结果不仅仅是当前棋子排布，也包括之前行棋和对子的记录，如行动步数，估值概率等等。这个数据结构定义为BoardContext。
• 由一个棋局生成所有合法行棋的算法，MoveGenerator，反复迭代MoveGenerator可以生成一棵博弈树，博弈树称为ChessTree
• 一个优化过的Alpha/Beta树搜索算法，即AlphaBetaSearch();
• 一个根据BoardContext的估值函数，即BoardValue();

因此这个算法由一个核心数据结构BoardContext和MoveGenerator(),AlphaBetaSearch()以及BoardValue()三个核心算法组成。

BoardContext

棋局表示，不同与其他明棋类游戏，军棋必须包含之前的行棋历史信息，这些历史信息包括：

• 棋子的子力评估，如吃过团长的必须必须标记为 大于团，或吃过合作方未知子力的棋子
• 其次棋子的行棋记录，即是否挪动过，是否按照工兵线走过，是否吃过子以及行动步数等
• 失子情况 每个棋局由当前棋子布置信息和以上历史信息构成。首先需要设计好布置信息，由于军棋棋盘是不规则的十字交叉结构，又有轨道线、行营、大本营等属性。 棋盘设计上采用以正中心为(0,0)坐标，极坐标方式，采用最内圈为1，布子第一线为2，类推，编排为 8 x 20 的矩阵，顺时钟方向为正。 每个未知棋子，设计一个猜度函数，输出最接近的棋子估计，在生成博弈树的时候，这个函数生成组合分支概率。

ChessTree

• 全展开 对军棋中碰子需要进行全计算，即考虑各种合理子力，进行子节点生产，对于后期和残局可以考虑采样这样策略。

• 概率展开 为了避免全展开搜索，对军棋中碰字需要进行概率计算，而不是针对各种可能进行全展开，而是只考虑几种情况，对每种情况进行猜测。 当我方棋子与未明确敌方棋子对撞的时候，会有三个不同的结局，三个不同结局首先需要赋予三个权重，但做极大极小值反向推理的时候，三个值需要乘以权重系数。作为一个值进行反向推理。 如下图所示，4,5,6三个子节点属于一组，每个拥有一个不同权值，在向上递归的时候需要将三个值合并计算一个新的值与其他子节点(如1,2,3)进行极大极小，以及Apha/Beta裁剪。

                [_1]
    [1_1]  [1_2]  [1_3]  {[1_4 w] [1_5 w] [1_6 w]}  [1_7] 

为何生成对应的权重，必须设计一个函数，即根据当前棋局和对撞的两个棋子，生成一个三项的概率表，包括(我方胜，对方胜以及一起取走，其中一起取走也细分为遇炸弹，和遇同级子)。 因此最多的情况下会存在四个带权重的组合分支（例如，军长和一个未行动过的子一起取走）。

• 关于工兵的处理

由于工兵的路线不限制，因此展开所有棋局的时候，会造成大量的无效分支，因此必须要提前考虑工兵的路线裁剪。

参考网站