目前的军棋博弈程序大多是采用基于人类经验的局面评估模型，这种模型存在不确定性高、主观因素大、调整参数困难等多方面问题。我们研究了一种针对不完全局面的三层决策模型，该模型基于规则进行暗棋推理和局面特征提取，联合神经网络局面评估模型进行博弈树搜索，通过棋谱和自我对弈方式来训练。
待完善
博弈树中节点估值由局面评估算法决定。因此正确提取局面特征是搜索算法能正常工作的基础。根据不同种类的棋类游戏规则的不同，对于军棋的局面特征提取，我们参考了文献[6]的方案并对其进行了改进。提取下列几种特征：
军棋中从排长到司令的8种类型棋子的价值按照棋子的大小关系从小到大递增。
- 在军棋棋盘中有5种类型的棋位，每种不同的棋位上棋子的移动能力不同。移动能力越强则在该位置增加的价值越多。在公路上与在铁路上棋子的移动能力有所不同，在公路上棋子每次只能移动1格，而铁路线上的棋子可以移动到铁路线上其他任意位置上。所以铁路线上的棋子增加的价值就更多。
- 行营中的棋子不可以被攻击，而且敌方行营距离敌方大本营更近，所以敌方行营的价值更高一些。
相邻棋子之间存在相互影响，并且这些影响分为积极影响和消极影响。若某一棋子相邻己方棋子如果比该棋子更大，那么对该棋子有保护作用，产生积极的影响，会增加该棋子的价值。相邻地方棋子如果通过概率推断得出其比我方棋子大，则相邻敌方棋子会产生负面作用，减小该棋子的价值。对相邻的棋子，我们考虑两个因素影响棋子的价值，它们是：
- 该棋子附近本方棋子中大于该棋子价值的棋子的价值大小
- 该棋子附近敌方棋子中最大的价值大小
对于军旗的保护，我们考虑后三排，包括6个公路线上的棋位，7个铁路线上的棋位、两个大本营和两个行营。其中对两个行营，特别是对军旗附近的那个行营控制十分重要，该营可控制附近8个位置的棋位，其中一个棋位到军旗只有一步，二个棋位到军棋只有两步，一旦让对手控制该棋位后，对方可防可守。本方只有调集大量的兵力回防，使用于攻击的兵力下降。
基于上述原因，我们规定后三排军旗保护的原则为：
- 计算该位置到军旗的最少步数，靠军旗所在的棋位越近，棋子价值增加15/最少步数。
- 若我方棋子临近敌方军旗，则此时的最佳策略是直接吃掉敌方的军旗。基于这种原则，吃掉军棋的奖励值应该是无穷大，所以这里设定吃掉对方军棋的策略会对整个局面的评分增加1000，以鼓励我方棋子吃掉敌方军旗。
- 本模块参见git仓库Chess AI
极大极小搜索先将博弈树展开到指定层数l，从展开的第一层到第l层，奇数层为我方行动，偶数层为对手行动。对l层的各个局面节点使用局面评估函数进行估值。这样可以在l-1层节点n的子节点中选择最大/最小的节点评分作为的节点n评分（如果局面估值大表示利于我方，那么我方行动的层选择最大值，对手行动的层选择最小值），这样可以获得层所有节点评分，再对层递归实行此过程，直至获得第一层所有局面的评分，选择评分最大的节点即为最优决策。
如果局面评估函数完全准确，那么直接对第一层使用局面评估函数进行估值就可以得到最优结果。但由于局面评估函数总存在偏差，一般来讲，距离终局越近局面评估越准确，因此要尽可能搜索更多层。
极大极小搜索需要对博弈树进行层的充分展开，尽管可以使用Alpha-Beta剪枝减小搜索空间，但对于状态空间较大的游戏，这种详细的搜索在计算上并不可行。因此使用神经估值网络进行改进。
- 本模块参见git仓库DL Chess AI
输入数据包括：
- 目前棋盘
- 概率矩阵的每一行对应棋盘坐标
- 目前回合数
- 我方棋子数
- 对手棋子数
- 局面特征
为了更好的对概率矩阵和棋盘提取特征，首先将棋盘与概率矩阵拼接为21×21的矩阵，空余位置使用零填充。其后的网络结构参照了棋盘大小相近的小型五子棋神经网络模型AlphaGomoku[10]，该模型为AlphaZero[11]一个小型化有效实现。我们最终设计的结构可参见value_net.py。
模型对于棋盘和概率矩阵两个二维张量采取使用卷积层先扩大、后缩小的方法，得到一个较小的特征图，将其Flatten后与其它一维特征共同参与全连接层运算。该做法使得这两个输入并不会在最后的全连接层运算中占据过多“席位”，强调了其对基于规则提取的特征的辅助作用。最终，通过Sigmoid层得到结果，作为对输入局面胜率的估计。
未训练过的模型与全国机器博弈大赛中其它所有AI程序均对局一次，每次对局都会自动保存棋谱并标注胜负。所有对局结束后，统计整体胜率，将棋谱拆分为局面，按所属的对局胜负对所有局面进行标注（标签为胜负两类）。这样就得到了可用于训练的数据。使用训练得到的新模型继续与其它AI程序进行对局，每次获得新数据后，将新数据加入原先数据中进行训练，这样做是为了避免特殊对局造成模型效果反复。每次训练都基于历史胜率最高的模型进行[12]，当胜率到达一个阈值后，开始进行随机自对局混合训练，即每次对局随机选择对手（其它AI程序或历史模型）。使用这种增量训练可以增强模型对不同类型对手的应对能力，使其能够全方位成长。
待完善
- zmk负责了整个算法的设计与大部分模块的实现，编写了棋谱复盘工具。也负责了训练工作
- 艾德润负责了蒙特卡洛搜索模块的实现（当前未使用）、编写了对局工具。也负责了训练工作
- 马一民负责了训练数据格式转换模块的实现。也负责了训练工作。
- 论文An Evolutionary Game Tree Search Algorithm of Military Chess Game Based on Neural Value Network发表于2020年的中国控制与决策会议(CCDC2020)
- [6] 张红明. 四国军棋人机博弈系统及有约束推理的研究和实现[D].南京航空航天大学,2010.
- [10] Xie, Zheng, Fu, XingYu, Yu, JinYuan. AlphaGomoku: An AlphaGo-based Gomoku Artificial Intelligence using Curriculum Learning[J].
- [11] Silver D , Hubert T , Schrittwieser J , et al. Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm[J]. 2017.
- [12] Zhu F , Guan S . Ordered incremental training with genetic algorithms[J]. International Journal of Intelligent Systems, 2010, 19(12):1239-1256.
