// longminigo.c version 1.06; by Mathijs Romans
// shorter version on http://www.romansland.nl/minigo
//
// Comments and documentation by Mark Hampton

// This program plays the game of go

// Note that the first move is made by the computer and this is the most CPU expensive move
// because the number of possible moves is largest at the beginning
// So it can take a while (30 sec in 2009) for the board to be drawn

// Issues for future improvement
//   When the program starts draw an empty board and indicate the computer is "thinking"
//   The test in findeyes for eyes is not perfect
//   Below is an example of one of the rare baord positions where the eyes are not detected
//OOOO
//OXXOOOOOOO
//OX XXXXXXO
//OXXOOOOOXO
//OOXO O OXOO
//OXOOOOOXXO
//OXXXXXX XO
//OOOOOOOXXO
//      OOOO

// The basic sequence of operation is :
// main function  
//   gets user's move or the computer trys every available move on the board and chooses the best move
//   to decide on the best move the computer runs a monte-carlo simulation by calling the game function LEVEL times
//   and chooses the move which results in the highest cumulative score from the simulated games
//   draw the board on the terminal using  the draw function
//   exit if the game has finished (both players pass) 
// game function
//   simulate a game by playing our random valid moves until the board is filled up
//   the move function will return true if the move is valid
//   score the game using chinese rules
//   return the score of the game (if there are no moves to make this will give the final score)

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#define LEVEL 1000 // number of games simulated
#define FALSE 0
#define TRUE 1
#define SIZE 9 // size of the board i.e. 9x9
#define VOID 0 // not used
#define BEYE 2 // a single empty position surrounded by black stones
#define WEYE 3 // a single empty position surrounded by white stones
#define ILLEGAL 8 // can't play here because of ko
#define BEYEILLEGAL 10 // a single point eye for black that is an illegal move for white
#define WEYEILLEGAL 11 // a single point eye for white that is an illegal move for black
#define BLACK 4 // black stone on the board
#define WHITE 5 // white stone on the board
#define FIELD for(x=0;x<SIZE;x++) for(y=0;y<SIZE;y++)
#define IFOR4 for (i=0;i<4;i++)
#define infield(x,y) (x>=0 && x<SIZE && y>=0 && y<SIZE)

// the board position (variables b,p) can never be 1
		
int xq,yq,x,y,lib[SIZE][SIZE],b[SIZE][SIZE],turn,pturn,p[SIZE][SIZE],ko,kox,koy,pas,tpas;
int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,1,0,-1,1,-1,1,-1};

// Return true if a group has liberties
// also builds lib[x][y] which indicates the position of the liberties  
int liberties(int x, int y, int color)
{
	int i;
	if (!infield(x,y)) // not on the board
		return FALSE;
	if (b[x][y] != BLACK && b[x][y] != WHITE) // no white or black stone
		return TRUE;
 	if (b[x][y] != color || lib[x][y]) // an opponent's stone or already checked this position
		return FALSE;
	lib[x][y] = TRUE; // indicates this position has been checked (stops recursion)
	IFOR4 // check surrounding positions for liberties
		if (liberties(x+dx[i],y+dy[i],color)) 
			return TRUE;
	return FALSE;
}

// Capture a group of stones
void take(int x, int y)
{
	int i;
	if (!infield(x,y) // not on the board 
	    || b[x][y]!=(turn+1)%2+4) // oponnent's stone
		return;
	b[x][y] = 0; // empty the board position
	kox = x;
	koy = y;
	ko++; // if > 1 then not a ko if 1 then might be a ko
	IFOR4
	  take(x+dx[i],y+dy[i]); // capture other stones in the group
}

// This program was made for an old-fashioned terminal window with a black 
// background and a white foreground. This is why the "XXX" stones are the white 
// stones.
void draw()
{
	for (x=0;x<SIZE;x++)
	  printf("  %c   ",'a'+x);
	printf("\n");
	for(y=0;y<SIZE;y++) {
	  for(x=0;x<SIZE;x++) {
	    switch (b[x][y])
	      {
	      case BLACK:
		printf(" _|_  ");
		break;
	      default:
		printf("  |   ");
	      }
	  }
	  printf("\n");
	  for(x=0;x<SIZE;x++) {
	    switch (b[x][y])
	      {
	      case BLACK:
		printf("/   \\_");
		break;
	      case WHITE:
		printf("_XXX__");
		break;
	      case BEYE:
		printf("__B___");
		break;
	      case WEYE:
		printf("__W___");
		break;
	      case BEYEILLEGAL:
		printf("__Bx__");
		break;
	      case WEYEILLEGAL:
		printf("__Wx__");
		break;
	      case ILLEGAL:
		printf("__x___");
		break;
	      case 0: //EMPTY 
		printf("__|___");
		break;
	      default:
		printf("__%i___",b[x][y]);
		
	      }
	  }
	  printf(" %i\n",y+1);
	  for(x=0;x<SIZE;x++) {
	    switch (b[x][y])
	      {
	      case BLACK:
		printf("\\___/ ");
		break;
	      case WHITE:
		printf(" XXX  ");
		break;
		
	      default:
		printf("  |   ");
	      }
	  }
	  printf("\n");
	}
	printf("\n");
}

