基于Qt和博弈算法的五子棋游戲設(shè)計(jì)

趙杰，李亞文，楊濱峰

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

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

1 方案設(shè)計(jì)

1.1 總體方案

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

圖1 網(wǎng)絡(luò)模型結(jié)構(gòu)

1.2 網(wǎng)絡(luò)對(duì)戰(zhàn)

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

圖2 運(yùn)行流程圖

1.3 人機(jī)對(duì)弈

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

表1 棋型評(píng)估表

2 局面評(píng)估與博弈

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

圖3 博弈樹

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

2.1 極大極小值搜索

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

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

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

2.2 α-β 剪枝算法

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

圖5 剪枝算法示意圖

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

2.3 AC模式匹配

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

3 測(cè)試結(jié)果

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

3.1 基礎(chǔ)功能測(cè)試

本平臺(tái)的基礎(chǔ)功能主要從人機(jī)對(duì)弈、房間創(chuàng)建與加入、網(wǎng)絡(luò)對(duì)弈三個(gè)方面進(jìn)行功能測(cè)試。其中，人機(jī)對(duì)弈具備設(shè)置先后手、設(shè)置難度、悔棋、重新開始等功能，其功能實(shí)現(xiàn)如圖6所示。

圖6 人機(jī)對(duì)弈界面

游戲大廳展示所有已創(chuàng)建的房間信息，通過表格中按鈕加入退出房間、開始游戲，通過表格下方的按鈕創(chuàng)建關(guān)閉房間。通過刷新按鈕刷新表格內(nèi)所有房間信息。功能實(shí)現(xiàn)如圖7所示。網(wǎng)絡(luò)對(duì)弈界面實(shí)現(xiàn)網(wǎng)絡(luò)中雙人對(duì)弈、聊天、 悔棋、認(rèn)輸?shù)裙δ埽δ軠y(cè)試如圖8所示。

圖7 游戲大廳界面

圖8 網(wǎng)絡(luò)對(duì)弈界面

3.2 速度性能測(cè)試

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

表2 3～6層深度下算法每計(jì)算一步所需時(shí)間

本文分別對(duì)比文獻(xiàn)[9]和文獻(xiàn)[10]中的計(jì)算數(shù)據(jù)，分別取文中在3層、5層深度下算法每計(jì)算一步所需時(shí)間數(shù)據(jù)（取五次對(duì)局時(shí)間平均）和4層、6層深度下計(jì)算一步所需時(shí)間，結(jié)果分別見表3和表4。

表3 文獻(xiàn)[9]五子棋博弈算法3層和5層深度下每計(jì)算一步所需時(shí)間

表4 文獻(xiàn)[10]五子棋博弈算法4層和6層深度下每計(jì)算一步所需時(shí)間

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

表5 本文算法不同深度每計(jì)算一步所需時(shí)間

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

4 結(jié)語

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