基于CNN模型的亚马逊棋搜索算法设计*

北京信息科技大学计算机学院 李若溪 高铭

亚马逊棋AI搜索算法包括蒙特卡洛搜索算法、改进后的α-β剪枝算法，极大极小搜素算法，经检验发现蒙特卡洛搜索算法取得较好的成果，但原有的搜索算法由于搜索的博弈树层数为固定值，会产生超时或搜索层数过少造成搜索不完全的问题，尝试使用CNN模型优化原有的亚马逊棋搜索算法。设计一个基于CNN模型的优化器，该优化器将当前棋盘的权值作为输入层，进行三层卷积，输出层为当前局面下的最优层数。在同等计算力条件下，采用蒙特卡洛与α-β剪枝算法，令采用CNN模型优化后的搜索算法与固定搜索层数的算法进行对弈，前者的不败率为73.4%。经过实验，发现通过CNN模型自动生成搜索层数的算法对胜率产生了较好的影响。

亚马逊棋发明于1988年，是一种两人棋。一个完整的亚马逊棋局面包括棋盘、棋子、箭，博弈系统包括：落子生成器、落子搜索引擎以及局面得分的评估函数。生成器针对已下的棋局的局面，结合落子的搜索引擎对下一步一定范围内的节点数进行搜索，利用评估函数对每个节点进行评分，返回给落子的生成器进行下棋。综上而言，对胜率产生影响的主要因素是搜索算法与评估函数，亚马逊棋的局面评估函数主要包括以下三个特征的评估值，分别为Territory、Position、Mobility，而搜素算法包括搜索层数与搜索方式，搜索层数的优化为本文的主要研究内容。

最初，大多数强大的亚马逊程序都使用传统的基于极小值的算法，这类程序有Invader和Amazong。……