/* This may look like c to you, but it's really -*-c++-*- */

/*   GMA or "The Go-moku Apprentice" is a go-moku implementation that
 *   learns the game from its own (and its opponents') mistakes.
 *   Copyright (C) 1998 Johan Walles (d92-jwa@nada.kth.se)
 *
 *   This program is free software; you can redistribute it and/or modify 
 *   it under the terms of the GNU General Public License as published by 
 *   the Free Software Foundation; either version 2 of the License, or 
 *   (at your option) any later version. 
 *
 *   This program is distributed in the hope that it will be useful, 
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of 
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
 */

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string>
#include <string.h>
#include <time.h>

#include "scores.h"
#include "pattern.h"
#include "moves.h"
#include "gma.h"

#define BOARD_SIZE 50
#define MAX_DEPTH 2

#define PLAYER_ME 0
#define PLAYER_OPPONENT 1

#define SQUARE_O          0
#define SQUARE_X          1
// Empty squares are generally empty_far...
#define SQUARE_EMPTY_FAR  2
// ... but squares near the action are empty_near.
// The computer considers only empty_near squares when
// thinking of moves to make.
#define SQUARE_EMPTY_NEAR 3
#define SQUARE_EMPTY SQUARE_EMPTY_NEAR
#define SQUARE_UNKNOWN    4

char board[BOARD_SIZE][BOARD_SIZE][MAX_DEPTH];
int dx[4], dy[4];
int winner = -1;
int beginner = -1;
Scores scores;
Moves patterns[2];
string data_file_name;
int last_x, last_y;
int n_moves[2]; // How many moves have each player made?
bool winning_move_detected = false;

void terminate_function(char *source_filename,
			int source_line,
			char *errstr)
{
  if (errstr == NULL)
    errstr = strerror(errno);
  fprintf(stderr,
	  "\n*** GMA Terminated at line %d of %s:\n*** %s\n",
	  source_line,
	  source_filename,
	  errstr);
  exit(EXIT_FAILURE);
}

void init_board()
{
  int x, y, b;

  // Clear the board
  for (x = 0; x < BOARD_SIZE; x++)
    for (y = 0; y < BOARD_SIZE; y++)
      for (b = 0; b < MAX_DEPTH; b++)
	board[x][y][b] = SQUARE_EMPTY_FAR;

  // Mark the middle square as suitable for setting a marker
  board[BOARD_SIZE/2][BOARD_SIZE/2][0] = SQUARE_EMPTY_NEAR;

  dx[0] = 0;  dy[0] =  1;  // Down
  dx[1] = 1;  dy[1] =  0;  // Right
  dx[2] = 1;  dy[2] =  1;  // Down-right
  dx[3] = 1;  dy[3] = -1;  // Up-right

  last_x = -1;
  last_y = -1;

  // No player has made any move
  n_moves[0] = 0;
  n_moves[1] = 0;
}

void init_players()
{
  patterns[0].clear();
  patterns[1].clear();
  
  winner = -1;
}

