#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>

#define WINNING_SCORE      24
#define NUM_BOWLS          12
#define STONES_PER_BOWL    4
#define MAX_POSSIBLE_MOVES 6
#define POS_INFIN          24
#define NEG_INFIN          -24
#define PASS               -1
#define DEFAULT_DEPTH      16

#define TRACE FALSE
#define T if (TRACE) 
#define DEBUG
#undef NDEBUG

#define NDEBUG TRUE

typedef enum boolean_e {FALSE, TRUE} boolean;
typedef enum winner_e {PLAYER_ONE, PLAYER_TWO, DRAW, NONE} Winner;
typedef enum player_type_e {AUTO, SEMI, MANUAL} Player_type;
typedef enum max_min_e {MAX, MIN} Max_min;

static int depth[2];
static Player_type type[2];
static boolean rand_board;
static int repeat;
static boolean display;
static boolean firstmove;
static boolean creep;

struct Game_s {
	int stones[NUM_BOWLS];
	int score[2];
	int next;
};
typedef struct Game_s Game;


struct Move_list_s {
	int move[MAX_POSSIBLE_MOVES];
	int num_moves;
};
typedef struct Move_list_s Move_list;


static int total_stones(Game *g) {
	int b;
	int s = 0;
	
	for (b = 0; b < NUM_BOWLS; b++)
		s += g->stones[b];
	
	return s;
}


static void starting_position(/*@out@*/ Game *g) {
	int b;

	g->next = 0;
	g->score[0] = g->score[1] = 0;

	if (rand_board)
		do {
			for (b = 0; b < NUM_BOWLS; b++)
				g->stones[b] = 1 + (rand() % 8);
		} while (total_stones(g) < 2*WINNING_SCORE);
	else
		for (b = 0; b < NUM_BOWLS; b++)
			g->stones[b] = STONES_PER_BOWL;
}


static int owner(int b) __attribute__ ((const));
static int owner(int b) {
	if (b < NUM_BOWLS / 2)
		return 0;
	else return 1;
}


//static boolean must_pass(Game *g, int p) __attribute__ ((regparm (1)));
static boolean must_pass(Game *g, int p) {
	int b;
	for (b = 0; b < NUM_BOWLS; b++)
		if (owner(b) == p && g->stones[b] != 0)
			return FALSE;
	return TRUE;
}


static boolean contains_bad_chars(char *s) {
	char c;

	for (c = (char) 1; c <= '~'; ((int) c)++) {
		if (isspace((unsigned char) c))
			continue;
		if (c >= '0' && c <= '9')
			continue;
		if (strchr(s, (int) c) != 0)
			return TRUE;
	}
	
	return FALSE;
}


static int get_int() {
	const int BUFSIZE = 10;
	char buf[BUFSIZE];

	do {
		buf[0] = '\0';
		buf[BUFSIZE-1] = 'x';
		(void) fgets(buf, BUFSIZE, stdin);
		if (buf[BUFSIZE-1] == '\0' || buf[0] == '\0') {
			printf("Invalid length input\n");
			buf[0] = '\0';
		} else if (contains_bad_chars(buf)) {
			printf("Input contains bad chars\n");
			buf[0] = '\0';
		}
	} while (buf[0] == '\0');

	return atoi(buf);
}


//static int opponent(int p) __attribute__ ((const));
static int opponent(int p) {
	return (p == 1) ? 0 : 1;
}


static int get_move(Game *g) {
	if (must_pass(g, g->next)) {
		char c = 'x';
		printf("Player %d cannot move ", g->next+1);
		printf("- enter p to pass\n");
		do {
			c = (char) getchar();
		} while (c != 'p' && c != 'P');
		(void) getchar();
		return PASS;
	} else {
		int m = -2;
		do {
			printf("Player %d: which bowl? ", g->next+1);
			m = get_int() - 1;
			if (m < 0 || m >= NUM_BOWLS) {
				printf("No such bowl\n");
				m = -2;
			} else if (owner(m) != g->next) {
				printf("Bowl not yours\n");
				m = -2;
			} else if (g->stones[m] == 0) {
				printf("Bowl contains no stones\n");
				m = -2;
			}
		} while (m == -2);
		return m;
	}
}


