// Copyright 2011 Thomas R. Davis
//
// This file is part of Hack.
//
// Hack 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.
//
// Hack 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 Hack; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

// Documentation:
//
// hack will play red-blue hakenbush against a user, but it can also
// be used just to analyze positions, and to try multiple coloring
// patterns on positions to give some idea of how hard a winning position
// is to win.  It does this by playing a large number of games (1000 by
// default) and presenting colorings that are lost more than x% of the
// time by random play.  x% is currently 95%.  At the end of the play, a
// listing like this:
//
// Wins: 384/400 RRBRRBBRBBRRBBBBBR: value = 1/4
//
// means that Blue lost 384 times out of 400 when it played randomly
// against Red playing perfectly.  Blue initially had an advantage of
// 1/4, and to achieve this, the edges 0, 1, 2, ... must be colored
// red, red, blue, red, red, blue, ... in order.
//
// Checking all colorings does just that: it checks the 2^n ways of
// coloring all the edges.  Many such colorings are obviously useless
// where there are many more of one color than the other.
//
// Checking "most" of the colorings looks only at games where there are
// roughly the same number of red and blue edges.  In fact, if there are
// N edges, and x = floor(N/2), it checks games with x reds, with x-1
// reds and with x+1 reds.  It would be easy to modify the code to
// check more or fewer.
//
// There is documentation of the program in the routine
// helpmessage(), below.
//
// For now, the game must have fewer than 64 edges or nodes.
//
// I would compile this with optimization on, like this:
//
// cc hack.c -o hack -O3
//
// Bugs, comments, suggestions, rants, et cetera to:
//
// tomrdavis@earthlink.net

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAXNODES 128
#define MAXEDGESPERNODE 64
#define MAXEDGES 64
#define HASHTABLESIZE 1157007

#define BLUE 1
#define RED 2

//#define DEBUG

int hashcounter = 0;

// for now, the nodes in the initial game must be sequential: can't
// leave out any nodes from 0 up to the max node number.
// edge[i][0] = first node
// edge[i][1] = second node
// edge[i][2] = color (RED or BLUE)
// edge[i][3] is used for marking edges

struct game {
	int edge[MAXEDGES][4];
} G;

int edgecount = 0;

typedef struct { // den > 0 always, for now, den = 2^n, for some n
	int num, den;
} surreal;

int componentlist[MAXEDGES][MAXEDGES];
surreal componentvalues[MAXEDGES];

int node[MAXNODES][MAXEDGESPERNODE];
int mark[MAXNODES];

struct gamevalue {
	long long int game;
	surreal value;
};

struct hashentry {
	struct hashentry *next;
	struct gamevalue gv;
};

struct hashentry *hashtable[HASHTABLESIZE];

long long int getgamevalue(struct game *g)
{
	int i=0;
	long long int gv = 0;
	while (g->edge[i][0] != -1) {
		gv <<= 1;
		if (g->edge[i][0] >= 0)
			gv |= 1;
		i++;
	}
	return gv;
}

int hashvalue(long long int x)
{
	return x % HASHTABLESIZE;
}

int lookupgamevalue(long long int gv, surreal *value)
{
	int hashval = hashvalue(gv);
	struct hashentry *he = hashtable[hashval];
	while (he) {
		if (he->gv.game == gv) {
			*value = he->gv.value;
			return 1;
		}
		he = he->next;
	}
	return 0;
}

struct hashlink {
	struct hashentry *entrylist;
	struct hashlink *next;
};

struct hashlink *listlist = 0;
static struct hashentry *helist;
static int helistcount = 1000;

void addgamevalue(long long int gv, surreal *value)
{
	struct hashlink *linklink;
	int hashval = hashvalue(gv);
	if (helistcount == 1000) {
		helist = (struct hashentry *)malloc(1000*sizeof(struct hashentry));
		linklink = (struct hashlink *)malloc(sizeof(struct hashlink));
		linklink->entrylist = helist;
		linklink->next = listlist;
		listlist = linklink;
		helistcount = 0;
	}
	struct hashentry *he = helist + helistcount++;
	he->gv.game = gv;
	he->gv.value = *value;
	he->next = hashtable[hashval];
	hashtable[hashval] = he;
	hashcounter++;
}