// note where eyes are (a single empty position surrounded by one color)
// color is 1 or 0
// I used the following test for eyes: an empty position is an eye if at
// least 3 out of 4 positions diagonally bordering it are either stones of your 
// color or also an eye. For a position on the edge it is 2 out of 2 positions, 
// for a position on the corner it is 1 out of 1 position. Since this means that 
// one eye can depend on another, I first assume all empty positions are eyes, 
// then keep removing invalid eyes until there is no change any more. This is the 
// meaning of the do ... while (changed) loop.

// Note that this test is not perfect: one can imagine an extremely peculair 
// board position where eyes are not marked by this test !!
void findeyes(int color)
{
	int changed,eyeness,i;
	FIELD // 2D loop through board dimensions
	{
	  if (b[x][y] > 7) // remove old illegal moves
	    b[x][y] -= 8; // BEYEILLEGAL becomes BEYE, WEYEILLEGAL becomes WEYE
	  if (b[x][y] == 0) // Empty
	    b[x][y] = 2+color; // Set board position to BEYE or WEYE
	}
	do 
	{
	  changed=FALSE;
	  FIELD // 2D loop through board dimensions
	    if (b[x][y] == 2+color) // if board position is BEYE or WEYE
	      {
		IFOR4 // looping around 4 neighboring positions
		  if (infield(x+dx[i],y+dy[i]) // on the board 
		      && b[x+dx[i]][y+dy[i]] != 4+color) // not the same color as the EYE
		    goto notaneye; // not an eye
		eyeness = 0;
		IFOR4 // looping around 4 neighboring positions		
		  if (infield(x+dx[i+4],y+dy[i+4]) // is the diagonal neighbor
		      && (b[x+dx[i+4]][y+dy[i+4]] == 4+color // is a stone of the same color
			  || b[x+dx[i+4]][y+dy[i+4]] == 2+color)) // is marked as part of an EYE of this color
		    eyeness++;
		if (x == 0 || x == SIZE-1) // edge of the board
		  eyeness++;
		if (y == 0 || y == SIZE-1) // edge of the board
		  eyeness++;			
		if (eyeness < 3) // at least 3 of the 4 positions diagonally bordering it are either 
                                 // stones of the same color, outside the board, or also an eye
		  {
		  notaneye:
		    changed = TRUE;
		    b[x][y] = 0; // clear the board position from B/WEYE to empty
		  }
	      }
	}
	while (changed); // keep removing invalid eyes until there is no change any more
}

int move(int xloc, int yloc)
{
	int i,prev;
	prev = b[xloc][yloc];
	b[xloc][yloc] = turn%2+4; //try move, set the board position to BLACK or WHITE
	ko = 0;
	IFOR4 // loop from 0 to 3, to check the 4 positions around the move
	{
	  if (infield(xloc+dx[i],yloc+dy[i]) // is move on the board 
	      //&& !lib[xloc+dx[i]][yloc+dy[i]] // lib will always be false here
	      && b[xloc+dx[i]][yloc+dy[i]] == (turn+1)%2+4 // is an opponent's stone  
	      && !liberties(xloc+dx[i],yloc+dy[i],(turn+1)%2+4)) // the opponent's group has no liberties 
	    take(xloc+dx[i],yloc+dy[i]); // capture that group
	  FIELD lib[x][y]=0; // reset all the liberty counts
	}
	i=liberties(xloc,yloc,b[xloc][yloc]); // true if the group created with move has at least on liberty 
	FIELD lib[x][y]=0; // reset all the liberty counts
	if (i)	// proper move
	{
	  pas = FALSE; // cancel passing
	  findeyes(turn%2); // Mark eyes on the board	
	  if (ko==1) // might be a ko so we need to check
	    {
	      b[kox][koy] += 8;	// new ko, mark board position as B/WEYEILLEGAL
	      IFOR4 // to check the 4 positions around the move
		if (infield(xloc+dx[i],yloc+dy[i]) // on the board
		    && b[xloc+dx[i]][yloc+dy[i]] == 4+turn%2) // same color of stone (connected to a group)
		  {
		    b[kox][koy] -= 8; // not a ko
		    break;
		  }
	    }
	  return TRUE; // move is OK
	}
	b[xloc][yloc] = prev+8; // illegal move, do not play here
	return FALSE;
}

