基于人工智能的六子棋博弈平臺研究與實現

段 浴，王宛宛

（1.重慶移通學院 大數據與軟件學院，重慶 401520；2.重慶交通職業學院 大數據學院，重慶 402247）

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

1 系統需求分析

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

1.1 系統功能性需求

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

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

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

1.2 系統功能性需求

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

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

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

2 系統設計

2.1 系統總設計

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

（2）在實現方面：對六子棋的數據結構、棋子觸發、搜索算法等進行了設計和實現的過程。

（3）在系統規范方面：實現了程序的標準化、統一化，增強了軟件的可擴展性、可維護性以及實用性。

2.2 軟件結構

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

2.2.1 模塊一

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

2.2.2 模塊二

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

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

2.3 設計原理

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

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

2.4 系統功能設計

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

2.5 系統流程圖

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

圖1 系統流程圖

3 系統實現

3.1 開發平臺和工具選擇

開發工具：Visual Studio 2017，開發語言：c#。

3.2 算法設計（UCT 算法）

3.2.1 UCT 算法簡介

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

（1）selection（選擇）：從根節點出發，使用UCB 公式，連續子節點向下至葉子節點進行選擇。

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

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

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

3.2.2 UCT 算法過程

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

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

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

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

4 系統測試

本系統采用黑盒測試方法。

4.1 功能測試

功能測試如圖2 所示。

圖2 功能測試

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

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

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

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

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

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

圖3 獲勝局展示

4.2 性能分析

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

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

表1 A 組對弈情況表

表2 B 組對弈情況表

表3 C 組對弈情況表

表4 D 組對弈情況表

表5 E 組對弈情況表

表6 5 組對弈情況匯總表

5 結束語

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