/**
* 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--