Pattern pattern_from_board(int player, int x0, int y0, int board_no = 0)
{
  Pattern pattern;

  int plusminus;
  int lastsign;
  int repetition;
  int x, y;
  int direction, t;
  int p_index = 0;
  int dont_care_state;
  int sign;
  unsigned char oldchar;
  int i1, i2;
  int n_nonempty;
  int local_winner;
  
  if ((x0 < 4) || (x0 > (BOARD_SIZE - 5)) ||
      (y0 < 4) || (y0 > (BOARD_SIZE - 5)))
    terminate("pattern_from_board(): Scanning outside board unhandled");

  for (direction = 0; direction <= 3; direction++)
    {
      for (plusminus = -1; plusminus <= 1; plusminus += 2)
	{
	  n_nonempty = 0;
	  dont_care_state = 0;
	  pattern[p_index] = '\0';
	  lastsign = -42;
	  repetition = 0;
	  
	  for (t = 1; t <= 4; t++)
	    {
	      if (dont_care_state == 3)
		{
		  // We've seen O followed by X or vice versa
		  pattern[p_index] =
		    (pattern[p_index] << 2) + PATTERN_DONTCARE;

		  continue;
		}
	      
	      x = x0 + t * plusminus * dx[direction];
	      y = y0 + t * plusminus * dy[direction];
	  
	      sign = board[x][y][board_no];

	      // Treat all empty squares the same
	      if (sign == SQUARE_EMPTY_FAR)
		sign = SQUARE_EMPTY;
	      
	      // Update the repetition counter
	      if (sign == lastsign)
		repetition++;
	      else
		{
		  repetition = 1;
		  lastsign = sign;
		}

	      if (sign == SQUARE_EMPTY)
		{
		  // Empty square
		  pattern[p_index] =
		    (pattern[p_index] << 2) + PATTERN_EMPTY;
		  
		  // Two empties in a row should make the following
		  // signs irrelevant
		  if (repetition == 2)
		    dont_care_state = 3;
		}
	      else if (sign == player)
		{
		  // My sign
		  pattern[p_index] =
		    (pattern[p_index] << 2) + PATTERN_MINE;
		  dont_care_state |= 1;
		  n_nonempty++;
		}
	      else // if (sign == (1 - player))
		{
		  // Opponent's sign
		  pattern[p_index] =
		    (pattern[p_index] << 2) + PATTERN_YOURS;
		  dont_care_state |= 2;
		  n_nonempty++;
		}
	    }

	  if (n_nonempty == 0)
	    pattern[p_index] = 0;

	  p_index++;
	}
    }

  if ((local_winner = pattern.winner()) != -1)
    {
      // This move makes one player a winner!

      winning_move_detected = true;

      unsigned char complete_pattern;

      if (local_winner == PLAYER_ME)
	complete_pattern =
	  PATTERN_MINE +
	  (PATTERN_MINE << 2) +
	  (PATTERN_MINE << 4) +
	  (PATTERN_MINE << 6);
      else
	complete_pattern =
	  PATTERN_YOURS +
	  (PATTERN_YOURS << 2) +
	  (PATTERN_YOURS << 4) +
	  (PATTERN_YOURS << 6);
      
      for (direction = 0; direction < 8; direction++)
	pattern[direction] = complete_pattern;
    }
  
  for (direction = 1; direction <= 8; direction += 2)
    {
      // Sort for in-line symmetry (xxo ooo == ooo oxx)
      if (pattern[direction] > pattern[direction - 1])
	{
	  oldchar = pattern[direction];
	  pattern[direction] = pattern[direction - 1];
	  pattern[direction - 1] = oldchar;
	}
    }

  for (p_index = 4; p_index <= 8; p_index += 4)
    {
      // Sort for axial symmetry (which one is vertical/horizontal
      // doesn't matter)
      i1 = pattern.nth_axis((p_index / 2) - 2);
      i2 = pattern.nth_axis((p_index / 2) - 1);

      if (i1 < i2)
	{
	  oldchar = pattern[p_index - 1];
	  pattern[p_index - 1] = pattern[p_index - 3];
	  pattern[p_index - 3] = oldchar;
	      
	  oldchar = pattern[p_index - 2];
	  pattern[p_index - 2] = pattern[p_index - 4];
	  pattern[p_index - 4] = oldchar;
	}
    }

  return pattern;
}

