基于人工智能的六子棋博弈平臺研究與實現(xiàn)

段 浴，王宛宛

（1.重慶移通學(xué)院 大數(shù)據(jù)與軟件學(xué)院，重慶 401520；2.重慶交通職業(yè)學(xué)院 大數(shù)據(jù)學(xué)院，重慶 402247）

人工智能不斷發(fā)展，在圍棋、五子棋、象棋等棋類當(dāng)中的應(yīng)用非常廣泛，眾所周知的有AlphaGo、深藍等[1-2]。五子棋人盡皆知，然而六子棋知道的人卻很少。相比于五子棋、象棋、國際象棋等其他許多棋種，六子棋不具先手優(yōu)勢[3]。而且理論上游戲所使用的棋盤可以是無限大的。事實上，六子棋的狀態(tài)空間復(fù)雜度和游戲樹復(fù)雜度遠比五子棋高幾個數(shù)量級，其已經(jīng)和圍棋及國際象棋的復(fù)雜度差不多[4]。本系統(tǒng)就是為人工智能應(yīng)用于六子棋做鋪墊，為機器人與玩家對弈做鋪墊。本系統(tǒng)會為玩家提供博弈平臺，并做出研判。

1 系統(tǒng)需求分析

本系統(tǒng)主要是做六子棋博弈研判。棋局中先完成連六或長連者獲勝。當(dāng)所有棋盤交點全部下滿而無人宣告獲勝時為和局。

1.1 系統(tǒng)功能性需求

（1）悔棋，對弈過程中，可進行悔棋操作。

（2）判定是否獲勝。玩家每次落子后，系統(tǒng)會搜索當(dāng)前棋面，并進行判定，直至某方獲勝。

（3）重新開始，在對局過程中如有一方提前認輸或者已分出勝負。便可開啟下一局對弈。

1.2 系統(tǒng)功能性需求

（1）先手控制，走子提示。

（2）計時器，通過系統(tǒng)計時器來提示玩家，限制玩家每一手棋的時間。

（3）角色控制，當(dāng)輪到對方下棋時，己方角色會變成灰色，且不能移動棋子。

2 系統(tǒng)設(shè)計

2.1 系統(tǒng)總設(shè)計

（1）在界面方面：應(yīng)簡單實用方便，可以滿足不同層次使用者的需求。

（2）在實現(xiàn)方面：對六子棋的數(shù)據(jù)結(jié)構(gòu)、棋子觸發(fā)、搜索算法等進行了設(shè)計和實現(xiàn)的過程。

（3）在系統(tǒng)規(guī)范方面：實現(xiàn)了程序的標(biāo)準(zhǔn)化、統(tǒng)一化，增強了軟件的可擴展性、可維護性以及實用性。

2.2 軟件結(jié)構(gòu)

整個軟件分為兩個主要模塊，第一個模塊是界面部分，第二個模塊是算法模塊，主要是進行勝負判定的算法代碼。

2.2.1 模塊一

模塊一主要是完成界面的顯示以及與用戶的交互、相關(guān)信息的顯示以及與用戶的交互、提示框等。該模塊首先完成的是棋盤的顯示，包括背景部分以及棋盤上的方格。另外一部分是菜單項，包含重新開始、后退兩個操作。此模塊包含的類有class MyFrame，class mypoint，class myline，還包括一些相應(yīng)的監(jiān)聽類來響應(yīng)用戶的鼠標(biāo)操作等。

2.2.2 模塊二

模塊二主要是完成對勝負的判定，是依照六子棋的規(guī)則來進行設(shè)計，在每一方落子結(jié)束之后判斷是不是有一方已經(jīng)能夠連成六子，也就是勝出了。

此模塊包含的類有class sixp、class search 等。

2.3 設(shè)計原理

軟件的設(shè)計是依據(jù)吳毅成教授發(fā)明的六子棋的游戲規(guī)則來設(shè)計，這主要體現(xiàn)在算法模塊上[5]。勝負的判斷使用方法hadsix（），從各個方向掃描是否有連成六個子。

博弈判定的過程可分為兩個部分。第一個部分為當(dāng)對手落子后，AI 更新博弈樹和主路徑[6]。第二個部分為當(dāng)自己落子后，AI 更新博弈樹和主路徑。AI 通過博弈樹和主路徑來記錄博弈的過程，因此更新博弈樹和主路徑是等價的。

2.4 系統(tǒng)功能設(shè)計

重新開始菜單項可以以當(dāng)前選擇的模式重新開始；后退菜單項可以用來完成悔棋，使用戶退回到上一步，可以連續(xù)使用，直到回到初始狀態(tài)。

2.5 系統(tǒng)流程圖

系統(tǒng)流程圖如圖1 所示。本系統(tǒng)使用二維數(shù)組儲存棋盤信息，分別用0、1、2 表示黑子、白子、空白。每次落子后都會生成棋形向量，使用搜索算法對當(dāng)前棋局進行博弈判定。

