Try   HackMD

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

在這一個章節，會告訴您該如何進行簡單的局面判斷。同時為了使日後的程式維護更加方便，我們會將函式獨立出一個（或多個）檔案，並且提供定義標頭檔。

五子連線

在章節入門之中，您已經可以寫出一個亂數版的五子棋程式了，但它仍然不夠聰明對吧！因此我們需要加入一些判斷，讓程式能夠根據棋局的變化決定要下子在哪個位置。我們來回顧一下目前的程式碼：

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main(int argc, char *argv[]){

    char chessboard[19][19];
    char letter_arr[19] = "ABCDEFGHIJKLMNOPQRS";
    int i = 0, j = 0;
    int b = 0, w = 0;
    int row = 0, col = 0;
    int quit = 0;

    for(i=0; i<19; i++){
        for(j=0; j<19; j++){
            scanf(" %c", &chessboard[i][j]);
            if( chessboard[i][j]=='1')
                b++;
            else if(chessboard[i][j]=='0')
                w++;
        }
    }

    if( (strcmp(argv[1],"Black")==0) && (b==0) && (w==0) ){
        printf("J, 10\n");
        exit(0);
    }

    srand(time(NULL));
    while(!quit){
        row = rand()%19;
        col = rand()%19;
        if(chessboard[row][col] == '.'){
            printf("%c, %d\n", letter_arr[col], row+1);
            quit = 1;
        }
    }

}

接下來將告訴您如何進行勝者（五子連線）的判斷。

在後續的講解中，我們將使用 E 、 S 、 W 、 N 、 SE 、 SW 、 NE 、 NW 分別代表棋盤上的東、南、西、北、東南、西南、東北、西北等方向。

方位 E

我們首先在 function.h 中定義各項 function prototype，請看範例程式碼：

function.h

typedef enum {Black = 49, White = 48, None = 0} Player;

Player checkHorizontal(char (*p)[5]);
Player checkVertical(char (*p)[19]);
Player checkDiagonal(char (*p)[19]);
Player checkBackDiagonal(char (*p)[19]);

Player check4Winner(char chessboard[19][19]);
  • Player：
    在此 enumeration 中， 49 與 48 分別代表字元 1 與 0 在 ASCII 中的代碼。
  • checkHorizontal()：
    此函式用於判斷方位 E 的五子連線。
  • checkVertical()：
    此函式用於判斷方位 S 的五子連線。
  • checkDiagonal()：
    此函式用於判斷方位 SE 的五子連線。
  • checkBackDiagonal()：
    此函式用於判斷方位 SW 的五子連線。
  • check4Winner()：
    此函式用於呼叫各方位的判斷函式，並且回傳最終結果。

以上述程式碼的框架，我們針對棋盤上的 E 、 S 、 SE 、 SW 等四個方位的檢查，至於 N 、 W 、 NE 、 NW 則不需加以檢查。我們只所以不需要從五子連線的結尾處往開頭處檢查，是因為就同一個連線而言，我們已經從開頭處進行檢查了，而不需要重複進行檢查。

在 main.c 中，我們透過呼叫 check4Winner() 來進行勝負判定，並且在 check4Winner() 呼叫四個方位的判定函式。需要注意的是，在 main.c 以及 function.c 中都必須引入函式標頭檔案 function.h 。
請看範例程式碼：

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "function.h"

int main(int argc, char *argv[]){

    char chessboard[19][19];
    char letter_arr[19] = "ABCDEFGHIJKLMNOPQRS";
    Player winner;
    int i = 0, j = 0;
    int b = 0, w = 0;
    int row = 0, col = 0;
    int quit = 0;

    for(i=0; i<19; i++){
        for(j=0; j<19; j++){
            scanf(" %c", &chessboard[i][j]);
            if( chessboard[i][j]=='1')
                b++;
            else if(chessboard[i][j]=='0')
                w++;
        }
    }

    winner = check4Winner(chessboard);
    if(winner == Black)
        printf("Black win!\n");
    else if(winner  == White)
        printf("White win!\n");
    else
        printf("Quack! Quack!\n");
}

function.c

#include <stdio.h>
#include <stdlib.h>
#include "function.h"

Player check4Winner(char chessboard[19][19]){
    int i = 0, j = 0;
    Player winner;
    for (i=0; i<19; i++){
        for(j=0; j<19; j++){
            // 在此進行每個位置的檢查
            winner = checkHorizontal(char (*p)[5]);
            if(winner != None)
                return winner;
        }
    }
    return None;
}

