鄧丁朋　孟坤

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

?

在線棋牌用戶智能化等級評定算法研究

鄧丁朋1孟坤2

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

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

1　介紹

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

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

2　已有的成果

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

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

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

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

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

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

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

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

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

4　用戶識別算法

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

4.1棋子位置評估值，棋子靈活度評估值

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

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

4.2一些情況下的棋子的評估值

1）當(dāng)棋子成王時，給予棋子所在方外加150分（依次遞推），因為成王的棋子的走法十分靈活，戰(zhàn)斗力也十分驚人。

2）連吃的情況下給予加分30分（依次遞推），因為對方少了棋子，這時對方在理論上上是減分的，而自己在加分，這種情況在客觀上也符合判斷。

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

4.3權(quán)值的使用

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

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

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

比賽結(jié)束時，一個數(shù)組里的數(shù)的最大值能夠體現(xiàn)這個棋子的水平是因為他在某一狀態(tài)下能夠達(dá)到自己棋的最高水平，而這個水平的到達(dá)完全是根據(jù)棋子的算法、走法策略以及評估函數(shù)所決定的，不具備偶然性，是這個棋子算法性能上的體現(xiàn)。

4.44總結(jié)

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

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

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

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

很明顯在一行中，中間的位置上權(quán)值要大于兩邊的權(quán)值，理由是中間的棋子走法基本比兩邊的多，而且中間棋子一旦被吃掉，那么邊上的棋子的局勢也就很不明朗；前排的棋子的權(quán)值普遍高于后排的（最后一排除外），因為前排的棋子一旦被吃掉，那么后排的也危在旦夕，但是最后一排之所以不符合這個規(guī)律是因為最后一排一旦棋子走動，那么對方的棋子就很容易成王而對自己造成更大的損失。

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

5.2筆者的想法如下

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

6　實驗分析

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

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

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

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

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

77　總結(jié)

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

注: 本文由市教委“PXM2015_014224_000050本科生培養(yǎng)-大學(xué)生科研訓(xùn)練(市級)”項目和“感知與計算智能聯(liá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ī)博弈算法實驗》講義李淑琴 2013.12

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

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