void inithashtable()
{
	int i;
	surreal val;
	struct hashlink *save;

	while (listlist) {
		free(listlist->entrylist);
		save = listlist;
		listlist = listlist->next;
		free(save);
	}
	helistcount = 1000;
	hashcounter = 0;
	val.num = 0; val.den = 1;
	for (i = 0; i < HASHTABLESIZE; i++)
		hashtable[i] = 0;
	addgamevalue(0, &val);
	return;
}

int surlessthan(surreal *a, surreal *b)
{
	long long int an, ad, bn, bd;
	
	an = a->num; ad = a->den; bn = b->num; bd = b->den;
	if (an * bd < bn * ad) return 1;
	return 0;
}

void reduce(surreal *a)
{
	int n = a->num, d = a->den;
	if (n < 0) {
		n = -n;
		while (((n&1) == 0) && ((d&1) == 0)) {
			n >>= 1; d >>= 1;
		}
		a->num = -n;
		a->den = d;
		return;
	}
	while (((n&1) == 0) && ((d&1) == 0)) {
		n >>= 1; d >>= 1;
	}
	a->num = n;
	a->den = d;
}

void surrealsum(surreal *ain, surreal *bin, surreal *aplusb)
{
	surreal a = *ain, b = *bin;
	int f, g;

	if (a.den < b.den) {
		f = b.den/a.den;
		a.num *= f;
		a.den *= f;
	} else if (a.den > b.den) {
		f = a.den/b.den;
		b.num *= f;
		b.den *= f;
	}
	aplusb->num = a.num + b.num;
	aplusb->den = b.den;
	reduce(aplusb);
	return;
}

int surmiddle(surreal *a, surreal *b, surreal *surmid) // a < b
{
	int f, d, nextnum, g;
	surreal alocal = *a, blocal = *b;
	int swap = 0;

#ifdef DEBUG
	if (0 == surlessthan(a, b)) {
		fprintf(stderr, "Bad surreal order: %d/%d < %d/%d fails\n",
			a->num, a->den, b->num, b->den);
		return -1;
	}
#endif /* DEBUG */
	if (a->num < 0 && b->num > 0) {
		surmid->num = 0;
		surmid->den = 1;
		return 1;
	}
	if (b->num < 0 || a->num < 0) { // swap
		surreal tmp;
		tmp = alocal;
		alocal = blocal;
		blocal = tmp;
		swap = 1;
		alocal.num *= -1;
		blocal.num *= -1;
	}
	// get the same denominator:
	if (alocal.den < blocal.den) {
		f = blocal.den/alocal.den;
		alocal.den *= f;
		alocal.num *= f;
	} else {
		f = alocal.den/blocal.den;
		blocal.den *= f;
		blocal.num *= f;
	}
	d = alocal.den; // d is common denominator
	if (alocal.num + 1 == blocal.num) {
		surmid->num = alocal.num + blocal.num;
		surmid->den = 2*d;
		if (swap) { // swap back
			surmid->num *= -1;
		}
		//printf("%d/%d < %d/%d < %d/%d\n", a->num, a->den, surmid->num, surmid->den, b->num, b->den);
		return 1;
	}
	while (1) {
		nextnum = ((alocal.num + d)/d)*d;
		if (nextnum < blocal.num) {
			surmid->num = nextnum;
			surmid->den = alocal.den;
			reduce(surmid);
			if (swap) { // swap back
				surmid->num *= -1;
			}
			//printf("%d/%d < %d/%d < %d/%d\n", a->num, a->den, surmid->num, surmid->den, b->num, b->den);
			return 1;
		}
		d = d/2;
	}
}

