計算機藏式夾棋博弈系統(tǒng)中局面估值方法的研究

尕藏扎西 安見才讓

摘? 要： 局面估值或局面評估是計算機博弈系統(tǒng)的核心部分之一。良好的評估函數(shù)才能對局勢作出客觀的判斷，較快地的找到最佳走法，讓計算機博弈系統(tǒng)看得更準。針對藏式夾棋的博弈問題，提出一種結(jié)合藏式夾棋棋規(guī)的靜態(tài)評估函數(shù)和結(jié)合MC的動態(tài)評估函數(shù)。對兩種評估函數(shù)的準確率和效率進行了對比測試。

關(guān)鍵詞： 計算機博弈; 藏式夾棋; 靜態(tài)評估; 動態(tài)評估

中圖分類號：TP391.1? ? ? ? ? 文獻標志碼：A? ? ?文章編號：1006-8228（2019）09-61-03

Research on situation evaluation method in computer Tibetan chess game system

Gaznag zhaxi，? Anjian Cairang

（School of Computing，Qinghai University for Nationalities， Xining， Qinghai 810007， China）

Abstract： Situational valuation or situation assessment is one of the core parts of the computer game system. A good evaluation function can make an objective judgment on the situation， and ensure to find the best way to make the computer game system more accurate. Aiming at the game problem of Tibetan chess， this paper proposes a static evaluation function combined with Tibetan chess rules and a dynamic evaluation function combined with MC. The accuracy and efficiency of the two evaluation functions are compared and tested.

Key words： computer game; Tibetan chess; static evaluation; dynamic evaluation

0 引言

計算機博弈是人工智能研究的重要載體，也是目前最具挑戰(zhàn)性的研究方向之一，人工智能的快速發(fā)展極大地推動了科技進步和社會發(fā)展[1]。國內(nèi)外計算機圍棋、國際象棋、亞馬孫棋等等研究已成熟[2，9]。而計算機藏棋領(lǐng)域的研究才剛剛起步，還面臨著很大的挑戰(zhàn)。藏式夾棋搜索空間大、下棋規(guī)則多、盤面變化快。研究搜索藏式夾棋博弈和局面評估函數(shù)有很大的技術(shù)挑戰(zhàn)和意義。與搜索算法一樣，評估函數(shù)也是計算機博弈系統(tǒng)最核心的部分，它的好壞影響著今后局勢的發(fā)展趨勢。如果說搜索引擎是讓程序看得更遠，那么評估函數(shù)則是讓程序看得更準。

本文根據(jù)藏式夾棋本身的規(guī)則，提出一種靜態(tài)評估函數(shù)與MC算法結(jié)合的適合于藏式夾棋博弈系統(tǒng)的動態(tài)評估方法。可為實現(xiàn)較高博弈水平的藏式夾棋博弈系統(tǒng)打下基礎(chǔ)。

1 藏式夾棋評估標準

1.1 子力

在藏式夾棋中，單個棋子來講，每個棋子的作用都差不多，棋子的影響力更多的取決于它周圍的環(huán)境，和該棋子連接或距離較近的己方棋子和空位置都是決定其影響力的因素，它會受哪些棋子的影響，這些棋子對它的影響力的范圍值是多少，具體如何等。

1.2 位置

位于棋盤不同位置的棋子，即使其子力相同，其作用可能差別很大。在藏式夾棋中，棋子之間的相對位置是衡量其作用的一個關(guān)鍵。在棋盤中有些點是縱橫線的交叉點和兩個對角線的交叉點，因此這種點會影響八個方向或會受到八個方向的影響。而有的點只是對角線的交叉點或棋盤邊線上的點，這些點的影響力相對較小。

1.3 機動

在藏式夾棋中，機動性的概念也有重要體現(xiàn)。藏式夾棋中的一塊棋，如果周圍有較開闊的擴展空間，或者可以方便地自己的其他棋塊中間相夾對方棋快，那么其機動性就較高;反之，如果一塊棋已被對方完全夾擊，其機動性就很小。

2 藏式夾棋局面估值方法

在評估棋局盤面時，通常存在兩個相互矛盾的因素：準確性高低與性能好壞。當評估越準確越全面時，計算機的博弈水平也自然而然的越高，但是時間對于博弈來說是很重要的約束條件，計算機博弈最好是既要保證一定的正確率來進行評估，也要盡可能多地訪問局面數(shù)，同時，當評估考慮到的因素越細致，就越能提高其準確性，但是會消耗大量計算時間，訪問的局面數(shù)就有所降低，從而影響搜索的深度與廣度[3]。對計算機博弈當前盤面的評估方法分為：靜態(tài)評估和動態(tài)評估。

