一種基于改進權重的黑白棋AI的設計與實現

徐剛 翟夢姣

摘要：本文基于改進權重設計并實現了一個黑白棋的人工智能程序，系統可以設置計算層數，經測試，程序效果較好。

關鍵詞：黑白棋;AI;設計與實現

中圖分類號：TP18?? 文獻標識碼：A?? 文章編號：1672-9129（2020）04-0054-02

Abstract： In this paper， based on the improved weight design and implementation of a black and white ai program， the system can be set to calculate the number of layers， through testing， the program effect is better.

Key words：Black and white; AI; Design and Implementation

前言：黑白棋，又叫翻轉棋（Reversi）、奧賽羅棋（Othello）等。近年來，人工智能是重要的研究領域之一。研究黑白棋的AI有助于了解人類只能行為。網上已有較多黑白棋的AI程序。經過測試，筆者發現網上常見的黑白棋棋盤每個格子的權重如果做一定程度的調整，比如，適當降低四個角的格子的權重，且適當增加四條邊每個格子的權重，那么有助于提升黑白棋AI的水平。接下來的部分筆者將詳述該系統的需求，設計和實現。

1 系統需求和設計目標

系統可以自動畫出黑白棋的棋盤，供雙方落子，并實時顯示雙方的棋子數量，是否分出勝負和勝負關系，以及接下來該哪一方落子。當用鼠標點擊棋盤某個格子時，需要做判斷。如果棋盤已滿，或者接下來雙方都沒有可以下子的格子，則根據雙方的棋子數量自動判斷勝負關系并顯示出來;如果上個條件不滿足且某一方落子后，并不能導致另一方的任何棋子被吃掉，則落子無效，仍有該方走棋;如果上述兩個條件均不滿足且某一方落子后，另一方沒有可以落子的格子，則由某一方繼續走棋;如果上述幾個條件均不滿足且某一方落子后可以導致另一份某些棋子被吃掉，則換另一方走棋。系統AI需要根據棋盤每個格子的權重，自動計算當時系統方的權重值和玩家方的權重值。首先，遍歷接下來若干步雙方所有可能的落子順序;然后，計算每一種可能后系統方的權重值;之后，選出權重值最大的一種然后落子并等待玩家方的下一步走棋;最后依次類推，直到分出勝負。系統AI需要根據棋盤每個格子的權重，自動計算當時系統方的權重值和玩家方的權重值。首先，遍歷接下來若干步雙方所有可能的落子順序;然后，計算每一種可能后系統方的權重值;之后，選出權重值最大的一種然后落子并等待玩家方的下一步走棋;最后依次類推，直到分出勝負。此外，系統還要允許用戶設置計算層數，并根據計算層數計算勝率最高的點。同時，允許用戶在游戲進行中隨時改變系統AI控制哪一方的棋子，并作出對應的操作。

2 系統主要功能實現

本系統使用C#程序設計語言，在Visual Studio 2010軟件下編譯運行通過。系統為該軟件下的Windows窗體應用程序。程序要需要若干個Label控件用于顯示黑方棋子數量、白方棋子數量、接下來該何方走棋;使用一個GroupBox控件和三個RadioButton控件來設置玩家為黑棋，或白棋，或兩方都是玩家;使用一個TextBox控件來設置AI搜索層數，層數越多，AI越智能，但是消耗系統資源較大。使用Panel控件當作棋盤，并使用Graphic類的Pen子類畫出棋盤和棋子。具體方法是，首先畫出一個邊框較粗的正方形作為棋盤外框，并占據整個Panel控件，然后在里面畫出等距的7條豎線和7條橫線，之后在中心的四個格子里以某對角兩格作為一種顏色畫出黑色棋子，另一個對角兩格畫出白色棋子，最后等待玩家用鼠標點擊棋盤某格，根據情況畫出棋子。接下來以玩家為黑棋為例，詳述整個系統AI的實現;當玩家為白棋時則反之;如果兩方都是玩家只需判斷落子是否已經分出勝負和是否落子有效即可[1-2]。