void set_mark(int x, int y, int mark_to_set)
{
  int dx, dy, b;

  int old_mark;

  Pattern pattern;

  // Check that the coordinates are on-board
  if ((x < 0) || (x > BOARD_SIZE) ||
      (y < 0) || (y > BOARD_SIZE))
    terminate("Mark set outside board!");
  
  // Sanity check
  old_mark = board[x][y][0];

  if (((mark_to_set == SQUARE_X) || (mark_to_set == SQUARE_O)) &&
      ((old_mark == SQUARE_X) || (old_mark == SQUARE_O)))
    terminate("Mark set in occupied square!");

  // Remember this move so that we can use it for scoring later
  pattern = pattern_from_board(mark_to_set, x, y);
  patterns[mark_to_set][pattern]++;

  for (b = 0; b < MAX_DEPTH; b++)
    board[x][y][b] = mark_to_set;
  
  for (dx = -3; dx <= 3; dx++)
    for (dy = -3; dy <= 3; dy++)
      for (b = 0; b < MAX_DEPTH; b++)
	if ((x + dx >= 0) && (x + dx < BOARD_SIZE) &&
	    (y + dy >= 0) && (y + dy < BOARD_SIZE) &&
	    (board[x + dx][y + dy][b] == SQUARE_EMPTY_FAR))
	  board[x + dx][y + dy][b] = SQUARE_EMPTY_NEAR;

  last_x = x;
  last_y = y;

  n_moves[mark_to_set]++;
  if (beginner == -1)
    beginner = mark_to_set;
}

int score_position(int x, int y, int player)
{
  int result;
  int record = INT_MIN;
  int xx, yy, score;

  result = scores.get_score(pattern_from_board(player, x, y));

  // Winning moves get INT_MAX points
  if (result == INT_MAX)
    return INT_MAX;
  
  // FIXME: This routine could possibly be optimized by first
  // computing the opponent's best move on an unmodified board, and
  // then recurse only when I make that particular move.  Otherwise,
  // that move's score could be deducted from my move's score.  This
  // concept needs some tuning though; a move may be rendered
  // worthless by some other move, but the general idea probably
  // holds.
  
  // FIXME: The recursion depth in the below loop should depend on the
  // MAX_DEPTH constant instead of being hard coded as below.

  // Check out what the other player can do to us if we make this move
  board[x][y][1] = player;
  for (xx = 0; xx < BOARD_SIZE; xx++)
    for (yy = 0; yy < BOARD_SIZE; yy++)
      if (board[xx][yy][1] == SQUARE_EMPTY_NEAR)
	{
	  score = scores.get_score(pattern_from_board(1 - player,
						      xx,
						      yy,
						      1));
	  
	  if (score > record)
	    record = score;
	}
  board[x][y][1] = board[x][y][0];

  // The opponent wins if we make this move.  That's bad.
  if (record == INT_MAX)
    return INT_MIN;
  
  return result - record;
}

void computer_make_move()
{
  static int move_buffer_size = 100;
  static int *xbuf = (int *)malloc(move_buffer_size * sizeof(int));
  static int *ybuf = (int *)malloc(move_buffer_size * sizeof(int));
  int next_free_move = 0;
  int x, y, score;
  int movex, movey, record = INT_MIN;
  int i;

  // Set no-moves-evaluated-marker
  xbuf[0] = -1;

  // For all squares
  for (x = 0; x < BOARD_SIZE; x++)
    for (y = 0; y < BOARD_SIZE; y++)
      {
	// Check "near" squares only
	if (board[x][y][0] == SQUARE_EMPTY_NEAR)
	  {
	    score = score_position(x, y, PLAYER_ME);

	    if ((score > record) ||
		(xbuf[0] == -1))  // Is this the first move being scored?
	      {
		next_free_move = 0;
		xbuf[next_free_move] = x;
		ybuf[next_free_move] = y;
		next_free_move++;
		record = score;
	      }
	    else if (score == record)
	      {
		xbuf[next_free_move] = x;
		ybuf[next_free_move] = y;
		next_free_move++;
		
		if (next_free_move >= move_buffer_size)
		  {
		    // Extend the buffers if necessary
		    move_buffer_size += 100;

		    xbuf = (int *)realloc(xbuf,
					  move_buffer_size * sizeof(int));
		    ybuf = (int *)realloc(ybuf,
					  move_buffer_size * sizeof(int));
		  }
	      }
	  }
      }

  if (next_free_move == 0)
    terminate("computer_make_move(): No move to make");

  // Pick movex and movey from the list of possible squares
  i = (int) (((float) next_free_move) * rand() / (RAND_MAX+1.0));
  
  if (i >= next_free_move)
    terminate("computer_make_move(): Attempt to make move outside list");
  
  // movex and movey are the move's coordinates
  movex = xbuf[i];
  movey = ybuf[i];

  if ((movex < 0) ||
      (movex >= BOARD_SIZE) ||
      (movey < 0) ||
      (movey >= BOARD_SIZE))
    terminate("computer_make_move(): Coordinate outside board");

  if ((board[movex][movey][0] != SQUARE_EMPTY_NEAR) &&
      (board[movex][movey][0] != SQUARE_EMPTY_FAR))
    terminate("Computer_make_move(): Square not empty");

  // Tell the UI about our move
  printf("%d %d\n", movex, movey);
  fflush(stdout);
  
  // Remember the move
  set_mark(movex, movey, PLAYER_ME);
}

