國立屏東大學電腦五子棋 AI 程式競賽 - 進階篇

# 國立屏東大學電腦五子棋 AI 程式競賽 - 進階篇 ## Table of Contents - [進階](#進階) - [權重分析](#權重分析) - [概念](#概念) - [進攻或是防守](#進攻或是防守) - [分析步驟（以活四為例）](#分析步驟以活四為例) - [虛擬碼](#虛擬碼) ## 進階在此章節，我們會提供您一些想法，幫助您提升程式的棋力，以便在競賽中取勝。 ### 權重分析 #### 概念請參考以下範例，若您是黑子（1）且輪到您的回合，依照目前的局面，您應該將棋子落在（F, 10）或是（K, 10）以獲得勝利，因此這兩個點具有最高的「權重」。透過分析棋盤上每一個點的權重，可以幫助您的程式找出最佳的落子位置。 ```text A B C D E F G H I J K L M N O P Q R S 1 . . . . . . . . . . . . . . . . . . . 2 . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . 4 . . . . . . . . . . . . . . . . . . . 5 . . . . . . . . . . . . . . . . . . . 6 . . . . . . . . . . . . . . . . . . . 7 . . . . . . . . . . . . . . . . . . . 8 . . . . . . . . . . . . . . . . . . . 9 . . . . 0 0 0 0 0 . . . . . . . . . . 10 . . . . . . 1 1 1 1 . . . . . . . . . 11 . . . . . . . . . . . . . . . . . . . 12 . . . . . . . . . . . . . . . . . . . 13 . . . . . . . . . . . . . . . . . . . 14 . . . . . . . . . . . . . . . . . . . 15 . . . . . . . . . . . . . . . . . . . 16 . . . . . . . . . . . . . . . . . . . 17 . . . . . . . . . . . . . . . . . . . 18 . . . . . . . . . . . . . . . . . . . 19 . . . . . . . . . . . . . . . . . . . ``` 為了方便講解權重的概念，接下來的棋盤範例會以 x 代表黑子、 o 代表白子。 #### 進攻或是防守請看以下範例，假設我方為黑子，由於在此黑子周圍的八個點可以提供更多的連線機會，因此我們會將此黑子周圍的八點標註為「權重 1 」，而其餘地方因為無法提供更高的連線機會，因此權重為 0。 ```text . . . . . . . . . . . . . . . . 1 1 1 . . . . 1 x 1 . . . . 1 1 1 . . . . . . . . . . . . . . . . ``` 在下列範例中，我方依然是黑子，但我們可以發現，若我們將棋子落在「權重 2 」的位置時，雖然可以使我方達成活三，但同時也會提供對手產生活四的機會，因此在白子活三的兩端我們會將權重調高至「權重 3 」，以便讓程式在這樣的局面採取防守而不是進攻的策略。 ```text . . . . . . . . 3 o o o 3 . . 1 1 1 1 . . . 2 x x 2 . . . 1 1 1 1 . . . . . . . . . . . . . . . . ``` 接下來我們考慮幾個比較複雜的局面，在以下範例中，白子看似呈現兩組活二，但實際上卻已經構成「洞四」，因此在（H, 7）位置的權重勢必為最高權重，若黑子沒有將棋子落在該位置，白子就會獲得勝利。 ```text A B C D E F G H I J K L M N O P Q R S 1 . . . . . . . . . . . . . . . . . . . 2 . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . 4 . . . . . . . . . . . . . . . . . . . 5 . . . . . o . . . . . . . . . . . . . 6 . . . . . . o . . . . . . . . . . . . 7 . . . . . . . . . . . . . . . . . . . 8 . . . . . . . . o . . . . . . . . . . 9 . . . . . . . . . o . . . . . . . . . 10 . . . . . . . x x x . . . . . . . . . 11 . . . . . . . . . . . . . . . . . . . 12 . . . . . . . . . . . . . . . . . . . 13 . . . . . . . . . . . . . . . . . . . 14 . . . . . . . . . . . . . . . . . . . 15 . . . . . . . . . . . . . . . . . . . 16 . . . . . . . . . . . . . . . . . . . 17 . . . . . . . . . . . . . . . . . . . 18 . . . . . . . . . . . . . . . . . . . 19 . . . . . . . . . . . . . . . . . . . ``` #### 分析步驟（以活四為例） 1. 讀入棋盤每一個位置，並且呼叫判斷活四各個角度的函式。 2. 在函式中判斷是否為活四，並且回傳符合活四條件的棋子顏色。 3. 呼叫紀錄活四位置的函式。 4. 在紀錄活四位置函式中，判斷回傳顏色與角度，並且呼叫權重比較函式。 5. 在權重比較函式中，比較權重陣列每個位置的權重，若新的權重大於該位置原本的權重，則進行替換。 6. 可透過分析黑子與白子的權重陣列進行落子判斷。 #### 虛擬碼接下來將透過虛擬碼簡單講解如何使用權重分析的概念。 FiveInARow.c ```c // An array to record the weight of black chess at each posistion on the chessboard int BBR[19][19]; // To compare the weight of black chess at each position on the cheesboard void blackcompare(int i, int j, int br) { int k, l; if (BBR[i][j] < br) BBR[i][j] = br; else if(BBR[i][j]==br) BBR[i][j] += 1; // for (k = 0; k < 19; k++){ // for (l = 0; l < 19; l++) // { // printf("At %d %d BR is %d \n", k, l, BBR[k][l]); // } // } } Player live4Horizontal(char (*p)[6]) { int i, j=0, b=0, w=0; for(i=0;i<6;i++){ if((i==0 || i==5) && ((*p)[i]==46)) j++; if((*p)[i]==Black) b++; else if((*p)[i]==White) w++; } if((b==4) && (j==2)) return Black; else if((w==4) && (j==2)) return White; else return None; } void locationLivw4(Player live4, int i, int j, int d){ if(live4==Black){ switch(d) { case 0: blackcompare(i, j, 4); blackcompare(i, j+5, 4); break; case 45: blackcompare(i, j, 4); blackcompare(i+5, j+5, 4); break; case 90: blackcompare(i, j, 4); blackcompare(i+5, j, 4); break; case 135: blackcompare(i, j, 4); blackcompare(i-5, j+5, 4); break; } } else if(live4==White){ // The same code } } Player check4Winner(char chessboard[19][19]){ Player live4; for(i=0; i<19; i++>){ for(j=0; j<19; j++){ // Live 4 in a hroizontal line (0 degrees) if(j<=13){ live4 = live4Horizontal((char (*)[6])&cheesboard[i][j]); locationLive4(live4, i, j, 0); } // Live 4 in a vertical line (90 degrees) if(i<=13){ live4=live4Vertical((char (*)[19])&chessboard[i][j]); locationLive4(live4, i, j, 90); } // Live 4 in a diagonal line (45 degrees) if((i<=13)&&(j<=13)){ live4=live4Diagonal((char (*)[19])&chessboard[i][j]); locationLive4(live4, i, j, 45); } // Live 4 in a back diagonal line (135 degrees) if((i<=13)&&(j>=5)){ live4=live4BackDiagonal((char (*)[19])&chessboard[i+5][j-5]); locationLive4(live4, i+5, j-5, 135); } } } } ```