鄧丁朋　孟坤

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

?

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

鄧丁朋1孟坤2

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

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

1　介紹

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

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

2　已有的成果

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

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

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

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

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

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

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

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

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

4　用戶識別算法

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

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

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

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

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

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

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

3）當(dāng)自己的棋子的最后一排走出去了應(yīng)該給予減分30，因為這為對方成王提供了機會，二自己走出去的棋子還沒有達到最優(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)棋子能夠達到這一個水平的時，比如達到二段，這時如果對方是一段的話，那么棋子就會占據(jù)很大的優(yōu)勢，或者說優(yōu)勢十分明顯，而如果這時對方是三段的話或者更高，則處于劣勢，應(yīng)該及時調(diào)整策略，追趕對方的權(quán)值。

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

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

4.44總結(jié)

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

5　評估矩陣的選取（位置權(quán)重）

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

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ù)是，和對方(不同博弈水平的棋子)進行大量的對弈，獲取雙方的權(quán)值數(shù)組以及比賽的輸贏結(jié)果并且還要把不同博弈水平的棋子進行對弈獲得輸贏結(jié)果和權(quán)值數(shù)組。處理過程為：

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

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

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

77　總結(jié)

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

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

參考文獻

[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.

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