//static void move(Game *g, int m) __attribute__ ((regparm (1)));
static void move(Game *g, int m) {
	int player = g->next;

	g->next = opponent(g->next);

	if (m != PASS) {
		int old_stones[NUM_BOWLS];
		int left = g->stones[m];
		int target, b;
	     
		for (b = 0; b < NUM_BOWLS; b++)
			old_stones[b] = g->stones[b];
		
		g->stones[m] = 0;
		target = (m + 1) % NUM_BOWLS;
		
		while (left-- > 0) {
			if (old_stones[target] == 1) {
				if (g->stones[target] == 1) {
					g->stones[target] = 0;
					++ g->score[player];
				}
				++ g->score[player];
			} else
				++ g->stones[target];
			
			target = (target + 1) % NUM_BOWLS;
		}
	}
}


//static int score(Game *g, int player) __attribute__ ((regparm (1)));
static int score(Game *g, int player) {
	int other_player = opponent(player);

	if (g->score[player] >= WINNING_SCORE)
		return POS_INFIN;
	else if (g->score[other_player] >= WINNING_SCORE)
		return NEG_INFIN;
	else
		return g->score[player] - g->score[other_player];
}


static void draw(Game *g) {
	int b;
	
	if (!display)
		return;

	printf("\n--------\n");
	printf("Score: %d - %d (%d to Player 1)\n", 
	       g->score[0],
	       g->score[1],
	       g->score[0] - g->score[1]);
	printf("Player %d's turn\n", g->next+1);
	
	printf("Bowl number:");
	for (b = NUM_BOWLS - 1; b >= (NUM_BOWLS / 2); b--)
		printf("\t%d", b+1);
	printf("\n\t");
	for (b = NUM_BOWLS - 1; b >= (NUM_BOWLS / 2); b--)
		printf("\t%d", g->stones[b]);

	printf("\n\n\t");
	for (b = 0; b < (NUM_BOWLS / 2); b++)
		printf("\t%d", g->stones[b]);
	printf("\nBowl number:");
	for (b = 0; b < (NUM_BOWLS / 2); b++)
		printf("\t%d", b+1);

	printf("\n\n");
}


static int minimax_ab(Game *g, 
		      int depth,
		      int a,
		      int b,
		      /*@out@*/ /*@null@*/ int *out_move)
//  __attribute__ ((regparm (3)))
  ;

static int minimax_ab(Game *g,
		      int depth,
		      int a,
		      int b,
		      /*@out@*/ /*@null@*/ int *out_move)
{
	int sc = score(g, g->next);

	if (depth == 0 || sc == NEG_INFIN || sc == POS_INFIN) {
		/* Leaf node. */
		return sc;
	} 

	if (must_pass(g, g->next)) {
		/* Only one move is possible - pass. */
		int s;
		Game ng = *g;
		if (out_move) *out_move = PASS;
		move(&ng, PASS);
		s = -minimax_ab(&ng, depth - 1, -b, -a, 0);
		if (s > a)
			return s;
		else
			return a;
	}

	/* Otherwise the possible moves are this player's bowls. */
	int first, last, bowl;
	if (g->next == 0) {
		first = 0;
		last = NUM_BOWLS / 2 - 1;
	} else {
		first = NUM_BOWLS / 2;
		last = NUM_BOWLS - 1;
	}

	if (out_move) *out_move = -1; /* 'unknown' */
		
	for (bowl = first; bowl <= last; bowl++)
		if (g->stones[bowl] > 0) {
			Game ng = *g;
			int s;
			move(&ng, bowl);
			s = -minimax_ab(&ng, depth - 1,
					-b, -a, 0);
			if (s > a) {
				a = s;
				if (out_move) *out_move = bowl;
			}
			if (a >= b)
				break;
		}

	if (out_move && *out_move == -1) {
		for (bowl = first; bowl <= last; bowl++)
			if(g->stones[bowl] > 0) {
				*out_move = bowl;
				break;
			}
	}

	return a;
}


static int best_move(Game *g, int player) {
	int best, s;
	s = minimax_ab(g, depth[player],
		       NEG_INFIN,
		       POS_INFIN,
		       &best);

	if (creep)
	     ++ depth[player];

	fprintf(stderr, "Best move for player %d has score %d\n", player+1, s);
	return best;
}