系統首先等待玩家落子，并建立兩個8行8列的二維整型數組代表棋盤落子情況，其中1代表黑棋，-1代表白棋，0代表該位置沒有棋子，第一個數組代表棋盤的實時狀態，第二個數組作代表臨時棋盤以作判斷落子是否有效使用。如果鼠標點擊了Panel控件，則觸發其MouseDown事件，如果鼠標點擊了棋盤的橫線、豎線或已有的落子點時，則其為無效落子，系統什么都不做并繼續等待玩家落子;如果點擊到了其他部分，則根據規則判斷是否可以導致系統方丟子，具體方法是：（1）把新的落子賦值到第二個數組中;（2）判斷該子上、下、左、右、左上、左下、右上和右下八個方向行進一格是否有對方棋子，如果都沒有對方棋子則落子無效，系統繼續等待玩家落子，并把第二個數組恢復到之前狀態;（3）如果有對方棋子，則繼續向該方向搜索，直到找到本方棋子為止，如果八個方向都沒有本方棋子，則該落子仍為無效落子，系統繼續等待玩家落子，并把第二個數組恢復到之前狀態;（4）如果有方向能找到本方落子，則其為有效落子。之后把此方向落子點和找到的本方棋子間的所有對方棋子的值-1賦值為本方棋子的值1，并根據第二個數組在棋盤中重新畫出每個格子新的棋子，并把第二個數組的值賦值到第一個數組，最后重新計算其中1和-1的數量，并賦值給相應的Label控件的Text值。然后判斷是否分出勝負。具體方法是：（1）先判斷棋盤是否全是某方棋子，即判斷第一個數組是否全是0和1，或者全是0和-1，如果是，則分出了勝負，并把相應Label控件的Text值改為某方勝;（2）判斷棋盤是否走滿，即判斷第一個數組是否有0值，如果沒有即為走滿，并統計雙方棋子數量，即計算其中1和-1的數量，并賦值給相應的Label控件的Text值，然后判斷哪一方的數量更多，并把哪方勝出或平手的信息賦值給相應的Label控件的Text值。（3）如果沒有分出勝負，則繼續落子。之后判斷是否仍該本方走棋。方法是：（1）當一方落子后，為有效落子，未分出勝負時，按照之前的方法，用另一方的棋子遍歷棋盤剩余所有空位，即找出第一個數組中，值為0的格。并將其賦值為另一方的棋子對應的值，然后判斷其是否為有效落子;（2）如果沒有有效落子，則還由之前一方繼續落子;（3）重復上一步，直到另一方有有效落子為止。

對于電腦AI的算法使用遞歸算法。具體方法為：（1）如果計算層數為一層時的勝率最高的點，即遍歷所有可落子的點，然后計算之后AI的總權重值，求助讓AI權重值最大的點。在程序中，可以跟據第一個二維數組，遍歷其中數組為0的點，并按照上文方法判斷有效點和求出落子后的棋盤對應的二維數組，將每種情況的最大權重值和對應的索引值存入臨時變量，然后用冒泡法求出權重最大的點，并使用Graphic類的子類Pen根據索引值畫出權重值最大的點和新的棋盤的棋子情況，最后仍要對是否分出勝負和是否仍由之前一方繼續落子做出判斷并進行相應操作;（2）如果計算層數不為一層。比如為N層，則先找出所有落子方和對手方各落一個子的情況。在程序中，可以按照上文方法找尋落子方的落一字的所有有效點，然后在找到的所有情況下，按照同樣方法找出另一方接下來的所有有效點，期間可能要不斷申請多個二維數組。之后的問題即求出計算層數為N-1層時，總權重值最大的點和對應的索引，此時可由遞歸函數求得。得出勝率最高點后也需要判斷是否分出勝負和是否仍由之前一方繼續落子做出判斷并進行相應操作。考慮到目前計算機的內存足夠大，足夠存儲多個二維數組，則該算法不用考慮內存溢出問題。經過測試，筆者給出的各個格子的權重值數組，左上角16位依次為50，25，20，15，25，25，15，10，20，15，15，5，15，10，05，0。其余48位與此角各值呈中心對稱。考慮到玩家可能在游戲過程中，可能會臨時改變AI和玩家的棋子，即在游戲中，玩家點擊了相應RadioButton控件，此時根據該控件的CheckedChanged事件是否觸發相應的來判斷是否改變用AI計算另一方接下來的勝率最高的點并作出相應操作。在測試中，還需要兩個TextBox控件和兩個Label控件，其中兩個TextBox控件用于存放目前棋盤對應的二維數組和接下來計算層數為一層時，落子到最優點后的棋盤對應情況，兩個Label控件用于實時顯示黑白雙方的權重值[3]。

3 系統測試

測試計算機的CPU為AMD FX-8350，內存為16GB，操作系統為Windows 7 x64 SP1。系統運行良好，當計算層數達到12層或以上時，一般玩家難以勝過系統AI。當計算層數達到20層或以上時，計算機運行有明顯的延遲。

4 小結

本文根據改進權重的AI，設計并實現了一個黑白棋人工智能程序。系統效果較好。但是還系統還有很多需要改進和完善的地方。比如：程序界面的美觀性，棋盤和棋子的顏色、樣式，落子的效果等。下一步的重點是對該系統做出優化，減少系統資源占用，比如根據之前的計算創造出棋譜，以及創新出新的占用資源少，并且勝率更高的算法。

參考文獻：

[1]美蘭多夫，等著.VisualStudio2010高級編程[M].北京：清華大學出版社.2012.

[2]本杰明·帕金斯，等著.C#入門經典[M].北京：清華大學出版社.2019.

[3]王喆.深度學習推薦系統[M].北京：電子工業出版社.2020.

作者簡介：徐剛（1985-），碩士，研究方向：計算機技術和經濟分析。