采用遗传算法优化点点连格棋评估函数参数

王允臣，毕方明

中国矿业大学 计算机学院，江苏 徐州 221116

1 引言

机器博弈是人工智能研究的重要分支，被喻为人工智能领域的果蝇。计算机博弈系统可分为四部分：局面表示、行动集合、评估函数和博弈树搜索。搜索算法是人工智能中问题求解的基本方法。Von Nenumann和Boerl在20世纪20年代提出的极小极大定理是搜索算法的数学基础；始于20世纪50年代的alpha-beta剪枝算法在搜索效率上前进了一大步。1980年的PVS（Principal Variation Search，亦称NegaScout）搜素算法，内部节点强有序时效率优于alpha-beta搜索；1994年出现的MTD（f）算法，始终用空窗探测逼近真值，借助“置换表”增速完成搜索，略优于PVS搜索[1]，两者为目前的主流方法。多数游戏的博弈树非常庞大，无法完备搜索，常规做法是搜索一定的深度，此时的叶节点由评估函数近似估值。评估函数的好坏直接影响到之后局势的发展[2]，如果说搜索引擎是博弈系统的眼睛，评估函数则是博弈系统的大脑。评估函数一般必须包含5个方面的要素，分别是固定子力值、棋子位置值、棋子灵活度值、威胁与保护值、动态调整值。每一方面的值又是由许多参数构成的。评估函数中上述参数的组合往往依赖于编程人员自身的知识和经验，这就导致很难达到最优。有学者已经把遗传算法引入评估函数，试图学习棋子之间的动态联系，但是效果不是很理想。本文以点点连格棋为例，设计了一种评估函数，使用遗传算法[3]对评估函数中的参数进行优化，为了加快遗传算法的收敛速度，在适应度函数中加入了问题领域知识[4]。

2 遗传算法应用于评估函数参数优化的解决方案

遗传算法是由美国Michigan大学的Holland教授于1969年提出，后经Dejong、Goldberg等人归纳总结所形成的一类模拟进化算法。近年来，遗传算法作为智能计算（神经网络、模糊处理和进化计算）的重要组成部分，一直是研究的一个热点，在应用领域也取得了相当好的结果，如多极值函数的优化问题、组合优化问题、调度问题等。

遗传算法并行度高，对初值的依赖性小，具有快速全局搜索能力，而且鲁棒性也明显优于传统爬山法[5]、模拟退火算法[6]和蚁群算法，但是具有早熟和收敛速度慢的特点，针对其缺点本文将目标函数相邻两代的一阶差分信息加入适应度函数加强搜索能力，防止早熟，并采用改进遗传算法使得收敛速度得到提高，使其最有可能在点点连格棋中取得成功。

2.1 点点连格棋基本概念

自由度：格子中未被占领的边的条数。

相邻：坐标分别为(i,j)和(k,l)的两个格子成为相邻的条件为：当且仅当|i-k|+|j-l|=1，并且两个公共边未被占领。

链：存在一组格子BS={b0,b1,…,bi,…,bn}，有bi的自由度为2，且b0、bn之间最多只有一个相邻属于BS，其余所有格子均有两个相邻，并有这两个格子均为BS中的格子，那么BS称为链，b0与bn称为该链的端点，b0与bn可以为同一个格子。

短链：由1个或2个格子组成的链。

长链：由3个或3个以上的格子组成的链。

双交：下棋方一步就可以占领两个格子的情形。

2.2 评估函数的参数选取

点点连格棋以一个空的棋盘开始，对弈双方轮流在相邻的两点之间放置一横线或竖线。当一方占领一个格子之后得到一分，并继续下一步。当所有的线被占领之后，游戏结束。得分较高者得胜。点点连格棋评估函数的设计通常依赖于几个定理[7]，下面加以介绍。

定理1无论初始棋盘的尺寸如何，总有以下式子成立：

其中，Dots指的是初始棋盘点的个数，Doublecrosses指的是棋局结束时，共形成的双交的个数，Turns指的是棋局结束时，共经历了多少轮的走棋。

定理2如果棋盘共有奇数个点，则先手方应当形成奇数条长链以取胜，后手方应形成偶数条长链以取胜；若棋盘共有偶数个点，则先手方应当形成偶数条长链，后手方应形成奇数条长链以取胜。

定理2被称为长链定理，它是Berlekamp对定理1的一个推论。

