基于赛制组织的遗传变异棋局样例生成算法

田 欣，姬 波,2，卢红星,2，柳宏川,2，尤惠彬

1(郑州大学 信息工程学院,郑州 450001)

2(郑州大学 产业技术研究所第四代工业研究所,郑州 450001)

1 引 言

计算机棋类游戏被认为是人工智能领域的“果蝇”，对其的深入研究有助于对机器智能中很多基本问题的理解.作为计算机棋类游戏的3个里程碑，chinook，深蓝和alphazero分别在西洋跳棋，国际象棋和围棋比赛中取得了战胜人类选手的成绩，大大鼓舞了投身于这个领域的研究人员[1].

1999年Kumar Chellapilla等人就提出在不依赖专家知识库的条件下，设计完全连接的前馈神经网络，采用种群中互相博弈和遗传变异的知识传递方式，使用多层前馈神经网络评估棋盘位置，极小极大搜索策略进行搜索，以每一场比赛的最终结果(即赢、输或平局)来完成神经网络的竞争生存，最终筛选出种群中的最优选手作为优胜者，该选手能够击败两名专家级选手，并与一名高手打成平局[2].随后Su Z采用遗传算法解决跳棋博弈中的评价问题，在计算机上模拟两个“玩家”之间的交替演化过程，博弈的输方依次向获胜方进行参数调整和进化.有效地解决了传统搜索算法由于搜索程度的加深而带来的计算量大幅增加的问题[3].为增加搜索树的深度并减少运行时间，2014年Neto H C等人提出一种高效无监督进化学习系统，利用进化计算的方法，在选择棋步时，保持深度前瞻搜索，使用搜索预测值来选择与当前棋盘状态相对应的最佳移动，神经网络的权值通过一个评价函数进行更新，该评价函数通过时域差分方法自动调整，使棋盘状态的选择过程自动化[4].2016年David O E等人针对国际象棋程序缺乏学习能力的现象，提出一种基于深度神经网络的端到端的国际象棋学习方法.在没有任何先验知识的情况下，依赖于数百万个国际象棋游戏中黑白棋赢的局面，使用无监督训练从一个给定的位置提取高级特征，而有监督训练学习则比较两个国际象棋位置并选择更有利的一个.实验表明，由此产生的神经网络(DeepChess)与最先进的国际象棋程序不相上下[5].紧接着AlphaGo诞生，针对不可穷举的大型游戏，为减少搜索空间，使用策略网络选择移动，价值网络评估棋盘位置.这些神经网络采用监督学习针对人类专家游戏中随机抽样的动作进行训练，预测人类专家动作，利用强化学习进行自对弈.并提出一种将蒙特卡罗模拟与价值策略网络相结合的搜索算法，通过这种搜索算法，AlphaGo达到了很高的胜率[6].然而，专家数据集通常是昂贵的、不可靠的或根本不可用的.因此AlphaGo Zero出现，提出一种完全基于强化学习的算法，使用自对弈，从随机游戏开始，没有任何监督或人类数据，训练循环中加入了前瞻搜索，只使用棋盘上的黑白棋子作为输入特征，在搜索时只依赖于一个单一的神经网络来评估位置和样本移动，而不执行任何蒙特卡罗rollout，提高了学习的速度、精度和稳定性[7].2018年将这一算法同时应用到国际象棋，shogi和围棋中，对这3款游戏使用相同的算法和网络架构.从随机游戏开始，除了游戏规则外没有任何领域知识，用深度神经网络、通用强化学习算法和通用树搜索算法取代了传统游戏程序中使用的手工知识和特定领域的扩展，完全从自对弈中学习移动概率和价值估计.研究结果表明，一种通用的强化学习算法可以在没有特定领域的人类知识或数据的情况下学习[8].2017年也曾尝试通过仅从人类游戏的数据库中学习来进化一种最先进的评估功能，并取得了成功，这是通过监督和非监督学习相结合实现的，在监督学习阶段，选择大师级游戏数据库中的位置和在这个位置上的获胜移动，进化模仿人类大师的行为，而在非监督学习阶段，这些进化的生物通过共同进化的方式得到进一步的改进.结果表明，进化的程序比两届世界计算机国际象棋冠军表现更好[9].2018年一种新的监督学习方法被提出，通过训练人工神经网络评估棋局，针对大约300万个由高水平棋手进行的不同棋局，使用Stockfish的评估功能对它们打分，通过训练不同的人工神经网络体系结构来理解国际象棋的位置，该网络根据深度为1的一组候选移动对可能的未来棋盘状态进行评分，而无需进一步探究.从而找到一个精确的国际象棋位置的评估，更侧重于发现国际象棋中固有的模式识别知识，而无需深入研究一大堆未来的棋盘状态[10].

