王歷昊 黃為新 劉灝辰

摘要：近年來，新型棋類游戲?qū)映霾桓F。愛因斯坦棋作為奧林匹亞電腦游戲程式競賽指定棋類之一，雖然規(guī)則簡單，但變化多樣，富有趣味，對人工智能算法的探索也有一定的意義。利用C++語言實(shí)現(xiàn)愛因斯坦棋，結(jié)合Qt平臺進(jìn)行圖形用戶界面設(shè)計(jì)，以alpha-beta剪枝法優(yōu)化博弈樹進(jìn)行決策，最終實(shí)現(xiàn)了人機(jī)對戰(zhàn)功能，為棋類游戲的設(shè)計(jì)與實(shí)現(xiàn)提供了一個(gè)新的方式。

關(guān)鍵詞：愛因斯坦棋；Qt；圖形用戶界面；價(jià)值估計(jì)；博弈

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）07-0095-02

Abstract： In recent years， new chess games have emerged in endlessly. Einstein chess， as one of the designated chess categories in Olympia computer game program competition， although its rules are simple， is still varied and interesting. And it is also meaningful to the exploration of artificial intelligence algorithms. Einstein chess is implemented by C++ language， whose GUI is designed with Qt platform， and game tree is optimized by alpha-beta pruning algorithm for decision-making， so that man-machine game function is finally realized， which provides a new way for the design and implementation of chess games.

Key words： Einstein chess； Qt； GUI； value estimation； game

1 背景

AlphaGo以4：1的戰(zhàn)績戰(zhàn)勝圍棋大師李世石的新聞再一次引起了人們對棋類博弈的關(guān)注。愛因斯坦棋作為近年來新興的兩人骰子棋類游戲，成為電腦游戲程式競賽的指定棋類之一。它作為一種典型的博弈游戲，能對博弈結(jié)果直觀反應(yīng)，測試算法智能程度。

本文利用Qt平臺來開發(fā)一個(gè)愛因斯坦棋游戲，設(shè)計(jì)時(shí)的重點(diǎn)為玩家進(jìn)行操作的圖形化界面和可以對棋局進(jìn)行價(jià)值評估，判斷行棋的算法。

2 愛因斯坦棋簡介

棋盤大小為5×5，初始布置為將六枚己棋任意擺在棋盤己側(cè)左上角的3*3的三角域。

雙方每回合輪流擲骰子，然后選擇一枚與骰點(diǎn)同樣數(shù)字的己棋朝朝下、右、或右下方移動一格至任何棋位，若無同點(diǎn)棋則改為移動最接近該數(shù)的己棋之一。當(dāng)移到任何方棋子，將原位棋子移除棋盤不再使用。以先抵達(dá)敵方角落位，或消滅所有敵棋為勝。

3 軟件結(jié)構(gòu)設(shè)計(jì)

本系統(tǒng)主要分為如下三個(gè)模塊：玩家對棋子的控制模塊，電腦對棋子的控制模塊，系統(tǒng)的界面設(shè)計(jì)模塊。軟件總體框架如圖2所示。

4 游戲的具體設(shè)計(jì)與實(shí)現(xiàn)

4.1.1 玩家對棋子的控制

玩家對棋子的控制模塊主要包括鼠標(biāo)事件的發(fā)生，玩家在用戶界面的操作。鼠標(biāo)事件的發(fā)生是玩家通過鼠標(biāo)來輸入給定的指令，如選取棋子移動，實(shí)現(xiàn)吃子等等，這需要在棋子與棋盤兩個(gè)控件之中傳遞消息，并更新狀態(tài)。而Qt中的信號和槽機(jī)制[1] ，可以有效解決這個(gè)問題。

信號和槽的聲明：

private slots：

void changeState（int condition）；

void on_btn_clicked（）；

被選中的棋子發(fā)送信號：

if（e->button（）==Qt：：LeftButton）{

point=e->pos（）；

if（condition==0）{

this->setFlat（false）；

condition=1；

emit statechanged（condition）；

return；

}

}

接收信號并處理：

void Widget：：on_btn_clicked（）{

......

}

void Widget：：changeState（int condition）{

......

}

4.1.2 電腦對棋子的控制

