爱恩斯坦棋计算机博弈关键技术研究

摘要

计算机博弈是人工智能领域的重要研究方向之一，被誉为人工智能学科的“果蝇”。爱恩斯坦棋属于完备信息博弈棋种，是一种棋局信息完全透明的博弈类型，即博弈双方在任何时候都能完全掌握当前的棋局信息。然而，它不同于其它的完备信息博弈棋种，在双方行棋过程中需通过投掷骰子来确定可走的棋子，具有随机性，这使博弈系统对棋盘局势的分析和决策带来一定的挑战。自2012年爱恩斯坦棋被列为中国大学生计算机博弈大赛项目之后，国内越来越多的人专注于研究针对爱恩斯坦棋的博弈技术。现有估值函数的研究往往是从进攻、防守和概率三个因素分析局势的优劣，将这些因素以不同权重线性相加来组成估值函数。通过这种方式构造的估值函数一般会受到设计者自身博弈水平的限制，而且很难得到一个最优的权重。此外，搜索算法的研究大多是针对Alpha-Beta搜索算法和期望极大极小搜索算法的改进，但是这些搜索算法过于依赖估值函数，估值函数的好坏决定了整个博弈系统的水平。 本文以爱恩斯坦棋为研究对象，研究爱恩斯坦棋计算机博弈的关键技术。在搜索算法方面，本文引入蒙特卡洛树搜索(Monte-Carlo tree search，MCTS)算法，提出了概率启发的并行MCTS算法，用概率节点表示投骰子事件，以多对多的方式连接其子节点，并对概率节点进行并行效率优化。在估值方面，本文设计爱恩斯坦棋特征向量的表示方法，使用基于多层感知机的价值网络进行估值，并在训练过程中将价值网络与概率启发的MCTS算法结合，提高样本质量和棋力。在博弈系统方面，设计并实现了爱恩斯坦棋博弈系统，具有人机交互、自动化对弈、棋谱存取以及训练网络等功能，建立了计算机博弈算法设计与分析的验证工具。本文的主要创新点如下: (1)在博弈树搜索方面，设计了用于表示随机事件的数据结构，并提出了概率启发的并行蒙特卡洛树搜索算法。一方面，在博弈树中使用概率节点来表示掷骰子事件，使用多对多的形式连接概率节点和最大值或最小值节点;另一方面，将蒙特卡洛树搜索算法用于上述博弈树中，并对该算法的并行化方法做优化。通过实验分析和实践证明，概率启发的并行蒙特卡洛树搜索算法具有较高的搜索效率和智能水平，并在2018年中国大学生计算机博弈大赛荣获亚军（一等奖）; (2)在估值方法方面，本文研究并设计了基于多层感知机的价值网络，以评估棋盘对当前行棋方的价值。首先，本文从棋盘盘面中提取48维的特征向量，设计价值网络模型，并与概率启发的并行蒙特卡洛树搜索算法结合。其次，从AlphaGo Zero程序中得到启发，设计了样本采集、网络训练和棋力评估三个阶段的价值网络的训练过程。通过实验分析，本文提出的价值网络模型经过训练后有较高的智能水平，并且结合价值网络的概率启发并行蒙特卡洛树搜索算法以55.3％的胜率战胜未结合价值网络的算法; (3)在博弈系统方面，本文设计并实现了爱恩斯坦棋博弈系统，包括训练子系统和对弈交互子系统。训练子系统用于执行和管理价值网络的训练进程，根据用户输入的相关参数训练神经网络，查看和保存训练过程中的误差和胜率变化，存取训练完成的网络模型;对弈交互子系统提供用户与系统中的算法进行对弈的功能，用户可选择系统中已有策略，手动设置策略参数，实现人-人、人-机和机-机自动对弈，将对弈过程可视化，并存储对弈棋谱。 综上所述，本文在搜索、估值与系统三个方面进行爱恩斯坦棋计算机博弈技术的研究。首先，针对随机性的问题对蒙特卡洛树搜索算法进行了修正和并行优化，提升算法的搜索效率和智能水平;其次，设计了基于多层感知机的价值网络模型及其训练方法，进一步提升棋力;最后，实现了爱恩斯坦棋博弈系统，建立计算机博弈算法设计与分析的验证工具。