目前棋类智能的研究主要集中在优化搜索算法、评价函数以及提高学习能力3个方面，旨在找到每一步移动的最佳动作，同时通过提高学习能力，得到一个强大的人工智能选手[11].即使目前的人工智能选手已经可以战胜人类选手，但在棋类“果蝇”身上依然存在很多未能透彻研究的问题.有限的学习样例很大程度可以决定人工智能选手的能力，但对于学习样例的具体产生方式却未能引起足够的重视.

因此，本文提出一种学习样例的生成算法，将体育赛制(混合赛制、循环赛制、淘汰赛制)和遗传算法结合，借用成熟公正的体育赛制高效的组织形式为人工智能选手匹配对手，结合遗传算法自组织、自适应和自学习的特性，逐步进化选手，将优胜者之间的对局做为学习样例.然后，以西洋跳棋为实例进行实验，并通过定量分析指标建立学习样例生成方式的评价体系，评价基于混合赛制、循环赛制和淘汰赛制3种不同体育赛制生成的学习样例的优劣，并探讨在行棋局数相同的情况下，最适合西洋跳棋的赛制组织形式.实验表明，本文提出的样例生成方式可以有效产生样例，且在样本综合规模指标T下，3种赛制中基于混合赛制和循环赛制产生的学习样例具有更高的质量，同时基于样例训练的选手能力对比表明，循环赛制最适合于西洋跳棋游戏的样例产生.

2 研究背景

2.1 遗传算法

遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的随机化搜索方法.它最初是由1975年美国的J.Holland教授提出，借鉴进化生物学中的一些现象而发展起来的，通过运用生物遗传与进化的特点，将要解决的问题模拟成一个生物进化过程，将一些待优化的解决方案作为群体.每一个群体通过繁殖、变异、竞争，实现优胜劣汰，逐步得到问题的解[12].

遗传算法运用遗传算子来进行遗传操作，包括优选适应性强的个体的“选择”，个体间交换基因产生新个体的“交叉”，个体间基因突变而产生新个体的“变异”.

选择：选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想.根据个体的适应度，按照一定的规则，从第n代群体中选择出一些具有优良性状的个体遗传到(n+1)代群体.在这一选择过程中，个体适应度越大，则被选择到下一代的机会越大.某个体i的适应度为fi，种群大小为NP，则i被选择的概率如公式(1)所示：

(1)

交叉：交叉算子模仿自然界有性繁殖的基因重组过程，其作用在于将已有的优良基因遗传给下一代个体，并生成包含更复杂基因的新个体.最常用的交叉算子为单点交叉.即在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体[13].

(2)

随着应用领域的扩展，遗传算法的研究出现了引人注目的新动向，即基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特规则生成功能的崭新的机器学习算法.这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望.目前遗传算法已经在人工智能领域最具有挑战性的计算机棋类游戏中得到了广泛的应用.Esch,J使用遗传算法，将神经网络模拟为玩家，玩家通过对标准参数和权值进行随机变化的过程，互相竞争生存和产生后代，幸存的玩家从游戏中提取信息并提高他们的能力.该程序达到了可以通过棋子的位置和位置值以及神经网络来评估棋盘位置的目的[14].Vazquezfernandez E等人针对国际象棋程序提出，将进化算法种群中的每一个个体都代表一个具有特定权重的评价函数的虚拟参与者，且算法中所执行的动作与数据库中某个特定游戏中人类象棋大师所执行的动作相等.结果表明，该方法得到的权值与国际象棋理论得到的权值相近[15].之后，遗传算法被用到棋类游戏的多个方面，用于优化得到更好的参数.2014年David O E等人使用遗传算法来进化国际象棋程序的评估函数和选择搜索机制参数.通过模仿人类大师的行为，以共同进化的方式得到进一步的改进，最终得到了与顶级锦标赛相似的性能[16].Hootan Dehghani在2017年提出一种基于遗传算法的棋局树空间约简方法.将遗传算法应用于减少国际象棋博弈树的搜索空间，与Min-Max算法相比，在准确性和速度上具有更好的性能[17].

