『実用Common Lisp』に出てくるオセロをCに移植(単純なCPU対戦まで)

othello.c

#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;
}