2.1 靜態(tài)局面評估方法

藏式夾棋是一種較復(fù)雜的棋類，因此直接從整體上進行判斷或評估棋盤局面的話，其計算復(fù)雜性高而無法準確的判斷。因此，分塊組合是非常重要的一步。在本文中按棋規(guī)來各個規(guī)則分塊組合;我們在進行評估之前先對棋規(guī)則做一個分塊，然后再各個模塊被充分評估后，將各個模塊的評估結(jié)果綜合起來，得出整個盤面的一個評估值。

2.1.1 進攻值

在藏式夾棋中進攻方法主要是夾法和打槍法兩種。因此首先計算夾法的估值，在計算打槍法的估值。最后把兩個估值綜合起來，確定為最終的進攻值。夾法規(guī)則的估值計算公式如下：

[expJ=i=1nP（i）]? ⑴

[expJ]為夾法規(guī)則的進攻值，i為被夾的棋子號，n為被夾的總數(shù)。P（i）為對應(yīng)棋子的價值。在藏式夾棋中每個棋子的作用都差不多，因此在這里每個棋子的價值定義為1。

打槍規(guī)則的估值計算公式如下：

[expQ=j=1mP（j）]? ⑵

[expQ]為打槍規(guī)則的進攻值，j為已打槍的棋子號，m為被打槍的總數(shù)。P（j）為對應(yīng)棋子的價值（棋子的價值定義為1）。

按以上的夾法規(guī)則的進攻值和打槍規(guī)則的進攻值綜合為藏式夾棋的進攻值。藏式夾棋的進攻值計算公式為如下：

[expJQ=i=1nP（i）+j=1mP（j）? ? Pi=1，Pj=1]? ⑶

2.1.2 威脅值

所謂威脅值，就是當輪到對手方行棋時，己方棋子被對手棋子吃掉的可能性評估，亦即我方棋子受到對方棋子威脅的評估值，也稱對方對我方的威脅度。在藏式夾棋中對方對我方的威脅方式也是夾法和打槍法兩種。對方用夾法來威脅的估值計算公式如下：

[axpJ=i=1nP（i）]? ?⑷

[axpJ]為對方用夾法規(guī)則來威脅的估值，i為對方夾我方的棋子號，n為被夾的總數(shù)。P（i）為對應(yīng)棋子的價值。在評估函數(shù)時用來計算當前局面對我方有利的估值。因此，計算威脅值時，對方的每個棋子的價值設(shè)為-1。

對方用打槍規(guī)則威脅的估值計算公式如下：

[axpQ=j=1mP（j）]? ?⑸

[axpQ]為對方用打槍規(guī)則威脅的估值，j為對方已打槍的我方棋子號，m為被打槍的總數(shù)。P（j）為對應(yīng)棋子的價值（棋子的價值定義為-1）。

按以上對方用夾法規(guī)則的威脅值和打槍規(guī)則的威脅值綜合為藏式夾棋的威脅值。藏式夾棋的威脅值計算公式為如下：

[axpJQ=i=1nP（i）+j=1mP（j）? ?Pi=-1，Pj=-1]? ⑹

2.1.3 藏式夾棋的靜態(tài)估值方法

按以上談?wù)?，本文對藏式夾棋的靜態(tài)局面估值方法用了分塊組合的方法。首先計算了當前局面的進攻值，在計算當前局面對我方的威脅值。最后將進攻值和威脅值的綜合后確定為當前局面的評估值。藏式夾棋的靜態(tài)局面評估函數(shù)為如下：

[Evalboard=expJQ+axpJQ ]? ⑺

[expJQ]為當前局面的進攻值，[axpJQ]為當前局面的威脅值。

2.2 動態(tài)局面評估

評估算法其準確性將直接影響搜索算法的走向，也因此決定了博弈性能的優(yōu)劣[7]。靜態(tài)評估方法盡管具有一定的效果，但每個棋局的情況各不相同，應(yīng)對方法也不同，不可能只采用某一固定法則去套用所有可能的情況，總會有例外出現(xiàn)，最重要的是，我們現(xiàn)在還沒有找到一種非常準確的規(guī)則來能囊括所有可能遇到的問題[6]。通常決定靜態(tài)評估算法好壞的關(guān)鍵是我們對要解決的問題有非常清晰的認識，只有充分了解問題所在，才可能通過編程來解決。針對這種情況，蒙特卡羅（Monte Carlo，簡稱為MC）算法就是一種可供考慮的方法，它通過對當前局面下所有可以選擇的點進行大量模擬，得出勝負的統(tǒng)計概率，一般勝率較高的點就認為是可以選擇的較好的點[5]。

