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

國立屏東大學電腦五子棋 AI 程式競賽──進階篇
- 權重分析
- 技術上的細節

在此章節，我們會提供您一些想法，幫助您提升程式的棋力，以便在競賽中取勝。

權重分析

概念

請參考以下範例，若您是黑子（1）且輪到您的回合，依照目前的局面，您應該將棋子落在（F, 10）或是（K, 10）以獲得勝利，因此這兩個點具有最高的「權重」。透過分析棋盤上每一個點的權重，可以幫助您的程式找出最佳的落子位置。

   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。

. . . . . . .
. . . . . . .
. . 1 1 1 . .
. . 1 x 1 . .
. . 1 1 1 . .
. . . . . . .
. . . . . . .

在下列範例中，我方依然是黑子，但我們可以發現，若我們將棋子落在「權重 2 」的位置時，雖然可以使我方達成活三，但同時也會提供對手產生活四的機會，因此在白子活三的兩端我們會將權重調高至「權重 3 」，以便讓程式在這樣的局面採取防守而不是進攻的策略。

. . . . . . .
. 3 o o o 3 .
. 1 1 1 1 . .
. 2 x x 2 . .
. 1 1 1 1 . .
. . . . . . .
. . . . . . .

接下來我們考慮幾個比較複雜的局面，在以下範例中，白子看似呈現兩組活二，但實際上卻已經構成「洞四」，因此在（H, 7）位置的權重勢必為最高權重，若黑子沒有將棋子落在該位置，白子就會獲得勝利。

   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 . . . . . . . . . . . . . . . . . . .

分析步驟（以活四為例）

讀入棋盤每一個位置，並且呼叫判斷活四各個角度的函式。
在函式中判斷是否為活四，並且回傳符合活四條件的棋子顏色。
呼叫紀錄活四位置的函式。
在紀錄活四位置函式中，判斷回傳顏色與角度，並且呼叫權重比較函式。
在權重比較函式中，比較權重陣列每個位置的權重，若新的權重大於該位置原本的權重，則進行替換。
可透過分析黑子與白子的權重陣列進行落子判斷。

虛擬碼

接下來將透過虛擬碼簡單講解如何使用權重分析的概念。

FiveInARow.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);
            }
        }
    }
}

技術上的細節

argv[1] 為你本次程式執行所持的棋子，"Black" 為黑；"White" 為白。
stdin 格式為 361 個棋盤字元，以 ASCII 編碼。
cwd 為 /tmp/gomoku，tmpfs，整個 /tmp 除了 /tmp/gomoku/${使用者名稱} 以外都可以讀寫並保留到直到對奕（十盤棋）結束（或是你的程式 return 1）。
stdout 格式必須符合 /[A-S], ((1[0-9])|[1-9])\n?/ （正規表達式）