int isgrounded(int e, struct game *g, int initialcall)
{
	int i, n0, n1;

	if (initialcall == 1) {
		i = 0;
		while (node[i][0] != -1) mark[i++] = 0;
	}
	if ((n0 = g->edge[e][0]) == 0 || (n1 = g->edge[e][1]) == 0) return 1;
	if (n0 == -2) return 0;
	if (mark[n0] == 0) {
		mark[n0] = 1;
		i = 0;
		while (node[n0][i] != -1)
			if (isgrounded(node[n0][i++], g, 0)) return 1;
	}
	if (mark[n1] == 0) {
		mark[n1] = 1;
		i = 0;
		while (node[n1][i] != -1)
			if (isgrounded(node[n1][i++], g, 0)) return 1;
	}
	return 0;
}

void markedges(struct game *g, int nodenum)
{
	int i = 0, e;
	while ((e = node[nodenum][i]) != -1) {
		if (g->edge[e][3] == 0 && g->edge[e][0] != -2) {
			g->edge[e][3] = 1; // mark it
			markedges(g, g->edge[e][0]);
			markedges(g, g->edge[e][1]);
		}
		i++;
	}
}

void prunegame(struct game *g)
{
	int i;
	
	for (i = 0; i < edgecount; i++)
		g->edge[i][3] = 0; // not looked at yet
	markedges(g, 0); // mark edges connected to node 0
	for (i = 0; i < edgecount; i++)
		if (g->edge[i][3] == 0)
			g->edge[i][0] = -2;
}

int findcomponents(struct game *g)
{
	int i, j, k, n1, n2, componentcount = 0, changed;
	struct game G = *g;
	int nodes[MAXNODES];
	
	for (i = 0; i < MAXEDGES; i++)
		for (j = 0; j < MAXEDGES; j++)
			componentlist[i][j] = 0;
	i = 0;
	while (isemptygame(&G) == 0) {
		for (i = 0; i < MAXNODES; i++) nodes[i] = 0;
		i = 0;
		while (G.edge[i][0] == -2) i++;
		if (G.edge[i][0] != 0) nodes[G.edge[i][0]] = 1;
		if (G.edge[i][1] != 0) nodes[G.edge[i][1]] = 1;
		do {
			changed = 0;
			for (j = 1; j < MAXNODES; j++) {
				if (nodes[j] == 1) {
					k = 0;
					while (node[j][k] != -1) {
						n1 = G.edge[node[j][k]][0];
						n2 = G.edge[node[j][k]][1];
						if (n1 > 0 && nodes[n1] == 0) {
							nodes[n1] = 1;
							changed = 1;
						}
						if (n1 > 0 && n2 > 0 && nodes[n2] == 0) {
							nodes[n2] = 1;
							changed = 1;
						}
						k++;
					}
				}
			}
		} while (changed == 1);
		for (j = 1; j < MAXNODES; j++) {
			if (nodes[j] == 1) {
				for (k = 0; k < edgecount; k++) {
					if (G.edge[k][0] == j || G.edge[k][1] == j) {
						componentlist[componentcount][k] = 1;
						G.edge[k][0] = -2;
					}
				}
				
			}
		}
		componentcount++;
	}
	return componentcount;
}

void printcomponents(int count)
{
	int i, j;
	for (i = 0; i < count; i++) {
		printf("%d: ", i);
		for (j = 0; j < MAXEDGES; j++)
			if (componentlist[i][j]) printf("%d, ", j);
		printf("\n");
	}
}

int sanitycheckgame(struct game *g)
{
	int i;
	
	i = 0;
	while (g->edge[i][0] != -1) {
		if (g->edge[i][0] < 0 || g->edge[i][0] >= MAXEDGES) return 0;
		if (g->edge[i][1] < 0 || g->edge[i][1] >= MAXEDGES) return 0;
		i++;
	}
	i = 0;
	while (g->edge[i][0] != -1)
		if (isgrounded(i++, g, 1) == 0) return 0;
	return 1;
}

printgame(struct game *g)
{
	int i, j;
	printf("Edges:\n");
	i = 0;
	while (g->edge[i][0] != -1) {
		if (g->edge[i][0] >= 0)
			printf("%3d: %3d %3d %s\n", i, g->edge[i][0], g->edge[i][1],
				(g->edge[i][2] == RED) ? "Red" : "Blue");
		i++;
	}
	printf("\n");

#ifdef NOTDEF
	printf("\nNodes:\n");
	i = 0;
	while (node[i][0] != -1) {
		printf("%3d: ", i);
		j = 0;
		while (node[i][j] != -1)
			printf("%3d ", node[i][j++]);
		printf("\n");
		i++;
	}
#endif /* NOTDEF */
}