電腦對棋子的控制主要依靠動態(tài)建立決策樹，輔以alpha-beta剪枝法進(jìn)行優(yōu)化實(shí)現(xiàn)[2]。首先是對棋局的價(jià)值評估：評估函數(shù)需要考慮電腦方的進(jìn)攻值，每個(gè)棋子對對方終點(diǎn)的威脅程度，故用每個(gè)棋子被選中的概率乘上其當(dāng)前的棋子位置的value值并求和，為[attack=k=05p[k]?value1]；電腦方的防守值，即人方的進(jìn)攻值，計(jì)算方法同上，為[defense=k=611p[k]?value2]。圖3為對右下角一方來說，棋子在棋盤每個(gè)位置的一種value值。最后某一步走法的value為兩數(shù)值相減所得結(jié)果，即[value=attack-defense]。若value值大于0則對己方有利，反之則不利。其中概率的求法則是用到了簡單的搜索和遍歷。

之后需要動態(tài)建立決策樹，樹的每一個(gè)節(jié)點(diǎn)代表某步棋的走法，決策樹層數(shù)越多，電腦的落子越有威脅，游戲難度越大。

具體來說，雙方對弈若干步后，從可能的走法中用極大極小搜索算法選擇一步較好的走法。定義電腦方為Max方，玩家為Min方。當(dāng)輪到Max方行棋時(shí)，決策樹為極大層，Max方應(yīng)考慮對自己利益值最大的走法；輪到Min方行棋時(shí)，決策樹為極小層，Max方應(yīng)考慮使Min方獲得的利益最小。指定一個(gè)搜索深度，當(dāng)達(dá)到該深度，或已出現(xiàn)勝負(fù)局面時(shí)，調(diào)用評估函數(shù)，返回評估值，通過對上述的兩種方式交替遞推，得出最終的最優(yōu)走法。

通常決策搜索樹的分支呈指數(shù)級增長，即使規(guī)定了一定的搜索深度，仍需要大量的計(jì)算，采用alpha-beta剪枝法優(yōu)化后，就可以刪去一些不必要的分支，從而加快計(jì)算過程。

定義極大層的下界為alpha，極小層的上界為beta，alpha-beta剪枝規(guī)則描述如下：

1）alpha剪枝。當(dāng)搜索至任一極小值層某結(jié)點(diǎn)的beta值不大于它任一前驅(qū)極大值層結(jié)點(diǎn)的alpha值，即alpha（前驅(qū)層） [≥]beta（后繼層），終止該Min結(jié)點(diǎn)以下的搜索。這個(gè)Min結(jié)點(diǎn)最終的倒推值即為所定義的beta值。

2）beta剪枝。當(dāng)搜索至任一極大值層某結(jié)點(diǎn)的alpha值不小于它任一前驅(qū)極小值層結(jié)點(diǎn)的beta值，即alpha（后繼層） [≤]beta（前驅(qū)層）時(shí)，終止該Max結(jié)點(diǎn)以下的搜索，這個(gè)MAX結(jié)點(diǎn)最終倒推值即為所定義的alpha值。

通過alpha-beta剪枝，會裁減掉很多不可能的情況，從而提升運(yùn)算速度。

4.1.3 系統(tǒng)界面設(shè)計(jì)

在主界面中，玩家可查詢游戲規(guī)則，選擇游戲難度，或者開始人機(jī)對戰(zhàn)。

在人機(jī)對戰(zhàn)界面中，玩家可在開局時(shí)在己方區(qū)域任意擺放棋子，是否先手由游戲系統(tǒng)擲骰子隨機(jī)決定，玩家每回合都可點(diǎn)擊按鈕得到骰子點(diǎn)數(shù)，根據(jù)提示以移動由此決定的棋子。如圖4所示。

5 結(jié)束語

本游戲軟件已經(jīng)通過測試，基本上達(dá)到了本次軟件設(shè)計(jì)開發(fā)的預(yù)期目的。此次設(shè)計(jì)開發(fā)的難點(diǎn)在于決策樹的生成與優(yōu)化，筆者選擇了alpha-beta剪枝法作為優(yōu)化方式，這雖然是一種傳統(tǒng)算法，但已足夠滿足愛因斯坦棋等較簡單棋種的需求。

參考文獻(xiàn)：

[1] 仇國巍. Qt圖形界面編程入門[M]. 北京： 清華大學(xué)出版社， 2017.

[2] 鄭培銘， 何麗. 基于計(jì)算機(jī)博弈的五子棋AI設(shè)計(jì)[J]. 電腦知識與技術(shù)， 2016（33）： 80-81， 90.

【通聯(lián)編輯：謝媛媛】