一種基于改進(jìn)權(quán)重的黑白棋AI的設(shè)計(jì)與實(shí)現(xiàn)

徐剛 翟夢(mèng)姣

摘要：本文基于改進(jìn)權(quán)重設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)黑白棋的人工智能程序，系統(tǒng)可以設(shè)置計(jì)算層數(shù)，經(jīng)測(cè)試，程序效果較好。

關(guān)鍵詞：黑白棋;AI;設(shè)計(jì)與實(shí)現(xiàn)

中圖分類(lèi)號(hào)：TP18?? 文獻(xiàn)標(biāo)識(shí)碼：A?? 文章編號(hào)：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

前言：黑白棋，又叫翻轉(zhuǎn)棋（Reversi）、奧賽羅棋（Othello）等。近年來(lái)，人工智能是重要的研究領(lǐng)域之一。研究黑白棋的AI有助于了解人類(lèi)只能行為。網(wǎng)上已有較多黑白棋的AI程序。經(jīng)過(guò)測(cè)試，筆者發(fā)現(xiàn)網(wǎng)上常見(jiàn)的黑白棋棋盤(pán)每個(gè)格子的權(quán)重如果做一定程度的調(diào)整，比如，適當(dāng)降低四個(gè)角的格子的權(quán)重，且適當(dāng)增加四條邊每個(gè)格子的權(quán)重，那么有助于提升黑白棋AI的水平。接下來(lái)的部分筆者將詳述該系統(tǒng)的需求，設(shè)計(jì)和實(shí)現(xiàn)。

1 系統(tǒng)需求和設(shè)計(jì)目標(biāo)

系統(tǒng)可以自動(dòng)畫(huà)出黑白棋的棋盤(pán)，供雙方落子，并實(shí)時(shí)顯示雙方的棋子數(shù)量，是否分出勝負(fù)和勝負(fù)關(guān)系，以及接下來(lái)該哪一方落子。當(dāng)用鼠標(biāo)點(diǎn)擊棋盤(pán)某個(gè)格子時(shí)，需要做判斷。如果棋盤(pán)已滿(mǎn)，或者接下來(lái)雙方都沒(méi)有可以下子的格子，則根據(jù)雙方的棋子數(shù)量自動(dòng)判斷勝負(fù)關(guān)系并顯示出來(lái);如果上個(gè)條件不滿(mǎn)足且某一方落子后，并不能導(dǎo)致另一方的任何棋子被吃掉，則落子無(wú)效，仍有該方走棋;如果上述兩個(gè)條件均不滿(mǎn)足且某一方落子后，另一方?jīng)]有可以落子的格子，則由某一方繼續(xù)走棋;如果上述幾個(gè)條件均不滿(mǎn)足且某一方落子后可以導(dǎo)致另一份某些棋子被吃掉，則換另一方走棋。系統(tǒng)AI需要根據(jù)棋盤(pán)每個(gè)格子的權(quán)重，自動(dòng)計(jì)算當(dāng)時(shí)系統(tǒng)方的權(quán)重值和玩家方的權(quán)重值。首先，遍歷接下來(lái)若干步雙方所有可能的落子順序;然后，計(jì)算每一種可能后系統(tǒng)方的權(quán)重值;之后，選出權(quán)重值最大的一種然后落子并等待玩家方的下一步走棋;最后依次類(lèi)推，直到分出勝負(fù)。系統(tǒng)AI需要根據(jù)棋盤(pán)每個(gè)格子的權(quán)重，自動(dòng)計(jì)算當(dāng)時(shí)系統(tǒng)方的權(quán)重值和玩家方的權(quán)重值。首先，遍歷接下來(lái)若干步雙方所有可能的落子順序;然后，計(jì)算每一種可能后系統(tǒng)方的權(quán)重值;之后，選出權(quán)重值最大的一種然后落子并等待玩家方的下一步走棋;最后依次類(lèi)推，直到分出勝負(fù)。此外，系統(tǒng)還要允許用戶(hù)設(shè)置計(jì)算層數(shù)，并根據(jù)計(jì)算層數(shù)計(jì)算勝率最高的點(diǎn)。同時(shí)，允許用戶(hù)在游戲進(jìn)行中隨時(shí)改變系統(tǒng)AI控制哪一方的棋子，并作出對(duì)應(yīng)的操作。

2 系統(tǒng)主要功能實(shí)現(xiàn)

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

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

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

3 系統(tǒng)測(cè)試

測(cè)試計(jì)算機(jī)的CPU為AMD FX-8350，內(nèi)存為16GB，操作系統(tǒng)為Windows 7 x64 SP1。系統(tǒng)運(yùn)行良好，當(dāng)計(jì)算層數(shù)達(dá)到12層或以上時(shí)，一般玩家難以勝過(guò)系統(tǒng)AI。當(dāng)計(jì)算層數(shù)達(dá)到20層或以上時(shí)，計(jì)算機(jī)運(yùn)行有明顯的延遲。

4 小結(jié)

本文根據(jù)改進(jìn)權(quán)重的AI，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)黑白棋人工智能程序。系統(tǒng)效果較好。但是還系統(tǒng)還有很多需要改進(jìn)和完善的地方。比如：程序界面的美觀性，棋盤(pán)和棋子的顏色、樣式，落子的效果等。下一步的重點(diǎn)是對(duì)該系統(tǒng)做出優(yōu)化，減少系統(tǒng)資源占用，比如根據(jù)之前的計(jì)算創(chuàng)造出棋譜，以及創(chuàng)新出新的占用資源少，并且勝率更高的算法。

參考文獻(xiàn)：

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

[2]本杰明·帕金斯，等著.C#入門(mén)經(jīng)典[M].北京：清華大學(xué)出版社.2019.

[3]王喆.深度學(xué)習(xí)推薦系統(tǒng)[M].北京：電子工業(yè)出版社.2020.

作者簡(jiǎn)介：徐剛（1985-），碩士，研究方向：計(jì)算機(jī)技術(shù)和經(jīng)濟(jì)分析。