reversi3.c~

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#define INFINITY 64
struct xy
{
  int x;
  int y;
};

struct xy directions[8] = {
  { -1, -1 }, {  0, -1 }, { 1, -1 }, 
  { -1,  0 },             { 1,  0 }, 
  { -1,  1 }, {  0,  1 }, { 1,  1 } 
};

int board[8][8];
int board_copy[8][8];
void init_board()
{
  int x, y;
  for (y = 0; y < 8; y++) 
    for (x = 0; x < 8; x++)
      board[x][y] = 0;

  board[4][3] = board[3][4] =  1;  // black disks
  board[3][3] = board[4][4] = -1;  // white disks
}

void print_board()
{
  int x, y;
  puts("\n abcdefgh");
  for (y = 0; y < 8; y++) {
    printf("%d", y + 1);
    for (x = 0; x < 8; x++) {
      const int d = board[x][y];
      char c = '.';
      if (d ==  1) c = 'O'; // black disk
      if (d == -1) c = '#'; // white disk
      putchar(c);
    }
    putchar('\n');
  }
  putchar('\n');
}

int can_flip(const int side,  
	     struct xy sq, const struct xy dir) // square, direction
{
  assert(board[sq.x][sq.y] == 0);
  int n = 0;
  do {
    sq.x += dir.x; 
    sq.y += dir.y; 
    n++;
    if (sq.x < 0 || sq.x >= 8 || sq.y < 0 || sq.y >= 8) return 0;
  } while (board[sq.x][sq.y] == -side);
  if (board[sq.x][sq.y] == 0) return 0;
  if (n <= 1) return 0;
  return 1;
}

int is_legal_move(int side, struct xy sq)
{
  assert(sq.x >= 0 && sq.x < 8 && sq.y >= 0 && sq.y < 8);
  int i;
  if (board[sq.x][sq.y] != 0) return 0;
  for (i = 0; i < 8; i++) {
    if (can_flip(side, sq, directions[i])) return 1;
  }
  return 0;
}

int place_disk(const int side, const struct xy sq)
{
  assert(is_legal_move(side, sq));
  int n = 0, i;
  for (i = 0; i < 8; i++) {
    const struct xy dir = directions[i];
    if (!can_flip(side, sq, dir)) continue;
    int x = sq.x + dir.x;
    int y = sq.y + dir.y;
    while (board[x][y] == -side) {
      board[x][y] = side;
      n++;
      x += dir.x;
      y += dir.y;
    }
  }
  board[sq.x][sq.y] = side;
  assert(n > 0);
  return n;
}

int generate_random_move(const int side, struct xy *move)
{
  struct xy legal_moves[60];
  int x, y, nmoves = 0, nempty = 0;
  for (x = 0; x < 8; x++) {
    for (y = 0; y < 8; y++) {
      if (board[x][y] != 0) continue;
      nempty++;
      struct xy sq;
      sq.x = x; sq.y = y;
      if (!is_legal_move(side, sq)) continue;
      assert(nmoves < 60);
      legal_moves[nmoves++] = sq;
    }
  }
  if (nempty == 0) return -1;
  if (nmoves == 0) return  0;
  *move = legal_moves[rand() % nmoves];
  return 1;
}

int eval_func(){
  int diskn,bn,wn;
  int x,y;
  struct xy corner[4] ={{0,0},{0,7},{7,0},{7,7}};
  struct xy near_corner[12] ={{0,1},{1,0},{1,1},{1,6},{0,6},{1,7},{6,0},{6,6},{7,6},{6,7},{7,1},{6,1}};
  bn = 0;
  wn = 0;
  for(x = 1; x < 7; x++){
    for(y = 1; y < 7; y++){
      if(board[x][y] == 1){
	bn ++;
      }
      else if(board[x][y] == -1){
	wn ++;
      }
    }
  }
  int i;
  for(i = 0; i < 8; i++){
    const struct xy cor = corner[i];
    if(board[cor.x][cor.y] == -1){
      wn += 1.5;
    }
    else if(board[cor.x][cor.y] == 1){
      bn += 1.5;
    }
  }
  for(i = 0; i < 12; i++){
    const struct xy ncor = near_corner[i];
    if(board[cor.x][cor.y] == -1){
      wn += 0.5;
    }
    else if(board[cor.x][cor.y] == 1){
      bn += 0.5;
    }
  }
  diskn = bn - wn;
  return diskn;
}

