基于Qt和博弈算法的五子棋游戲設計

趙杰，李亞文，楊濱峰

（商洛學院電子信息與電氣工程學院，陜西商洛 726000）

隨著網絡的發(fā)展，棋牌類益智休閑游戲迅速火爆起來，受到許多人的歡迎與喜愛，相關企業(yè)及諸多學者與教育工作者也對此產生極大的興趣[1-3]。萬坤等[4]基于C/S（客戶端/服務器）網絡架構實現了五子棋游戲的設計，采用MySQL數據庫和V-Play設計實現游戲框架，使用QML腳本語言實現游戲界面設計，用戶間通信由服務器統(tǒng)一調度轉發(fā)通信更容易實現。王夢尋等[5]通過STM32單片機及觸摸屏設計了人機對戰(zhàn)五子棋系統(tǒng)。蔣志鳳等[6]基于Linux設計了一款象棋游戲，在基礎游戲模式基礎上增加了“悔棋”功能及其他的娛樂玩法，但該系統(tǒng)的可移植性差。棋牌類游戲中，人機對戰(zhàn)與機器博弈是重要的設計因素[7-8]。也有研究者針對五子棋進行了相應研究。周洋等[9]利用極小極大值搜索提升運算速度，利用剪枝算法修剪不必要的分支，進一步提升搜索速率。鄭健磊等[10]利用局部搜索、多線程技術、淺層最優(yōu)算法優(yōu)化剪枝算法，以提升著棋的速度和準確率。本文對五子棋博弈進行研究，利用Qt開發(fā)框架實現五子棋游戲博弈對戰(zhàn)平臺，在使用極大極小值搜索和α-β剪枝算法的基礎上，選用AC自動機進行模式匹配，進一步優(yōu)化博弈算法，以期提升搜索與匹配效率。

1 方案設計

1.1 總體方案

主界面上顯示單人與多人游戲模式選擇，方便用戶自主選擇游戲方式，并在該界面添加常見的設置功能和退出游戲功能，設置功能主要用于設置一些游戲屬性。當用戶選擇單人游戲后，畫面將跳轉到人機對戰(zhàn)界面，實現與電腦AI對戰(zhàn)游戲，設置電腦難度和先后手順序后即可開始游戲，玩家落子后交由計算機算法運算。多人游戲具備創(chuàng)建游戲和加入游戲的功能，在游戲大廳中會顯示所有玩家的房間信息，玩家可自行決定是否創(chuàng)建、加入游戲。當有用戶加入房間后，房主即可選擇開始對弈。和單人游戲一樣玩家雙方擁有選擇悔棋的權利，但需對弈雙方同意后才能實現。當游戲結束后，房主可等待對方準備后重新開始對弈。在對弈過程中若一方選擇退出游戲視為認輸，退出后跳轉到游戲大廳界面。系統(tǒng)網絡結構同時采用TCP的C/S模型和UDP的廣播來實現。當用戶選擇多人游戲后，用戶會使用UDP廣播發(fā)送請求房間信息，網絡上存在房間的主機將自己的房間信息以UDP協(xié)議發(fā)送給請求的用戶，用戶之間不必通過建立連接來通信，這樣所有的用戶就可以知道存在的房間信息，從而更新游戲大廳信息。當房間信息發(fā)生改變時，該房主將會重新發(fā)送房間信息來更新其他用戶的大廳信息。當用戶建立房間后，該用戶將變?yōu)榉掌鳎⒈O(jiān)聽其他用戶客戶端的連接，有用戶加入房間后，二者便建立TCP連接，變成P2P點對點通信模式用于傳輸二者的對弈、聊天[11]。設計思想結構圖如圖1所示。

圖1 網絡模型結構

1.2 網絡對戰(zhàn)

數據的接收發(fā)送使用Socket編程和Qt的多線程機制。房間信息的請求、發(fā)送都是使用UDP廣播傳輸，當用戶創(chuàng)建房間后就開啟TCP服務器，用戶的一切操作請求、游戲信息都是通過TCP連接傳輸。各用戶間房間信息發(fā)送使用UDP廣播實現，而和其他玩家對弈時的信息交流采用C/S模式，各用戶間房間信息發(fā)送使用UDP廣播實現，而和其他玩家對弈時的信息交流采用C/S模式。用戶可以選擇建立游戲房間（即創(chuàng)建TCP服務器）還是加入別人的游戲房間（請求TCP連接）進行對弈。用戶可以選擇自己建立游戲房間（即創(chuàng)建TCP服務器）或加入別人的游戲房間（請求TCP連接）進行對弈。用戶落子后將落子信息發(fā)送給對弈對手，由對手判斷這步棋是否獲得勝利，若對方獲得勝利則重置游戲棋盤，并將對方獲勝消息發(fā)送給對弈對手。若雙方在信息交互中等待超時響應，由程序判斷對方是否斷開連接。程序的運行流程如圖2所示。

