# DL Chess AI **Repository Path**: sg-first/DL-Chess-AI ## Basic Information - **Project Name**: DL Chess AI - **Description**: No description available - **Primary Language**: Python - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2019-07-25 - **Last Updated**: 2021-11-02 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README 基于神经估值网络进行博弈树搜索的军旗AI算法 ============ 摘要 ---------- 目前的军棋博弈程序大多是采用基于人类经验的局面评估模型，这种模型存在不确定性高、主观因素大、调整参数困难等多方面问题。我们研究了一种针对不完全局面的三层决策模型，该模型基于规则进行暗棋推理和局面特征提取，联合神经网络局面评估模型进行博弈树搜索，通过棋谱和自我对弈方式来训练。 暗棋推理 --------- 待完善 局面特征提取 ----------- 博弈树中节点估值由局面评估算法决定。因此正确提取局面特征是搜索算法能正常工作的基础。根据不同种类的棋类游戏规则的不同，对于军棋的局面特征提取，我们参考了文献[6]的方案并对其进行了改进。提取下列几种特征： ### 棋子的固定价值 军棋中从排长到司令的8种类型棋子的价值按照棋子的大小关系从小到大递增。 ### 棋子所在位置的增加价值 * 在军棋棋盘中有5种类型的棋位，每种不同的棋位上棋子的移动能力不同。移动能力越强则在该位置增加的价值越多。在公路上与在铁路上棋子的移动能力有所不同，在公路上棋子每次只能移动1格，而铁路线上的棋子可以移动到铁路线上其他任意位置上。所以铁路线上的棋子增加的价值就更多。 * 行营中的棋子不可以被攻击，而且敌方行营距离敌方大本营更近，所以敌方行营的价值更高一些。 ### 相邻棋子间的影响 相邻棋子之间存在相互影响，并且这些影响分为积极影响和消极影响。若某一棋子相邻己方棋子如果比该棋子更大，那么对该棋子有保护作用，产生积极的影响，会增加该棋子的价值。相邻地方棋子如果通过概率推断得出其比我方棋子大，则相邻敌方棋子会产生负面作用，减小该棋子的价值。对相邻的棋子，我们考虑两个因素影响棋子的价值，它们是： * 该棋子附近本方棋子中大于该棋子价值的棋子的价值大小 * 该棋子附近敌方棋子中最大的价值大小 ### 对己方军旗的保护和对敌方军旗的进攻 对于军旗的保护，我们考虑后三排，包括6个公路线上的棋位，7个铁路线上的棋位、两个大本营和两个行营。其中对两个行营，特别是对军旗附近的那个行营控制十分重要，该营可控制附近8个位置的棋位，其中一个棋位到军旗只有一步，二个棋位到军棋只有两步，一旦让对手控制该棋位后，对方可防可守。本方只有调集大量的兵力回防，使用于攻击的兵力下降。 基于上述原因，我们规定后三排军旗保护的原则为： * 计算该位置到军旗的最少步数，靠军旗所在的棋位越近，棋子价值增加15/最少步数。 * 若我方棋子临近敌方军旗，则此时的最佳策略是直接吃掉敌方的军旗。基于这种原则，吃掉军棋的奖励值应该是无穷大，所以这里设定吃掉对方军棋的策略会对整个局面的评分增加1000，以鼓励我方棋子吃掉敌方军旗。 博弈树极大极小搜索 --------- * 本模块参见git仓库[Chess AI](https://gitee.com/sg-first/Chess-AI) 极大极小搜索先将博弈树展开到指定层数`l`，从展开的第一层到第`l`层，奇数层为我方行动，偶数层为对手行动。对`l`层的各个局面节点使用局面评估函数进行估值。这样可以在`l-1`层节点`n`的子节点中选择最大/最小的节点评分作为的节点`n`评分（如果局面估值大表示利于我方，那么我方行动的层选择最大值，对手行动的层选择最小值），这样可以获得层所有节点评分，再对层递归实行此过程，直至获得第一层所有局面的评分，选择评分最大的节点即为最优决策。 如果局面评估函数完全准确，那么直接对第一层使用局面评估函数进行估值就可以得到最优结果。但由于局面评估函数总存在偏差，一般来讲，距离终局越近局面评估越准确，因此要尽可能搜索更多层。 极大极小搜索需要对博弈树进行层的充分展开，尽管可以使用Alpha-Beta剪枝减小搜索空间，但对于状态空间较大的游戏，这种详细的搜索在计算上并不可行。因此使用神经估值网络进行改进。 神经估值网路 --------- * 本模块参见git仓库[DL Chess AI](https://gitee.com/sg-first/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. 程序目录 -------