/* simple-go.c v0.2 */

/* A simple implementation of the Goban used in the game of
   Wei'qi/Baduk/Igo/Go.  Features included: undo, notion of Ko and
   komi, and semi-automatic scoring after both Japanese and Chinese
   rules.  Notice, the notion of Ko is only approximative, but handles
   %99 of real-world ko situation.

   This implemented is only intented as a "proof of concept" and does
   not represent production code quality.  Indeed, some details in the
   chinese scoring needs further examination.  The data structures and
   algorithms used are intentionally not optimized at all, and may
   easily prove unrealistic for a memory tight implementation, like
   the Sony MagicLink.  The purpose of this program is to show *what*
   to compute, not *how*.

   Written for Sony New Technology November 1996 by Tommy Thorn */

/* Comments: This was written in a few hours, with half of the time
   spend commenting the code.  There are no known bugs, but a few
   misfeatures or missing functionallity:

     - Removing groups in the counting phase should toggle the
       liveness of the group.  As it is, undo provides the same
       functionallity, but less flexible.

     - It would be easy to add the construction of game trees with
       variations.

     - Chinese counting is not fully completed.

     - Heap allocated memory is not free'd.  The implementation of
       undo uses way too much memory (e.g.  200 moves * ~ 400 bytes pr
       board ~= 80k) */

/* The major game configuration is controlled by three global
   variables: dim, china_rules, and komi.

   `dim' gives the size of the square board.

   `china_rules' switches between chinese and japanese counting.  In
   the former, stones left on the board are included in the score.  (I
   believe the passes also affect scoring, but I have not yet examined
   the details.)

   `komi' is a score adjustment, used to balance the advantage of
   black starting with the initiative.  Typical value is 5.5 for an
   even game, and 0.5 for handicap games. */

int dim = 5;                  /* 19 for a 19 x 19 game */
int china_rules = 0;          /* 1 for chinese counting */
double komi = 0;              /* 5.5 */

/* To maximize the readability of this program, the data structures
   and algorightms are explicitly very simple.  The board of Goban is
   represented as a two-dimentional array of colors.  The "color" seen
   is used to mark already visited places in the transtive closure
   algorithms */

typedef enum color {
  empty, black, white, seen
} color, **goban;

#define togglecolor(c) (3-(c))	/* black -> white, white -> black */

char *color_name [] = {"empty", "black(#)", "white(O)"};

/* The approach to support "undo" is extremely simple: just save all
   the state.  Only the board itself needs more support than is
   provided by C.

   `new_goban' allocates an empty board.
   `copy_goban' creates a distinct copy of an existing board.

   NOTICE: Freeing of memory is irrelevant to my point and is
   subsequently omitted.  */

extern void *malloc(int);	/* Don't need no stinkin' header files */

goban new_goban()
{
  goban copy = malloc(sizeof(color *) * dim);
  int i;
  for (i = 0; i < dim; i++) {
    copy[i] = malloc(sizeof(color) * dim);
    memset(copy[i], empty, dim*sizeof(color));
  }
  return copy;
}

goban copy_goban(goban orig)
{
  goban copy = malloc(sizeof(color *) * dim);
  int i;
  for (i = 0; i < dim; i++) {
    copy[i] = malloc(sizeof(color) * dim);
    memcpy(copy[i], orig[i], dim*sizeof(color));
  }
  return copy;
}

/* This implementation has a very crude user interface.  Still, the
   printing of the board follows established standards on the Internet
   Go servers and the newsgroup rec.games.go closely.  (except the '_'
   for the Ko).  Actually, the handicap marks are wrongly placed for
   board sizes other than 19x19 and 13x13 */

void print_board(goban board, int ko_x, int ko_y)
{
  int x,y;

  for (y = dim-1; y >= 0; --y) {
    printf("%2d", y+1);
    for (x = 0; x < dim; ++x) {
      char c;
      if (x == ko_x && y == ko_y)
	c = '_';
      else if ((x - 3) % 6 == 0 && (y - 3) % 6 == 0)
	c = "+#O"[board[x][y]];
      else
	c = ".#O"[board[x][y]];
      printf("%2c",c);
    }
    printf("\n");
  }
  printf("  ");
  for (x = 0; x < dim; ++x)
    printf("%2c","abcdefghjklmnopqrst"[x]);
  printf("\n");
}

/* The `get_move' function is responsible for the lower part of the
   user interface.  Current status is display and the user is queried
   for a next move, or, after having entered the counting phase,
   groups to remove (as they are dead).

   The game is considered to have entered counting after two
   consecutive passes (without a Ko) */

typedef enum move_kind {
  play, pass, remove, end, undo, quit
} move_kind;

