Ticket #150: Monte_Carlo_board_code.c

/* Special board code for Monte Carlo simulations.
 *
 * A liberty edge is the combination of the position of the liberty
 * and the direction to a string given by the index into the delta[]
 * array. A liberty edge at lib with corresponding string in direction
 * delta[dir] is encoded as (lib << 2 | dir).
 *
 * The stones of a string are linked in a cyclic list through the
 * next_stone field, just like the global board does.
 *
 * Likewise the liberty edges corresponding to each string are
 * connected in a doubly linked cyclic list through the
 * previous_liberty_edge and next_liberty_edge fields.
 *
 * The reference stone has to be the same for every stone in a string
 * but it doesn't have to be a predictable one, in contrast to the
 * origin in the global board. The reference stone is the only one
 * which is guaranteed to have a valid pointer to the "first" liberty
 * edge (just an arbitrary element in the circular list).
 */


struct mc_board {
  Intersection board[BOARDSIZE];
  int board_ko_pos;
  int reference_stone[BOARDMAX];
  int next_stone[BOARDMAX];
  int first_liberty_edge[BOARDMAX];
  int previous_liberty_edge[4 * BOARDMAX];
  int next_liberty_edge[4 * BOARDMAX];
};


/* Add a liberty edge for a string at pos with liberty at lib and
 * direction dir.
 */
static void
mc_add_liberty_edge(struct mc_board *mc, int pos, int lib, int dir)
{
  int this_liberty_edge = (lib << 2) | dir;
  int reference = mc->reference_stone[pos];
  int first_liberty_edge = mc->first_liberty_edge[reference];

  gg_assert(lib + delta[dir] == pos);
  
  if (first_liberty_edge) {
    int second_liberty_edge = mc->next_liberty_edge[first_liberty_edge];
    mc->previous_liberty_edge[this_liberty_edge] = first_liberty_edge;
    mc->next_liberty_edge[this_liberty_edge] = second_liberty_edge;
    mc->next_liberty_edge[first_liberty_edge] = this_liberty_edge;
    mc->previous_liberty_edge[second_liberty_edge] = this_liberty_edge;
  }
  else {
    mc->first_liberty_edge[reference] = this_liberty_edge;
    mc->next_liberty_edge[this_liberty_edge] = this_liberty_edge;
    mc->previous_liberty_edge[this_liberty_edge] = this_liberty_edge;
  }
}


/* Remove a liberty edge for a string at pos with liberty at lib and
 * direction dir.
 */
static int
mc_remove_liberty_edge(struct mc_board *mc, int pos, int lib, int dir)
{
  int reference = mc->reference_stone[pos];
  int this_liberty_edge = (lib << 2) | dir;
  int next = mc->next_liberty_edge[this_liberty_edge];
  int previous = mc->previous_liberty_edge[this_liberty_edge];
  
  gg_assert(lib + delta[dir] == pos);
  
  if (next == this_liberty_edge) {
    mc->first_liberty_edge[reference] = 0;
    return 0;
  }

  mc->next_liberty_edge[previous] = next;
  mc->previous_liberty_edge[next] = previous;
  if (mc->first_liberty_edge[reference] == this_liberty_edge)
    mc->first_liberty_edge[reference] = next;

  return next;
}


/* Join the strings at str1 and str2. It is assumed that str1 is a
 * newly placed stone (possibly already joined with other strings) and
 * that the liberty edge corresponding to the liberty at the newly
 * placed stone has not yet been removed.
 */
static void
mc_join_strings(struct mc_board *mc, int str1, int str2)
{
  int reference = mc->reference_stone[str2];
  int liberty_edge2 = mc->first_liberty_edge[reference];
  int liberty_edge1 = mc->first_liberty_edge[mc->reference_stone[str1]];
  int next1;
  int next2;
  int pos = str1;

  /* Update the reference stone for str1. */
  do {
    mc->reference_stone[pos] = reference;
    pos = mc->next_stone[pos];
  } while (pos != str1);

  /* Switch next_stone pointers to join the strings. */
  next1 = mc->next_stone[str1];
  mc->next_stone[str1] = mc->next_stone[str2];
  mc->next_stone[str2] = next1;

  /* Join the circular liberty_edge structures. We know that str2
   * still has a liberty listed at the newly added stone so
   * liberty_edge2 is guaranteed to be non-zero.
   */
  if (liberty_edge1 != 0) {
    next1 = mc->next_liberty_edge[liberty_edge1];
    next2 = mc->next_liberty_edge[liberty_edge2];
    mc->next_liberty_edge[liberty_edge1] = next2;
    mc->next_liberty_edge[liberty_edge2] = next1;
    mc->previous_liberty_edge[next1] = liberty_edge2;
    mc->previous_liberty_edge[next2] = liberty_edge1;
  }
}


