尕藏扎西 安見才讓

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

關(guān)鍵詞： 計(jì)算機(jī)博弈; 藏式夾棋; 靜態(tài)評(píng)估; 動(dòng)態(tài)評(píng)估

中圖分類號(hào)：TP391.1? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：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 引言

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

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

1 藏式夾棋評(píng)估標(biāo)準(zhǔn)

1.1 子力

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

1.2 位置

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

1.3 機(jī)動(dòng)

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

2 藏式夾棋局面估值方法

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

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

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

2.1.1 進(jìn)攻值

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

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

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

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

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

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

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

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

2.1.2 威脅值

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

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

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

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

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

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

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

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

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

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

[Evalboard=expJQ+axpJQ ]? ⑺

[expJQ]為當(dāng)前局面的進(jìn)攻值，[axpJQ]為當(dāng)前局面的威脅值。

2.2 動(dòng)態(tài)局面評(píng)估

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

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

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

Step1：選擇。把當(dāng)前盤面作為搜索樹的根節(jié)點(diǎn)，在可以選擇的節(jié)點(diǎn)中隨機(jī)選擇一個(gè);

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

Step3：模擬。對(duì)當(dāng)前棋局進(jìn)行模擬，即隨機(jī)下完整盤棋，模擬結(jié)束后，就可計(jì)算出根節(jié)點(diǎn)下每個(gè)子節(jié)點(diǎn)在模擬棋局中的獲勝概率。

3 實(shí)驗(yàn)結(jié)果

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

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

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

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

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

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

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

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

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

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

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