黑白棋博弈系統(tǒng)設計

劉佳瑤, 林 濤

(1 河北工業(yè)大學 國際教育學院, 天津300131； 2 河北工業(yè)大學 人工智能與數(shù)據(jù)科學學院, 天津300131)

0 引 言

人工智能是近年來非常活躍的研究領域,計算機博弈是人工智能研究的重要分支［1］。 黑白棋在西方和日本是一種深受大眾廣泛喜愛的游戲,又叫奧賽羅棋(Othello)、蘋果棋或正反棋(Anti reversi)。雖然黑白棋規(guī)則簡單,但其變化復雜,非常有趣味性。 黑白棋程序設計是通過編程使計算機學會黑白棋的規(guī)則,使計算機可以與人進行對弈。 本文采用Eclipse 設計博弈黑白棋程序,應用了Minimax 算法進行搜索,通過Alpha-Beta 剪枝減少搜索數(shù)量。

1 黑白棋規(guī)則

黑白棋由黑、白兩種棋子組成,各32 枚,棋盤是64 個8×8 的正方格,棋子要落在方格內(nèi)［2］。 黑白棋的下棋方法：

(1)在每一場棋局開始時,棋盤的正中間有交叉放置的黑、白棋各兩枚,執(zhí)黑棋一方先落子。

(2)在空的方格新落下己方棋子,同時使對手一枚及以上棋子翻轉(zhuǎn),為一次合法的落子。

(3)對手棋子被翻轉(zhuǎn)的條件：己方新落下的棋子與棋盤上已有的同色棋子間,被夾住的所有對手棋子(和己方棋子中間無間隙),夾住的方向可以是任何方向。

(4)每次落子可以翻轉(zhuǎn)所有滿足條件(3)的對手棋子,可以翻轉(zhuǎn)的對手棋子必須被翻轉(zhuǎn)。

(5)若棋盤上沒有位置能實現(xiàn)翻轉(zhuǎn)對方的棋子,則本輪由對手選擇落子的位置,直到己方有合法的落子位置為止。

(6)如果一方有合法的落子位置,則必須選擇落子,不可以選擇放棄。

(7)棋局持續(xù)下去,直到棋盤填滿或者雙方都無合法棋步可下。

(8)當棋盤被下滿時,游戲結(jié)束；當棋盤上只有一方的棋子時,游戲結(jié)束。 游戲結(jié)束后,棋盤上剩余棋子多的一方贏得比賽。

2 走棋著法

2.1 局面表達

局面表達指將黑白棋的棋盤上的信息轉(zhuǎn)化為電腦可以識別的數(shù)據(jù)。 局面表達的過程就是將人機對弈過程中棋局的棋子數(shù)據(jù)和整體局面信息,用計算機能夠識別的語言進行描述的過程［3］。 對于棋子,黑色用B,白色用W；對于黑白棋的棋盤,可以分為橫軸和縱軸,橫軸用a-h 的英文字母表示,縱軸用1-8 的阿拉伯數(shù)字表示。

并做以下定義：

(1)定義棋子的位置Position。 用有兩個參數(shù)的關鍵字Position 表示棋子的位置,第一個參數(shù)表示棋子的行,第二個參數(shù)表示棋子的列(從左到右為0-7,從上到下為0-7)。

(2) 定 義 棋 子 的 顏 色 Player。 用 對 象PlayerWhite 表示白色,用對象PlayerBlack 表示黑色。 類Player 定義玩家棋子顏色,其參數(shù)為對象PlayerWhite 或PlayerBlack。

(3)定義棋子Piece。 用兩個參數(shù)的類Piece 定義一個棋子,第一個參數(shù)為關鍵字Position 表示棋子的位置,第二個參數(shù)為類Player 定義玩家棋子顏色。

(4)定義棋盤Board。 Board 列表定義棋盤。 列表元素類型為(3)中的棋子Piece,每次玩家或計算機落子后,將該棋子Piece 類(含顏色和位置信息)加入到列表Board 中。

(5)定義初始棋盤狀態(tài)initialBoard。 棋盤正中有兩枚白棋和兩枚黑棋,共四枚棋子交叉放置。

2.2 著法表示

著法指棋子從一個位置挪動到另一個位置,或棋盤上的某個棋子變成其他棋子的過程,著法對應于人機對弈中的行棋［3］。 在黑白棋博弈過程當中著法指：棋盤上所下棋子的位置；人機兩方落子后,需改變顏色的棋子；什么情況下游戲結(jié)束。

(1)判斷落子位置是否為空。 即遍歷列表Board 中的每一個元素,判斷是否有某一個元素中的位置為落子位置,沒有則說明落子位置為空,否則不為空。

(2)將棋子落在該位置,并改變棋盤狀態(tài)。 首先判斷落子位置是否為空,若為空則按2.4 中的方法將可以反轉(zhuǎn)的對手棋子全部反轉(zhuǎn),否則出現(xiàn)錯誤。