在 check4Winner() 中，我們首先呼叫 checkHorizontal() 來進行方位 E 的五子連線判斷，此部分要從目前所在的 chessboard[i][j] 這個位置開始，往右檢查合計 5 個位置，此函式的參數為一個指向具有五個元素的字元陣列之指標。
因應這個函式的參數需求，我們在呼叫它時需要將正要檢查的 chessboard[i][j] 這個元素所在的位址，視為是一個具有 5 個字元的陣列之開頭，並將這個位址傳給 checkHorizontal() 函式。
參數傳入之後，在 checkHorizontal() 中的檢查相當容易，從該函式的角度來看，所傳入的只不過是一個簡單的一維陣列，我們可以使用以下程式碼來完成檢查：

Player checkHorizontal(char (*p)[5]){
    int i = 0;
    int b = 0, w = 0;
    for(i=0; i<5; i++){
        if((*p)[i] == Black)
            b++;
        else if((*p)[i] == White)
            w++;
    }
    if(b == 5)
        return Black;
    else if(w == 5)
        return White;
    else
        return None;
}

值得注意的是，我們並不是永遠都需要去進行方位 E 的檢查！如果在某個位置其往右的方向已經少於 5 個位置，那麼就不可能找到從此處出發的五子連線！因此， check4Winner() 函式內的程式碼還要再加入一個條件如下：

if(j <= 14){
    winner = checkHorizontal(char (*p)[5]);
    if(winner != None)
        return winner;
}

現在，我們來看看完整的範例程式碼：

#include <stdio.h>
#include <stdlib.h>
#include "function.h"

Player checkHorizontal(char (*p)[5]){
    int i = 0;
    int b = 0, w = 0;
    for(i=0; i<5; i++){
        if((*p)[i] == Black)
            b++;
        else if((*p)[i] == White)
            w++;
    }
    if(b == 5)
        return Black;
    else if(w == 5)
        return White;
    else
        return None;
}

Player check4Winner(char chessboard[19][19]){
    int i = 0, j = 0;
    Player winner;
    for (i=0; i<19; i++){
        for(j=0; j<19; j++){
            if(j<=14){
                winner = checkHorizontal((char (*)[5])&chessboard[i][j]);
                if(winner != None) return winner;
            }
        }
    }
    return None;
}

方位 S

接下來我們將進行方位 S 的檢查，此部分我們必須要從目前所在的 chessboard[i][j] 這個位置開始，往下檢查合計 5 個位置。
基本上，此段程式碼與 checkHorizontal() 幾乎完全一樣，其差別在於比較的對象從 (*p)[i] 變成了 *p[i] ，此差別就形成了 row 與 column 方向的差異。請參考範例程式碼：

Player checkHorizontal(char (*p)[19]){
    int i = 0;
    int b = 0, w = 0;
    for(i=0; i<5; i++){
        if(*p[i] == Black)
            b++;
        else if(*p[i] == White)
            w++;
    }
    if(b == 5)
        return Black;
    else if(w == 5)
        return White;
    else
        return None; 
}

同樣的，在 check4Winner() 中，我們一樣考慮到了往方位 S 的方向是否還有 5 個以上的位置：

if(i<=14){
    winner = checkVertical((char (*)[19]) &chessboard[i][j]);
    if(winner != None) return winner;
}

方位 SE

接下來的 SE 方向是要從 chessboard[i][j] 往右下角方向進行檢查，由於需要使用到往下的方向，我們仍是使用 char (*p)[19] 作為其參考的型態定義。
這裡仍然是使用 (*p)[i] 來進行比對，但是在迴圈累加 i 而往右移動的同時，我們也使用 p++ 來將指標 p 往下移動一個 row 。請參考範例程式碼：

Player checkDiagonal(char (*p)[19]){
    int i = 0;
    int b = 0, w = 0;
    for(i=0; i<5; i++){
        if((*p)[i] == Black)
            b++;
        else if((*p)[i] == White)
            w++;
        p++;
    }
    if(b == 5)
        return Black;
    else if(w == 5)
        return White;
    else
        return None;
}

當然，在呼叫 checkDiagonal() 的時候也要注意往右下的方向必須要不少於 5 個的位置：

if((i<=14) && (j<=14)){
    winner = checkDiagonal((char (*)[19]) &chessboard[i][j]);
    if(winner != None) return winner;
}

方位 SW

最後我們來看看往 SE 方向的檢查，其參數之設計與前面的 checkDiagonal() 一致，並且也要確保其左下與下方有足夠的位置，因此加入 if((i<=14) && (i>=4)) 的條件判斷：

if((i<=14) %% (j>=4)){
    winner = checkBackDiagonal((char (*)[18]&chessboard[i][j]));
    if(winner != None) return winner;
}

為了便利設計起見，在呼叫 checkBackDiagonal() 時，所傳入的並不是 chessboard[i][j] 的位址，而是 chessboard[i+4][j-4] 的位置，並且由此位置開始往右上角進行檢查。為何不傳入 chessboard[i][j] 往左下檢查至 chessboard[i+4][j-4] 呢？主要原因是為了避免索引值為負而增加設計上的複雜度。請參考以下程式碼：