static Winner winner(Game *g) {
	if (g->score[0] >= WINNING_SCORE) {
		return PLAYER_ONE;
	} else if (g->score[1] >= WINNING_SCORE) {
		return PLAYER_TWO;
	} else if (must_pass(g, 0) && must_pass(g, 1)) {
		if (g->score[0] > g->score[1])
			return PLAYER_ONE;
		else if (g->score[1] > g->score[0])
			return PLAYER_TWO;
		else
			return DRAW;
	}
	return NONE;
}


static void describe_player(int p) {
	printf("Player %d: ", p+1);
	if (type[p] == AUTO)
		printf("automatic ");
	else if (type[p] == SEMI)
		printf("semi-automatic ");
	else
		printf("manual\n");

	if (type[p] != MANUAL)
		printf("depth %d\n", depth[p]);
}


static void batch(char **args) {
	int i, m;
	Game g;
	g.next = atoi(args[0]);
	depth[g.next] = DEFAULT_DEPTH;
	g.score[0] = atoi(args[1]);
	g.score[1] = atoi(args[2]);
	for (i = 0; i < NUM_BOWLS; i++)
		g.stones[i] = atoi(args[3+i]);
	display = (atoi(args[NUM_BOWLS+3]) != 0);
	firstmove = FALSE;
	if (display) {
	     describe_player(0);
	     draw(&g);
	}

	m = best_move(&g, g.next);
	if (display) {
	     printf("Recommended move for player %d ", g.next+1);
	     if (m == PASS)
		  printf("- pass\n");
	     else
		  printf("- bowl %d\n", m+1);
	} else
	     if (m == PASS)
		  printf("pass\n");
	     else
		  printf("%d\n", m);
}


static void init(int argc, char **argv) {
	int p, s;

	if (argc == 1) {
		int i = 0;
		while (i != 1 && i != 2) {
			printf("Enter 1 for computer goes first, ");
			printf("2 for second\n");
			(void) scanf("%d", &i);
		}
		(void) getchar();
	        -- i;
		type[i]           = SEMI;
		depth[i]          = DEFAULT_DEPTH;
		type[opponent(i)] = MANUAL;
		rand_board        = FALSE;
		repeat            = 1;
		display           = TRUE;
		creep             = FALSE;
	} else if (argc == 6) {
		for (p = 0; p <= 1; p++) {
			int d = atoi(argv[p+1]);
			if (d == 0) 
				type[p] = MANUAL;
			else {
				type[p] = AUTO;
				depth[p] = d;
			}
		}

		if ((s = atoi(argv[3])) != 0) {
			srand((unsigned int) s);
			rand_board = TRUE;
		} else
			rand_board = FALSE;
		
		if ((repeat = atoi(argv[4])) == 0) {
			fprintf(stderr, "repeat == 0\n");
			exit(EXIT_FAILURE);
		}
		
		display = (atoi(argv[5]) != 0);
	} else if (argc == NUM_BOWLS + 5) {
		batch(&(argv[1]));
		exit(0);
	} else
		fprintf(stderr, "usage: %s <player 1> <player 2> <seed> <repeat> <display>\n",	argv[0]);
}


int main(int argc, char **argv) {
	Game g;
	int orig_total_stones;

	init(argc, argv);
	while (repeat-- > 0) {
		if (display) {
			printf("\n----------------\n");
			printf("New game of Owari\n");
			describe_player(0);
			describe_player(1);
		}
		starting_position(&g);
		firstmove = TRUE;
		orig_total_stones = total_stones(&g);
		if (display)
			printf("%d stones\n", orig_total_stones);
		draw(&g);
		while (winner(&g) == NONE) {
			int m;
			
			if (type[g.next] != MANUAL) {
				m = best_move(&g, g.next);
				if (display) {
					printf("Recommended move for player %d ", g.next+1);
					if (m == PASS)
						printf("- pass\n");
					else
						printf("- bowl %d\n", m+1);
				}
				if (type[g.next] == SEMI)
					m = get_move(&g);
			} else
				m = get_move(&g);
			
			move(&g, m);
			draw(&g);
		}
	
		if (display) {
			if (winner(&g) == PLAYER_ONE) {
				printf("Player 1 has won\n");
 			} else if (winner(&g) == PLAYER_TWO) {
				printf("Player 2 has won\n");
			} else {
				printf("A draw\n");
			}
		}

		printf("%d %d %d\n", depth[0], depth[1], winner(&g));
	}
	return 0;
}