长链定理是评估函数设计的重要依据。以4×4棋盘为例，根据长链定理，我方应该致力于形成偶数条长链，假设我方行棋之后形成如图1（a）所示的棋局（这里有a，b两条长链），那么无论对方采取何种策略，最终一条链一定可以由我方捕获，我方处于优势地位。然而仅仅依赖长链定理无法保证评估函数准确性。比如我方行棋之后形成如图1（b）所示的棋局，这里同样有a，b两条长链，但是对手只需选择图中1处的边，就可以扭转局势，使我方处于绝对的劣势。以上分析表明，棋局的估值取决于多种棋型的配合[8]同时对棋型数目的奇偶性敏感。为此，本文设计了如下评估函数：

其中ri=nimod2,ni表示第i种棋型在当前棋局中的数目；Ai1,Ai2是第i种棋型的参数；N代表棋局中不同棋型的种类数，本文中选取的棋型为长链、短链、双交、自由度为3、自由度为4的格子，因此N=5。

图1 偶数条长链情形

2.3 适应度函数的计算

适应度是描述个体性能的主要指标，遗传算法根据适应度的大小对个体进行优胜劣汰。适应度函数的选择决定了算法优化的导向，对算法的收敛性以及收敛速度的影响较大。

遗传算法可采用的选择方法很多，有轮盘选择法、局部选择法、截断选择法和锦标赛选择法等。首先采用如下方法设计目标函数，让每个个体与现有的博弈算法（陪练算法）进行先后手的比赛，根据每场比赛所花费的回合数来确定目标函数的取值。如果己方获胜，则回合数越少函数值应该越大；如果对方获胜，则回合数越多目标函数值应该越大。因此目标函数的设计如下：

其中x为一场比赛的回合数，k为可调系数，它表示己方获胜时回合数对适应度的重要程度。这里取k=6。适应度函数直接由目标函数映射而成，即：

为充分考虑目标函数的变化趋势，防止遗传过程中优选的染色体只在一个较平坦的区域徘徊，导致“早熟”的情况，本文借鉴何新贵、梁久祯提出的方法[4]，把目标函数的相邻两代的一阶差分加入进来，采用如下新的适应度函数：

其中，权值ε∈[ ]0,1，称为控制因子，用以体现适应度函数值和函数值变化率对求解问题的重要程度；fit()x为原始适应度函数，fitmin和fitmax分别表示当前代群体中个体适应度的最小值和最大值；∇f()x ，∇fmin和∇fmax分别定义为：

其中xp，xc分别表示父代和子代染色体，n表示种群规模。

为了提高效率，本文对染色体中的每个参数进行分别考虑，本文中一个染色体对应10个参数，一个参数对应一种棋型的权重，因此一个染色体对应一个适应度矩阵[fit(x)′1，fit(x)2，…，fit(x)′i…，fit(x)′n]，这里 n=10。

2.4 交叉和变异操作

交叉方法很多，有单点交叉、多点交叉、顺序交叉、循环交叉等等。为了方便起见，本文采用单点交叉，随机地选择染色体中的一个二进制位作为交叉点将父个体的两个参数交叉形成子个体的两个参数。

对每个参数以一定的变异率进行突变[9]，因为采用的是二进制串表示，这里只需根据变异率对基因进行0-1翻转即可。变异是一种局部随机搜索，与选择/交叉算子结合在一起，保证了遗传算法的有效性。同时保持了种群的多样性，防止出现非成熟收敛。

这里选择对染色体中每一个参数进行操作是由于一条染色体对应的参数比较多，如果直接对整条染色体进行操作，那么有的参数可能得不到更多的交叉和变异操作，使得收敛时间变长，效果不理想。

2.5 改进遗传算法

文献[10]指出遗传算法具有收敛速度慢的缺点。这对于该文研究的问题来说是一个极大的挑战。因为适应度函数是基于博弈结果设计的，每个个体都需要与陪练算法进行博弈并决出胜负方可计算其适应度值。随着进化程度的提高，博弈所需要的时间也会极大地增加，其中的时间代价无疑是一个极大的挑战。本文从以下两方面对遗传算法进行改进：引入自适应遗传算法，使交叉率和变异率随着个体适应度自动调整；加入启发式信息指导下一代的生成。

遗传算法的收敛性受交叉率pc和变异率pm的影响[11-12]。交叉率越大新个体产生的速度越快，但是交叉率过大又不利于保护目前适应度高的个体的染色体结构，而交叉率过低，又使得个体进化过于缓慢，搜索过程停滞不前。对于变异率，如果变异率过低不利于产生新个体，而且搜索容易陷入局部最优，变异率过高，遗传算法很容易退化为随机搜索算法。由于目前还没有固定的方式来确定pc和pm，只能通过实验的方法不断优化，这个过程比较繁琐。为此，本文引入自适应遗传算法[9，13]，对每个染色体设计如下的交叉率和变异率矩阵[pc1,pc2,…,pci,…,pcn]和 [pm1,pm2,…,pmi,…,pmn]，其中n=10，对应一个染色体中的参数总数。pci和pmi随着个体适应度自动调整。下面给出pci和pmi的计算公式如下：