2.2 体育赛制

体育赛制是目前一种较为成熟公正的赛制组织形式，多用于在竞赛中对比赛规则和参赛选手的具体安排，组织参赛选手合理高效的进行比赛.合理设置赛制，可以尽可能保证本次比赛的顺利进行，同时缩短比赛时间，在一定程度上还可以保证每个参赛选手的公平.赛制包括多种竞赛形式，主要有循环赛制、淘汰赛制和混合赛制.

2.2.1 循环赛制

在有多个队参加比赛时，每一队要与其他各队至少进行一次(单循环)或多次(多循环)比赛，对每轮比赛胜负分别赋予不同的分值，最后以累计分值之和决定最终名次.循环制一般适用于参赛队数不多，有足够竞赛时间的比赛，而且由于参加竞赛的各队都有相遇比赛的机会，是一种比较公平合理的比赛制度.当参赛队数为n，进行单循环赛时，整个赛事总比赛轮次N如公式(3)所示：

(3)

2.2.2 淘汰赛制

淘汰赛制是指逐步淘汰失败者，使胜者按预定比赛表进入下一轮比赛.淘汰赛制主要分为两大类，第一类是单淘汰制，即比赛过程中选手只要失败一次就被淘汰，直到决出最后的冠军；第二类是双败复活淘汰制，将选手分为胜者组和败者组，选手负一场后并未被淘汰，只是跌入败者组，每一轮败者组的比赛又分为两个阶段.第一个阶段，由当前败者组中的幸存者相互对阵，负者被淘汰，胜者进入第二个阶段；第二个阶段，由第一阶段中败者组的胜者对阵刚刚在本轮由胜者组中淘汰下来的选手，胜者进入下一轮中的败者组，负者被淘汰[18].淘汰赛制适用于有大量参赛者的比赛.

当淘汰赛制的参赛队数A正好为2n时，整个赛事总比赛轮次N如公式(4)所示；否则，整个赛事总比赛轮次是较大的一个以2为底的幂的指数.

(4)

2.2.3 混合赛制

混合赛制就是将循环赛与淘汰赛在比赛中先后使用，最后决出比赛名次，完成比赛工作.混合赛一般分两个阶段进行，第一阶段常采用分组循环赛，第二阶段常采用淘汰赛[19].混合赛综合了循环赛和淘汰赛的优点，弥补了两者的不足，既有利于参赛者相互交流，又最大限度地减少比赛胜负的偶然性.

3 基于赛制组织形式的遗传变异样例生成算法

综合遗传算法自组织、自适应和自学习的特性以及体育赛制成熟公正的赛制组织形式，本文提出了一种基于赛制组织形式的遗传变异学习样例生成算法，该算法将遗传算法和体育赛制相结合，借助体育赛制中循环赛制、淘汰赛制和混合赛制3种不同的赛制组织形式，为人工智能选手匹配对手，并使用遗传变异方法使选手逐代进化，最后将优胜者之间的对局做为学习样例.基于赛制组织形式的遗传变异样例生成算法整体上分为5个步骤：

1)借助人工经验确定初始种群：在项目组已有实验结果的基础上，得到一个较好的神经网络，对该神经网络的参数设置一个浮动值，随机得到多个神经网络，每一个神经网络视为一个选手，初始得到多个对弈选手；

2)借助体育赛制的组织形式，为每个选手匹配对手：所有选手根据循环赛制、淘汰赛制或混合赛制的组织形式，为自己匹配相应的对弈选手，根据赛制的不同，每个选手将与不同的对手进行一次或两次对弈；

