基于Qt的愛因斯坦棋游戲設計與實現

王歷昊 黃為新 劉灝辰

摘要：近年來，新型棋類游戲層出不窮。愛因斯坦棋作為奧林匹亞電腦游戲程式競賽指定棋類之一，雖然規則簡單，但變化多樣，富有趣味，對人工智能算法的探索也有一定的意義。利用C++語言實現愛因斯坦棋，結合Qt平臺進行圖形用戶界面設計，以alpha-beta剪枝法優化博弈樹進行決策，最終實現了人機對戰功能，為棋類游戲的設計與實現提供了一個新的方式。

關鍵詞：愛因斯坦棋；Qt；圖形用戶界面；價值估計；博弈

中圖分類號：TP311 文獻標識碼：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的戰績戰勝圍棋大師李世石的新聞再一次引起了人們對棋類博弈的關注。愛因斯坦棋作為近年來新興的兩人骰子棋類游戲，成為電腦游戲程式競賽的指定棋類之一。它作為一種典型的博弈游戲，能對博弈結果直觀反應，測試算法智能程度。

本文利用Qt平臺來開發一個愛因斯坦棋游戲，設計時的重點為玩家進行操作的圖形化界面和可以對棋局進行價值評估，判斷行棋的算法。

2 愛因斯坦棋簡介

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

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

3 軟件結構設計

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

4 游戲的具體設計與實現

4.1.1 玩家對棋子的控制

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

信號和槽的聲明：

private slots：

void changeState（int condition）；

void on_btn_clicked（）；

被選中的棋子發送信號：

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 電腦對棋子的控制

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

之后需要動態建立決策樹，樹的每一個節點代表某步棋的走法，決策樹層數越多，電腦的落子越有威脅，游戲難度越大。

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

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

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

1）alpha剪枝。當搜索至任一極小值層某結點的beta值不大于它任一前驅極大值層結點的alpha值，即alpha（前驅層） [≥]beta（后繼層），終止該Min結點以下的搜索。這個Min結點最終的倒推值即為所定義的beta值。

2）beta剪枝。當搜索至任一極大值層某結點的alpha值不小于它任一前驅極小值層結點的beta值，即alpha（后繼層） [≤]beta（前驅層）時，終止該Max結點以下的搜索，這個MAX結點最終倒推值即為所定義的alpha值。

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

4.1.3 系統界面設計

在主界面中，玩家可查詢游戲規則，選擇游戲難度，或者開始人機對戰。

在人機對戰界面中，玩家可在開局時在己方區域任意擺放棋子，是否先手由游戲系統擲骰子隨機決定，玩家每回合都可點擊按鈕得到骰子點數，根據提示以移動由此決定的棋子。如圖4所示。

5 結束語

本游戲軟件已經通過測試，基本上達到了本次軟件設計開發的預期目的。此次設計開發的難點在于決策樹的生成與優化，筆者選擇了alpha-beta剪枝法作為優化方式，這雖然是一種傳統算法，但已足夠滿足愛因斯坦棋等較簡單棋種的需求。

參考文獻：

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

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

【通聯編輯：謝媛媛】