int readgame(FILE *f, struct game *g)
{
	int n1, n2, i;
	char c;

	for (i = 0; i < MAXNODES; i++)
		node[i][0] = -1;
	while (fscanf(f, "%d %d %c\n", &n1, &n2, &c) != EOF) {
	    if (n1 == -1 && n2 == -1) {
	    	g->edge[edgecount][0] = -1;
	    	g->edge[edgecount][1] = -1;
	    	//printgame(g);
	    	return sanitycheckgame(g);
	    }
	    if (n1 > n2) { // guarantees they're in order
	    	int temp = n1;
	    	n1 = n2;
	    	n2 = temp;
	    }
	    g->edge[edgecount][0] = n1;
	    g->edge[edgecount][1] = n2;
	    g->edge[edgecount][2] = (c == 'B') ? BLUE : RED;
	    i = 0;
	    while (node[n1][i] != -1) i++;
	    node[n1][i++] = edgecount;
	    node[n1][i] = -1;
	    if (n1 != n2) {
	    	i = 0;
			while (node[n2][i] != -1) i++;
			node[n2][i++] = edgecount;
			node[n2][i] = -1;
	    }
	    edgecount++;
	}
	return 0;
}

void cutedge(int e, struct game *g)
{
	//int i;

	g->edge[e][0] = -2;
	prunegame(g);
	return;
/*
	i = 0;
	while (g->edge[i][0] != -1) {
		if (g->edge[i][0] != -2)
			if (isgrounded(i, g, 1) == 0) {
				g->edge[i][0] = -2;
			}
		i++;
	}
*/
}

int isemptygame(struct game *g)
{
	int i = 0;
	
	while (g->edge[i][0] != -1)
		if (g->edge[i++][0] >= 0) return 0;
	return 1;
}

int Bestred, Bestblue;

void componentvalue(struct game *g, surreal *value, int firsttime)
{
	surreal bluemax, redmin, newvalue;
	struct game newg;
	int i, j;
	long long int gv;
	
	// maybe we already did it?
	if (lookupgamevalue(gv = getgamevalue(g), value)) return;

	bluemax.den = -1; // illegal
	redmin.den = -1; // illegal

	//if (isemptygame(g)) {
	//	value->num = 0;
	//	value->den = 1;
	//	return;
	//}
	i = 0;
	while (g->edge[i][0] != -1) {
		if (g->edge[i][0] >= 0) {
			newg = *g;
			cutedge(i, &newg);
			componentvalue(&newg, &newvalue, 0);
			switch (g->edge[i][2]) {
				case BLUE:
					if (bluemax.den == -1) {
						bluemax = newvalue;
					} else if (surlessthan(&bluemax, &newvalue)) {
						bluemax = newvalue;
					}
					break;
				case RED:
					if (redmin.den == -1) {
						redmin = newvalue;
					} else if (surlessthan(&newvalue, &redmin)) {
						redmin = newvalue;
					}
					break;
				default:
					fprintf(stderr, "Component error!\n");
					exit(-1);
			}
		}
		i++;
	}
	if (bluemax.den == -1) {
		bluemax.den = 1;
		bluemax.num = -10000;
	}
	if (redmin.den == -1) {
		redmin.den = 1;
		redmin.num = 10000;
	}
#ifdef DEBUG
	if (-1 == surmiddle(&bluemax, &redmin, value)) { // horrible error!
		printgame(g);
		exit(-1);
	}
#else
	surmiddle(&bluemax, &redmin, value);
#endif /* DEBUG */
	addgamevalue(gv, value);
}