其中，pca=0.9，pcb=0.6，pma=0.1，pmb=0.001。fmax是群体中最大适应度值；favg是每代群体的平均适应值；f′是要交叉的两个个体中较大的适应值；f是要突变个体的适应度值。分析式子可知当适应度值越接近最大适应度值，pci和pmi的值就越小，这就降低了优良基因被破坏的可能，保证了算法的收敛性。

文献[5]指出爬山法具有收敛速度快的优点。本文受爬山法启发，在遗传算法中加入启发式信息指导下一代的生成，以求加快算法的收敛速度。

2.2节设计的评估函数共有10个参数，为了提高启发式信息的准确度，本文对每个参数进行分别考虑。具体操作如下：根据当前代个体适应度值采用轮盘赌方法选出双亲并按照2.4节介绍的交叉变异操作产生新个体，重复这个过程直到生成代替上一代种群的新一代种群。在选出下一代群体之后对所有个体按照适应度值从小到大排序。按照顺序遍历每一个参数j，把编码该参数的bit位转换为整数值，如果所有值都是递增的，那么就把pnj更新为pnj+Δj并更新到该染色体编码中，否则就取所有值的平均值δj并取与其相差绝对值最大的一个染色体，将其参数pij更新为δj并更新到该染色体编码中。

其中pij代表当前代中第i个个体（染色体）的第j个参数转换成整数后对应的值，n代表当前代中个体的总数。

3 实验测试与结果

3.1 实验策略

改进遗传算法需要大量的博弈训练才能得到较好的结果，时间问题是必须要考虑的关键因素。本文采用梯度训练的方法来达到花费较少时间取得更好效果的目的。具体包括三个方面，选择一种高效的博弈树搜索算法；逐步提高博弈算法搜索的深度；逐步增强陪练算法的强度。

1978年，Stockman提出了SSS*算法[14]并且证明它是一个正确的极小极大算法而且它永远不会搜索alpha-beta剪枝的节点。然而SSS*算法最大的缺点就是较大的存储需求，并且需要维护OPEN表。文献[15]针对SSS*算法[14]的存储需求大，需要维护OPEN表顺序等缺点提出了AB-SSS*算法。AB-SSS*算法通过反复的以空窗调用alpha-beta过程实现了与SSS*算法完全相同的搜索过程，解决了SSS*算法存在的缺点。而且由文献[14]知道，SSS*算法搜索的节点数比alpha-beta少，效率高。因此本文采用AB-SSS*算法作为二者的搜索算法。

搜索深度对时间的影响是巨大的，开始阶段由于评估函数参数未得到有效优化，即使搜索很大的深度最终得到的估值仍然是不准确的，因此时间代价过高。然而当评估函数参数得到有效优化后，如果搜索深度仍得不到相应提高，棋力就无法更好的提升，遗传算法会认为这是由于当前个体的基因不够优良从而继续对其进行进化，这样算法收敛的时间就会增加。

陪练算法的强弱同样会影响训练时间和结果的准确性。开始阶段陪练算法过强，遗传算法的选择趋于单一化；陪练算法一直很弱，则不利于选择出优良个体。本文对训练的不同阶段采用不同强度的陪练算法。

陪练算法的强弱体现在两个方面：评估函数的准确度和搜索的深度。在训练的开始阶段（前100代），使用根据自己的经验设计的评估函数，评估函数估值计算的伪代码如下所示：

在训练到达一定阶段后，再采用与遗传算法得出的相同参数的评估函数，这时通过搜索深度来区分二者的棋力。在训练的前期（前100代）中期（100代到200代）后期（200代到300代），遗传算法的AB-SSS*算法的搜索深度分别取2、5、7；陪练算法的AB-SSS*算法的搜索深度分别取2、8、10。AB-SSS*算法的伪代码参考文献[14]。

3.2 实验结果

对改进适应度函数和自适应遗传算法的评估函数进行梯度训练实验，实验由50代、100代、150代、200代、250代、300代的冠军组成一个小组进行组内先后手的循环赛，胜者加3分，和棋加1分，负者加0分。最后的积分情况如图2所示。

图2 训练积分表

通过图2可以发现，采用改进遗传算法梯度训练的评估函数，训练代数越多，棋力越强，效果明显，而采用改进遗传算法非梯度训练的评估函数，棋力差别相对较小，且会有不稳定的情况。这说明改进遗传算法具有更快的收敛速度。为了进一步验证本文提出的梯度训练方案的有效性，取改进遗传算法梯度训练、改进遗传算法非梯度训练以及改进蚁群算法[16]非梯度训练300代的冠军组成一个小组进行组内先后手的循环赛，重复进行10次，统计获胜情况如图3所示。