圖2 運行流程圖

1.3 人機對弈

電腦AI針對玩家落子信息擇優(yōu)選擇對應落子的目標落子。電腦AI會根據一定的計算規(guī)則計算棋盤全部位置的落子權重分數，根據分數選擇落子目標。要對某一個位置進行打分就需要制定相應規(guī)則，按照評分規(guī)則計算位置評分。根據五子棋對弈的各種棋型指定棋型評估表，AI匹配棋型計算位置評分。棋型評估情況如表1所示。表1中X代表空位，O代表棋子，其中每一種棋型對應一個評分，評分越高代表其擁有越強的威脅。高評分的位置具有較大的優(yōu)勢威脅，相應的比它小的威脅再多加起來也不會超過其評分。表1中對某些對稱棋型沒有完全記錄（如跳活三的對稱OOXOX），但在設計數據結構實現時會對其進行定義（共計16種）。若某個棋子的兩邊都存在敵方棋子，則該位置這個方向的分數記為0。

表1 棋型評估表

2 局面評估與博弈

通過棋型評估表，對該位置橫、豎、正、反、斜向的相關范圍掃描匹配棋型，累加評分得出該位置的最終評分。該算法雖然具備判斷棋盤所有位置的分數優(yōu)勢的能力，但是它最大的缺陷就是計算一步結果，只能看見眼前的利益，但分數最高的也不一定是最好的落子位置。將所有的局面列舉計算穩(wěn)定的收益分布構建最小生成樹形，計算其局面評分形成樹狀圖形，如圖3所示。以整個棋局作為獨立的評估單位，若局面分數越大，則對當前棋手越有利，反之分數越小，對當前棋手越不利。

圖3 博弈樹

根據“零和博弈”理論，敵方落子位置有很大可能是對己方最不利的位置，也就是對己方評分最小的位置上[12]。通過對比子節(jié)點收益情況，選擇使己方收益最大的落子位置。

2.1 極大極小值搜索

使用極大極小值搜索算法思路，假設從四步棋局開始考慮，作為敵方肯定希望第四步分數最小，所以把同一第三步下的第四步的最小的分數作為第三步的分數，對于己方而言，第三步的棋局分數應該越大越好，所以將同一第二步下的所有第三步的最大分求出作為第二步的分數。同理將同一第一步下的所有第二步中最小的分數作為第一步的分數，最后找所有第一步中的最大值作為己方決策的最終位置，這就是極大極小值的計算方法。設計思路如圖4所示。在設計實現算法時，其中MAX層數據就是其下一層分支中的最大值，而MIN層數據也是其下一層分支中的最小值。

圖4 極大極小值搜索示意圖

若要這樣深層遍歷所有可能節(jié)點，計算其局面分數將會導致產生非常大的計算量。雖然可以盡量排除局面中較遠的點，但是越往后，每計算一步棋將要考慮三四十個位置，按照8層深度計算最少也有308=6 561億個分支。所以還需要一些算法對目前算法進行優(yōu)化。

2.2 α-β 剪枝算法

α-β剪枝算法相當于極大極小值算法的改進型算法，是由遞歸實現的一種搜索樹算法，將搜索樹中極大值用α表示，而極小值用β表示。每個節(jié)點都會有一個α-β的數值，通過比較來判斷是否繼續(xù)搜索該節(jié)點，數值的大小對應對下棋者的利弊。剪枝算法如圖5所示。

圖5 剪枝算法示意圖

MAX可以看成己方落子層，MIN層就是敵方落子層，雙方都不會使對方利益最大化，但都希望自己利益最大化。當搜索MAX層時，假設已搜索到當分支下同一層中所有已搜索過的最大值α，就剪掉其下一層所有比α值小的節(jié)點分支。當搜索MIN層時，假設已搜索到當分支下同一層中所有已搜索過的最小值β，就減掉其下一層所有比β值大的節(jié)點分支。在初始時α將被賦予-∞，β將被賦予+∞，在搜索過程中搜索MAX會將α不斷變大，搜索MIN會將β不斷變小。這樣就會有一個[α，β]的窗口區(qū)域，窗口不斷縮小，最終被窗口篩選出的值就是最優(yōu)的選擇。隨著搜索的進行，會出現一種局面分數比α大但比β小的情況，說明該落法對弈雙方都可以考慮落子。但當這種局面出現時要將其舍棄，所以必須在博弈樹的上一層選擇另一種下法。

