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

鄧丁朋　孟坤

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.

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