3)选手对弈：选手与根据赛制所匹配的对手按照游戏规则进行对弈；

4)得到学习样例：在对弈结束之后，将获胜局中获胜优势较大的棋局信息作为学习样例；

5)进化选手：一轮比赛包含多场选手之间的对弈，每一场选手对弈结束后，根据该场对弈结果的输赢，保留获胜优势较大的选手，淘汰劣势选手.本轮比赛结束之后，所有保留下来的选手作为本次进化的父代，所有父代之间交叉变异产生子代，得到下一轮比赛的选手.

3.1 西洋跳棋简介

3.1.1 西洋跳棋游戏规则

西洋跳棋是一种在8×8棋盘上进行的技巧游戏，以吃掉或堵住对方所有棋子去路为胜利.棋盘上有黑白两种颜色的方块，黑色方块不能放置任何棋子，白色为所有棋子行棋方块，棋盘的左上角为黑色方块，且相邻的方块不能为同种颜色[20].有两名玩家，分别被称为“红方”和“蓝方”，红蓝双方各有12个相同颜色的棋子，分别占据棋盘两边(上方为“蓝方”，下方为“红方”)，如图1所示.

图1 西洋跳棋64格棋盘

游戏规则规定“红方”为先手，双方轮流下棋.“未成王”的棋子只能向对方左上角或右上角且无人占据的格子斜走一格.当棋子到达对方底线时则“成王”，王棋可向4个斜线方向中任意一个方向移动.但棋子在“成王”后不能马上继续吃棋，须等下一回合才可移动.在行棋过程中，执行吃子优先的规则，吃子时，敌方的棋子必须是在己方棋子的左上角或右上角的格子，而且该敌方棋子的对应的左上角或右上角必须没有棋子.若一个棋子可以吃棋，那么它必须吃而不可以走其他棋子.若出现连吃情况，则连吃的优先级高于吃子，且继续吃直到无法再吃为止.

出现下述情况则判定为该局游戏结束：

1)任意一方玩家的棋子被全部吃完，则判定留在棋局上的玩家为获胜方.

2)棋局上留有双方棋子，若一方所有棋子被堵住无法继续移动，则判定另一方为获胜方；若留在棋盘上的双方所有棋子均被堵住而无法继续移动，则判定双方平局.

3)移动步数超过最大限度且仍未分出胜负，则判定双方平局.

3.1.2 棋盘表示

棋子的强度代表着该棋子的水平.根据棋类游戏的规则，每一个棋子都有其独特的移动方式，这意味着它在不同情况下的作用和重要程度是不同的.不同棋子的共同取值方式由数组元素{-K，-1，0，+1，+K}表示，以正负号区分玩家和对手.其中：-K表示蓝王棋、-1表示普通蓝棋、0表示空格(无棋子)、+1表示普通红棋、+K表示红王棋.本文K值设定为2.0.当普通棋子变成王棋后，棋子图像由圆形变为标有“王”字样的圆形用于区分普通棋子与王棋.

3.2 确定初始种群

本文将一个完整的BP神经网络定义为一个人工智能选手，每一个选手又视为遗传算法中的一个染色体，采用十进制编码方式对每一个染色体进行编码.该BP神经网络以西洋跳棋的32个棋盘状态作为输入信息，且有两个隐藏层信息，隐藏层结点个数分别为5和3，一个输出层信息，结构如图2所示[21].因此，一个神经网络有187个权重和阈值参数，即每一个选手信息由187个神经网络参数组成.

图2 BP神经网络结构

根据目前项目组的实验结果，已通过自对弈训练出一个优秀选手，该选手同样包含187个神经网络参数.本文借助人工经验来确定初始种群，在该选手的基础上，对其参数设置浮动值，得到多个人工智能选手.由于所有选手都基于初始的优秀选手得到，因此相对于随机生成的初始选手，该方法得到的每一个选手的能力虽然存在差异，但分布较为均匀.

