Skip to content

Instantly share code, notes, and snippets.

@takoeight0821 takoeight0821/othello.c
Last active May 22, 2018

Embed
What would you like to do?
『実用Common Lisp』に出てくるオセロをCに移植(単純なCPU対戦まで)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define EMPTY 0
#define BLACK 1
#define WHITE 2
#define OUTER 3
int all_dir[8] = {-11, -10, -9, -1, 1, 9, 10, 11};
void initialize_board(int board[100]) {
for (int i = 0; i < 100; i++) {
board[i] = OUTER;
}
for (int i = 11; i <= 88; i++) {
if (1 <= (i % 10) && (i % 10) <= 8) {
board[i] = EMPTY;
}
}
board[44] = WHITE; board[45] = BLACK;
board[54] = BLACK; board[55] = WHITE;
}
char char_of(int piece) {
if (piece == EMPTY) return '.';
if (piece == BLACK) return 'x';
if (piece == WHITE) return 'o';
return '?';
}
/* posが座標として正しい整数かどうか */
int is_valid(int pos) {
return (11 <= pos && pos <= 88) && (1 <= pos % 10 && pos % 10 <= 8);
}
/* 相手の色を返す */
int opponent(int color) {
if (color == BLACK) return WHITE;
return BLACK;
}
/* 返せる石があるならその座標を, なければ0を返す */
int would_flip(int pos, int color, int board[], int dir) {
int c = pos + dir;
if (board[c] == opponent(color)) { /* dir方向の隣が相手の石なら,挟んでいるかを判定 */
while (board[c] == opponent(color)) { /* 相手の石がつづく限りdir方向に進む */
c += dir;
}
if (board[c] == color) return c; /* 挟む石が見つかればその座標を返す */
return 0; // board[c] == OUTER || board[pos] == EMPTY
} else {
return 0;
}
}
/* ひっくり返す */
void make_flips(int pos, int color, int board[], int dir) {
int bracketer = would_flip(pos, color, board, dir);
if (bracketer) {
for (int c = pos + dir; c != bracketer; c += dir) {
board[c] = color;
}
}
}
/* boardに手を適用する */
void make_move(int pos, int color, int board[]) {
board[pos] = color;
for (int i = 0; i < 8; i++) {
make_flips(pos, color, board, all_dir[i]);
}
}
void copy_and_make_move(int pos, int color, int from[], int to[]) {
for (int i = 0; i < 100; i++) {
to[i] = from[i];
}
make_move(pos, color, to);
}
/* ひっくり返せる石があるかどうか(== 合法な手かどうか) */
int is_legal(int pos, int color, int board[]) {
if (board[pos] == EMPTY) {
for (int i = 0; i < 8; i++) {
if (would_flip(pos, color, board, all_dir[i])) {
return 1;
}
}
}
return 0;
}
/* 合法な手がありうるか */
int any_legal_move(int color, int board[]) {
for (int i = 11; i <= 88; i++) {
if ((1 <= i % 10 && i % 10 <= 8) && is_legal(i, color, board)) {
return i;
}
}
return 0;
}
/* 次のターンがどちらのものか(どっちでもなければ(== ゲーム終了なら)0を返す) */
int next_to_play(int board[], int prev_pl) {
int opp = opponent(prev_pl);
if (any_legal_move(opp, board)) return opp;
if (any_legal_move(prev_pl, board)) {
printf("%c has no moves and must pass.\n", char_of(opp));
return prev_pl;
}
return 0;
}
int human(int color, int board[]) {
int pos;
printf("%c to move: ", char_of(color));
scanf("%d", &pos);
return pos;
}
int rand0_until(int n) {
int r = rand() % n;
return r;
}
int random_strategy(int color, int board[]) {
int pos = 0;
while (!(is_valid(pos) && is_legal(pos, color, board))) {
pos = rand0_until(100);
}
return pos;
}
int maximize(int (*eval_fn)(int color, int board[]), int color, int board[]) {
int max_score = -100; // マス数以上の点差はつかない
int best_pos = 0;
int cpy[100];
for (int i = 11; i <= 88; i++) {
if (is_valid(i) && is_legal(i, color, board)) {
copy_and_make_move(i, color, board, cpy);
if (max_score < (*eval_fn)(color, cpy)) {
max_score = (*eval_fn)(color, cpy);
best_pos = i;
}
}
}
return best_pos;
}
int count(int color, int board[]) {
int ret = 0;
for(int i = 0; i < 100; i++) {
if (board[i] == color) ret++;
}
return ret;
}
int count_diff(int color, int board[]) {
return count(color, board) - count(opponent(color), board);
}
int maximize_diff(int color, int board[]) {
return maximize(count_diff, color, board);
}
int weights[100] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 120, -20, 20, 5, 5, 20, -10, 120, 0,
0, -20, -40, -5, -5, -5, -5, -40, -20, 0,
0, 20, -5, 15, 3, 3, 15, -5, 20, 0,
0, 5, -5, 3, 3, 3, 3, -5, 5, 0,
0, 5, -5, 3, 3, 3, 3, -5, 5, 0,
0, 20, -5, 15, 3, 3, 15, -5, 20, 0,
0, -20, -40, -5, -5, -5, -5, -40, -20, 0,
0, 120, -20, 20, 5, 5, 20, -10, 120, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
int weighted_pos (int color, int board[]) {
int opp = opponent(color);
int sum = 0;
for (int i = 0; i < 100; i++) {
if (board[i] == color) {
sum += weights[i];
} else if (board[i] == opp) {
sum -= weights[i];
}
}
return sum;
}
int maximize_weighted(int color, int board[]) {
return maximize(weighted_pos, color, board);
}
typedef struct {
int value;
int move;
} AlphaBetaResult;
AlphaBetaResult alpha_beta(int color, int board[], int achievable, int cutoff, int depth, int (*eval_fn)(int color, int board[])) {
AlphaBetaResult ret = { 0, 0 };
int board2[100];
if (depth == 0) {
ret.move = eval_fn(color, board);
return ret;
}
if (any_legal_move(color, board)) {
int best_move = 0;
for (int i = 11; i <= 88; i++) {
if (is_legal(i, color, board)) {
best_move = i;
}
}
for (int i = 11; achievable < cutoff && i <= 88; i++) {
if (!is_legal(i, color, board)) {
continue;
}
copy_and_make_move(i, color, board, board2);
int val = -(alpha_beta(opponent(color), board2, -cutoff, -achievable, depth - 1, eval_fn)).value;
if (val > achievable) {
achievable = val;
best_move = i;
}
}
ret.move = best_move;
ret.value = achievable;
return ret;
}
if (any_legal_move(opponent(color), board)) {
ret = alpha_beta(opponent(color), board, -cutoff, -achievable, depth - 1, eval_fn);
ret.value = -ret.value;
return ret;
} else {
int diff = count_diff(color, board);
if (diff < 0) {
ret.value = INT_MIN;
} else if (diff > 0) {
ret.value = INT_MAX;
} else {
ret.value = 0;
}
return ret;
}
}
int alpha_beta_weighted(int color, int board[]) {
AlphaBetaResult ret = alpha_beta(color, board, INT_MIN, INT_MAX, 10, weighted_pos);
return ret.move;
}
/* 手の入力から適用まで */
int get_move(int (*strategy)(int color, int board[]), int color, int board[]) {
int pos;
pos = (*strategy)(color, board);
if (is_valid(pos) && is_legal(pos, color, board)) {
printf("%c moves to %d.\n", char_of(color), pos);
make_move(pos, color, board);
} else {
printf("Illegal move: %d\n", pos);
get_move(*strategy, color, board);
}
return pos;
}
void print_board(int pl_color, int board[]) {
printf(" 1 2 3 4 5 6 7 8\n");
for (int row = 1; row <= 8; row++) {
printf(" %d ", row * 10);
for (int col = 1; col <= 8; col++) {
int piece = board[col + 10 * row];
char c = char_of(piece);
if (pl_color != EMPTY && c == '.' && is_legal(col+10*row, pl_color, board)) {
c = '_';
}
printf("%c ", c);
}
printf("\n");
}
}
int main(void) {
int board[10 * 10];
int player = BLACK;
initialize_board(board);
srand((unsigned)time(NULL));
while(player != 0) {
print_board(player, board);
if(player == BLACK) {
get_move(human, player, board);
} else {
get_move(alpha_beta_weighted, player, board);
}
player = next_to_play(board, player);
}
printf("The game is over. Final result:\n");
print_board(EMPTY, board);
printf("%c - %c = %d\n", char_of(BLACK), char_of(WHITE), count_diff(BLACK, board));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.