極大值極小值搜索設計五子棋

源代碼可在這里下載

摘要：

設計一個五子棋對戰AI，使用極大值極小值搜索，并使用α-β剪枝減少復雜度。采用啟發式函數對整個棋局形式進行評估，并作為極大值極小值搜索的依據。

一、導言

1.1 問題描述：

本次實驗要求設計一個五子棋的AI，要求能與人類對戰，并具有較好的用戶交互界面。

1.2 背景介紹：

五子棋是世界智力運動會競技項目之一，是一種兩人對弈的純策略型棋類游戲，是世界智力運動會競技項目之一，通常雙方分別使用黑白兩色的棋子，下在棋盤直線與橫線的交叉點上，先形成5子連線者獲勝。棋盤由橫縱各15條等距離，垂直交叉的平行線構成，在棋盤上，橫縱線交叉形成了225個交叉點為對弈時的落子點。

盡管五子棋先后于1992年、2001年被計算機證明原始無禁手、原始有禁手規則下先手必勝，在五子棋專業比賽中采用現代開局規則（如基于無禁手的兩次交換規則（Swap-2），基于有禁手的索索夫-8規則（Soosorv-8））遠比原始規則復雜，并未被終結。然而，相比電腦象棋，電腦五子棋的發展是緩慢的。頂級五子棋程序雖長于局部計算，但缺乏大局觀，因此很多五子棋專家相信目前的五子棋程序依舊無法超越最強的人類棋手。

1.3 使用方法：

極大極小搜索算法、α-β剪枝算法。

1.4 方法介紹：

極大極小策略是考慮雙方對弈若干步之后，從可能的步中選一步相對好的步法來走，即在有限的搜索深度范圍內進行求解。

定義一個靜態估價函數f，以便對棋局的態勢做出優劣評估。

規定：
max和min代表對弈雙方；
p代表一個棋局（即一個狀態）；
有利于MAX的態勢，f(p)取正值；
有利于MIN的態勢，f(p)取負值；
態勢均衡，f(p)取零值；

1.5 MINMAX的基本思想：

• 當輪到MIN走步時，MAX應該考慮最壞的情況（即f(p)取極小值）
• 當輪到MAX走步時，MAX應該考慮最好的情況（即f(p)取極大值）
• 相應于兩位棋手的對抗策略，交替使用上面兩種方法傳遞倒推值。

α-β剪枝算法是采用有界深度優先策略進行搜索，當生成節點達到規定的深度時，就立即進行靜態估計，而一旦某個非端節點有條件確定倒推值時，就立即賦值。

定義：

• α值：有或后繼的節點，取當前子節點中的最大倒推值為其下界，稱為α值。節點倒推值>=α；
• β值：有與后繼的節點，取當前子節點中的最小倒推值為其上界，稱為β值。節點倒推值<=β；

α-β 剪枝：

• β剪枝：節點x的α值不能降低其父節點的β值，x以下的分支可停止搜索，且x的倒推值為α；
• α 剪枝：節點x的β值不能升高其父節點的α值，x以下的分支可停止搜索，且x的倒推值為β；

二、對弈AI落子的程序設計

AI落子的函數如下。當前落子輪到AI時，進行落子。如果是先手第一步，直接下天元位置，否則調用choose函數選擇一個落子位置。最后改變下棋的次序狀態。