(3)判斷游戲是否結(jié)束。 當雙方都沒有合法棋子可以下時,游戲結(jié)束,棋子多的一方獲勝,通過Board 的元素個數(shù)是否為64 進行判斷；當棋盤還沒有下滿時,如果棋盤上只剩下一個顏色的棋,則游戲結(jié)束,棋盤上剩下棋子的一方獲勝。 通過判斷某一玩家落子并進行相應反轉(zhuǎn)后,Board 中是否僅有一種顏色的棋子進行判斷。

2.3 判斷本次落子是否有效

黑白棋中落子有效有兩個條件：首先要求落子在棋盤的一個空的位置；其次要求新落下的棋子可以翻轉(zhuǎn)對手一個或多個棋子。 因此每次落子前要檢查該次落子是否有效,使用isOccupied 函數(shù)判斷該位置是否為空,使用toFlip 函數(shù)判斷落子后可以翻轉(zhuǎn)對手的棋子集合是否為空,從而判斷本次落子是否有效。

2.4 反轉(zhuǎn)

每次落子后,當自己放下的棋子在所有方向內(nèi)有一個自己的棋子,則被夾在中間的對方棋子全部翻轉(zhuǎn)成為自己的棋子。 通過窮舉實現(xiàn)反轉(zhuǎn)。 落子位置的橫向棋子翻轉(zhuǎn)過程如下：

(1)得到棋盤上與所下棋子在同一行的所有棋子的列表row。

(2)從列表row 中篩選出與所下棋子同種顏色的所有棋子,放在列表samePlayer 中。

(3)依次判斷所下棋子與samePlayer 中的每一個棋子中間是否全部為異色棋子,是則反轉(zhuǎn)中間的棋子,否則保持不變。

(4)對棋盤上的與所下棋子在同一列、同一條直線上從左上到右下、同一條直線上從右上到左下的棋子,分別進行(1)(2)(3)操作。

3 局面評估

3.1 給不同位置設置權重

對于不同的位置賦予不同的權重w, 使用函數(shù)score,計算將己方棋子放在某一位置后,當前棋面上己方的分數(shù)s(即當前棋面上己方棋子的個數(shù))。

(1)首先判斷是否可以放在四個角落的位置,如圖1。 如果可以,則這是最優(yōu)的位置,令w = 64,保證我方可以盡快占領角的位置。 因為黑白棋的四個角很重要,所以在游戲過程中絕不能輕易的讓對手進角［4］。

圖1 最優(yōu)位置Fig. 1 The optimal location

(2)避免在緊靠角的地方放棋子,如圖2。 如果放在這個地方,令w = 1。

圖2 緊靠角的位置Fig. 2 Right next to the corner

(3)避免在緊靠邊的地方放棋子,如圖3。 如果放在這個地方,令w = 3。

圖3 緊靠邊的位置Fig. 3 Close to the side

(4)避免在緊靠邊角的地方放棋子,如圖4,如果放在這個地方,令w = 2。

圖4 緊靠邊角的位置Fig. 4 Close to the side and corner

(5)當雙方落棋子少于12 枚時(開局系統(tǒng)給出的四枚除外),如果棋子放在藍色方框以內(nèi),如圖5所示,令w = s ＋4。 最好不要把棋子放在藍色方框之外。 這個部分的宗旨是先占滿藍色方框,把對方逼出方框。

(6)早翻轉(zhuǎn)很多對手的棋子實際上會給對手一個優(yōu)勢。 相反,應該采取這樣的行動：在棋盤上有一半或更多的棋子之前,盡量將棋子放在可以最少反轉(zhuǎn)對手棋子的位置。 例如：在棋盤上有一半或更多的棋子之前,放在A 位置可以反轉(zhuǎn)對手3 個棋子,放在B 位置可以反轉(zhuǎn)對手5 個棋子,則選擇放在A位置。 在棋盤上有一半或更多的棋子之前, 令w =60 - s。

(7)其他情況,令w = s。

圖5 中心位置Fig. 5 Center position

3.2 Minimax 搜索

Minimax 搜索算法(即極大-極小算法),該算法要求己方在最壞情況中選擇最好的,其第一要義是按照對自己最有利的決策,對盤面進行模擬。 如果能夠評價某一時刻其中一方的優(yōu)劣程度,則另一方走棋時就會選一種使對方優(yōu)勢盡可能小的走法［5］。假設對手每一步都會將我方引入從當前看理論上價值最小的格局方向,即對手具有完美決策能力。 因此我方的策略應該是選擇那些對方所能達到的讓我方最差情況中最好的,也就是讓對方在完美決策下所對我造成的損失最小。