由公式(5)通过对初始优秀选手的每一个参数浮动得到多个不同的人工智能选手.其中，Nw是神经网络中权重和阈值的数量(此处为187)，fd是浮动参数值且fd∈(0,1)，di是神经网络的一个参数值，r是区间(0,1)内的随机值，y是浮动后得到的相对应的神经网络的一个参数.

(5)

3.3 借助赛制匹配对手

借助体育赛制成熟公正的组织形式，为每一个选手匹配其对手，以达到选手之间对弈的高效性.分别采用3种不同的体育赛制，即循环赛制、淘汰赛制和混合赛制，为选手匹配不同的对手.

3.3.1 采用循环赛制

当选手较多时，采用分组循环赛制.对初始选手进行分组，每组内选手的匹配方式采用′U′型逆时针旋转法，将所有选手逆时针旋转排列.为使选手之间尽量公平，先进行一次′U′型交叉匹配，然后之后的每一轮都将进行′U′型平行匹配.采用′U′型逆时针旋转法编排方式，在每一轮选手匹配结束后，所有选手将依次逆时针旋转一位，使每个选手都尽量能和组内的其它选手比赛.′U′型逆时针旋转法的编排方法如图3所示，以每组内4个选手为例:

图3 ′U′型逆时针旋转法

需进行5轮比赛，每一轮匹配的双方选手如表1所示.

表1 循环赛对局编排表

采用′U′型逆时针旋转法，可以减少选手比赛轮次，且使每个选手尽可能与组内的其他选手都进行一次比赛，并尽量都能担任先手和后手的角色，避免了因先后手的区别对对弈结果产生的影响.

3.3.2 采用淘汰赛制

为避免匹配的双方选手之间的偶然性以及选手的意外失误，采用复活淘汰赛制，选手只有两次都失败才被淘汰，这种赛制可以给选手多一次的机会.每个选手依次和相邻的下一个选手匹配为对手，选手分为胜者组和败者组，选手负一场后，并未被淘汰，还能再进行一次比赛，选手只有两次都失败才被淘汰，这种赛制可以给选手多一次的机会.8个选手的淘汰赛制的具体对局编排表如图4所示.

图4 复活淘汰赛对局编排表

3.3.3 采用混合赛制

所有选手先进行组内循环赛，然后将组内循环赛的获胜选手作为淘汰赛的初始选手，进行复活淘汰赛.混合赛中的组内循环赛和复活淘汰赛采用和以上相同的方式.

3.4 选手对弈

所有选手根据赛制的组织形式，匹配到自己的对手，然后双方进行对弈，在对弈过程中，对于每一个位置都向下执行一层搜索，确定下一步走子，使用BP神经网络来评估棋盘分值，红方选择下一步移动的最大值，蓝方选择最小值.

在西洋跳棋中，棋盘分值的计算均以当前棋盘的32个有效位置作为输入，权重和阈值的初始值即为该选手的参数值，以BP神经网络输出的唯一标量值作为当前棋局状态的分值.BP神经网络仍采用图2所示的结构，每个节点的净输入值Si经过sigmod激活函数f(x)变换后得到该节点的输出.当前棋盘状态的估值Vo的计算如公式(6)所示：

(6)

其中，H1j为第1层隐藏层每个节点的值，H2l为第2层隐藏层每个节点的值，Wij、Wjl、Wlo分别为输入层和第1层隐藏层、第1层隐藏层和第2层隐藏层、第2层隐藏层和输出层之间的权重，bj、bl和bo分别为第1层隐藏层、第2层隐藏层和输出层的阈值.

3.5 生成学习样例

在每一轮对弈结束后，有3种对局结果，分别为输、赢和平局.本文仅在所有的获胜棋局中，挑选在m(m很小)步之内就获胜的棋局和获胜n(n很大)子的棋局作为学习样例.之所以没有将所有的获胜棋局作为学习样例，一方面是排除那些“侥幸获胜”的棋局棋局，另一方面，我们认为通过训练获胜局优势较大的棋局局面得到的选手相对于其他棋局局面来说能力可能更强.