void calcgamevalue(struct game *g, surreal *value)
{
	int componentcount, i, j;
	struct game G;
	surreal locvalue;

	componentcount = findcomponents(g);
	for (i = 0; i < componentcount; i++) {
		G = *g;
		//inithashtable(0);
		j = 0;
		while(G.edge[j][0] != -1) {
			if (componentlist[i][j] == 0)
				G.edge[j][0] = -2;
			j++;
		}
		componentvalue(&G, &locvalue, 1);
		componentvalues[i] = locvalue;
	}
	locvalue.num = 0;
	locvalue.den = 1;
	for (i = 0; i < componentcount; i++)
		surrealsum(&locvalue, &componentvalues[i], &locvalue);
	*value = locvalue;
}

void findbestgamemoves(struct game *g)
{
	surreal bluemax, redmin, newvalue;
	struct game newg;
	int i, j;
	long long int gv;
	int bestred = -1, bestblue = -1;
	
	Bestred = Bestblue = -1;

	bluemax.den = -1; // illegal
	redmin.den = -1; // illegal

	if (isemptygame(g)) {
		Bestred = bestred;
		Bestblue = bestblue;
		return;
	}
	i = 0;
	while (g->edge[i][0] != -1) {
		if (g->edge[i][0] >= 0) {
			newg = *g;
			//j = 0;
			//while (g->edge[j][0] != -1) {
			//	newg.edge[j][0] = g->edge[j][0];
			//	newg.edge[j][1] = g->edge[j][1];
			//	newg.edge[j][2] = g->edge[j][2];
			//	j++;
			//}
			//newg.edge[j][0] = -1;
			cutedge(i, &newg);
			calcgamevalue(&newg, &newvalue);
			switch (g->edge[i][2]) {
				case BLUE:
					if (bluemax.den == -1) {
						bluemax = newvalue;
						bestblue = i;
					} else if (surlessthan(&bluemax, &newvalue)) {
						bluemax = newvalue;
						bestblue = i;
					}
					break;
				case RED:
					if (redmin.den == -1) {
						redmin = newvalue;
						bestred = i;
					} else if (surlessthan(&newvalue, &redmin)) {
						redmin = newvalue;
						bestred = i;
					}
					break;
			}
		}
		i++;
	}
	if (bluemax.den == -1) {
		bluemax.den = 1;
		bluemax.num = -10000;
	}
	if (redmin.den == -1) {
		redmin.den = 1;
		redmin.num = 10000;
	}
	//surmiddle(&bluemax, &redmin, value);
	if (1) {
		Bestred = bestred;
		Bestblue = bestblue;
	}
}

int readnumber()
{
	char str[100];
	int i = 0, c, val;
	while (1) {
		c = getchar();
		if (c == '\n') {
			str[i] = 0;
			sscanf(str, "%d", &val);
			return val;
		}
		str[i++] = c;
	}
}

void helpmessage()
{
printf("By default, Blue moves first, and the computer plays Red\n");
printf("The '-r' option lets you play Red\n");
printf("The '-m' option tells the machine to play first\n");
printf("\n");
printf("The '-g' option tests the game as follows: Blue chooses\n");
printf("moves at random and the machine plays Red perfectly.  The\n");
printf("fraction displayed shows the fraction of times the machine\n");
printf("won.  If this number is close to 1, it is a tough game\n");
printf("for Blue to win\n");
printf("\n");
printf("The '-w' option puts you in wizard mode and all game\n");
printf("values and best moves are presented for each position\n");
printf("\n");
printf("The '-c' option tries all possible colorings and searches\n");
printf("for games that are hard for blue to win.  The sequences\n");
printf("printed indicate how the edges should be colored\n");
printf("\n");
printf("The '-C' option tries all colorings with roughly the same\n");
printf("number of blue and red segments and searches\n");
printf("for games that are hard for blue to win.  The sequences\n");
printf("printed indicate how the edges should be colored\n");
printf("\n");
printf("The '-n <count>' gives the number of times the random\n");
printf("games for the -c and -C options should be played\n");
printf("<count> should be an integer larger than 100\n");
printf("\n");
printf("The '-p <fraction>' gives the proportion of wins for red\n");
printf("in games for the -c and -C options necessary for reporting\n");
printf("the result.  <fraction> is .95 by default\n");
printf("\n");
printf("As an example, the command:\n");
printf("\n");
printf("hack -C -p .995 file.hack\n");
printf("\n");
printf("will display results where 99.5% of the time red wins.\n");
printf("\n");
printf("Game format:\n");
printf("\n");
printf("The gamefile is an ascii (text) file where each line consists\n");
printf("of a pair of nodes followed by a 'R' or 'B' to indicate\n");
printf("whether the edge is red or blue.  The final line looks like\n");
printf("this:\n");
printf("\n");
printf("-1 -1 X\n");
printf("\n");
printf("Node 0 is the ground and (at least for now) do not leave out\n");
printf("any node numbers.  Here is a sample file for the game that looks\n");
printf("like a \"Y\", where the two upper edges are red and the lower edge\n");
printf("is blue:\n");
printf("\n");
printf("0 1 B\n");
printf("1 2 R\n");
printf("1 3 R\n");
printf("-1 -1 X\n");
printf("\n");
printf("You can add a blue loop to the top of node 3 above by adding this:\n");
printf("\n");
printf("3 3 B\n");
printf("\n");
printf("just before the final line.\n");
printf("\n");
printf("For now, the game must have fewer than 64 edges or nodes.\n");
}