/* Remove the string at str from the board. */
static int
mc_remove_string(struct mc_board *mc, int str)
{
  int other = OTHER_COLOR(mc->board[str]);
  int pos = str;
  int num_removed_stones = 0;
  int k;
  
  do {
    for (k = 0; k < 4; k++)
      if (mc->board[pos + delta[k]] == other)
        mc_add_liberty_edge(mc, pos + delta[k], pos, k);
    mc->board[pos] = EMPTY;
    num_removed_stones++;
    pos = mc->next_stone[pos];
  } while (pos != str);

  return num_removed_stones;
}


/* Initialize a Monte Carlo board struct from the global board.
 */
static void
mc_init_board_from_global_board(struct mc_board *mc)
{
  int stones[BOARDMAX];
  int num_stones;
  int pos;
  int k;
  int r;
  
  memcpy(mc->board, board, sizeof(mc->board));
  mc->board_ko_pos = board_ko_pos;

  /* FIXME: next_stone[] can be copied directly from the global board
   * data structure.
   */
  memset(mc->next_stone, 0, sizeof(mc->next_stone));
  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
    if (IS_STONE(board[pos]) && mc->next_stone[pos] == 0) {
      num_stones = findstones(pos, BOARDMAX, stones);
      mc->first_liberty_edge[pos] = 0;
      for (r = 0; r < num_stones; r++) {
        mc->next_stone[stones[r]] = stones[(r + 1) % num_stones];
        mc->reference_stone[stones[r]] = pos;
        for (k = 0; k < 4; k++) {
          if (board[stones[r] + delta[k]] == EMPTY)
            mc_add_liberty_edge(mc, stones[r], stones[r] + delta[k],
                                (k + 2) % 4);
        }
      }
    }
  }
}


/* Count the number of stones in the string at str. Stop counting if
 * maxstones is reached.
 */
static int
mc_countstones(struct mc_board *mc, int str, int maxstones)
{
  int stone = str;
  int num_stones = 0;
  do {
    num_stones++;
    stone = mc->next_stone[stone];
  } while (stone != str && num_stones < maxstones);

  return num_stones;
}

/* Is a move at pos by color suicide? */
static int
mc_is_suicide(struct mc_board *mc, int pos, int color)
{
  int k;
  
  if (mc->board[SOUTH(pos)] == EMPTY
      || mc->board[WEST(pos)] == EMPTY
      || mc->board[NORTH(pos)] == EMPTY
      || mc->board[EAST(pos)] == EMPTY)
    return 0;

  for (k = 0; k < 4; k++) {
    int first_liberty_edge;
    int liberty_edge;
    int additional_liberty = 0;
    if (!ON_BOARD(pos + delta[k]))
      continue;

    first_liberty_edge = (pos << 2) | k;
    liberty_edge = mc->next_liberty_edge[first_liberty_edge];
    while (liberty_edge != first_liberty_edge) {
      if ((liberty_edge >> 2) != pos) {
        additional_liberty = 1;
        break;
      }
      liberty_edge = mc->next_liberty_edge[liberty_edge];
    }

    if ((mc->board[pos + delta[k]] != color) ^ additional_liberty)
      return 0;
  }

  return 1;
}


/* Is a move at pos by color legal? */
static int
mc_is_legal(struct mc_board *mc, int pos, int color)
{
  if (pos == PASS_MOVE)
    return 1;

  if (mc->board[pos] != EMPTY)
    return 0;

  if (pos == mc->board_ko_pos) {
    if (mc->board[WEST(pos)] == OTHER_COLOR(color)
        || mc->board[EAST(pos)] == OTHER_COLOR(color)) {
      return 0;
    }
  }

  return !mc_is_suicide(mc, pos, color);
}


/* Is the string at str in atari? Always place one liberty of the
 * string in lib, unless it's a null pointer.
 */
static int
mc_is_in_atari(struct mc_board *mc, int str, int *lib)
{
  int reference = mc->reference_stone[str];
  int first_liberty_edge = mc->first_liberty_edge[reference];
  int liberty = first_liberty_edge >> 2;
  int liberty_edge = mc->next_liberty_edge[first_liberty_edge];
  if (lib)
    *lib = liberty;
  while (liberty_edge != first_liberty_edge) {
    if ((liberty_edge >> 2) != liberty)
      return 0;
    liberty_edge = mc->next_liberty_edge[liberty_edge];
  }

  return 1;
}


