在线棋牌用户智能化等级评定算法研究

邓丁朋　孟坤

1.北京信息科技大学 计算机学院，北京　2，北京信息科技大学，计算机学院，讲师，北京



在线棋牌用户智能化等级评定算法研究

邓丁朋1孟坤2

1.北京信息科技大学 计算机学院，北京2，北京信息科技大学，计算机学院，讲师，北京

摘要：在线棋牌游戏拥有巨大用户群，一方面是由于棋牌游戏拥有良好的群众基础，早已成为日常休闲的重要选择之一；另一方面，在线棋牌游戏对资源要求较少，可以为各种媒介所承载，使用和访问门槛较低。保证用户体验质量，提高用户黏性是在线棋牌游戏运营商密切关注的问题。主要工作集中在提供性能较高、使用友好的对弈平台，和用户喜好智能分析识别引擎。前者在于提高用户的操作和视觉快感；后者在于针对性推荐对弈智能算法（包括在线对弈人员的配对）。本文旨在给出一种基于大数据的用户水平快速识别算法，并以西洋跳棋为例分析该算法实现的可能性和有效性。

1　介绍

计算机博弈被认为是人工智能领域最具有挑战性的研究方向之一。人工智能的先驱们曾表明，如果掌握了下棋的本质，续页就掌握了人类智能行为的核心，计算机博弈为人工智能提供了一个良好的实验场所。近些年随着人们越来越对计算机博弈的重视，计算机博弈也取得了很大的发展。计算机博弈是既简单方便、经济实用，又具有丰富内涵、变化无穷的思维逻辑的研究载体。个把小时就可以下一盘棋，就可以对电脑的“智能”进行测试，而且可以悔棋、重试、复盘，并可以一步步地发现电脑与人脑功能的差距，通过不断提高电脑的智力水平。在计算机博弈系统的基础上是可以开展一系列人工智能领域的科学研究。因此，有人将计算机博弈比作是人工智能学科的“果蝇”，是研究人类思维和实现机器思维最好的实验载体。

人们主要的研究方向为对博弈中，搜索算法、评估函数、以及机器学习算法等的研究，但是这些算法忽略了一个问题，那就是对等级评定算法的研究。在线博弈是一个新兴的一种博弈方式，通过在线的方式来决定双方博弈水平的高低，所以一个好的等级评定算法会起到一个很重要的作用。而且在线博弈要求对对方的棋艺要非常了解，要让对方有输有赢，这样才会产生用户的连续性。而近阶段，人们对这方面的重视度远远不够。

2　已有的成果

对于用户水平的识别，人们现在也有了一定的成果如，通过和对方进行若干次博弈，计算胜负率来判定；通过机器学习来评估对方的水平等等，并且人们在搜索算法上以及机器学习上等都有了一定的成绩。在搜索算法上，已有极大极小搜索算法，Alpha-Beta搜索算法，负极大值搜索算法，基于蒙特卡洛模拟的博弈树搜索算法等，在评估函数上，更好更合理的设计方式也被人民所运用。

3　算法依赖关系

西洋跳棋作为一款集益智，休闲为一体的古老的游戏，和我们常见跳棋游戏不同的是，西洋跳棋在棋盘上、棋子形状、游戏规则等有很大区别。他的规则十分简单，游戏双方在10*10（另有8*8）的的棋盘上进行对弈，黑方先走，黑方和红方各有20枚棋子。比赛规则：

1.在整个对弈过程中，白格子是用不到的，棋子自始至终都是在黑格子中沿对角线方向移动和停止。对弈的目标是对方所有的棋子吃掉或者形成一个局面逼使对方棋子不能移动；

2.只要在对角线方向邻近的黑格内有对方的棋子并且在过去的黑格是空位，就可以跳过对方的棋子并且吃掉，这种称为跳吃，如果没有这种着法，那就只能沿着对角线方向移动一格。跳吃的时候，在具有多种选择的情况下，必须选择吃子数量最多的着法，如果不止一个棋子或者不止一个路线，可以在跳吃对方同样最多的棋子，玩家可以自主选择哪个棋子或者向哪个方向前进。

3.任何一个棋子达到了对方底线并且停止在对方底线上的棋子便立刻加冕，从此以后便成为了王，这时这颗棋子便和普通棋子有所区别，“王”可以在对角线上移动任意多个空格，同样，在跳吃的时候，“王”可以跳过对方棋子前后任意数量的空格，但是一般棋子是可以吃掉王的。

4.未加冕的棋子只能向前移动，但是跳着吃，连续跳吃，这种时候可以是向前、向后或者前后组合。

西洋跳棋的程序结构和算法依赖关系如下：

通过棋类规则来制定搜索函数来确定棋的走位，通过评估函数来评估棋盘的状态，把数值赋予到搜索函数之中来更新走法，其中也可以加上机器学习算法来帮助评估函数赋予的精确，最后通过等级评定来确定对方的水平的优劣，把评估值赋予到评估函数之中，在搜索函数上可以运用多种搜索算法，如Alpha-Beta搜索算法，极大极小值算法等。

4　用户识别算法

笔者设计的等级评定算法根据棋盘状态来判定如下：

4.1棋子位置评估值，棋子灵活度评估值

同样一个棋子，处在棋盘的不同位置上其价值大小不大相同，想法是把这些可行性的位置给出评估值，比如当对方的棋子成王时，给的权值就相对较高，当对方棋子处于出状态时，权值为0.根据下棋经验，笔者设计的评估矩阵如图：