int a[10000000];
int acount = 0;

char *zeros = "00000000000000000000";
char *ones = "11111111111111111111";

int genint(char *s)
{
	int x = 0;
	while (*s) {
		x <<= 1;
		if (*s++ == '1') x |= 1;
	}
	return x;
}

// choose k 1's from n

comstr(char *prev, int k, int n)
{
	char local[25];

	if (k == 0) {
		strcpy(local, prev);
		strcat(local, &zeros[20-n]);
		a[acount++] = genint(local);
		return;
	}
	if (k == n) {
		strcpy(local, prev);
		strcat(local, &ones[20-n]);
		a[acount++] = genint(local);
		return;
	}
	strcpy(local, prev);
	strcat(local, "0");
	comstr(local, k, n-1);
	strcpy(local, prev);
	strcat(local, "1");
	comstr(local, k-1, n-1);
	return;
}

int counttry = 1000;

int playmanygames(struct game *g, int count);

void checkallcolorings(struct game *g)
{
	int i;
	surreal value;
	int gamecount = 1;
	int currentgame, dummy;
	double x;
	
	for (i = 0; i < edgecount; i++) gamecount *= 2;
	for (currentgame = 0; currentgame < gamecount/2; currentgame++) {
		printf("tested %d of %d\r", currentgame, gamecount/2); fflush(stdout);
		dummy = currentgame;
		for (i = 0; i < edgecount; i++) {
			if (dummy & 1)
				g->edge[i][2] = RED;
			else
				g->edge[i][2] = BLUE;
			dummy >>=1;
		}
		inithashtable();
		calcgamevalue(g, &value);
		x = ((double)value.num)/((double)value.den);
		if (value.num != 0 && fabs(x) < .51) {
			if (value.num < 0) { // swap colors
				for (i = 0; i < edgecount; i++) {
					if (g->edge[i][2] == RED)
						g->edge[i][2] = BLUE;
					else
						g->edge[i][2] = RED;
				}
				inithashtable();
				calcgamevalue(g, &value);
			}
			if (playmanygames(g, counttry)) {
				for (i = 0; i < edgecount; i++)
					printf("%c", g->edge[i][2] == BLUE ? 'B' : 'R');
				printf(": value = %d/%d ", value.num, value.den);
				printf("positions = %d\n", hashcounter);
			}
		}
	}
	exit(0);
}