Player checkBackDiagonal(char (*)[18]){
    int i = 0;
    int b = 0, w = 0;
    for(i=0; i<5; i++){
        if((*p)[0] == Black)
            b++;
        else if((*p)[0] == white)
            w++;
        p++;
    }
    if(b == 5)
        return Balck;
    else if(w == 5)
        return White;
    else
        return None;
}

四子連線

當棋盤上出現了四子連線的時候，極大的機率代表某一方即將獲勝，因此本章節將列出幾個具有代表性的四子連線局面，來讓你的程式能夠落下勝利的最後一子。

活四

活四即代表四子連線的情況下，兩端皆有空位，因此當活四出現的時候基本上就代表勝負已定。若是我方出現活四，只需要在四子連線的任一端下子便可獲勝，若敵方出現活四，我方仍然可以進行最後的阻擋（掙扎）。請看以下棋盤範例：

   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 . . . . . . . 1 1 1 1 . . . . . . . . 
10 . . . . . . . . . . . . . . . . . . . 
11 . . . . . . . . . . . . . . . . . . . 
12 . . . . . . . . . . . . . . . . . . . 
13 . . . . . . . . . . . . . . . . . . . 
14 . . . . . . . . . . . . . . . . . . . 
15 . . . . . . . . . . . . . . . . . . . 
16 . . . . . . . . . . . . . . . . . . . 
17 . . . . . . . . . . . . . . . . . . . 
18 . . . . . . . . . . . . . . . . . . . 
19 . . . . . . . . . . . . . . . . . . .

假設我方為黑子（1），對手為白子（0），若輪到我方回合，我們可以選擇將棋子下在（G, 9）或是（M, 9）的位置，如此一來我方即可獲得勝利。若現在為對手回合，則敵方可以選擇在（G, 9）或是（M, 9）位置進行阻擋。

死四

死四代表在四子連線的情況下，其中一端遭到阻擋，因此當我方出現死四的時候有極大機率能夠獲勝，但也有可能被對手搶先一步進行阻擋。請看以下棋盤範例：

   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 1 1 1 1 . . . . . . . .
10 . . . . . . . . . . . . . . . . . . . 
11 . . . . . . . . . . . . . . . . . . . 
12 . . . . . . . . . . . . . . . . . . .
13 . . . . . . . . . . . . . . . . . . . 
14 . . . . . . . . . . . . . . . . . . . 
15 . . . . . . . . . . . . . . . . . . . 
16 . . . . . . . . . . . . . . . . . . . 
17 . . . . . . . . . . . . . . . . . . . 
18 . . . . . . . . . . . . . . . . . . . 
19 . . . . . . . . . . . . . . . . . . .

在上面的棋盤中，我方依然為黑子（1），敵方為白子（0），可以發現我方在（H, 9）到（L, 9）呈現死四，原因是因為在四子連線的情況下有其中一端遭到對手棋子或是棋盤邊界阻擋。若輪到我方回合，我們可以將棋子下在（M, 9）的位置以獲得勝利，若是對手的回合，則對手可以選擇在（M, 9）進行阻擋。

洞四

洞四則是較為特殊的情況。請看以下棋盤範例：

   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 . . . . . . 1 1 1 . 1 . . . . . . . . 
 7 . . . . . . . . . . . . . . . . . . . 
 8 . . . . . . . . . . . . . . . . . . . 
 9 . . . . . . 1 1 . 1 1 . . . . . . . .
10 . . . . . . . . . . . . . . . . . . . 
11 . . . . . . . . . . . . . . . . . . . 
12 . . . . . . 1 . 1 1 1 . . . . . . . .
13 . . . . . . . . . . . . . . . . . . . 
14 . . . . . . . . . . . . . . . . . . . 
15 . . . . . . . . . . . . . . . . . . . 
16 . . . . . . . . . . . . . . . . . . . 
17 . . . . . . . . . . . . . . . . . . . 
18 . . . . . . . . . . . . . . . . . . . 
19 . . . . . . . . . . . . . . . . . . .

在上面棋盤範例中，我們列出了三種不同狀態的洞四，如同前面幾個範例，當我方為黑子（1），敵方為白子（0）的情況下，若是輪到我方回合，只需要在（J, 6）、（I, 9）或是（H, 12）這三個位置下子即可獲得勝利。若是輪到對手的回合，對手只需要在（J, 6）、（I, 9）或是（H, 12）這三個位置下子便可成功進行阻擋。

以上我們僅列出了幾個可能的情況，除了上述的局面，您也可以依照這樣的邏輯去設計三子連線、兩子連線的情況，並且搭配五子連線中所提到各個方位的判斷，同時也須考慮當棋子連線的時候，是否會碰到棋盤邊界的問題。

Last changed by 
 
junwu
0
1917
Published on HackMD