这些评估值的赋予，大致显示的哪些位置的重要性，不仅仅对于进攻对方，对于防守也是很有意义的，权值赋予的准不准确也是评判算法优劣的一种方式。

4.2一些情况下的棋子的评估值

1）当棋子成王时，给予棋子所在方外加150分（依次递推），因为成王的棋子的走法十分灵活，战斗力也十分惊人。

2）连吃的情况下给予加分30分（依次递推），因为对方少了棋子，这时对方在理论上上是减分的，而自己在加分，这种情况在客观上也符合判断。

3）当自己的棋子的最后一排走出去了应该给予减分30，因为这为对方成王提供了机会，二自己走出去的棋子还没有达到最优位置。

4.3权值的使用

根据这些权值，在对弈中，把权值相加，每一个状态都会对应一个权值，于是就会生成一个权值元组或者叫做数组，找到这个组的数的最大值就能评判对方的水平，理由如下:

1.首先给权值设置一个范围比如100-150为一段，150-200为二段，200-250为三段等等。当棋子能够达到这一个水平的时，比如达到二段，这时如果对方是一段的话，那么棋子就会占据很大的优势，或者说优势十分明显，而如果这时对方是三段的话或者更高，则处于劣势，应该及时调整策略，追赶对方的权值。

2.矩阵中权值的给予能体现每一个棋格的重要性，某一状态下，你的权值越高，说明你的棋处于进攻状态下的棋子多与对方的棋子，很明显，胜算也就大，换句话说水平是高于对方的。

比赛结束时，一个数组里的数的最大值能够体现这个棋子的水平是因为他在某一状态下能够达到自己棋的最高水平，而这个水平的到达完全是根据棋子的算法、走法策略以及评估函数所决定的，不具备偶然性，是这个棋子算法性能上的体现。

4.44总结

要想把这些棋子的权值的赋予精确，需要大量的实验，大量的数据来分析，这里我给的仅仅是大致的趋势。但是在一定意义上是具备合理性的。

5　评估矩阵的选取（位置权重）

位置权重的选择需要自己有着大量对西洋跳棋的了解。值的选取是笔者在根据自己在进行大量下棋的过程中，直观的选取。

5.1笔者选取的规则

很明显在一行中，中间的位置上权值要大于两边的权值，理由是中间的棋子走法基本比两边的多，而且中间棋子一旦被吃掉，那么边上的棋子的局势也就很不明朗；前排的棋子的权值普遍高于后排的（最后一排除外），因为前排的棋子一旦被吃掉，那么后排的也危在旦夕，但是最后一排之所以不符合这个规律是因为最后一排一旦棋子走动，那么对方的棋子就很容易成王而对自己造成更大的损失。

这种选取一定是不太准确，存在一定的误差，那么如何调整这些参数，使得权值的选取更加的准确，更加的合理。

5.2笔者的想法如下

根据大量的下棋数据来更改变化这些权值，核心思想是：在比赛中，如果对方赢了，那么你的权值数组里面的最大值一定要确保小于对方权值数组里的最大值，这样才能保证结果合理。

6　实验分析

算法处理过程特别能够体现算法是不是能够得到合理高效的利用，笔者给出的处理过程如下：

目前需要的数据是，和对方(不同博弈水平的棋子)进行大量的对弈，获取双方的权值数组以及比赛的输赢结果并且还要把不同博弈水平的棋子进行对弈获得输赢结果和权值数组。处理过程为：

如果自己的棋胜于对方，那么再取一组数据，使那个棋的水平高于自己，为了方便说明情况，做如下命名，自己的棋为a,水平高于自己的棋为b，水平低于自己的棋为c，”<”表示符号左边的棋输，符号右边的赢。根据刚才说的情况，即选取的棋子特征如下：c

二分法运用如下：假如取（n+1）组数据，那么就会有小于n*(n-1)/2组对比数据，选择符合二分法条件的进行如上处理，算法实现上可用递推的方式。

注：由于取值数量比较大，所以每一次更改权值一定是微调，幅度不宜过大。

77　总结

笔者这种算法是一种比较经济的算法，由于是基于在线博弈的，所以很容易获取大量的数据，通过这些数据来调整游戏的等级评定算法，进而优化用户体验。在线博弈是一种商业的行为，游戏公司通过编写高质量的棋盘游戏等，来获取用户体验，进而得到大量用户，所以一个好的用户体验能够增加用户数量，以此来获得效益，本文通过对等级评定算法的研究，来评估用户的博弈水平，让用户在对弈的时候输赢得当。

注: 本文由市教委“PXM2015_014224_000050本科生培养-大学生科研训练(市级)”项目和“感知与计算智能联合实验室”经费支持

参考文献

[1]Introducing Individual and Social LearningInto Evolutionary Checkers Belal Al-Khateeb and Graham Kendall, Senior Member, IEEE 2012

[2]Checkers Is Solved Jonathan Schaeffer, et al.Science 317, 1518 (2007);

[3]《计算机博弈算法实验》讲义李淑琴 2013.12

[4]算法.第4版[美]Robert Sedgewick，[美] Kevin Wayne著，人民邮电出版社 2012.

关键字：计算机博弈等级评定算法 西洋跳棋 博弈水平快速识别算法 人工智能 在线博弈。