int game()
{
	int count;
	for(;turn<10*SIZE*SIZE;turn++) // limit the simulation to this number in the case of a triple ko
	  {
	    count=0;
	    // count available moves
	    FIELD if (!b[x][y] || b[x][y] == 2+(turn+1)%2) // board is empty or an opponent's eye
	      count++; 
	    do
	      {
		if (!count) // filled all possible plays
		  {
		    findeyes(turn%2); // mark the eyes
		    if (pas) // if previous player passed
		      {
			// counting with chinese rules
			xq=0;
			FIELD
			  if (b[x][y] == BLACK || b[x][y]== BEYE)
			    xq++;
			return 2*xq-81;	//end of game
		      }
		    pas = TRUE;
		    break;
		  }
		// Choose a random move
		do
		  {
		    xq=rand()%SIZE;
		    yq=rand()%SIZE;
		  }
		while (!(!b[xq][yq] // empty position
			 || b[xq][yq] == 2+(turn+1)%2)); // opponent's territory
		if (move(xq,yq)) // legal move
		  break;
		count--;
	      }
	    while (1);
	  }
	return 0; //triple ko
}

int main()
{
        int tx,ty,tot,i,hx,hy,h;
	char input[20];
	srand(time(0));
	ko = 0;
	FIELD // Initialize 2D arrays
	{
		p[x][y] = 0;
		lib[x][y] = 0;
	}
	for (pturn=0;TRUE;pturn++)
	{
	  if (pturn%2) // computer always starts the game
		do //human move
			{
				turn = pturn;
				hx = -1;
				printf("YOUR MOVE!\n");
				scanf ("%s",input);
				if(input[0] == 'p')
					break;
				if(input[0] == 'q') // added by MH to allow quiting the game
				  return 0; // exit program
				hx = input[0] - 'a'; // reduce to a co-ordinate from 0 to 9
				hy = input[1] - '1'; // reduce to a co-ordinate from 0 to 9
				if (hx >= 0 && hx < SIZE && hy >= 0 && hy < SIZE // within the bounds of the board
				    && b[hx][hy] < 4 // board position is empty, BEYE or WEYE
				    && move(hx,hy)) // make the move if it is legal
					break;
			}
		while(1); // keep requesting a valid move
		else
		  { // computer move
		    hx = -1; // best move will be the next move found
                    // Try every move available
		    for (tx=0;tx<SIZE;tx++)
		      for (ty=0;ty<SIZE;ty++)
			if ((!p[tx][ty] // empty
			     || p[tx][ty] == 3)) // or opponents eye
			  {
			    turn = pturn;
			    // copy p into b
			    FIELD b[x][y] = p[x][y];
			    if (move(tx,ty)) // if move is possible
			      {
				tot = 0;
				for (i=0;i<LEVEL;i++) // simulate LEVEL games
				  {
				    FIELD b[x][y] = p[x][y]; // restore original board
				    move(tx,ty); // play the move we are investigating
				    turn++; 
				    tot += game(); // play out the game (avoiding triple ko)
				    turn = pturn;  // reset for next simualted game
				  }
				if (hx == -1 || tot > h)
				  {
				    hx = tx;	//
				    hy = ty;	// remember best move
				    h = tot;	//
				  }
			      }
			  }
		  }
	  // copy p into b
	  FIELD b[x][y] = p[x][y];
	  if (hx != -1) // a move was found
	    {
	      tpas=FALSE; // don't pass
	      move(hx,hy); // make the move
	    }
	  else // no move was found
	    {
	      //findeyes(turn%2); // should be no need to call this
	      printf("PASS!\n");
	      if (tpas)  // end of game (have already passed)
		{
		  turn++;
		  xq=game();
		  if (xq>0)
		    printf("BLACK");
		  else
		    printf("WHITE");
		  printf(" WINS WITH %i POINTS!\n",xq>0?xq:-xq);
		  return 0;
		}
	      tpas = TRUE;
	    }	
	  // copy b into p
	  FIELD p[x][y] = b[x][y];
	  draw(); // update the board in the terminal
	}
	return 0; // exit program
}