鄧丁朋　孟坤

1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京　2，北京信息科技大學(xué)，計(jì)算機(jī)學(xué)院，講師，北京

?

在線棋牌用戶智能化等級(jí)評(píng)定算法研究

鄧丁朋1孟坤2

1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京2，北京信息科技大學(xué)，計(jì)算機(jī)學(xué)院，講師，北京

摘要：在線棋牌游戲擁有巨大用戶群，一方面是由于棋牌游戲擁有良好的群眾基礎(chǔ)，早已成為日常休閑的重要選擇之一；另一方面，在線棋牌游戲?qū)Y源要求較少，可以為各種媒介所承載，使用和訪問(wèn)門檻較低。保證用戶體驗(yàn)質(zhì)量，提高用戶黏性是在線棋牌游戲運(yùn)營(yíng)商密切關(guān)注的問(wèn)題。主要工作集中在提供性能較高、使用友好的對(duì)弈平臺(tái)，和用戶喜好智能分析識(shí)別引擎。前者在于提高用戶的操作和視覺快感；后者在于針對(duì)性推薦對(duì)弈智能算法（包括在線對(duì)弈人員的配對(duì)）。本文旨在給出一種基于大數(shù)據(jù)的用戶水平快速識(shí)別算法，并以西洋跳棋為例分析該算法實(shí)現(xiàn)的可能性和有效性。

1　介紹

計(jì)算機(jī)博弈被認(rèn)為是人工智能領(lǐng)域最具有挑戰(zhàn)性的研究方向之一。人工智能的先驅(qū)們?cè)砻?，如果掌握了下棋的本質(zhì)，續(xù)頁(yè)就掌握了人類智能行為的核心，計(jì)算機(jī)博弈為人工智能提供了一個(gè)良好的實(shí)驗(yàn)場(chǎng)所。近些年隨著人們?cè)絹?lái)越對(duì)計(jì)算機(jī)博弈的重視，計(jì)算機(jī)博弈也取得了很大的發(fā)展。計(jì)算機(jī)博弈是既簡(jiǎn)單方便、經(jīng)濟(jì)實(shí)用，又具有豐富內(nèi)涵、變化無(wú)窮的思維邏輯的研究載體。個(gè)把小時(shí)就可以下一盤棋，就可以對(duì)電腦的“智能”進(jìn)行測(cè)試，而且可以悔棋、重試、復(fù)盤，并可以一步步地發(fā)現(xiàn)電腦與人腦功能的差距，通過(guò)不斷提高電腦的智力水平。在計(jì)算機(jī)博弈系統(tǒng)的基礎(chǔ)上是可以開展一系列人工智能領(lǐng)域的科學(xué)研究。因此，有人將計(jì)算機(jī)博弈比作是人工智能學(xué)科的“果蠅”，是研究人類思維和實(shí)現(xiàn)機(jī)器思維最好的實(shí)驗(yàn)載體。

人們主要的研究方向?yàn)閷?duì)博弈中，搜索算法、評(píng)估函數(shù)、以及機(jī)器學(xué)習(xí)算法等的研究，但是這些算法忽略了一個(gè)問(wèn)題，那就是對(duì)等級(jí)評(píng)定算法的研究。在線博弈是一個(gè)新興的一種博弈方式，通過(guò)在線的方式來(lái)決定雙方博弈水平的高低，所以一個(gè)好的等級(jí)評(píng)定算法會(huì)起到一個(gè)很重要的作用。而且在線博弈要求對(duì)對(duì)方的棋藝要非常了解，要讓對(duì)方有輸有贏，這樣才會(huì)產(chǎn)生用戶的連續(xù)性。而近階段，人們對(duì)這方面的重視度遠(yuǎn)遠(yuǎn)不夠。

2　已有的成果