void AI::putChess() {if(AIBoard->now) return; //不是AI下時，跳過 if(first == 1 && AIBoard->chess[7][7] == 0){ //先手第一步直接下中間 AIBoard->chess[7][7] = 1;}else{choose(); //選擇一個位置 AIBoard->chess[chooseX][chooseY] = first; //將這個位置放置我們的棋子 }AIBoard->now = !AIBoard->now; //改變下棋次序的狀態 }

在計算落子位置之前，有兩個預備的函數。一個是就算某一條線的分值，一個是計算整個棋盤的分值，后者需調用前者。而計算落子時，又需要計算整個棋盤的分值。

int AI::getGoalOfPoint(int *a, int color) {if(a[0] == color && a[1] == color && a[2] == color && a[3] == color && a[4] == color) return 100000; //五子 if(a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == color && a[5] == 0) return 10000; //活四子 if(a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == 0) return 1000; //活三子 if((a[0] == -1*color && a[1] == color && a[2] == color && a[3] == color && a[4] == color && a[5] == 0) ||(a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == color && a[5] == -1*color)) return 1000; //死四子 if(a[0] == 0 && a[1] == color && a[2] == color && a[3] == 0) return 100; //活二子 if((a[0] == -1*color && a[1] == color && a[2] == color && a[3] == color && a[4] == 0) ||(a[0] == 0 && a[1] == color && a[2] == color && a[3] == color && a[4] == -1*color)) return 100; //死三子 if(a[0] == 0 && a[1] == color && a[2] == 0) return 10; //活一子 if((a[0] == -1*color && a[1] == color && a[2] == color && a[3] == 0) ||(a[0] == 0 && a[1] == color && a[2] == color && a[3] == -1*color)) return 10; //死二子 return 0; }

計算棋盤的分值的函數如下。SumGoal為總分數，然后遍歷每一個點。

int AI::getGoalOfChess(board nowBoard, int color) {int sumGoal = 0;for(int i = 0; i < ROW; i++){for(int j = 0; j < COL; j++) { //掃描所有的點

每一個點的處理如下。

int line[6]; //記錄該點出發的線，一個六個 line[0] = nowBoard.chess[i][j]; //第一個是當前點 int x1 = i, y1 = j; int x2 = i, y2 = j; int x3 = i, y3 = j; int x4 = i, y4 = j; //朝四個方向變化的x，y坐標 for(int it = 1; it < 6; it++) {y1--;if(y1 >= 0) line[it] = nowBoard.chess[i][y1]; //如果有棋子，就賦值 else line[it] = -2; //沒有就賦一個無效值，下同 } sumGoal += getGoalOfPoint(line,color); //計算這一點的分值后相加 for(int it = 1; it < 6; it++) {x2++; y2--;if(y2 >= 0 && x2 < 15) line[it] = nowBoard.chess[x2][y2];else line[it] = -2; } sumGoal += getGoalOfPoint(line,color); for(int it = 1; it < 6; it++) {x3++;if(x3 < 15) line[it] = nowBoard.chess[x3][y3];else line[it] = -2; } sumGoal += getGoalOfPoint(line,color); for(int it = 1; it < 6; it++) {x4++; y4++;if(x4 < 15 && y4 < 15) line[it] = nowBoard.chess[x4][y4];else line[it] = -2; } sumGoal += getGoalOfPoint(line,color);

對于每一個點，我們朝其四個方向取6個點（含其自身）。如果某一方向超出棋盤范圍，就設一個無效值。每取一次，就調用剛剛那個函數計算一次分值，加到sumGoal。四個方向均如此，遍歷的每個子均如此，最后得出當前棋局對于color方的局勢分數。

接下來是使用極大值極小值搜索和α-β剪枝搜索落子位置。首先，深拷貝一個棋盤，用來進行預估。

board virtual0; srand(time(0)); for(int i = 0; i < ROW; i++){for(int j = 0; j < COL; j++)virtual0.chess[i][j] = AIBoard->chess[i][j];} //拷貝一個棋盤用來預估

然后是第一層極大值的搜索，首先將MAX值設一個最小值。然后遍歷棋盤，如果某一點無子且其周圍有子，則為一個預估點，假設這一點放置了本方的棋子。然后進行局勢判斷，如果已經贏了，就直接將MAX設為一個最大的值（添加了一個非常小的隨機因子）。然后給落子位置chooseX和chooseY賦值。最后取消這個落子，恢復棋盤。

int MAX = -1000000; //極大值先設為最小 for(int i0 = 0; i0 < ROW; i0++) {for(int j0 = 0; j0 < COL; j0++){if(virtual0.chess[i0][j0] == 0 && isAround(virtual0, i0, j0)){ //如果該處沒有棋子，并且周圍有棋子 virtual0.chess[i0][j0] = first; //放置棋子預測 if(getGoalOfChess(virtual0,first) >= 100000) {MAX = 1000000-rand()%100;chooseX = i0;chooseY = j0; //如果能獲勝，直接將MAX值設最大 virtual0.chess[i0][j0] = 0; //取消剛剛放置的棋子

如果沒有直接獲勝，就進行下一步預測，也就是極小值層的搜索。先將MIN設為最大，變量cut1用于剪枝以及判斷對方是否直接獲勝時使用。同樣遍歷棋盤，如果五子且其周圍有子，則為一個預估點，放置對手方的棋子。

int MIN = 1000000; //極小值先設為最小 bool cut1 = false;for(int p0 = 0; p0 < ROW; p0++){for(int q0 = 0; q0 < COL; q0++){if(virtual0.chess[p0][q0] == 0 && isAround(virtual0, p0, q0)){virtual0.chess[p0][q0] = -1*first; //放置一個棋子 if(getGoalOfChess(virtual0,-1*first) >= 100000 && getGoalOfChess(virtual0,first) < 10000) {MIN = -1000000+rand()%100; //如果對手方能贏，將極小值設為最小 cut1 = true; //跳出此次預測 virtual0.chess[p0][q0] = 0; //恢復棋盤 break;}

然后判斷對手方能否直接獲勝且本方無法獲勝。如果是則將MIN改為一個最小值。然后修改cut1的值，使這次極小層的搜索結束，還原棋盤，然后跳出循環。

如果對手方沒有直接取勝的點，繼續向下進行一層極大值的搜索，MAX1也是先設為最小。變量Cut2用來剪枝。同樣遍歷棋盤，如果五子且其周圍有子，則為一個預估點，放置本方的棋子。然后計算本方棋盤局勢減去對方棋盤局勢的分數（評估函數）。如果這個極大值小于這個分數，就重新為其賦值，最后還原這一步的棋盤。

int MAX1 = -1000000; bool cut2 = false; for(int i1 = 0; i1 < ROW; i1++) //又一層極大值的搜索 {for(int j1 = 0; j1 < ROW; j1++){if(virtual0.chess[i1][j1] == 0 && isAround(virtual0, i1, j1)){virtual0.chess[i1][j1] = first; //預測放置棋子 if(MAX1 < getGoalOfChess(virtual0,first)-getGoalOfChess(virtual0,-1*first)) MAX1 = getGoalOfChess(virtual0,first)-getGoalOfChess(virtual0,-1*first);//如果極大值小于啟發式函數，就重新賦值 virtual0.chess[i1][j1] = 0; //恢復棋盤 }

接下來是一個β剪枝

if(MIN < MAX1) //剪枝 {cut2 = true;break; } } if(cut2) break;

然后是第二層的極小值與第三層的極大值的一個倒推值的比較。如果極小值大，則重新賦值。最后恢復棋盤

if(MIN > MAX1) MIN = MAX1; //如果極小值大于倒推值，重新賦值 virtual0.chess[p0][q0] = 0; //恢復棋盤

然后是一個α剪枝。

if(MAX > MIN) //剪枝 {cut1 = true;break;} } if(cut1) break;

然后是最外一層的極大值和第二層的極小值的倒推值的比較。如果極大值小，則重新賦值，并且修改落子的坐標為當前預估落子的坐標。最后恢復棋盤。

if(MAX < MIN) //如果極大值小于倒推值 {MAX = MIN; //重新賦值 chooseX = i0; //改變放置的x，y坐標 chooseY = j0; } virtual0.chess[i0][j0] = 0;

以上就是AI落子的搜索過程。接下來是一些界面的設計和棋盤有關的代碼。

三、人類落子的相關代碼

人類落子的代碼和AI的基本思想是相同的，不同的是AI要通過算法計算落子坐標，而人類是根據鼠標點擊位置計算落子坐標。

如下，形參x，y為鼠標點擊的像素點的位置，我們通過計算將其轉化為棋盤下標。并且這個下標處沒有棋子時，放置人類的棋子。最后也要修改落子次序的狀態。

void human::putChess(int x, int y) {if(!humanBoard->now) return; //如果不是人類下，則放置棋子無效 int index_x = 0;int index_y = 0;if(x > 50) index_x = (x-50)/40+1;if(y > 50) index_y = (y-50)/40+1; //根據鼠標點擊的位置，計算放置棋子的下標 if(humanBoard->chess[index_x][index_y] == 0){humanBoard->chess[index_x][index_y] = first; //將該坐標放置上我們的棋子 humanBoard->now = !humanBoard->now; //改變下棋次序的狀態 } }

四、與繪制棋盤，勝負判斷有關的代碼

有一個棋盤的board類，負責繪制棋盤，存儲棋局信息，判定勝負等。這個類的構造函數如下。

首先是聲明一個二維數組用以存儲棋局信息。變量now代表當前應為哪方下，前文已用到。變量runState代表當前棋局是已經結束還是在正常對弈。RED_PEN是一個自定義的紅色畫筆。

接下來是繪制棋盤和棋子。繪制棋盤的代碼如下。hdc為窗口句柄，chooseX和chooseY為AI落子位置，默認為一個無效位置，我們要為AI的落子畫一個紅圈方便我們識別其先前落子位置。然后是兩個for循環，繪制了棋盤的橫線和豎線。

接下來是繪制棋子的過程。首先是獲取系統的黑色和白色畫刷。然后選擇黑色畫刷為天元點畫一個小黑點。

接下來遍歷棋盤畫棋子，每次遍歷棋盤，如果落子為1，則畫一個黑色圓圈，如果是-1則畫一個白色圓圈。（先手為黑子，后手為白子）畫完棋子后，再選擇紅色畫筆根據chooseX和chooseY畫一個圓圈作為AI落子提示。（如果chooseX和chooseY取值無效，這個紅色圓圈是畫不出來的，chooseX和chooseY默認值是一個無效值。）每次畫完紅圈后，要恢復默認的黑色畫筆。

接下來是檢測棋盤當中是否有一方（color方）已經獲勝，其思想與AI評估棋盤局勢基本相同，也是遍歷棋盤，每個點朝四個方向延伸，觀察是否有已成五子的線。如下是進行遍歷。

然后是每個點的處理，先是定義朝四個方向變化的x，y坐標，已經用于計數的count。首先，判斷當前的子是不是color顏色，如果不是直接過掉。如果是進行四次迭代，朝四個方向取四子，每有一子為color色，則count++，如果count最終為4，說明此線五子連珠，則sum++。最后如果sum大于0，則說明color色的棋子已有連成五子的線，則棋局結束，將代表棋局運行狀態的變量runState改為false。最后返回sum值，可以根據sum值，判斷某一方是否獲勝。

下邊是重置棋盤的reset函數，就是將整個二維數組置0，相關變量再度初始化。

五、與MFC、鼠標點擊相關的部分代碼

本次實驗是使用了win32程序，以及相關的MFC庫，用以實現界面和鼠標監聽等。先前已提到過少許界面方面的代碼，下邊將剩余代碼展示。

WM_PAINT是MFC中繪制窗口的消息，在窗口被創建時會被調用，也可以通過發送該條消息進行調用。每次調用時，先繪制棋盤，然后我們使用MessageBox語句彈出消息，詢問是否選擇先手，并根據其選擇，為AI和人類的先手變量first賦值，以及下棋次序的變量now賦值。如果是AI先手，則先讓AI落一子，然后再畫一次棋盤。

消息WM_LBUTTONDOWN,代表鼠標左鍵被按下。

監聽到此消息后，我們先獲取點擊的像素值。如果棋局尚未結束，我們將點擊的位置做為形參傳入到人類落子的函數中供其落子使用。然后繪制棋盤，判斷落子之后人類是否獲勝，如果獲勝則彈出消息框提示，否則就繼續進行。

緊接著便是AI落子的代碼，步驟與人類落子基本相同，不過無需獲取鼠標點擊位置。最終游戲結束時也是彈出消息框提醒。

如果檢測到棋局已經結束，我們再度彈出消息框，詢問是否再來一次。如果是，則重置棋盤，發送繪制棋盤的消息。否則就直接銷毀窗口。

以上為整個五子棋項目設計的主要部分。

六、結果分析

實驗環境：

本次實驗使用DEV C++編譯器，創建了DEV win32項目程序，并使用了MFC的庫進行界面和功能的設計。在代碼上，使用了多文件編輯，共有main.cpp, board.h, board.cpp, AI.h, AI.cpp, human.h, human.cpp等文件，以及board、AI、human等自定義類。

算法性能：

本次實驗采用極大極小搜索算法。搜索了三層（兩層極大值，一層極小值）。每次搜索均需要遍歷棋盤，棋盤大小為15*15，故三層搜索的復雜度為15的6次方。最后還需要遍歷棋盤進行局勢評估，所以最復雜的情況時，復雜度為15的8次方。這樣每走一步棋需要大約25.6億次左右的計算。對于目前的CPU處理速度，基本上在一秒鐘左右下一步棋，可以滿足與人正常對弈的時間需求。另外，由于使用了α-β剪枝算法，實際所需時間應當少于最復雜的時間。

對于本次的AI，三層的極大極小搜索基本可以在時間和對戰性能上取得平衡。

如果想要在對戰性能上取得更為突破性的進步，一種情況是進行更深層次的搜索，但是時間和計算能力上已無法滿足此需求，考慮可以使用多線程編程以加快計算。另一種情況是優化評估函數，根據網上的知識，大多數的五子棋AI在搜索上是大同小異的，真正產生差距的是評估函數的優化，所以改進對戰能力的更好的方法是優化評估函數，使其更能適應五子棋的規則，這方面所需要的是對于五子棋的一個深入了解。

主要參考文獻

• 現如今五子棋AI水平的一些討論
• AI設計參考
• 評估函數參考

總結

以上是生活随笔為你收集整理的极大值极小值搜索设计五子棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。