MC算法用于藏式夾棋中的思想是：當我們給定一個棋局時，程序會在當前所有可落子的位置中隨機選擇，并不斷重復(fù)這個過程，直到對弈結(jié)束，再把最終結(jié)果記錄下來，作為對當前局面的評估依據(jù)，即通過盡可能多的統(tǒng)計模擬棋局的結(jié)果來評估當前局面的好壞。相對于靜態(tài)評估，MC算法是一種動態(tài)搜索算法[4]。對于每個局面，可下的點最多不超過40個（棋盤上的交叉點總數(shù)），在這些點中可以比較容易的找到一些明顯更好的點。因此，當模擬次數(shù)達到一定次的時候，只要恰當?shù)倪x擇函數(shù)，在這些較好的點上就會聚集大量的模擬。

MC算法的實現(xiàn)步驟如下：

Step1：選擇。把當前盤面作為搜索樹的根節(jié)點，在可以選擇的節(jié)點中隨機選擇一個;

Step2：擴展。若該節(jié)點首次被選中，則將加入該點后的局面作為葉節(jié)點（沒有子節(jié)點的節(jié)點）加入搜索樹中，若該點并非首次被選中，則為該盤面作為子樹的根節(jié)點再構(gòu)建一次搜索樹;

Step3：模擬。對當前棋局進行模擬，即隨機下完整盤棋，模擬結(jié)束后，就可計算出根節(jié)點下每個子節(jié)點在模擬棋局中的獲勝概率。

3 實驗結(jié)果

為了實驗測試藏式夾棋靜態(tài)評估與動態(tài)評估的搜索效率和準確率，將兩種評估方法在搜索深度相同的前提下比較搜索效率和準確率。藏式夾棋在開局階段搜索樹較大，因此測試搜索效率時只有開局階段的二十步。兩種評估分別進行50局測試，并統(tǒng)計了開局階段前二十步的平均時間和勝率，作為衡量兩種評估方法在相同搜索深度中的搜索效率準確率。測試結(jié)果為表1和圖1所示。

4 結(jié)束語

本文討論了一種靜態(tài)的藏式夾棋局面估值方法和基于MC的動態(tài)局面估值方法。兩種方法有各自的優(yōu)勢與劣勢。靜態(tài)的估值方法有局限性，對局面的信息評估不全面、不準確?；贛C的動態(tài)估值方法對于搜索量巨大的局面，其收斂性很差，效率過低，耗時也很長。在后續(xù)的研究中，把基于MC的動態(tài)估值與靜態(tài)的估值方法結(jié)合。尋求一種快速的、節(jié)省資源占用的，準確的估方法是未來研究的主要目標[10]。

參考文獻（References）：

[1] 劉知青.現(xiàn)代計算機圍棋基礎(chǔ)[M].北京郵電大學(xué)出版社，2011.

[2] 于永波.基于蒙特卡洛樹搜索的計算機圍棋博弈研究[D].大連海事大學(xué)，2015.

[3] 周明明.基于專家系統(tǒng)和蒙特卡羅方法的計算機圍棋博弈的研究[D].南京航空航天大學(xué)，2012.

[4] 曹一鳴.基于蒙特卡羅樹搜索的計算機撲克程序[D].北京郵電大學(xué)，2014.

[5] 張小川.六子棋博弈的評估函數(shù)[J]. 重慶理工大學(xué)學(xué)報，2010.

[6] 劉明慧.計算機博弈的估值方法研究[D].東北大學(xué)，2008.

[7] 劉洋.點格棋博弈中UCT算法的研究與實現(xiàn)[D].安徽大學(xué)，2016.

[8] 王帥.一種德州撲克的牌力評估方法[J].計算機工程與科學(xué)，2017.

[9] 光洋.愛恩斯坦棋計算抓博弈系統(tǒng)的研究與實現(xiàn)[D].安徽大學(xué)，2016.

[10] 張玉琪.基于靜態(tài)評估的計算機圍棋UCT算法改進研究[D]. 南昌航空大學(xué)，2015.