基于α-β剪枝樹算法的安卓五子棋程序設(shè)計與實現(xiàn)

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

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

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? 引? 言

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

本文程序選用Java開發(fā)語言，在Android Studio開發(fā)環(huán)境中編譯開發(fā)，程序中實現(xiàn)了游戲?qū)倪x擇、游戲流程控制、游戲勝負判斷、基于α-β剪枝樹的自動下棋等功能。程序兼顧了趣味性和智能性，能夠幫助用戶豐富業(yè)余生活。

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

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

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

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

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

2? 程序設(shè)計與實現(xiàn)

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

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

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

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

3? 結(jié)? 論

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

參考文獻：

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

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

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

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

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

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