--Back--
/**
 * Othello example program
 * Made by Shiuh-Sheng Yu on 5/20/1997 at NCNU.  
 * Last modified date: 2003/01/08
 */
#include <stdio.h>
#include <string.h>
// 0代表沒有子
#define EMPTY  (unsigned char)0x00
// 第一個bit代表黑子
#define BLACK  (unsigned char)0x01
// 第二個bit代表白子
#define WHITE  (unsigned char)0x02
// 利用最後兩個bit 11(10進位 3), 用&判斷是否有子,用^改為對方
#define STONE  (unsigned char)0x03
// 第三個bit代表邊界
#define BOUND  (unsigned char)0x04
#define COMPUTER 1
#define HUMAN 2
/* 以一維陣列來代表二維盤面 */
static const unsigned char newboard[100] = {
    BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,WHITE,BLACK,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,BLACK,WHITE,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BOUND,
    BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND,BOUND
};
/* 八個方向 */
static const int directions[8]={1,-1,10,-10,-9,-11,9,11};
/* 定義盤面資料結構 */
struct othello {
    struct othello *parent; /* link to parent node, for game tree */
    float value;    /* value of the board in terms of player */
    int diskdiff;   /* current stone difference on board     */
    unsigned char board[100]; /* board status structure      */
    unsigned char turn;       /* whose turn to play          */
};

/**
 * 在螢幕上顯示盤面狀態
 */
void show_board(struct othello *this) {
    int i;
    printf("    a b c d e f g h\n  * * * * * * * * * *");
    for (i = 10; i < 90; i++) {
        if (i%10 == 0) { /* 要印新的一行 */
            printf("\n%c", '0'+(i/10));
        }
        switch (this->board[i]) {
            case WHITE: printf(" O"); break;
            case BLACK: printf(" X"); break;
            case BOUND: printf(" *"); break;
            case EMPTY: printf(" ."); break;
        }
    }
    printf("\n  * * * * * * * * * *\n");
}

/**
 * 顯示遊戲的最後結果
 */
void show_result(struct othello *this) {
    int b, w, p;
    show_board(this);
    for (b=w=0, p=11; p<89; p++) { // 計算雙方子數
        if (this->board[p] == BLACK) {
           b++;
        } else if (this->board[p] == WHITE) {
            w++;
        }
    }
    if (b > w) { // 黑贏了
        printf("\nX-%d vs. O-%d, X win %d.\n",b,w,b-w);
    } else if (b < w) { // 白贏了
        printf("\nX-%d vs. O-%d, O win %d.\n",b,w,w-b);
    } else { // 平手
        printf("\nX-%d vs. O-%d, TIE.\n",b,w);
    }
}
/**
 * 在this盤面下, test_side這一方能否下再pos(假設pos為空點). 傳回1表示可以, 0表示不行
 */
int is_legal(struct othello *this, int pos, unsigned char test_side) {
    unsigned char opp = test_side^STONE;
    int i, scan, dir;
    for (i = 0; i < 8; i++) { // 掃描8個方向
        if (this->board[scan = pos + (dir = directions[i])] == opp) { // 往方向i看pos下一個位置是否為敵方的子
            for (scan += dir; this->board[scan] == opp; scan += dir) // 跳過所有敵方的子
                ;
            if (this->board[scan] & test_side) { // 如果停下來的地方為自己的子,則pos可以下
                return(1);
            }
        }
    }
    return(0);
}

/**
 * 檢查this盤面, test_side是否都沒有地方可以下了
 */
int nolegal(struct othello *this, unsigned char test_side) {
    int pos;
    for (pos=11; pos<89; pos++) { // 對所有的空點, 檢查是否可以下
        if (this->board[pos]==EMPTY && is_legal(this, pos, test_side)) { // 找到可以下的地方了
            return(0);
        }
    }
    return(1); // 找不到地方可下
}

/**
 * 找出this盤面下, 所有turn方能下的位置, 將這些點存到moves裡, 並傳回找到的位置總數
 */
int find_legals(struct othello *this,  int *moves) {
    int pos, legal_moves=0;
    for (pos=11; pos<89; pos++) { // 掃描所有可能的位置
        if (this->board[pos]==EMPTY && is_legal(this, pos, this->turn)) { // 找到可下的地方
            moves[legal_moves++] = pos;
        }
    }
    return(legal_moves);
}

/**
 * 檢查輸入的字串是否為合法可下的位置, 不合法傳回0, 合法傳回buf字串所代表的座標位置
 */
int legal_input(struct othello *this, char* buf) {
    int pos;
    if (buf[0]<'a' || buf[0]>'h' || buf[1]<'1' || buf[1]>'8') { // 如果格式不對
        return(0);
    }
    pos = buf[0]-'a'+1+10*(buf[1] - '0'); // 進行座標轉換
    if (this->board[pos]==EMPTY && is_legal(this, pos, this->turn)) {
        return(pos);
    }
    return(0);
}

/**
 * 在this盤面下, 下turn方的一子在pos上
 */
