基于α-β剪枝樹算法的安卓五子棋程序設計與實現

摘? 要：本文設計并研發了一種基于智能算法的安卓五子棋應用程序，程序中包括兩種模式：玩家對弈和人機對弈，其中在人機對弈模式中，程序一方采用α-β剪枝樹算法實現。程序主要由界面顯示及控制模塊、玩家對弈模塊、人機對弈模塊和勝負判定模塊組成。經過測試，程序具有較高智能程度，能夠擊敗大多數業余選手，并且具有較好的人機交互界面和響應速度，兼顧了智能性與娛樂性。

關鍵詞：博弈論;α-β剪枝樹算法;五子棋;安卓程序

Abstract：This paper designs and develops an Android Gobang application program based on intelligent algorithm. The program includes two modes：player game and man-machine game. In the man-machine game mode，the program side uses α-β pruning tree algorithm. The program is mainly composed of interface display and control module，player game module，man-machine game module and win-loss judgment module. After testing，the program has a high degree of intelligence，can beat most amateur players，and has a better human-computer interaction interface and corresponding speed，taking into account the intelligence and entertainment.

Keywords：game theory;α-β pruning tree algorithm;Gobang;Android program

0? 引? 言

人工智能在最近幾年得到了飛速的發展，很多國家甚至把人工智能作為高科技發展計劃的重點項目，在此方面投入了巨大的資源。最優化策略是人工智能研究的一個分支，而博弈論則是最優化策略的一個代表性算法，博弈論的思想是窮舉當前狀態的所有后繼情況，計算最終收益，以求在可接受的條件內獲取盡量高的收益[1]。這種算法的思想和棋類游戲中對抗的思想類似，本文選用α-β剪枝樹算法，設計并開發一款安卓端的五子棋程序，程序中包括兩種模式：玩家對弈和人機對弈。在玩家對弈中，黑白棋子由兩名玩家控制，程序負責控制下棋的順序并判斷輸贏;而在人機對弈中，由玩家選擇一方，另一方由程序自動控制實現對弈。

本文程序選用Java開發語言，在Android Studio開發環境中編譯開發，程序中實現了游戲對弈選擇、游戲流程控制、游戲勝負判斷、基于α-β剪枝樹的自動下棋等功能。程序兼顧了趣味性和智能性，能夠幫助用戶豐富業余生活。

1? α-β剪枝樹算法原理

在五子棋人機對弈過程中，考察的重點在于哪一方的“眼光”更能超前[2]，雙方根據當前具有的完備的局面信息以及規則判斷自己和對方落子的所有情況并分別作為節點，匯總所有的節點，就可以得到一顆基于層次的博弈樹，落子時根據對博弈樹的權重進行搜索，選擇當前情況的最優解，即為五子棋的落子位置，但對于五子棋來說，博弈樹的每層節點數量可以達到幾十甚至上百，如果需要搜索連續的幾層節點，那么搜索的數量是指數級的，搜索時間可能是無法接受的。因此，需要采用一定的策略縮小搜索范圍，而α-β剪枝樹算法就是一種比較常用的棋類對弈游戲搜索算法[3]。

α-β剪枝樹算法是由遞歸實現的一種搜索樹算法，在搜索過程中主要關注兩個值，即α與β，α值用來表示在搜索過程中對自己有利的值中的最好值，β則為最不利于對方的值，每一個節點都可以返回一個與α-β相關的值，以此來判定是否繼續搜索[4]。在整個搜索過程中，MAX方被稱為α，MIN方被稱為β，雙方都擁有最優的值，在開始搜時，α被賦初值為-∞，β被賦初值為+∞，而在搜索過程中，節點MAX使α的值持續增長，節點MIN則使β持續遞減，因此形成了一個[α，β]區域，該區域被叫做窗口。該窗口中的值用來表示該節點的子節點的值的范圍，縮小窗口值的過程就是向下搜索的過程，最終在這個窗口中會留下最優值。當節點MAX得到該節點的子節點返回值大于β的值或者節點MIN得到該節點的子節點返回值小于α值，就會執行減枝。

如圖1所示，在MAX層，假如當前層中的節點值是已搜索過的所有值中最大的一個，如果發現下一層（MIN）中的其中一個節點可能會產生比剛才搜索到的最大值還要小，即可以把該節點直接剪掉。反之，如果在MIN層，找到了已搜索過的所有值中最小的一個，發現下一層（MAX）會產生比剛才搜索到的最小值還要大，即可把該節點直接剪掉。即雙方都不會走出讓對方更有利的一步。