图3 获胜情况

通过图3可以发现，对于遗传算法和蚁群算法，梯度训练的胜率均高于非梯度训练，同时改进遗传算法的获胜率高于改进蚁群算法。这也验证了本文提出的梯度训练方案的有效性。

实验发现程序迭代到300代以后，被优化的各个参数基本已不再变化此时的参数值如表1所示。

表1 训练结果

用进化到300代的参数组和完全根据经验设定的参数组的程序进行了比赛，结果进化到300代的参数组的胜率明显占优。

为了验证提出的梯度训练方法可以在保证准确度的情况下减少训练的时间，对遗传算法和陪练算法在不同的训练阶段采用相同的深度8，并且均采用相同的评估函数，进行实验（由于耗时严重，只训练50代）。结果如表2所示。

表2 训练时间

通过表2发现，二者耗时差距明显，用梯度训练与非梯度训练相同代数的评估函数在相同的环境（搜索算法一致，搜索深度相同）下进行50场对抗，统计输赢情况如表3所示。

表3 博弈数据

通过表3，看到搜索深度的增加并没有带来明显的优势，这也在一定程度上验证了本文的策略。

4 结论

经典遗传算法本身存在着收敛速度慢等缺陷，本文采用了一种新的适应度函数的计算方法，考虑了目标函数在搜索点的变化趋势，并将该信息加入适应度函数指导搜索的进行，使得搜索朝着具有较大函数值变化率的方向进行。采用改进遗传算法使用启发式信息指导下一代个体的生成，这些措施使算法的收敛度得到了提高。本文提出的梯度训练方案，有效地节省了训练时间。把遗传算法引入到评估函数参数优化中，避免了传统的手工调整参数，保证了参数的准确性和客观性，实验表明评估函数参数优化后的点点连格棋的棋力得到了提高，这也为开发高水平博弈算法提供了一种新的思路。

[1]Qiu Hongkun，Zhang Peng，Wang Yajie，et al.Analysis of search algorithm in computer game of Amazons[C]//The26thChineseControlandDecisionConference（2014 CCDC），2014：3947-3950.

[2]Runarsson T P，Lucas S M.Preference learning for move prediction and evaluation function approximation in othello[J].IEEE Transactions on Computational Intelligence&Ai in Games，2014，6（3）：300-313.

[3]Wei Xiaokun，Shao Wei，Zhang Cheng，et al.Improved self-adaptive genetic algorithm with quantum scheme for electromagnetic optimization[J].Microwaves，Antennas&Propagation IET，2014，8（12）：965-972.

[4]权芳芳，许峰.基于梯度的自适应量子遗传算法[J].软件导刊，2012，11（8）：31-33.

[5]罗彪，郑金华，杨平.基于定向爬山的遗传算法[J]计算机工程与应用，2008，44（6）：92-95.

[6]Gao C，Gao Y，Lv S.Improved simulated annealing algorithm for flexible job shop scheduling problems[C]//Chinese Control and Decision Conference，2016.

[7]Li Shuqin，Li Dongming，Yuan Xiaohua.Research and implementation of Dots-and-Boxes[J].Journal of Software，2012：256-262.

[8]谷蓉.计算机围棋博弈系统的若干问题研究[D].北京：清华大学，2003.

[9]Tao X，Wang S，Huangfu Y，et al.Geometry and power optimization of coilgun based on adaptive genetic algorithms[J].IEEE Transactions on Plasma Science，2015，43（5）：1208-1214.

[10]Leuven J，Reehuis E，Emmerich M，et al.User-derived mutation in highly constrained truck loading optimization[C]//IEEE Congress on Evolutionary Computation，CEC 2015，Sendai，Japan，May 2015.

[11]黄春.改进遗传算法的函数优化及应用[D].南宁：广西大学，2015.

[12]刘明，王瑞.基于自适应遗传算法的改进PID参数优化[J].计算机测量与控制，2015，23（3）：791-793.

[13]王骄，王涛，罗艳红，等.中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J].东北大学学报：自然科学版，2005，26（10）：949-952.

[14]Stockman G C.A minimax algorithm better than alphabeta?[J].Artificial Intelligence，1978，12（2）：179-196.

[15]Plaat A，Schaeffer J，Pijls W，et al.SSS*=alpha-bet+TT，TR-CS_94-17[R].Edmonton，AB，Canada：Universityof Alberta，1994-12.

[16]高雷阜，张秀丽，王飞.改进蚁群算法在SVM参数优化研究中的应用[J].计算机工程与应用，2015，51（13）：139-144.