void add_move(struct othello *this, int pos) {
    unsigned char opp = this->turn^STONE;
    int c, scan, i, dir;
    if (pos != 0) { // pos 若為0表示要pass
        for (i = 0; i < 8; i++) { // 檢查8個方向是否能吃掉對方的子
            // 跳過所有敵方的棋子
            for (scan = pos+(dir=directions[i]); this->board[scan] == opp; scan+=dir);
            // 如果停下來的地方是自己的子, 就可以吃了
            if (this->board[scan] & this->turn) {
                for (c = pos+dir; c != scan; c+=dir) { // 將所有敵方的子變成我方的
                    this->board[c] = this->turn;
                    this->diskdiff += 2; // 棋子數目的差距+2, 我方多1, 對方-1
                }
            }
        }
        this->diskdiff++; // 在加上要放上去的棋子
        this->board[pos] = this->turn; // 在pos放上自己的子
    }
    // 下完後, 該對方下了
    this->turn = opp;
    // diskdiff是用準備下的人的眼光看, 因此要*-1
    this->diskdiff = - this->diskdiff;
}

/**
 * 盤面好壞判斷函數, 請自行改寫
 */
void eval_func(struct othello *this) {
    this->value = this->diskdiff;
}

/**
 * 展開深度為depth的遊戲樹
 */
void alpha_beta(struct othello* this, int depth) {
    int k, legal_moves, legals[60];
    struct othello *p, tmp;
    if (depth <= 1) { // 到最底層了, 呼叫eval_func來判斷好壞
        eval_func(this);
    } else { // 繼續展開遊戲樹
        this->value = -1000000; /* set to maximum negative value */
        if ((legal_moves=find_legals(this, legals))==0) { // 如果沒地方可下
            legals[legal_moves++] = 0; // 那麼pass就變成合法的著手了
        }
        for (k = 0;k < legal_moves; k++) { // 對每個合法著手,一一展開遊戲樹
            memcpy(&tmp, this, sizeof(struct othello)); // 先複製盤面到tmp
            add_move(&tmp, legals[k]); // 在tmp上下一子
            tmp.parent = this; // 設定tmp是從this變化過來的
            alpha_beta(&tmp, depth - 1); // 由tmp展開深度為depth-1的遊戲樹
            if (this->value < -tmp.value) { // 如果下的這一步比之前的都要好(敵方不好就是我方好)
                this->value = -tmp.value; // 那這盤面對我而言最好的結果就是tmp的結果
                for (p = this->parent; p!=0 ;) { // 檢查對方(變化到此路徑的所有敵方著手)有這麼笨嗎?
                    if (this->value >= -p->value) { // 敵方已經找到不讓我有機會下成this盤面的好手了
                        return; // 假設對手不笨, 那我拼命算對方不會的下的變化幹嘛?
                    }
                    // 繼續往上跳兩層看對方的著手
                    p = p->parent;
                    if (p != 0) p = p->parent;
                }
            }
        }
    }
}

/**
 * 找出this盤面上的最好著手(往下看level層)
 */

int best(struct othello *this, int level) {
    int legal_moves, k, best=0, legals[60];
    struct othello tmp;
    // 先找出所有可能的著手
    legal_moves = find_legals(this, legals);
    // 設定我方一開始的優勢為負無窮大
    this->value = -1000000;
    // 嘗試每一個著手
    for (k = 0;k < legal_moves; k++) {
        memcpy(&tmp, this, sizeof(struct othello)); // 先複製到tmp
        add_move(&tmp, legals[k]); // 在tmp上下子
        tmp.parent = this; // 設定tmp是由this變化而來
        alpha_beta(&tmp, level); // 由tmp往下展開level層
        if (this->value < -tmp.value) { // 如果這個著手比前面的都要好
            this->value = -tmp.value;
            best = legals[k];
        }
    }
    return(best);
}

/**
 * 初始化struct othello
 */
void init_othello(struct othello *this) {
    memcpy(this->board,newboard,100); // 複製開始盤面
    this->diskdiff = 0; // 一開始雙方2-2
    this->turn = BLACK; // 黑方先下
    this->parent = 0; // 這是一開始的盤面, 不是從別的盤面變化來的
}

/**
 * 從this盤面開始下
 * black和white這兩個參數代表黑白雙方是由 "人" 還是 "電腦"下
 * 也就是說這局棋可以人和人, 也可以電腦和電腦下
 */
void play(struct othello *this, int black, int white, int level) {
    int who_play, pos;
    char buf[100];
    do {
        show_board(this); // 先顯示盤面
        if (nolegal(this, this->turn)) { // 假如應該下的人沒地方下
            pos = 0; // 則應該pass, 所以也不用管是人還是電腦下了
        } else {
            // 檢查是黑方下還是白方下
            if (this->turn == BLACK) {
                who_play = black;
            } else {
                who_play = white;
            }
            // 如果要下的那一方是電腦
            if (who_play == COMPUTER) {
                pos = best(this,level); // 呼叫best函數找出最好的著手
            } else { // 如果是人下
                do { // 一直讀輸入, 直到是合法的輸入為止
                    gets(buf);
                } while (!(pos = legal_input(this, buf)));
            }
        }
        add_move(this, pos); // 下子吧
    } while (!(nolegal(this, BLACK) && nolegal(this, WHITE))); // 如果雙方都不能下就結束了
    show_result(this); // 顯示最後結果
}

int main(int argc, char** argv) {
    // 內定黑方電腦先下, 白方人腦後下, 搜尋深度為5
    int first = COMPUTER, second = HUMAN, level = 5;
    struct othello newgame;
    // 依據命令列上的參數, 更改下棋者
    if (argc>=2 && tolower(*argv[1])=='h') {
        first = HUMAN;
    }
    if (argc>=3 && tolower(*argv[2])=='c') {
        second = COMPUTER;
    }
    if (argc>=4) {
        sscanf(argv[3],"%d",&level);
    }
    init_othello(&newgame);
    play(&newgame, first, second, level);
    return(0);
}

--Back--