move_kind get_move(goban board, int moveno, color toplay,
		   int ko_x, int ko_y,
		   int bp, int wp,
		   int *x, int *y,
		   int passes)
{
  print_board(board, ko_x, ko_y);
  printf("black(#)'s prisoners: %d white(O)'s prisoners: %d\n", bp, wp);
  do {
    char buf[80], c;
    int i;

    if (passes != 2)
      printf("move %d, %s to play: ",
	     moveno, color_name[toplay], " #O"[toplay]);
    else
      printf("Game over.  Select dead stones and count with 'C':");
    gets(buf);
    i = 0;
    while (buf[i] && buf[i] == ' ') i++;
    switch (buf[i]) {
    case 'Q': return quit;
    case 'U': return undo;
    case 'P': return pass;
    case 'C': return end;
    default:
      c = buf[0];
      sscanf(buf+1, "%d", y);
      if (*y > dim+1 || *y < 1 || c > 't' || c < 'a' || c == 'i')
	continue;
      if (c > 'i') --c;
      *x = c - 'a';
      --*y;
      if (*y > dim)
	continue;
      if (passes != 2)
	return play;
      else
	return remove;
    }
  } while (1);
}

/* Strongly connected groups of stones are captures when they have no
   more liberities.  A liberty is a vacant intersection adjacent to
   the stones.  The `haslibs' function recursively searches for such a
   liberty.  (A standard graph transitivity closure.)

   Notice: haslibs uses board destructively, and thus needs a fresh
   copy. */

int haslibs(goban board, int x, int y, color our)
{
  if (board[x][y] == empty)
    return 1;
  else if (board[x][y] != our)
    return 0;
  else {
    board[x][y] = seen; /* avoid looping */
    if (x > 0     && haslibs(board,x-1,y,our)) return 1;
    if (y > 0     && haslibs(board,x,y-1,our)) return 1;
    if (x < dim-1 && haslibs(board,x+1,y,our)) return 1;
    if (y < dim-1 && haslibs(board,x,y+1,our)) return 1;
    return 0;
  }
}

/* The `remove_group' function removes the strongly connected group of
   stones of color `our', situated at `(x,y)'.  (Yet another
   transitive closure.) */

int remove_group(goban board, int x, int y, color our)
{
  if (board[x][y] != our)
    return 0;
  else {
    int count = 1;
    board[x][y] = empty;
    if (x > 0)     count += remove_group(board,x-1,y,our);
    if (y > 0)     count += remove_group(board,x,y-1,our);
    if (x < dim-1) count += remove_group(board,x+1,y,our);
    if (y < dim-1) count += remove_group(board,x,y+1,our);
    return count;
  }
}  

/* Finally, the third closure function, `close_ter', is used to
   calculate the size of the (potential) territory at `(x,y)'.
   Territory is defined as the maximally connected set of vacant
   intersections, with the constraint that all stone adjacent to this
   set are of the same color (the owner).

   I admit to some slightly unclean bit hackery to simplify finding
   the owner of the territory */

int close_ter(goban board, int x, int y, int *owner)
{
  if (board[x][y] != empty) {
    if (board[x][y] != seen)
      *owner |= board[x][y];	/* This uses that black == 1 and white == 2 */
    return 0;
  } else {
    int count = 1;
    board[x][y] = seen;
    if (x > 0)     count += close_ter(board,x-1,y,owner);
    if (y > 0)     count += close_ter(board,x,y-1,owner);
    if (x < dim-1) count += close_ter(board,x+1,y,owner);
    if (y < dim-1) count += close_ter(board,x,y+1,owner);
    return count;
  }
}

/* With the above territory closure in hand, counting the final game
   is trivial, and amounts to applying it to all empty intersections.
   The difference in the chinese and japanese counting is apparent
   here. */

void count_game(goban board, int *b_terr, int *w_terr)
{
  int x, y, terr, owner;
  
  for (y = 0; y < dim; y++)
    for (x = 0; x < dim; x++)
      switch(board[x][y]) {
      case black:
	if (china_rules) ++*b_terr;
	break;
      case white:
	if (china_rules) ++*w_terr;
	break;
      case empty:
	owner = 0;
	terr = close_ter(board, x, y, &owner);
	if (owner == black) *b_terr += terr;
	if (owner == white) *w_terr += terr;
      }
}

/* Check to see the the group at `(x,y)' is captured.  If it is,
   capture it and return the number of stones taken off the board. */

int maybe_capture(goban board, int x, int y)
{
  if (board[x][y] != empty) {
    goban countboard = copy_goban(board);
    int alive = haslibs(countboard,x,y,board[x][y]);
    if (!alive)
      return remove_group(board,x,y,board[x][y]);
  }
  return 0;
}

/* The main game function `doplay' is a (admitted too big) recursive
   function that is called with the game state:
     - a representation of the stones on the `board'
     - the (purely informative) sequential move number `moveno'
     - the `(ko_x,ko_y)' Ko position if any and (-1,-1) if not
     - the current count of black and white prisoners `bp' and `wp'
     - the number of consecutive passes

   Undo is signalized by returning 1, thus letting `doplay' restart
   the loop. */