對(duì)于用戶水平的識(shí)別，人們現(xiàn)在也有了一定的成果如，通過(guò)和對(duì)方進(jìn)行若干次博弈，計(jì)算勝負(fù)率來(lái)判定；通過(guò)機(jī)器學(xué)習(xí)來(lái)評(píng)估對(duì)方的水平等等，并且人們?cè)谒阉魉惴ㄉ弦约皺C(jī)器學(xué)習(xí)上等都有了一定的成績(jī)。在搜索算法上，已有極大極小搜索算法，Alpha-Beta搜索算法，負(fù)極大值搜索算法，基于蒙特卡洛模擬的博弈樹搜索算法等，在評(píng)估函數(shù)上，更好更合理的設(shè)計(jì)方式也被人民所運(yùn)用。

3　算法依賴關(guān)系

西洋跳棋作為一款集益智，休閑為一體的古老的游戲，和我們常見跳棋游戲不同的是，西洋跳棋在棋盤上、棋子形狀、游戲規(guī)則等有很大區(qū)別。他的規(guī)則十分簡(jiǎn)單，游戲雙方在10*10（另有8*8）的的棋盤上進(jìn)行對(duì)弈，黑方先走，黑方和紅方各有20枚棋子。比賽規(guī)則：

1.在整個(gè)對(duì)弈過(guò)程中，白格子是用不到的，棋子自始至終都是在黑格子中沿對(duì)角線方向移動(dòng)和停止。對(duì)弈的目標(biāo)是對(duì)方所有的棋子吃掉或者形成一個(gè)局面逼使對(duì)方棋子不能移動(dòng)；

2.只要在對(duì)角線方向鄰近的黑格內(nèi)有對(duì)方的棋子并且在過(guò)去的黑格是空位，就可以跳過(guò)對(duì)方的棋子并且吃掉，這種稱為跳吃，如果沒(méi)有這種著法，那就只能沿著對(duì)角線方向移動(dòng)一格。跳吃的時(shí)候，在具有多種選擇的情況下，必須選擇吃子數(shù)量最多的著法，如果不止一個(gè)棋子或者不止一個(gè)路線，可以在跳吃對(duì)方同樣最多的棋子，玩家可以自主選擇哪個(gè)棋子或者向哪個(gè)方向前進(jìn)。

3.任何一個(gè)棋子達(dá)到了對(duì)方底線并且停止在對(duì)方底線上的棋子便立刻加冕，從此以后便成為了王，這時(shí)這顆棋子便和普通棋子有所區(qū)別，“王”可以在對(duì)角線上移動(dòng)任意多個(gè)空格，同樣，在跳吃的時(shí)候，“王”可以跳過(guò)對(duì)方棋子前后任意數(shù)量的空格，但是一般棋子是可以吃掉王的。

4.未加冕的棋子只能向前移動(dòng)，但是跳著吃，連續(xù)跳吃，這種時(shí)候可以是向前、向后或者前后組合。

西洋跳棋的程序結(jié)構(gòu)和算法依賴關(guān)系如下：

通過(guò)棋類規(guī)則來(lái)制定搜索函數(shù)來(lái)確定棋的走位，通過(guò)評(píng)估函數(shù)來(lái)評(píng)估棋盤的狀態(tài)，把數(shù)值賦予到搜索函數(shù)之中來(lái)更新走法，其中也可以加上機(jī)器學(xué)習(xí)算法來(lái)幫助評(píng)估函數(shù)賦予的精確，最后通過(guò)等級(jí)評(píng)定來(lái)確定對(duì)方的水平的優(yōu)劣，把評(píng)估值賦予到評(píng)估函數(shù)之中，在搜索函數(shù)上可以運(yùn)用多種搜索算法，如Alpha-Beta搜索算法，極大極小值算法等。

4　用戶識(shí)別算法

筆者設(shè)計(jì)的等級(jí)評(píng)定算法根據(jù)棋盤狀態(tài)來(lái)判定如下：

4.1棋子位置評(píng)估值，棋子靈活度評(píng)估值

同樣一個(gè)棋子，處在棋盤的不同位置上其價(jià)值大小不大相同，想法是把這些可行性的位置給出評(píng)估值，比如當(dāng)對(duì)方的棋子成王時(shí)，給的權(quán)值就相對(duì)較高，當(dāng)對(duì)方棋子處于出狀態(tài)時(shí)，權(quán)值為0.根據(jù)下棋經(jīng)驗(yàn)，筆者設(shè)計(jì)的評(píng)估矩陣如圖：