按照這種方式模擬出黑白棋可能的局面,所有局面就構成一棵極大極小決策樹,如圖6 所示。 第一行為游戲的初始狀況,第二行為對手可以下的棋的位置的所有情況,第三行為己方落子可能的情況,以此類推,畫出決策樹的更深層。 當搜索到預定深度時,對當前局面計算分值估算。 用函數(shù)score(Board)算出該層分值,當前層顏色與己方相同時,使之盡可能大。 從而選擇己方最壞情況中最好的位置進行落子。

博弈程序消耗的時間與搜索的層數(shù)緊密相關［6］。 因此要根據(jù)黑白棋的不同難度,以及計算機的運算速度等,設置計算機玩家可以向前看的步數(shù),即決策樹的深度。 讓計算機又快又準的找到目前最佳位置。

3.3 Alpha-Beta 剪枝

Alpha-Beta 剪枝用于裁剪搜索樹中不需要搜索的樹枝,以提高運算速度。 基本的原理是：當一個Min 節(jié)點的β 值≤任何一個父節(jié)點的α 值時,剪掉該節(jié)點的所有子節(jié)點；當一個Max 節(jié)點的α 值≥任何一個父節(jié)點的β 值時,剪掉該節(jié)點的所有子節(jié)點［7］。 本文的黑白棋博弈系統(tǒng)中指的是：刪除當前結(jié)點獲得的值小于其父節(jié)點之前得出的值的分支。通過剪枝操作可以有效的減少搜索節(jié)點的個數(shù),從而使程序運行更快速。

圖6 決策樹示意圖Fig. 6 Decision tree diagram

3.4 其他高級搜索算法

(1)蒙特卡洛樹搜索(MCTS)。 蒙特卡洛樹搜索算法的最佳下一步的預測完全不同于Minimax 中決策樹的生成過程。 MCTS 是對游戲進行多次模擬,最佳下一步的計算是根據(jù)嘗試和模擬結(jié)果進行的。 該方法在保證降低問題規(guī)模的同時,能保持所求解的近似最優(yōu)性［8］。 蒙特卡洛樹搜索首先將游戲的當前狀態(tài)作為一個獨立的根節(jié)點,例如：在黑白棋中,將當前的棋盤狀態(tài)作為一個根節(jié)點。 然后選擇一個節(jié)點進行擴展,并模擬,即完成一次從選擇節(jié)點到博弈結(jié)束的過程。 模擬的結(jié)果反向傳輸?shù)礁?jié)點,更新根節(jié)點信息。 MCTS 算法會在滿足最大抽樣次數(shù)或者達到時間耗盡等設置后,根據(jù)第一層節(jié)點中每個節(jié)點的估值,從中選擇一個決策作為本次MCTS 算法的最佳決策［8］。

(2) 遺傳算法(Genetic Algorithm)。 遺傳算法模擬了生物進化論的自然選擇和遺傳學機理的生物進化過程［9］。 該算法是通過模擬自然進化過程得到搜索最優(yōu)解的一種計算模型,且得到演變最后遺留選擇的基因,即對應該算法的最優(yōu)解［10］。 遺傳算法在初始化后,要對個體進行適應度計算,在黑白棋中,可根據(jù)局面評估中的原則,對棋盤中的位置進行評價。 通過運算將遺傳賦給下一代。 當群體的代數(shù)達到預先設定值時,適應度最高的個體為最優(yōu)解,完成算法。 算法運算過程：初始化→個體評價→選擇運算→交叉運算→變異運算→終止條件判斷。

4 測試與分析

經(jīng)過人機對弈測試,發(fā)現(xiàn)該系統(tǒng)反應較快,計算機出棋時間小于1s。 勝負率上,較為樂觀。 測試程序中,一方采用上述算法計算出落棋子位置,另一方模擬真人下棋,隨機在可落棋的方格內(nèi)著棋。 經(jīng)過100 次測試,該黑白棋博弈系統(tǒng)的勝出次數(shù)為87 次。

5 結(jié)束語

本文實現(xiàn)了黑白棋的人機對弈系統(tǒng)。 一個較好的人工智能對弈系統(tǒng)來自兩個方面的因素：首先是局面評估的準確；其次是博弈搜索的高效性,使程序可以在最短的時間內(nèi)搜索到足夠的深度。 本文在博弈樹搜索算法的設計上,運用了Minimax 搜索算法,雖然使用Alpha-Beta 剪枝取得了很好的效果,但是該算法依然會導致游戲樹較大,搜索空間較大,需要進一步進行剪枝操作或嘗試其他搜索算法。

該黑白棋對弈系統(tǒng)應在以下方面有待改善：(1)局面評估應該更加精準、高效。 (2)在黑白棋下棋的搜索算法中,使用選擇性剪枝策略。 (3)嘗試使用不同的搜索算法,并進行比較,使黑白棋對弈系統(tǒng)的搜索算法更加快速和精準。