双方对弈过程中，进入下一轮比赛的获胜选手，如果它在下一局面临的对手的走子方式不一样，它的走子方式也不一样，即对局局面不一样，这在一定程度上增加了学习样例的多样性.

3.6 进化选手

由于体育赛制选手编排的特点，每一轮比赛中包含多场选手之间的对弈，每一场选手对弈的结果有输、赢或平局，而我们仅针对在获胜选手中，选取在m(m很小)步之内就获胜的选手和本场对弈结束后获胜n(n很大)子的选手作为本次进化的父代.

一轮比赛结束后，将所有父代样本随机配对，然后在满足交叉概率Pc内随机选择一对父代个体，将这两个父代个体的部分结构加以替换重组而生成新个体.本文采用单点交叉方式，在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体.

为使遗传算法具有局部的随机搜索能力，且维持群体多样性，防止出现未成熟收敛的现象，在交叉操作后，对群体进行变异操作.对群中所有个体以事先设定的变异概率Pm判断是否进行变异，对进行变异的个体随机选择变异位，对该位基因值用随机生成的[-1,1]中的值来替换，从而形成新的个体.

进化完成后，所有的父代选手和子代选手作为下一轮对弈的初始选手.

3.7 算法复杂度

N表示算法的最大迭代次数，g表示循环赛的轮次，r表示淘汰赛进行的轮次，p表示进化种群数量.该算法的时间复杂度主要分为两部分：1)计算3种赛制的时间复杂度.循环赛制的时间复杂度为O(g)，淘汰赛制的时间复杂度为O(r)，混合赛制的时间复杂度为O(g+r)；2)计算选手进化的时间复杂度，该过程时间复杂度为O(p).当迭代N次时，基于3种不同赛制的算法的总时间复杂度分别为O(N(g+p))，O(N(r+p))，O(N((g+r)+p)).

基于赛制组织形式的遗传变异样例生成算法的基本步骤如下：

输入：BP神经网络的所有参数值，为一个初始选手；

输出：一定条件下获胜者的对局，即学习样例；

初始化：以一个BP神经网络代表一个选手，对该选手参数值浮动得到200个初始种群选手；

1.while(i < N)do

2. if(循环赛)then

3. for(i=0;i

4. 分组，组内采用“U”型逆时针旋转法匹配对手并对弈；

5. end for

6. else(淘汰赛)then

7. for(i=0;i<=r;i++)do

与相邻选手互为对手，采用复活淘汰赛方式对弈；

8. end for

9. else(混合赛)then

10. 先组内循环赛，循环赛获胜选手进入淘汰赛；

11. end if

12. if(红方m步内获胜或胜n子)then

13. 保存红方对局作为学习样例；

14. end if

15. if(红方或蓝方m步内获胜或获胜n子)then

16. 保存胜方选手至本代进化种群；

17. end if

18. for(i=0;i

19. 交叉，变异，得到下一代选手；

20. end for

21.end while

4 实验结果与分析

本文的算法实验平台是由项目组历时10个月自行开发的，该平台主要功能是实现西洋跳棋自对弈棋局学习样例生成器系统，主要包括界面初始化、行棋、学习样例生成和训练红方选手4大功能.

4.1 样例生成的可行性

实验借助人工经验，在目前项目组已有的实验结果基础上，通过对其优秀选手的参数值浮动，确定200个初始种群，并基于循环赛制、淘汰赛制和混合赛制3种不同的赛制为选手匹配对手，根据对弈结果(输、赢和平局)，仅选择在所有获胜棋局中，120步之内就获胜的棋局和获胜棋子数超过8子的棋局作为学习样例.在不同迭代次数下得到的学习样例如表2所示.

表2 3种不同的学习样例(M表示混合赛制、R表示循环赛制、K表示淘汰赛制)

由表2可以看出：

1)随着迭代次数的增加，基于混合赛制、循环赛制和淘汰赛制生成的学习样例的个数都逐渐增加，这说明本样例生成算法是可行的；

2)当迭代相同次数时，单位时间内基于淘汰赛制生成样例的效率最高，其次是循环赛制，最后是混合赛制，这与3.7节3种赛制的算法时间复杂度相吻合，表明该算法是正确的，可以有效产生样例.