void checkcombcolorings(struct game *g)
{
	int i;
	surreal value;
	int gamecount = 1;
	int currentgame, dummy;
	double x;
	
	comstr("", edgecount/2, edgecount);
	comstr("", edgecount/2-1, edgecount);
	for (currentgame = 0; currentgame < acount; currentgame++) {
		printf("tested %d of %d\r", currentgame, acount); fflush(stdout);
		dummy = a[currentgame];
		//printf("%x ", dummy);
		for (i = 0; i < edgecount; i++) {
			if (dummy & 1)
				g->edge[i][2] = RED;
			else
				g->edge[i][2] = BLUE;
			dummy >>=1;
		}
		inithashtable();
		calcgamevalue(g, &value);
		x = ((double)value.num)/((double)value.den);
		if (value.num != 0 && fabs(x) < .51) {
			if (value.num < 0) { // swap colors
				for (i = 0; i < edgecount; i++) {
					if (g->edge[i][2] == RED)
						g->edge[i][2] = BLUE;
					else
						g->edge[i][2] = RED;
				}
				inithashtable();
				calcgamevalue(g, &value);
			}
			if (playmanygames(g, counttry)) {
				for (i = 0; i < edgecount; i++)
					printf("%c", g->edge[i][2] == BLUE ? 'B' : 'R');
				printf(": value = %d/%d ", value.num, value.den);
				printf("positions = %d\n", hashcounter);
			}
		}
	}
	exit(0);
}

makerandombluemove(struct game *g)
{
	int edges[MAXEDGES];
	int blueedges = 0;
	int i = 0;
	while (i < edgecount) {
		while (g->edge[i][0] != -2 && g->edge[i][2] == RED) i++;
		if (i < edgecount) edges[blueedges++] = i++;
	}
	if (blueedges == 0) return 0;
	cutedge(edges[random() % blueedges], g);
	return 1;
}

// playrandomgame() assumes that the machine plays a perfect game for
// red and the blue player chooses moves randomly.  The routine returns
// 1 if the machine wins and 0 otherwise.  We assume that blue makes
// the first move.  We also assume there is a blue move available!

int playrandomgame(struct game *g)
{
	surreal value;
	
	while (1) {
		if (0 == makerandombluemove(g)) return 0;
		calcgamevalue(g, &value);
		if (value.num < 0) return 1;
		findbestgamemoves(g);
		if (Bestred == -1) return 0;
		cutedge(Bestred, g);
	}
}

double percent = .95;

int playmanygames(struct game *G, int count)
{
	int i=0, wins=0;
	struct game g;
	surreal value;
	srandomdev();
	for (i = 0; i < count; i++) {
		g = *G;
		wins += playrandomgame(&g);
	}
	if (wins > (int)(count*percent)) {
		printf("Wins: %d/%d ", wins, count);
		return 1;
	}
	return 0;
}

int machineside = RED, ismachinesmove = 0, testcolorings = 0, testthisgame = 0; 
int wizardmode = 0, testcombcolorings = 0;
char *gamefile = 0;

int parseoptions(int argc, char **argv)
{
    int i = 1, j;

    if (argc == 1) {
        fprintf(stderr, "Usage: %s [-hwrmcCg] [-n <count>] [-p <fraction>] <game filename> "
            "(%s -h for help)\n", argv[0], argv[0]);
        exit(1);
    }
    do {
        if (argv[i][0] == '-') { // read option(s)
            char *p = &(argv[i][1]), *q;
            while (*p) {
                switch (*p) {
                    case 'h': helpmessage(); exit(0); break;
                    case 'r': machineside = BLUE; break;
                    case 'm': ismachinesmove = 1; break;
                    case 'c': testcolorings = 1; break;
                    case 'C': testcombcolorings = 1; break;
                    case 'g': testthisgame = 1; break;
                    case 'w': wizardmode = 1; break;
                    case 'n':
                        i++;
                        counttry = atoi(argv[i]);
                        break;
                    case 'p':
                    	i++;
                    	percent = atof(argv[i]);
                    	break;
                    default: helpmessage(); exit(0); break;
                }
                p++;
            }
        } else {
            gamefile = argv[i];
        }
        i++;
    } while (i < argc);
    if (gamefile == 0) {
    	fprintf(stderr, "No game file specified\n");
    	exit(1);
    }
}