void undo_board(){
  int x,y;
  for(x = 0; x < 8; x++){
    for(y = 0; y < 8; y++){
      board[x][y] = board_copy[x][y];
    }
  }
}


int max_node(depth, max_depth,struct xy *bestmove){
  int best;
  struct xy legal_moves[max_depth];
  if (depth == max_depth){
    return eval_func();
  }
  else{
    best = -INFINITY;
  int x,y;
  for( x = 0; x < 8; x++){
    for(y = 0; y < 8; y++){
      if(board[x][y] == 0){
	struct xy tmp1;
	tmp1.x = x;
	tmp1.y = y;
	if(is_legal_move(0,tmp1)){
	  update_board(tmp1);
	 *bestmove = tmp1;
	  int v = min_node(depth+1,max_depth,*bestmove);
	if (v > best){
	  best = v;
	}
	undo_board();
	}
      }
    }
  }
  return best;
 }
}	
	

	

}

int min_node(depth, max_depth,struct xy *bestmove){
  int best;
  if(depth == max_depth){
    return eval_func();
  }
  else{
  best = INFINITY;
  int x,y;
   for( x = 0; x < 8; x++){
    for(y = 0; y < 8; y++){
      if(board[x][y] == 0){
	struct xy tmp;
	tmp.x = x;
	tmp.y = y;
	if(is_legal_move(1,tmp)){
	  update_board(tmp);
	  *bestmove = tmp;
	  int v = max_node(depth +1, max_depth, *bestmove);
	  if(v < best){
	    best = v;
	  }
	  undo_board();
	}
      }
    }
   }
   return best; 
}
}

int pass(){
  int x,y,flag;
  struct xy move;
  flag = 0;
  for(x = 0; x < 8; x ++){
    for(y = 0; y < 8; y++){
      move.x = x;
      move.y = y;
      if (is_legal_move(1,move)){
	flag = 1;
	return 0;
	break;
      }
    }
  }
  if(flag == 0){
    return 1;
  }
	
}

void win_lose(){
  int x,y;
  int n1,n2;
  n1 = 0;
  n2 = 0;
  int result = 0;
  for(x =0; x < 8; x++){
    for(y = 0; y < 8; y ++){
      if(board[x][y] == 1){
	n1++
	  }
      else if(board[x][y] == -1){
	n2++
	  }
    }
  }
  result = n1 - n2;
  if(result > 0){
    printf("O has won the game\n");
  }
  else if(result == 0){
    printf("Drew\n")
  }
  else{
    printf("# has won this game\n")
  }
	
}

int main(int argc, char **argv)
{
 const int human_side = (argc >= 2) ? atoi(argv[1]) : 0;

  init_board();
  print_board();
  int state1,state2;
  int turn;
  for (turn = 1;; turn *= -1) {
    struct xy move;
    if (turn == human_side) {
      if(!pass()){
	state1 = 0;
      do {
	char buf[1000];
	printf("Where? ");
	scanf("%s", buf);
	move.x = buf[0] - 'a';
	move.y = buf[1] - '1';
      } while (!is_legal_move(turn, move));
      }
      else{
	printf("pass\n");
	state1 = 1;
       }
    } else {
      const int r = generate_random_move(turn, &move);
      if (r == -1) break;     // no empty square
      if (r ==  0) {
	state2 = 1;
      } // pass (no legal move)
      else{
	state2 = 0;
      }
      printf("turn = %d, move = %c%c\n", turn, 'a' + move.x, '1' + move.y);
    }
    if(turn== human_side && state1 == 0){
    place_disk(turn, move);
    }
    if(turn == human_side *(-1) && state2 == 0){
      place_disk(turn, move);
    }
    print_board();
    if(state1 == 1 && state2 == 1){
      break;
    }
  }
  win_lose();
}