int doplay(goban board,
	   color toplay,
	   int moveno,
	   int ko_x, int ko_y,
	   int bp, int wp,
	   int passes)
{
  int cont;
  
  do {
    int x, y;
    move_kind mk = get_move(board, moveno, toplay,
			    ko_x, ko_y,
			    bp, wp, &x, &y, passes);
    goban new_board = copy_goban(board);
    int new_ko_x = -1, new_ko_y = -1; /* No Ko until proved otherwise */
    int new_bp = bp, new_wp = wp;
    cont = 0;
    switch (mk) {
    case remove:
      /* We are in the counting phases */
      if (board[x][y] != empty) {
	if (new_board[x][y] == black)
	  new_wp += remove_group(new_board,x,y,board[x][y]);
	else
	  new_bp += remove_group(new_board,x,y,board[x][y]);
	cont = doplay(new_board, toplay, moveno, -1, -1, new_bp, new_wp, 2);
      }
      break;

    case play:
      /* Regular play, first check the trivias */

      if (board[x][y] != empty) {
	printf("*** spot(%d,%d) taken by a %s stone\n",
	       x, y, color_name[board[x][y]]);
	continue;
      } else if (x == ko_x && y == ko_y) {
	printf("*** spot(%d,%d) is in KO\n", x, y, color_name[board[x][y]]);
	continue;
      } else {

	/* We assume the move is legal for now, and try to observe the
           effects.  In the case of a Ko the `a..d' variables 
           identifies where the Ko point is */

	int a = 0, b = 0, c = 0, d = 0;
	int captured = 0;
	new_board[x][y] = toplay;
	  
	if (x > 0)     captured += a = maybe_capture(new_board,x-1,y);
	if (y > 0)     captured += b = maybe_capture(new_board,x,y-1);
	if (x < dim-1) captured += c = maybe_capture(new_board,x+1,y);
	if (y < dim-1) captured += d = maybe_capture(new_board,x,y+1);
	  
	/* Suicide is when the group, at which the move was played,
           have no liberties (after having tried to capture the
           neighbords).  Suicide is not allowed. */
	if (!haslibs(new_board,x,y,toplay))
	  {
	    printf("*** Suicide is not allowed.\n");
	    continue;
	  }

	/* This implementation uses a simple approximation to Ko
	   (eternal repetition): Ko is when one stone is captured by an
	   unconnected stone, which is in atari after the move.
	   (Atari = has one liberty.) */

	if (captured == 1) {
	  /* Observation: has at least one liberty (captured == 1),
	   * thus this condition equals "Ko iff sum of non-enemy
	   * neighbors is 1" XXX: Prove this */
	  int k = 0;
	  color opponent = togglecolor(toplay);
	    
	  if (x > 0     && new_board[x-1][y] != opponent) ++k;
	  if (y > 0     && new_board[x][y-1] != opponent) ++k;
	  if (x < dim-1 && new_board[x+1][y] != opponent) ++k;
	  if (y < dim-1 && new_board[x][y+1] != opponent) ++k;
	  if (k == 1) {
	    /* Locate the ko using the saved captured counts */
	    new_ko_x = x; new_ko_y = y;
	    if (a) new_ko_x--;
	    if (b) new_ko_y--;
	    if (c) new_ko_x++;
	    if (d) new_ko_y++;
	  }
	}
	if (toplay == black)
	  new_bp += captured;
	else
	  new_wp += captured;
	cont = doplay(new_board,
		      togglecolor(toplay),
		      moveno+1,
		      new_ko_x,new_ko_y,
		      new_bp, new_wp, 0);
	break;
      }
    case pass:
      /* A double pass must not end the game if there were a Ko, so we
         don't count passes in suchs a case */
      cont = doplay(board, togglecolor(toplay),
		    moveno+1, -1,-1, bp, wp,
		    (ko_x == -1)?(passes+1):passes);
      break;
    case undo:
      return 1;
    case end: {
      int b_terr = 0, w_terr = 0;
      double b_score, w_score;

      count_game(board, &b_terr, &w_terr);
      printf("Game score\n");
      printf("Black(#): %d prisoners + %d territory = %g\n",
	     bp, b_terr, b_score = bp + b_terr);
      printf("White(O): %d prisoners + %d territory + %g komi = %g\n",
	     wp, w_terr, komi, w_score = wp + w_terr + komi);
      if (b_score > w_score)
	printf("Black(#) won with %g points\n", b_score - w_score);
      else
	printf("White(O) won with %g points\n", w_score - b_score);
      return 0;
    }
    case quit:
      return 0;
    }
  } while (cont);
}
  
main()
{
  goban board = new_goban();

  doplay(board,black,1,-1,-1,0,0,0);
}