基于数据库自学习的中国象棋研究

刘霞 张建刚 邢胜

摘 要：象棋软件一般可以通过很多方法提高棋力，但最好的方法是优化数据结构、改进搜索方式，这两种方法都有很高的博弈水平，但机器学习能力都较差。以前应用数据库自学习的方法都存在很大的缺陷。文章通过将判断失误的关键着法和局面值存储到数据库中，从而使后面的象棋步骤当中相同局面时转变策略，避免相同的失误步骤，从而实现自学习能力。

关键词：数据库；博弈树搜索；关键着法

引言

目前，象棋软件大多数存在的问题是不具有自学习能力，以前主要应用提高数据结构和计算机运行速度的方式来改进象棋软件的水平，而很少应用通过数据库记录计算机下棋过程中好的着法和局面值的方法，这种方法可以使计算机在以后相同局面时，转变象棋软件策略，不重复失败的老路，实现自学习能力。

1 棋类游戏典型的自学习方法

目前，自学习能力的实现方法有很多种，最主要有两种：一是应用加强的学习方法（包括三个方面：加强学习与神经网络相结合、同数据库结合以及瞬时差分TD算法）；二是自适应遗传算法，其中重点是加强学习的TD方法。

1.1 加强学习同神经网络结合（RBP）

在计算机棋类软件的发展过程中，机器自学习能力的发展有着成功的应用，比如Gerald Tesauro在1995年推出的西洋双陆棋TD-Gammon。通过150万盘比赛，最后取得世界冠军的水平。国内也有这方面的相关研究，王一非，哈尔滨工程大学硕士，2007年在其毕业论文中详细的说明并提出了应用RBP的缺点：神经网络运算量太大，自学习过程时间长，收敛时间过慢。

1.2 加强学习同数据库结合

长沙理工大学硕士付强2006年在其论文《基于激励学习的中国象棋研究》中已经提出了将象棋软件和数据库结合的方法，记录最好着法值，来提高自学习能力。经过1万多盘比赛结果，已经下败了传统软件。

1.3 瞬时差分TD 算法

早在1999年，ChrisSzeto就提出瞬时差分TD算法来优化棋类软件。经过多次游戏实验，将修正后的棋子子力值保存到数据库中，比之前通过经验与试算估计的方法更容易取得比赛的胜利，说明起到了优化作用。

2 基于数据库自学习的原理及实现

我们对过去的方法进行改进。通过博弈树搜索，利用数据库记录计算机不同的对手着法，只记录计算机输棋的情况，将搜索值赋给计算机存储。当计算机在以后的比赛中遇到此局面时，做出战略调整。从而实现象棋软件的自学习功能。这种方法尤其在计算机输棋时，就要向下多搜两层，所以值会更精确，值会更小，因为博弈树是最大最小搜索，具体解决方案如图1所示。

对比原方法：此方案中三角代表原来的方法，整个图代表应用数据库后由原来第五层值变成了现在的第七层值，如此以来就多搜了两层，所得值更小，更精确。

通过博弈树的最大最小值搜索，所以当深色方框的值更小时，它必被上层取最小值的圆所选中，而又因为它的值小，在更上层取最大值时会被舍去，所以不会运行最左边的方案，从而转变策略，实现了象棋软件的自学习能力。实验中整盘棋会有很多种局面，如果按图1方案，一开始就需要转变策略，但实际上不必开局转变。所以就需要判断哪些是失败的关键着法，需要对记录着法分析局面值，有所选择，将影响大的值保留下来，其他影响小的不做记录，这样不仅缩小了数据库，而且让策略的转变发生在最合适时。通过实验得出，分别对正值，负值，最接近0的值进行了实验，正值是代表胜利，负值代表输棋，0值基本代表平局。通过实验分析，最后选取的关键着法值即为第一次出现劣势且之后的棋无可挽回的下到输的着法。

3 实验结果及分析

黑‘×表示每一局面值，蓝‘○表示不同着法的局面值

此方法证实了它的自学习能力，采用王小春的象棋软件和应用数据库象棋软件对弈。数据库象棋软件又分为存储全部不同着法和存储关键着法。图2所示的是数据库软件先行，同王小春的象棋软件对弈输棋的存储值，黑点表示对弈31盘的评估值，蓝圈表示存储全部不同着法中16个不同值。存储关键着法中存储的是第四个篮圈值即第一次下降且以后没有更高值的点。

第一局对弈，先行的数据库象棋软件输给了王晓春的象棋软件。数据库象棋软件将遇到的局面值存储到数据库中；第二局对弈，存储关键着法通过记录的关键着法获胜，图3线上的点显示的是对弈赢棋的局面值；存储全部不同着法一开始就改变策略，实施的着法是上一盘的对称着法，所以又下输了。第三局对弈，存储全部不同着法也赢了王晓春的象棋软件。经上述实验表明在计算机输棋局面下，通过数据库搜索博弈树，将值赋给此着法。同时只记录关键着法，以减小数据库规模，具有更好的自学习能力。

参考文献

[1]Shi-Jim Yen， Jr-Chang Chen， Tai-Ning Yang， Shun-Chin Hsu， Computer Chinese Chess， ICGA Journal， March 2004.

[2]徐心和，王骄.中国象棋计算机博弈关键技术分析[J].小型微型计算机系统，2006，27（6）：961-965.

[3]许舜钦.电脑西洋棋和电脑象棋的回顾与前瞻[J].电脑学刊，1990，2（2）.

[4]付强，陈焕文.中国象棋人机对弈的自学习方法研究[J].计算机技术与发展，2007，17（12）.

[5]付强，陈焕文.基于RL算法的自学习博弈程序设计及实现[J].长沙理工大学学报，2007.12（4）：73-78.