2.3 AC模式匹配

雖然使用α-β剪枝算法優(yōu)化減少了算法的計算量，但是每次計算模式匹配的時候都需要重新依次遍歷匹配所有模式，這樣會在模式匹配上花費許多時間，因此本文選用AC自動機來進行模式匹配。AC自動機的實現有三個重要的組成部分：構建字典樹、尋找失配指針、字符串匹配。要用AC自動機完成計算就需先構造字典樹，從根節(jié)點開始將所有字符串依次排列成樹狀結構，若不存在字符節(jié)點就創(chuàng)建新的節(jié)點存儲該字符。在字典樹構建完之后需要構建匹配失敗時的回退機制，所以要對每個節(jié)點配置失配指針。設置原則是根節(jié)點下的所有節(jié)點失配指針指向根節(jié)點，所有子節(jié)點的失配指針指向其父節(jié)點的同深度的與其自己相同的節(jié)點，若沒有相同節(jié)點則指向根節(jié)點。構建匹配查找時，失配后就查找其失配指針所指節(jié)點的子節(jié)點繼續(xù)匹配，重復該過程直到匹配串走到結尾為止。使用AC算法能夠極大地減少計算局面分數時模式匹配的時間，提升計算速度。

3 測試結果

軟件設計采用Qt Designer跨平臺GUI資源庫，開發(fā)工具為Qt Creator 4.3.0，使用Qt 5.9 for Desktop打包工具。所測試數據皆在Windows10操作系統(tǒng)下完成。

3.1 基礎功能測試

本平臺的基礎功能主要從人機對弈、房間創(chuàng)建與加入、網絡對弈三個方面進行功能測試。其中，人機對弈具備設置先后手、設置難度、悔棋、重新開始等功能，其功能實現如圖6所示。

圖6 人機對弈界面

游戲大廳展示所有已創(chuàng)建的房間信息，通過表格中按鈕加入退出房間、開始游戲，通過表格下方的按鈕創(chuàng)建關閉房間。通過刷新按鈕刷新表格內所有房間信息。功能實現如圖7所示。網絡對弈界面實現網絡中雙人對弈、聊天、 悔棋、認輸等功能，功能測試如圖8所示。

圖7 游戲大廳界面

圖8 網絡對弈界面

3.2 速度性能測試

在玩家先手下，對不同難度對應的不同計算深度每走一步棋進行計算時間統(tǒng)計測試，計算時間通過使用QTimer類倒計時功能和超時響應槽函數設計計時器記錄算法用時，統(tǒng)計三次對局計算時間取平均值記錄如表2所示。

表2 3～6層深度下算法每計算一步所需時間

本文分別對比文獻[9]和文獻[10]中的計算數據，分別取文中在3層、5層深度下算法每計算一步所需時間數據（取五次對局時間平均）和4層、6層深度下計算一步所需時間，結果分別見表3和表4。

表3 文獻[9]五子棋博弈算法3層和5層深度下每計算一步所需時間

表4 文獻[10]五子棋博弈算法4層和6層深度下每計算一步所需時間

通過對比可以看出，本設計通過算法優(yōu)化使得算法AI的計算時間得到極大的縮減，計算時間擁有幾十倍之差，計算能力得到提升，提高了游戲體驗感。再次對7層、8層、9層深度下進行算法時間測試，測試結果如表5所示。

表5 本文算法不同深度每計算一步所需時間

從表5中可以看出，本設計在7層以下的計算時間都在1 s以下，且第8層下每計算一步所需時間平均不超過1 s。為了不影響游戲體驗，將最高難度設置為8層遍歷深度，在不影響游戲體驗感的同時，AI的計算能力和速度已滿足人機對弈要求。

4 結語

本文使用Qt的GUI交互設計工具，設計具有交互界面的五子棋游戲平臺，可以實現網絡對戰(zhàn)及人機對戰(zhàn)兩種游戲模式。該設計具有較高智能程度，并且具有較好的人機交互界面和響應速度。人機對戰(zhàn)博弈在采用極大極小值搜索和α-β剪枝算法的基礎上，引入AC自動機來加快模式匹配的計算，從而對博弈算法進行了速度優(yōu)化，計算時間明顯小于傳統(tǒng)搜索及α-β剪枝算法。