int main(int argc, char **argv)
{
	FILE *f;
	surreal value;
	int humanmove, ok;
	struct game Gsmall;
	int j;
	
	inithashtable();
	parseoptions(argc, argv);
	f = fopen(gamefile, "r");
	if (f == 0) {
		fprintf(stderr, "Couldn't open %s\n", gamefile);
		exit(-1);
	}
	if (0 == readgame(f, &G)) {
		fprintf(stderr, "Error: Ungrounded edge\n");
		exit(-1);
	}
	printgame(&G);
	if (testthisgame)
		playmanygames(&G, 5000);
	if (testcombcolorings)
		checkcombcolorings(&G);
	if (testcolorings)
		checkallcolorings(&G);
	while (isemptygame(&G) == 0) {
		calcgamevalue(&G, &value);
		if (wizardmode) {
			printf("Game value: %d/%d ", value.num, value.den);
			printf("Positions: %d\n", hashcounter);
		}
		findbestgamemoves(&G);
		if (Bestred != -1 && Bestblue != -1 && wizardmode)
			printf("Best moves: Red: %d=(%d, %d), Blue: %d=(%d, %d)\n", Bestred, G.edge[Bestred][0], G.edge[Bestred][1], Bestblue, G.edge[Bestblue][0], G.edge[Bestblue][1]);
		else if (Bestred == -1 && Bestblue !=-1 && wizardmode)
			printf("Best moves: Red: no moves, Blue: %d=(%d, %d)\n", Bestblue, G.edge[Bestblue][0], G.edge[Bestblue][1]);
		else if (Bestred != -1 && Bestblue == -1 && wizardmode)
			printf("Best moves: Red: %d=(%d, %d), Blue: no moves\n", Bestred, G.edge[Bestred][0], G.edge[Bestred][1]);
		else if (wizardmode)
			printf("Best moves: Red: no moves, Blue: no moves\n");
		if (ismachinesmove) {
			if (machineside == RED) {
				printf("Machine cuts %d=(%d, %d)\n", Bestred, G.edge[Bestred][0], G.edge[Bestred][1]);
				cutedge(Bestred, &G);
			} else {
				printf("Machine cuts %d=(%d, %d)\n", Bestblue, G.edge[Bestblue][0], G.edge[Bestblue][1]);
				cutedge(Bestblue, &G);
			}
			ismachinesmove = 0;
			printgame(&G);
			calcgamevalue(&G, &value);
			if (wizardmode)
				printf("Game value: %d/%d\n", value.num, value.den);
			findbestgamemoves(&G);
			if (Bestred != -1 && Bestblue != -1 && wizardmode)
				printf("Best moves: Red: %d=(%d, %d), Blue: %d=(%d, %d)\n", Bestred, G.edge[Bestred][0], G.edge[Bestred][1], Bestblue, G.edge[Bestblue][0], G.edge[Bestblue][1]);
			else if (Bestred == -1 && Bestblue !=-1 && wizardmode)
				printf("Best moves: Red: no moves, Blue: %d=(%d, %d)\n", Bestblue, G.edge[Bestblue][0], G.edge[Bestblue][1]);
			else if (Bestred != -1 && Bestblue == -1 && wizardmode)
				printf("Best moves: Red: %d=(%d, %d), Blue: no moves\n", Bestred, G.edge[Bestred][0], G.edge[Bestred][1]);
			else if (wizardmode)
				printf("Best moves: Red: no moves, Blue: no moves\n");
		}
		if (Bestblue == -1) {
			printf("Machine wins!\n");
			exit(0);
		}
		if (Bestred == -1) {
			printf("You win!\n");
			exit(0);
		}
		ok = 0;
		while (ok == 0) {
			printf("Your move >> ");
			humanmove = readnumber();
			if ((machineside==RED && G.edge[humanmove][2] == BLUE) ||
			    (machineside==BLUE && G.edge[humanmove][2] == RED))
						ok = 1;
			else printf("You must cut a %s edge\n", machineside==RED ? "blue" : "red");
		}
		//printf("human move = %d\n", humanmove);
		cutedge(humanmove, &G);
		printgame(&G);
		ismachinesmove = 1;
		//exit(0);
	}
	if (ismachinesmove)
		printf("You win!\n");
	else
		printf("Machine wins!\n");
	exit(0);
}