這些評(píng)估值的賦予，大致顯示的哪些位置的重要性，不僅僅對(duì)于進(jìn)攻對(duì)方，對(duì)于防守也是很有意義的，權(quán)值賦予的準(zhǔn)不準(zhǔn)確也是評(píng)判算法優(yōu)劣的一種方式。

4.2一些情況下的棋子的評(píng)估值

1）當(dāng)棋子成王時(shí)，給予棋子所在方外加150分（依次遞推），因?yàn)槌赏醯钠遄拥淖叻ㄊ朱`活，戰(zhàn)斗力也十分驚人。

2）連吃的情況下給予加分30分（依次遞推），因?yàn)閷?duì)方少了棋子，這時(shí)對(duì)方在理論上上是減分的，而自己在加分，這種情況在客觀上也符合判斷。

3）當(dāng)自己的棋子的最后一排走出去了應(yīng)該給予減分30，因?yàn)檫@為對(duì)方成王提供了機(jī)會(huì)，二自己走出去的棋子還沒(méi)有達(dá)到最優(yōu)位置。

4.3權(quán)值的使用

根據(jù)這些權(quán)值，在對(duì)弈中，把權(quán)值相加，每一個(gè)狀態(tài)都會(huì)對(duì)應(yīng)一個(gè)權(quán)值，于是就會(huì)生成一個(gè)權(quán)值元組或者叫做數(shù)組，找到這個(gè)組的數(shù)的最大值就能評(píng)判對(duì)方的水平，理由如下:

1.首先給權(quán)值設(shè)置一個(gè)范圍比如100-150為一段，150-200為二段，200-250為三段等等。當(dāng)棋子能夠達(dá)到這一個(gè)水平的時(shí)，比如達(dá)到二段，這時(shí)如果對(duì)方是一段的話，那么棋子就會(huì)占據(jù)很大的優(yōu)勢(shì)，或者說(shuō)優(yōu)勢(shì)十分明顯，而如果這時(shí)對(duì)方是三段的話或者更高，則處于劣勢(shì)，應(yīng)該及時(shí)調(diào)整策略，追趕對(duì)方的權(quán)值。

2.矩陣中權(quán)值的給予能體現(xiàn)每一個(gè)棋格的重要性，某一狀態(tài)下，你的權(quán)值越高，說(shuō)明你的棋處于進(jìn)攻狀態(tài)下的棋子多與對(duì)方的棋子，很明顯，勝算也就大，換句話說(shuō)水平是高于對(duì)方的。

比賽結(jié)束時(shí)，一個(gè)數(shù)組里的數(shù)的最大值能夠體現(xiàn)這個(gè)棋子的水平是因?yàn)樗谀骋粻顟B(tài)下能夠達(dá)到自己棋的最高水平，而這個(gè)水平的到達(dá)完全是根據(jù)棋子的算法、走法策略以及評(píng)估函數(shù)所決定的，不具備偶然性，是這個(gè)棋子算法性能上的體現(xiàn)。

4.44總結(jié)

要想把這些棋子的權(quán)值的賦予精確，需要大量的實(shí)驗(yàn)，大量的數(shù)據(jù)來(lái)分析，這里我給的僅僅是大致的趨勢(shì)。但是在一定意義上是具備合理性的。

5　評(píng)估矩陣的選?。ㄎ恢脵?quán)重）

位置權(quán)重的選擇需要自己有著大量對(duì)西洋跳棋的了解。值的選取是筆者在根據(jù)自己在進(jìn)行大量下棋的過(guò)程中，直觀的選取。

5.1筆者選取的規(guī)則

很明顯在一行中，中間的位置上權(quán)值要大于兩邊的權(quán)值，理由是中間的棋子走法基本比兩邊的多，而且中間棋子一旦被吃掉，那么邊上的棋子的局勢(shì)也就很不明朗；前排的棋子的權(quán)值普遍高于后排的（最后一排除外），因?yàn)榍芭诺钠遄右坏┍怀缘?，那么后排的也危在旦夕，但是最后一排之所以不符合這個(gè)規(guī)律是因?yàn)樽詈笠慌乓坏┢遄幼邉?dòng)，那么對(duì)方的棋子就很容易成王而對(duì)自己造成更大的損失。

這種選取一定是不太準(zhǔn)確，存在一定的誤差，那么如何調(diào)整這些參數(shù)，使得權(quán)值的選取更加的準(zhǔn)確，更加的合理。

5.2筆者的想法如下

根據(jù)大量的下棋數(shù)據(jù)來(lái)更改變化這些權(quán)值，核心思想是：在比賽中，如果對(duì)方贏了，那么你的權(quán)值數(shù)組里面的最大值一定要確保小于對(duì)方權(quán)值數(shù)組里的最大值，這樣才能保證結(jié)果合理。

6　實(shí)驗(yàn)分析

算法處理過(guò)程特別能夠體現(xiàn)算法是不是能夠得到合理高效的利用，筆者給出的處理過(guò)程如下：

目前需要的數(shù)據(jù)是，和對(duì)方(不同博弈水平的棋子)進(jìn)行大量的對(duì)弈，獲取雙方的權(quán)值數(shù)組以及比賽的輸贏結(jié)果并且還要把不同博弈水平的棋子進(jìn)行對(duì)弈獲得輸贏結(jié)果和權(quán)值數(shù)組。處理過(guò)程為：

如果自己的棋勝于對(duì)方，那么再取一組數(shù)據(jù)，使那個(gè)棋的水平高于自己，為了方便說(shuō)明情況，做如下命名，自己的棋為a,水平高于自己的棋為b，水平低于自己的棋為c，”<”表示符號(hào)左邊的棋輸，符號(hào)右邊的贏。根據(jù)剛才說(shuō)的情況，即選取的棋子特征如下：c

二分法運(yùn)用如下：假如取（n+1）組數(shù)據(jù)，那么就會(huì)有小于n*(n-1)/2組對(duì)比數(shù)據(jù)，選擇符合二分法條件的進(jìn)行如上處理，算法實(shí)現(xiàn)上可用遞推的方式。

注：由于取值數(shù)量比較大，所以每一次更改權(quán)值一定是微調(diào)，幅度不宜過(guò)大。

77　總結(jié)

筆者這種算法是一種比較經(jīng)濟(jì)的算法，由于是基于在線博弈的，所以很容易獲取大量的數(shù)據(jù)，通過(guò)這些數(shù)據(jù)來(lái)調(diào)整游戲的等級(jí)評(píng)定算法，進(jìn)而優(yōu)化用戶體驗(yàn)。在線博弈是一種商業(yè)的行為，游戲公司通過(guò)編寫高質(zhì)量的棋盤游戲等，來(lái)獲取用戶體驗(yàn)，進(jìn)而得到大量用戶，所以一個(gè)好的用戶體驗(yàn)?zāi)軌蛟黾佑脩魯?shù)量，以此來(lái)獲得效益，本文通過(guò)對(duì)等級(jí)評(píng)定算法的研究，來(lái)評(píng)估用戶的博弈水平，讓用戶在對(duì)弈的時(shí)候輸贏得當(dāng)。

注: 本文由市教委“PXM2015_014224_000050本科生培養(yǎng)-大學(xué)生科研訓(xùn)練(市級(jí))”項(xiàng)目和“感知與計(jì)算智能聯(lián)合實(shí)驗(yàn)室”經(jīng)費(fèi)支持

參考文獻(xiàn)

[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]《計(jì)算機(jī)博弈算法實(shí)驗(yàn)》講義李淑琴 2013.12

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

關(guān)鍵字：計(jì)算機(jī)博弈等級(jí)評(píng)定算法 西洋跳棋 博弈水平快速識(shí)別算法 人工智能 在線博弈。