4.2 样例质量

本文采用项目组提出的样例规模综合指标T，对该算法产生的学习样例进行定量分析，评价学习样例的质量.与学习样例直接相关的两个定量指标分别是：样例总个数s和样例重复率x=r/s.其中，r为重复样例个数，样例规模综合指标T如公式(7)所示：

T=α*y-(1-α)*x

(7)

s∈[0,+∞]；x=r/s；y=tanh(logs)；α为平衡因子且α∈[0,1]；T的值域范围为[0,1].当通过学习样例训练得到的选手胜率变化规律和T值的变化规律一致时，表明该学习样例质量较高.

通过对学习样例训练得到不同的选手，将这些选手作为红方，与随机选手对弈.实验结果如表3-表5所示，并根据表中数据绘制样例规模综合指标T(a=0.8)与胜率变化组合图，如图5所示.其中横坐标表示迭代次数，左侧数值表示T值，右侧数值表示通过学习样例训练得到的选手的胜率.

表3 基于混合赛制实验结果

表4 基于循环赛制实验结果

表5 基于淘汰赛制实验结果

通过对图5分析，可以发现：

图5 T值与红方胜率变化图

1)基于混合赛制和基于循环赛制生成的学习样例的规模综合指标T的变化规律和红方获胜概率的变化规律相同，均符合样例规模综合指标T的特点，表明基于这两种赛制得到的学习样例具有较高的质量；

2)基于淘汰赛制得到的学习样例的T值变化规律，虽然在迭代3000次和5000次时，与红方获胜概率的变化规律相同，但是当迭代次数增大时，T值和红方训练后的胜率变化规律变得不一致，因此基于淘汰赛制得到的学习样例质量具有不稳定性.

4.3 样例训练效果

为了进一步分析基于混合赛制、循环赛制和淘汰赛制生成的学习样例的优劣，本文采用BP神经网络对学习样例进行训练，以棋盘的32个状态作为输入值，当前棋盘状态的分值作为目标值，通过两层BP神经网络(第1个隐藏层结点个数为5，第2个隐藏层结点个数为3)的逆向反馈调整权值和阈值，最后得到一个神经网络模型，该模型即为根据学习样例训练得到的一个选手.

将基于3种赛制生成的学习样例训练得到的选手分别作为红蓝方，双方对弈多次，将多次对弈结果取均值，对应的结果如图6所示.

图6 选手对弈结果

图中横坐标表示迭代次数，纵坐标表示双方对弈结果.从图 6可以看出：

1)在迭代次数相同时，尽管双方平局居多，但不论基于循环赛制学习样例训练得到的选手是作为红方选手还是蓝方选手进行对弈，其结果相对于基于混合赛制学习样例训练得到的选手来说，其都具有一定的优势，这表明，基于循环赛制生成的学习样例的训练效果最佳.

2)基于循环赛制学习样例训练得到的选手和基于淘汰赛制学习样例训练得到的选手作为红蓝方对弈时，结果仍然是基于循环赛制学习样例训练得到的选手具有获胜优势，表明基于循环赛制生成的学习样例的训练效果同样优于淘汰赛制.

综合以上分析得出：

1)借助成熟公正的体育赛制组织形式为人工智能选手匹配对手，是可行和有效的，可以在短时间内生成大量有效样例；

2)基于样本规模综合指标T的评价表明，基于混合赛制和循环赛制产生的学习样例具有较高的质量，而基于淘汰赛制产生的学习样例质量则较为不稳定；

3)样例训练之后的选手能力比对实验表明，循环赛制最适合于西洋跳棋游戏.

5 结束语

目前对于计算机棋类游戏的研究目标多聚焦于人工智能选手与其他选手，尤其是人类冠军选手比赛的输赢结果上.虽然众所周知人工智能选手能力在很大程度上取决于学习样例，但样例的产生算法却没有引起足够重视和讨论.因此，本文提出了一种学习样例生成算法，借助体育赛制高效的组织形式为人工智能选手匹配对手，使用遗传算法使选手进化，最终将优胜者的对局信息作为学习样例.