/* Is a move at pos by color a self atari? */
static int
mc_is_self_atari(struct mc_board *mc, int pos, int color)
{
  int k;
  int captured = NO_MOVE;
  int liberty = NO_MOVE;
  int reference;
  int other;

  /* Quick test which is often effective. */
  if (((mc->board[SOUTH(pos)] == EMPTY)
       + (mc->board[WEST(pos)] == EMPTY)
       + (mc->board[NORTH(pos)] == EMPTY)
       + (mc->board[EAST(pos)] == EMPTY)) > 1)
    return 0;

  /* Otherwise look closer. */
  for (k = 0; k < 4; k++) {
    int first_liberty_edge;
    int liberty_edge;
    int additional_liberty = 0;
    int pos2 = pos + delta[k];
    if (mc->board[pos2] == EMPTY) {
      if (pos2 != liberty) {
        if (liberty != NO_MOVE)
          return 0;
        else
          liberty = pos2;
      }
    }
    else if (IS_STONE(mc->board[pos2])) {
      first_liberty_edge = (pos << 2) | k;
      liberty_edge = mc->next_liberty_edge[first_liberty_edge];
      while (liberty_edge != first_liberty_edge) {
        int lib = liberty_edge >> 2;
        if (lib != pos) {
          additional_liberty = 1;
          if (mc->board[pos2] == color) {
            if (lib != liberty) {
              if (liberty != NO_MOVE)
                return 0;
              else
                liberty = lib;
            }
          }
          else
            break;
        }
        liberty_edge = mc->next_liberty_edge[liberty_edge];
      }

      if (mc->board[pos2] != color && additional_liberty == 0) {
        captured = pos2;
        if (pos2 != liberty) {
          if (liberty != NO_MOVE)
            return 0;
          else
            liberty = pos2;
        }
      }
    }
  }

  if (liberty == NO_MOVE || captured == NO_MOVE)
    return 1;

  /* Now only the difficult case remains where there was no adjacent
   * empty stone, no adjacent friendly stone with an extra liberty,
   * and exactly one neighbor was captured. Then the question is
   * whether the capture produced a second liberty elsewhere.
   */
  reference = mc->reference_stone[captured];
  other = OTHER_COLOR(color);
  for (k = 0; k < 4; k++) {
    if (board[pos + delta[k]] == color) {
      int stone = pos + delta[k];
      do {
        int m;
        for (m = 0; m < 4; m++) {
          int pos2 = stone + delta[m];
          if (board[pos2] == other
              && pos2 != captured
              && mc->reference_stone[pos2] == reference)
            return 0;
        }
        stone = mc->next_stone[stone];
      } while (stone != pos + delta[k]);
    }
  }

  return 1;
}


/* Play the move at pos by color. */
static int
mc_play_move(struct mc_board *mc, int pos, int color)
{
  int k;
  int captured_stones = 0;
  int num_direct_liberties = 0;
  
  if (pos == PASS_MOVE) {
    mc->board_ko_pos = NO_MOVE;
    return 1;
  }
  
  /* The move must not be the ko point. */
  if (pos == mc->board_ko_pos) {
    if (mc->board[WEST(pos)] == OTHER_COLOR(color)
        || mc->board[EAST(pos)] == OTHER_COLOR(color)) {
      return 0;
    }
  }
  
  /* Test for suicide. */
  if (mc_is_suicide(mc, pos, color))
    return 0;

  mc->board_ko_pos = NO_MOVE;
  
  mc->board[pos] = color;
  mc->next_stone[pos] = pos;
  mc->reference_stone[pos] = pos;
  mc->first_liberty_edge[pos] = 0;

  for (k = 0; k < 4; k++) {
    int pos2 = pos + delta[k];
    if (mc->board[pos2] == EMPTY) {
      mc_add_liberty_edge(mc, pos, pos2, (k + 2) % 4);
      num_direct_liberties++;
    }
  }
  
  for (k = 0; k < 4; k++) {
    int pos2 = pos + delta[k];
    if (mc->board[pos2] == OTHER_COLOR(color)) {
      if (mc_remove_liberty_edge(mc, pos2, pos, k) == 0)
        captured_stones += mc_remove_string(mc, pos2);
    }
    else if (mc->board[pos2] == color) {
      if (mc->reference_stone[pos] != mc->reference_stone[pos2])
        mc_join_strings(mc, pos, pos2);
      mc_remove_liberty_edge(mc, pos2, pos, k);
    }
  }

  if (captured_stones == 1
      && mc->next_stone[pos] == pos
      && num_direct_liberties == 0)
    mc->board_ko_pos = mc->first_liberty_edge[pos] >> 2;
  
  return 1;
}