圖1 系統(tǒng)流程圖

3 系統(tǒng)實現(xiàn)

3.1 開發(fā)平臺和工具選擇

開發(fā)工具：Visual Studio 2017，開發(fā)語言：c#。

3.2 算法設(shè)計（UCT 算法）

3.2.1 UCT 算法簡介

UCT（上限置信區(qū)間）算法，將蒙特卡洛樹搜索與UCB 公式結(jié)合，基于UCT 的一些變形，是一種博弈樹搜索算法[7-8]。與傳統(tǒng)的搜索算法相比，它在超大型博弈樹的搜索過程中具有時間和空間上的優(yōu)勢。

（1）selection（選擇）：從根節(jié)點出發(fā)，使用UCB 公式，連續(xù)子節(jié)點向下至葉子節(jié)點進行選擇。

（2）expansion（擴展）：在游戲結(jié)束前，創(chuàng)建一個或多個子節(jié)點，并選取其中一個節(jié)點。

（3）simulation（模擬）：從選定的子節(jié)點開始，用隨機策略進行游戲。

（4）backPropagation（傳播）：使用隨機游戲的結(jié)果，更新從選擇子節(jié)點至根節(jié)點。

3.2.2 UCT 算法過程

首先，以當(dāng)前棋盤狀態(tài)對應(yīng)的節(jié)點，作為博弈樹的根節(jié)點。每次UCT 搜索，是當(dāng)前所到的節(jié)點，并不是尚未完全擴展的節(jié)點。如果該節(jié)點完全擴展，那么就計算UCB 值，選擇最大的節(jié)點往下走[9]。最終可能出現(xiàn)兩種可能：遇到了未完全擴展的節(jié)點，或遇到了終局節(jié)點。

終局節(jié)點就是直接沿著我們剛才來的路徑，一個一個節(jié)點備份棋局結(jié)果，否則就以一個可行狀態(tài)出發(fā)，進行隨機模擬。該模擬過程就是隨機在可行位置下不斷下子，直到棋盤結(jié)束。該隨機過程中并不記錄任何東西。模擬的結(jié)果是從剛才生成的0/0 節(jié)點開始，依次向上備份結(jié)果。

抽象地說，就是在找當(dāng)前UCT 樹的主路徑，然后取得主路徑新生成的尾節(jié)點，從這個尾節(jié)點出發(fā)進行模擬，備份得分的對象是新的主路徑，即為單次的UCT搜索。一次完整的UCT 算法求解，是要在限定的時間內(nèi)進行多次UCT 搜索的。每次UCT 搜索，都會改變博弈樹的結(jié)構(gòu)，影響下一次UCT 搜索的主路徑走向。而搜索得越多，結(jié)果也就越準(zhǔn)確。

UCT 算法的執(zhí)行位置介于record_part1 和record_part2 之間。因此，總算法的執(zhí)行順序為record_part1→ UCT → record_part2。若i 勝利，則mark=1；若i 失敗，則mark=-1；若平局，則mark=0。偽代碼如下：

4 系統(tǒng)測試

本系統(tǒng)采用黑盒測試方法。

4.1 功能測試

功能測試如圖2 所示。

圖2 功能測試

（1）棋盤|落子：在棋盤按先后順序落子，六子棋的規(guī)則是黑色方先落一子，然后從白色方開始后各落子，直至獲勝或棋盤走滿。

（2）計時器：顯示棋手雙方一共用時和單次落子時間。

（3）重新開始：清空棋盤，重新開始游戲。

（4）后退：即悔棋，倒退回上一步。

（5）角色：顯示棋手雙方的信息。

勝負終局棋判定如圖3 所示。

圖3 獲勝局展示

4.2 性能分析

測試方案是，邀請了5 組六子棋愛好者玩家使用本系統(tǒng)進行對弈，采用五局三勝制。使用比賽過程中每一個棋局的準(zhǔn)確率指標(biāo)來衡量系統(tǒng)的整體性能。

5 組分別為A、B、C、D、E 組，甲乙雙方進行對弈，每完成一局便互換黑白執(zhí)棋方。表1 至表5 分別為5組對弈情況表，表6 為5 組對弈情況匯總表。經(jīng)統(tǒng)計，所有5 組對弈準(zhǔn)確率均為100%，本系統(tǒng)達到預(yù)期設(shè)計效果。

表1 A 組對弈情況表

表2 B 組對弈情況表

表3 C 組對弈情況表

表4 D 組對弈情況表

表5 E 組對弈情況表

表6 5 組對弈情況匯總表

5 結(jié)束語

本系統(tǒng)突出軟件應(yīng)用與開發(fā)的創(chuàng)新性和實用性，使得人工智能、博弈論、計算機（機器）融合成為一個有機的整體。對于計算機博弈的研究來說，既能推動博弈論的發(fā)展，又能推動人工智能的發(fā)展。