void learn_from_winner()
{
  int n_such_moves;
  int player;
  int factor;
  
  Pattern pattern;
  
  for (player = 0; player < 2; player++)
    {
      // Learn twice if the second player won
      factor = ((winner != beginner) ? 2 : 1);

      // Learn negatively from the loser
      if (player != winner)
	factor = -factor;

      for (pattern = patterns[player].findfirst();
	   patterns[player].is_valid();
	   pattern = patterns[player].findnext())
	{
	  // How many such moves has the player made?
	  n_such_moves = patterns[player].lookup(pattern);

	  // Learn from those (and twice if the second player won)
	  scores.mark_good(pattern, n_such_moves * factor);
	}
    }

  if (scores.count() == 0)
    terminate("Don't know *anything* after game over!");

  if (!scores.dump(data_file_name.c_str()))
    fprintf(stderr,
	    "Warning: Failed to save knowledge base (%s)!\n",
	    strerror(errno));
}

int main()
{
  int order, x, y;

  // Initialise the random number generator
  srand(time(NULL));
  
  data_file_name = getenv("HOME");
  if (data_file_name.size() == 0)
    terminate("HOME variable not set; don't know where to put the data file");
  data_file_name += "/.gma-";
  data_file_name += VERSION;
  data_file_name += ".data";

  // Read scores from disk
  scores.init(data_file_name.c_str());
  
  init_board();
  init_players();

  do {
    if (scanf(" %d", &order) != 1)
      terminate("Error reading order");

    switch (order)
      {
      case ORDER_YOUR_MOVE:
	if (scanf(" %d %d", &x, &y) != 2)
	  terminate("Error reading my move coordinates");
	set_mark(x, y, PLAYER_ME);
	break;
	
      case ORDER_OPPONENTS_MOVE:
	if (scanf(" %d %d", &x, &y) != 2)
	  terminate("Error reading opponent's move coordinates");
	set_mark(x, y, PLAYER_OPPONENT);
	break;
	
      case ORDER_MAKE_MOVE:
	// Sanity check
	if (abs(n_moves[0] - n_moves[1]) > 1)
	  terminate ("One player has made more moves than the other!");
	
	computer_make_move();
	break;

      case ORDER_YOU_WIN:
	winner = PLAYER_ME;
	break;

      case ORDER_YOU_LOSE:
	winner = PLAYER_OPPONENT;
	break;

      default:
	terminate("Unknown order received");
      }
  } while (winner < 0);

  if (!winning_move_detected)
    terminate("The game is over but I didn't detect any winning move.  "
	      "This probably indicates a problem with the Pattern::winner() "
	      "method, with the UI or with the pattern_from_board() "
	      "function.");
  
  learn_from_winner();
  
  return 0;
}