在五子棋游戲中，如果某一個落點的結果不大于α，那么該落點就可以被視為是很差的落點，該落點將被拋棄;如果某一個落點的結果不小于β，那么就作廢整個節點，因為對方不希望出現這個局面，對方會有更好的落點避免這個局面出現，在判定過程中檔發現了一個不小于β的落點的結果，對該結果及其后續進行剪枝操作，不計算后續所有節點。但是當一個落點的結果介于α與β之間的時候，那么該落點就可以被一方考慮。在搜索過程中，α會持續增加以至于能反映新的情況，但是可能會出現計算超時的情況，因此還需添加其他限定條件，以保證搜索能夠及時停止，獲得一個可以接受的局部最優值，在本文中，考慮到安卓手機的性能，采取限定最大搜索4層的策略，來實現五子棋游戲中的人機對弈的效果。

2? 程序設計與實現

五子棋應用程序需要具有良好的人機交互體驗，界面要美觀，下棋計算時間要快，能供用戶選擇進行玩家對弈或者人機對弈功能，并且能夠自動判定勝負并記錄得分[5]。根據功能需求，將該程序劃分成如圖2所示的幾個模塊，程序的主要人機交互界面劃分如圖3所示。

頁面顯示及主控模塊：修改配置文件main.xml插入背景圖片，通過TextView字符串組件來顯示菜單與結束的字符串，用View.OnClickListener接口中的setOnClick Listener來監聽是否有觸摸，如果有觸摸則運行相應的狀態。程序運行過程中，自定義onDraw函數來繪制棋盤以及棋子，確保程序界面正常顯示和觸摸控制。

游戲模式選擇模塊：因為本程序可以由用戶選擇玩家對弈還是人機對弈兩種模式，所以在進入頁面中提供游戲模式選擇按鈕，用戶點擊按鈕時，名為mMenuTv的菜單的字符串組件將獲取到的選擇狀態傳遞給界面初始化函數showPopupWindow（）以及pop_choose_gobang配置文件來執行相應的操作。

游戲勝負判斷模塊：通過繼承View并重載返回值為布爾類型的onTouchEvent函數來判斷該觸碰是否可以落子，如果對應的位置為空的話，則在該位置記錄落子信息，并且判斷游戲勝負。勝負判斷主要通過獲取該點并通過遍歷它的周圍來判斷橫向、縱向或者斜向是否有五子相連，Android中的View橫縱坐標與正常的x、y軸不同，它是正常的坐標軸順時針旋轉90度，所以判斷五子相連的時候，橫向則是y軸加減、縱向才是x軸加減。如果遍歷出有五個字相連則調用GameOver函數中的Toast.makeText來顯示游戲結束，否則繼續游戲。勝負判斷的流程圖如圖4所示。

3? 結? 論

本文實現了一款Android平臺下的五子棋游戲程序。程序中可以實現玩家對弈和人機對弈的功能，其中人機對弈功能采用4層的α-β剪枝樹搜索算法實現，經過測試，程序的智能水平已經能夠達到業余中高級水平，并且程序運行速度較快，落子時間以及勝負判定時間都可以接受。程序基于Android 6.0開發，能夠兼容市面上絕大多數手機，兼顧了趣味性和智能性。

參考文獻：

[1] 董慧穎，王楊.多種搜索算法的五子棋博弈算法研究 [J].沈陽理工大學學報，2017，36（2）：39-43+83.

[2] 孫世文.五子棋人工智能算法實現研究 [J].中國新通信，2018，20（23）：143.

[3] 周洋，鄧莉，謝煜.一種五子棋博弈算法的分析 [J].現代計算機（專業版），2017（10）：8-10.

[4] 毛麗民，盧振利，劉叔軍，等.五子棋對弈機器人移動平臺的研究 [J].微特電機，2017，45（1）：9-14.

[5] 劉洋.點格棋博弈中UCT算法的研究與實現 [D].合肥：安徽大學，2016.

作者簡介：宋萬洋（1991-），男，漢族，天津人，助教，碩士研究生，研究方向：軟件工程、數據挖掘。