// This gathers statistics about Arimaa elementaries strategies

#define Player1 Stepping_pI_mI()
#define Player2 Stepping_pK_mK()

// Other bots are available in this file (Stepper(), Mover(), ...)
// or easily adapted. Any question: claude.chaunier@wanadoo.fr

const int Silence = 10000; // Statistics are displayed every 'Silence' games
// You better set it to 100 or so when a Mover is involved

#include <time.h>
typedef unsigned long ulong;	// this program assumes that long's are 32 bits

const ulong rand_seed = 0; // Another number here will yield different reproducible results
//const ulong rand_seed = std::time(0); // Use this line to get different results every time

/*
 0 X X X X X X X X
 X10 . . . . . . .
 X .20 . . . . . .
 X . .30 . . , . .
 X . . .40 . . . .
 X . . . .50 . . .
 X . . , . .60 . .
 X . . . . . .70 .
 X . . . . . . .80
 X X X X X X X X X90 X
*/

enum Direction { North=-9, West=-1, Here=0, East=+1, South=+9 };

const char Goldname[] = "Gold";
const char Silvername[] = "Silver";
const char* colorname[2] = { Goldname, Silvername };

enum Species { None=0, Rabbit, Cat, Dog, Horse, caMel, Elephant };
enum Color { Gold=0, Silver };

bool debug = false;

#include <string>
using namespace std;

const string EmptySquareSymbols = ".,-_ xX"; // I prefer the 2 first chars in there
const string AnimalSymbolStock = "RRRRRRRRCCDDHHMErrrrrrrrccddhhme";
const string SpeciesSymbols = " RCDHME rcdhme";
const Species species[32] = {
	Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, 
	Cat, Cat, Dog, Dog, Horse, Horse, caMel, Elephant,
	Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, Rabbit, 
	Cat, Cat, Dog, Dog, Horse, Horse, caMel, Elephant
};
int population[2];
int position[32];
bool living[32];

int active_side;
int move_count, ply_count;
int winner;

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <valarray>
#include <list>
#include <cmath>
#include <set>

// Some old compilers may not know the new official name for CLK_TCK?
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC	CLK_TCK
#endif

typedef unsigned char byte;		// 8 bits
typedef unsigned short ushort;	// assume 16 bits

// -------------------------------------------------------------------
// random number generator adapted from Donald Knuth's Standford GraphBase (1993)

ulong A[55];	// pseudo-random values (from 0 to 2^32-1, unlike Knuth's)
int iA;			// index of the last value in A[] that was used
ulong twirl;
ulong g = 1;	// growing pseudo-root modulo 2^32;

ulong flip_cycle()	// compute 55 more pseudo-random numbers
{	ulong *ii, *jj;

	for(ii = &A[0], jj = &A[31]; jj<=&A[54]; ++ii, ++jj) {
		if(twirl&1) twirl = 0x80000000UL+(twirl>>1); else twirl >>= 1;
		*ii = (*ii-twirl)*0x17196903UL-(*jj*0x19742103UL)^(g *= 0x21011975UL);
	}
	for(jj = &A[0]; ii<=&A[54]; ++ii, ++jj) {
		if(twirl&1) twirl = 0x80000000UL+(twirl>>1); else twirl >>= 1;
		*ii = (*ii-twirl)*0x17196903UL-(*jj*0x19742103UL)^(g *= 0x21011975UL);
	}
	// Knuth only did the fast *ii -= *jj and it was a catastroph for my hashing
	// function because my hash numbers are sums of random numbers and they would
	// often get unexpectedly equal.

	return A[iA = 54];
}

void init_rand(ulong seed)
{	ulong prev, next = 0x12011969UL; // Knuth set next=1 here instead

	A[0] = prev = twirl = seed^0xa5a5a5a5;	// not what Knuth did either, but as good
	for(ulong i = 21; i; i = (i+21)%55) {
		A[i] = next;
		if(twirl&1) twirl = 0x80000000UL+(twirl>>1); else twirl >>= 1;
		next = prev*0x17196903UL-next*0x19742103UL-twirl*0x21011975UL;
		// and here Knuth only did  next = prev-next-seed;
		prev = A[i];
	}
	flip_cycle();	// get the array values "warmed up"
	flip_cycle();
	flip_cycle();
	flip_cycle();
	flip_cycle();
}

inline ulong next_rand()
{	return (--iA>=0)? A[iA]: flip_cycle();
}

// -------------------------------------------------------------------

ulong hash_basis[92];
ulong hash_key, last_hash_key;

void init_hash() {
	for(int p=10; p<=80; p++) hash_basis[p] = next_rand();
}

inline void hash_clear(ulong * hash_table) {
		fill(hash_table,hash_table+16384,0UL);
}

inline void hash_insert(ulong * hash_table, const ulong key) {
	hash_table[(key & 0x0007ffe0L)>>5] |= 0x00000001L<<(key & 0x0000001fL);
}

inline bool hash_find(ulong * hash_table, const ulong key) {
	return (hash_table[(key & 0x0007ffe0L)>>5] & (0x00000001L<<(key & 0x0000001fL)))!=0;
}

// -------------------------------------------------------------------

template<int color> Direction& inc(Direction& d) {
	const Direction Up   = color? South: North;
	const Direction Left = color? East: West;
	const Direction Right= -Left;
	const Direction Down = -Up;

	switch(d) {
	case Here : return d = Up;
	case Up   : return d = Left;
	case Left : return d = Right;
	case Right: return d = Down;
	case Down : return d = Here;
	default: return d = Here;
	}
}

ostream& operator<< (ostream& s, const Direction d) {
	switch(d) {
	case North: return s << 'n' ;
	case West : return s << 'w' ;
	case Here : return s << 'x' ;
	case East : return s << 'e' ;
	case South: return s << 's' ;
	default   : return s << '?' ;
	}
}

int board[92]; // -1, 0, or 16+index in the array of animal
Species species_on_board[92];
int neighbours[2][92];

template<int color> inline bool subdued(const int a) {
	const int opponent = color^1;
	const int opponent_mask = 16+opponent*16;
	const int p = position[a];
	const Species s = species[a];
	
	return(
		neighbours[opponent][p]!=0 && (
			((board[p+North]&48)==opponent_mask && species_on_board[p+North]>s) ||
			((board[p+West ]&48)==opponent_mask && species_on_board[p+West ]>s) ||
			((board[p+East ]&48)==opponent_mask && species_on_board[p+East ]>s) ||
			((board[p+South]&48)==opponent_mask && species_on_board[p+South]>s)
		)
	);
}

template<int color> inline bool frozen(const int a) {
	const int opponent = color^1;
	const int p = position[a];
	const Species s = species[a];
	
	return(
		neighbours[opponent][p]!=0 && neighbours[color][p]==0 && (
			species_on_board[p+North]>s ||
			species_on_board[p+East ]>s ||
			species_on_board[p+West ]>s ||
			species_on_board[p+South]>s
		)
	);
}

void move_in(const int p, const int a) {
	const int color = a>>4;
	board[p] = a+16;
	species_on_board[p] = species[a];
	hash_key -= hash_basis[p]*species[a]*(color*2-1);
	position[a] = p;
	living[a] = true;
	++neighbours[color][p+North];
	++neighbours[color][p+West];
	++neighbours[color][p+East];
	++neighbours[color][p+South];
}

void move_out(const int p, const int a) {
	const int color = a>>4;
	--neighbours[color][p+South];
	--neighbours[color][p+East];
	--neighbours[color][p+West];
	--neighbours[color][p+North];
	living[a] = false;
	hash_key += hash_basis[p]*species[a]*(color*2-1);
	species_on_board[p] = None;
	board[p] = 0;
}

// -------------------------------------------------------------------

int goal_count[2];
int prey_count[2];

class Step {
public:
	int animal;
	int from_square;
	Direction direction;

	int to_square;

	int pushed_foe;	// pushed animal if any. -1 if none
	bool pushed;
	Species pulling_species; // None (=0) if none.

	int prey;		// trapped animal if any. -1 if none

public:
	bool is_pushing() const { return (pushed_foe>=0); };
	bool is_pushed() const { return pushed; };
	bool is_pulled() const { return (pulling_species!=None); };

	bool make();
	void undo() const;
	void init_pushed(const int pushedanimal) {
		animal = pushedanimal;
		from_square = position[pushedanimal];
		direction = Here;
		pushed = true;
		pulling_species = None;
		pushed_foe = prey = -1;
	}
	void init_not_pushed(const int tosquare, const Species pullingspecies) {
		direction = Here;
		to_square = tosquare;
		pushed = false;
		pulling_species = pullingspecies;
		prey = -1;
	}
	template<int color> void init_nor_pulled() {
		const int lowest_animal = color*16;
		const Direction Down = color? North: South;

		animal = lowest_animal+16;
		direction = Down;
		pushed = false;
		pulling_species = None;
		prey = -1;
	}
	template<int color> bool next();
	friend ostream& operator<< (ostream& stream, const Step step);
};

ostream& operator<< (ostream& stream, const Step step) {
	stream << AnimalSymbolStock[step.animal]
		<< char('a'-1+step.from_square%9)
		<< char('0'+9-step.from_square/9)
		<< step.direction ;
	if(step.prey>=0) {
		const int p =
			(step.from_square<32 && step.from_square!=24) || step.from_square==39 ? 30
			  : step.from_square<43 ? 33
			  : (step.from_square<59 && step.from_square!=51) || step.from_square==66 ? 57
			  : 60;
		stream << ' ' << AnimalSymbolStock[step.prey]
			<< char('a'-1+p%9)
			<< char('0'+9-p/9)
			<< 'x';
	}
	return stream;
}

bool Step::make() {
	if(board[from_square]!=animal+16 || board[to_square]!=0) return false;

	move_out(from_square,animal);
	move_in(to_square,animal);

	if((animal&24)==0) { // Gold Rabbit
		if(from_square<18) --goal_count[Gold];
		if(to_square<18) ++goal_count[Gold];
	}else if((animal&24)==16) { // Silver Rabbit
		if(from_square>72) --goal_count[Silver];
		if(to_square>72) ++goal_count[Silver];
	}

	// now remove any trapped animal
	if(((board[30]&48)==16 && neighbours[0][30]==0)
	|| ((board[30]&48)==32 && neighbours[1][30]==0)) {
		prey = board[30]-16;
		move_out(30,prey);
		++prey_count[prey/16];
		--population[prey/16];
	}else
	if(((board[33]&48)==16 && neighbours[0][33]==0)
	|| ((board[33]&48)==32 && neighbours[1][33]==0)) {
		prey = board[33]-16;
		move_out(33,prey);
		++prey_count[prey/16];
		--population[prey/16];
	}else
	if(((board[57]&48)==16 && neighbours[0][57]==0)
	|| ((board[57]&48)==32 && neighbours[1][57]==0)) {
		prey = board[57]-16;
		move_out(57,prey);
		++prey_count[prey/16];
		--population[prey/16];
	}else
	if(((board[60]&48)==16 && neighbours[0][60]==0)
	|| ((board[60]&48)==32 && neighbours[1][60]==0)) {
		prey = board[60]-16;
		move_out(60,prey);
		++prey_count[prey/16];
		--population[prey/16];
	}
	else prey = -1;
	return true;
}

void Step::undo() const {
	if(prey>=0) {
		++population[prey/16];
		--prey_count[prey/16];
		move_in(position[prey],prey);
	}

	if((animal&24)==0) { // Gold Rabbit
		if(from_square<18) ++goal_count[Gold];
		if(to_square<18) --goal_count[Gold];
	}else if((animal&24)==16) { // Silver Rabbit
		if(from_square>72) ++goal_count[Silver];
		if(to_square>72) --goal_count[Silver];
	}

	move_out(from_square+direction,animal);
	move_in(from_square,animal);
}

template<int color> bool Step::next() {
	const int opponent_mask = 32-color*16;
	const int lowest_animal = color*16;
	const Direction Up   = color? South: North;
	const Direction Down = -Up;

	if(is_pushed()) {
		do {
			if(inc<color^1>(direction)==Here) break;
			to_square = from_square+direction;
			if(board[to_square]==0) {
				return true; // ok, valid push
			}
		}while(true);
		return false;
	}
	if(is_pulled()) {
		do {
			if(inc<color^1>(direction)==Here) break;
			from_square = to_square-direction;
			if((board[from_square]&48)==opponent_mask
				&& species_on_board[from_square]<pulling_species) {
				animal = board[from_square]-16;
				pushed_foe = -1;
				return true; // ok, valid pull
			}
		}while(true);
		pulling_species = None;
		animal = lowest_animal+16;
		direction = Down; // so that inc(direction)==Here
	}
	do {
		do { // try another direction
			if(inc<color>(direction)==Here) break; // all directions explored, turn to another animal
			if(direction==Down && (animal&8)==0) break; // rabbits don't go down
			to_square = from_square+direction;
			if(board[to_square]==0) { // ok, the to_square is free
				pushed_foe = -1;
				return true;
			}
			if((board[to_square]&48)==opponent_mask
				&& species_on_board[to_square]<species[animal]) {
				pushed_foe = board[to_square]-16;
				return true; // watch out, the caller must delay that step and push before
			}
		}while(true);
		// try another animal
		do {
			if(--animal<lowest_animal) // no step left
				return false;
		}while(!living[animal] || frozen<color>(animal));
		from_square = position[animal];
		direction = Here;
	}while(true);
}

// -------------------------------------------------------------------

class Move {
public:
	Step step[4];
	int size; // number of steps
	double value;
	
	bool operator< (const Move& m2) const { return value < m2.value; };
	bool operator== (const Move& m2) const { return value == m2.value; };
	Move(): /* no_children(false), */ size(0), value(-1e50) {};
	template<int color> bool level_next(const int len);
	template<int color> bool next(const int len);
	template<int color> bool improving_much();
	void undo();
	bool make();
	friend ostream& operator<< (ostream& s, const Move m);
};

bool operator== (const Move& m1, const char * ms) {
	ostringstream ost;
	ost << m1;
	return ost.str() == ms;
}

ostream& operator<< (ostream& s, const Move m) {
	for(int i=0; i<m.size; i++) {
		if(i) s << ' ';
		if(m.step[i].is_pushing()) {
			s << m.step[i+1] << ' ' << m.step[i];
			++i;
		} else
			s << m.step[i];
	}
	return s;
}

template<int color> inline bool Move::improving_much() {
	return prey_count[color^1]>0 || goal_count[color]>0;
}

bool Move::make() {
	int i;
	for(i=0; i<size; i++) {
		if(!step[i].is_pushing()) if(!step[i].make()) break; // delay it if pushing a foe
		if(step[i].is_pushed()) if(!step[i-1].make()) {
			step[i].undo();
			break;
		}
	}
	if(i<size) {
		while(--i>=0) {
			if(step[i].is_pushed()) step[i-1].undo();
			if(!step[i].is_pushing()) step[i].undo();
		}
		return false;
	}
	return true;
}

void Move::undo() {
	while(size>0) {
		--size;
		// undo step[size]
		if(step[size].is_pushed()) step[size-1].undo(); // was delayed
		if(!step[size].is_pushing()) step[size].undo(); // delay it
	}
}

template<int color> bool Move::level_next(const int len) {
	if(size<len) {
		if(size>0 && step[size-1].is_pulled()==false && step[size-1].is_pushed()==false) {
			if(step[size-1].is_pushing())
lengthen_push:
				step[size].init_pushed(step[size-1].pushed_foe);
			else
				step[size].init_not_pushed(step[size-1].from_square,
					species[step[size-1].animal]);
		}else {
			step[size].init_nor_pulled<color>();
		}
	}
	else {
step_back:	// give up the parent
		if(--size<len-1) { ++size; return false; } // no next moves left
		// undo step[size]
		if(step[size].is_pushed()) {
			if(size<len) { ++size; return false; } // don't explore pushes at that level
			step[size-1].undo(); // was delayed
		}
		if(!step[size].is_pushing()) step[size].undo(); // delay it
	}
	do {	// get the next brother
		if(!step[size].next<color>()) goto step_back; // no brother left
	}while(size==3 && step[size].is_pushing()); // reject pushes on the last step
	
	// step forward
	if(!step[size].is_pushing()) step[size].make(); // delay it if pushing a foe
	if(step[size].is_pushed()) step[size-1].make(); // was delayed
	++size;
	
	if(step[size-1].is_pushing()) goto lengthen_push;
	
	return true;
}

template<int color> bool Move::next(const int len) {
	if(size<len /* && no_children==false */) {
		if(size>0 && step[size-1].is_pulled()==false && step[size-1].is_pushed()==false) {
			if(step[size-1].is_pushing())
lengthen_push:
				step[size].init_pushed(step[size-1].pushed_foe);
			else
				step[size].init_not_pushed(step[size-1].from_square,
					species[step[size-1].animal]);
		}else {
			step[size].init_nor_pulled<color>();
		}
	}
	else {
step_back:	// give up the parent
		if(--size<0) { ++size; return false; } // no next moves left
		// undo step[size]
		if(step[size].is_pushed()) step[size-1].undo(); // was delayed
		if(!step[size].is_pushing()) step[size].undo(); // delay it
	}
	do {	// get the next brother
		if(!step[size].next<color>()) goto step_back; // no brother left
	}while(size==len-1 && step[size].is_pushing()); // reject pushes on the last step
	
	// step forward
	if(!step[size].is_pushing()) step[size].make(); // delay it if pushing a foe
	if(step[size].is_pushed()) step[size-1].make(); // was delayed
	++size;
	
	if(step[size-1].is_pushing()) goto lengthen_push;
	
	return true;
}

// -------------------------------------------------------------------

int game_count;
enum End { Goal, OpposingGoal, NoMove, Repetition, TooLong };
End end_cause;
set<ulong> seen, twice;
Move recommended_move;

void init_globals()
{
	init_rand(rand_seed); // use this line to get reproducible 'random' results
//	init_rand(std::time(0)); // or use this to change the results
	init_hash();
}

void print_board() {
	for(int j=0; j<8; j++) {
		cout << endl;
		for(int i=0; i<8; i++) {
			if(board[j*9+10+i]>0)
				cout << AnimalSymbolStock[board[j*9+10+i]-16] << ' ';
			else cout << ". ";
		}
	}
}

void new_game() {
	ply_count = 0;
	active_side = Gold;
	fill(&board[0],&board[92],-1); // mark every square as being outside
	for(int p=10; p<81; ++p) if(p%9!=0) board[p] = 0;
	population[Gold] = population[Silver] = 0;
	fill(&living[0],&living[32],false);
	fill(&neighbours[0][0],&neighbours[2][0],0);
	goal_count[Gold] = goal_count[Silver] = 0;
	prey_count[Gold] = prey_count[Silver] = 0;
	winner = -1;
	last_hash_key = hash_key = 0;
	seen.clear();
	twice.clear();
}

bool game_over() {
	if(seen.insert(hash_key).second==false && twice.insert(hash_key).second==false) {
		winner = active_side; end_cause = Repetition;
	}
	else if(goal_count[active_side^1]>0) { winner = active_side^1; end_cause = Goal; }
	else if(goal_count[active_side]>0) { winner = active_side; end_cause = OpposingGoal; }
	else if(last_hash_key == hash_key) { winner = active_side; end_cause = NoMove; }
	else if(ply_count == 512) { winner = 2; end_cause = TooLong; }
	else {
		last_hash_key = hash_key;
		return false;
	}
	return true;
}

void play() {
	if(ply_count>=2) recommended_move.make();
	++ply_count;
	active_side ^= 1;
	if(prey_count[Silver]>0 || prey_count[Gold]>0) {
		seen.clear(); twice.clear(); // no position before can be repeated
		prey_count[Gold] = prey_count[Silver] = 0;
	}
}

// -------------------------------------------------------------------

inline int cube(const int x) { return x*x*x; }

double choice_size_sum, choice_size2_sum;
int min_choice_size = 10000000L, max_choice_size;
int choices_taken;

void random_completion() { // randomly fill in the two initial row to complete the first move
	for(int a = active_side*16+15; a>=active_side*16; --a) if(living[a]==false) {
		int p;
		do {
			p = (next_rand()&15);
			if(p>7) ++p;
			if(active_side == Gold) p = 80-p;
			else p += 10;
		}while(board[p]!=0);
		move_in(p,a);
		++population[active_side];
	}
}

Move ml[4][16384];

void Moving_pS_mS() {
	if(ply_count<2) {
		for(int a = 7; a>=0; --a) { // fill in the 2nd row with rabbits
			int p = a+19; // second row
			if(active_side == Gold) p = 90-p;
			move_in(p,a+active_side*16);
			++population[active_side];
		}
		random_completion();
		return;
	}
	ulong move_hash[16384] = {0};
	int mlsize[4] = {0};
	Move m;
	int n = 0;
	int max_value = -0x7fffffffL;

	recommended_move = m;
	ml[0][mlsize[0]++] = m; // start with the empty move
	hash_insert(move_hash,hash_key); // no null move

	for(int len=1; len<=4; len++) {
		for(int i=mlsize[len-1]; --i>=0; ) {
			m = ml[len-1][i];
			if(m.size==len) {
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
				continue;
			}

			m.make();
			while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
				if(hash_find(move_hash,hash_key)) continue;

				int Goldscore = 0, P = 0, C = 0;
				for(int a = 15; a>=0; --a) if(living[a]) {
					P += species[a];
					if(a<8) { Goldscore += cube(9-position[a]/9); ++C; }
				}
				Goldscore += P*(C+1);
				int Silverscore = P = C = 0;
				for(int a = 31; a>=16; --a) if(living[a]) {
					P += species[a];
					if(a<24) { Silverscore += cube(position[a]/9); ++C; }
				}
				Silverscore += P*(C+1);
				const int value = active_side==Gold? Goldscore*65536L-Silverscore:
					Silverscore*65536L-Goldscore;
					
				if(value>=max_value) {
					if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
					else if(next_rand()%(++n)==0) {	recommended_move = m; }
				}

				hash_insert(move_hash,hash_key);
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
			}
			m.undo();
		}
	}
	if(n>max_choice_size) max_choice_size = n;
	if(n<min_choice_size) min_choice_size = n;
	choice_size_sum += n;
	choice_size2_sum += double(n)*n;
	choices_taken++;
}

void Moving_pF_mF() {
	if(ply_count<2) {
		for(int a = 7; a>=0; --a) { // fill in the 2nd row with rabbits
			int p = a+19; // second row
			if(active_side == Gold) p = 90-p;
			move_in(p,a+active_side*16);
			++population[active_side];
		}
		random_completion();
		return;
	}
	ulong move_hash[16384] = {0};
	int mlsize[4] = {0};
	Move m;
	int n = 0;
	int max_value = -0x7fffffffL;
	int max_value2= -0x7fffffffL;

	recommended_move = m;
	ml[0][mlsize[0]++] = m; // start with the empty move
	hash_insert(move_hash,hash_key); // no null move

	for(int len=1; len<=4; len++) {
		for(int i=mlsize[len-1]; --i>=0; ) {
			m = ml[len-1][i];
			if(m.size==len) {
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
				continue;
			}

			m.make();

			while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
				if(hash_find(move_hash,hash_key)) continue;

				int Goldadvance = 0;
				for(int a = 7; a>=0; --a) if(living[a]) {
					Goldadvance += (1L)<<(3*(8-position[a]/9));
				}
				int Silveradvance = 0;
				for(int a = 16+7; a>=16; --a) if(living[a]) {
					Silveradvance += (1L)<<(3*(position[a]/9-1));
				}
				const int value = active_side==Gold? Goldadvance: Silveradvance;
				const int value2= active_side==Gold? -Silveradvance: -Goldadvance;
				if(value>max_value || (value==max_value && value2>=max_value2)) {
					if(value>max_value || value2>max_value2) {
						n = 1; max_value = value; max_value2 = value2; recommended_move = m;
					}
					else if(next_rand()%(++n)==0) {	recommended_move = m; }
				}

				hash_insert(move_hash,hash_key);
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
			}
			m.undo();
		}
	}
	if(n>max_choice_size) max_choice_size = n;
	if(n<min_choice_size) min_choice_size = n;
	choice_size_sum += n;
	choice_size2_sum += double(n)*n;
	choices_taken++;
}

void Moving_pmF() {
	if(ply_count<2) {
		for(int a = 7; a>=0; --a) { // fill in the 2nd row with rabbits
			int p = a+19; // second row
			if(active_side == Gold) p = 90-p;
			move_in(p,a+active_side*16);
			++population[active_side];
		}
		random_completion();
		return;
	}
	ulong move_hash[16384] = {0};
	int mlsize[4] = {0};
	Move m;
	int n = 0;
	int max_value = -0x7fffffffL;

	recommended_move = m;
	ml[0][mlsize[0]++] = m; // start with the empty move
	hash_insert(move_hash,hash_key); // no null move

	for(int len=1; len<=4; len++) {
		for(int i=mlsize[len-1]; --i>=0; ) {
			m = ml[len-1][i];
			if(m.size==len) {
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
				continue;
			}

			m.make();
			while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
				if(hash_find(move_hash,hash_key)) continue;

				int Goldadvance = 0;
				for(int a = 7; a>=0; --a) if(living[a]) {
					Goldadvance += (1L)<<(3*(8-position[a]/9));
				}
				int Silveradvance = 0;
				for(int a = 16+7; a>=16; --a) if(living[a]) {
					Silveradvance += (1L)<<(3*(position[a]/9-1));
				}
				const int value = active_side==Gold? Goldadvance-Silveradvance:
					Silveradvance-Goldadvance;
					
				if(value>=max_value) {
					if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
					else if(next_rand()%(++n)==0) {	recommended_move = m; }
				}

				hash_insert(move_hash,hash_key);
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
			}
			m.undo();
		}
	}
	if(n>max_choice_size) max_choice_size = n;
	if(n<min_choice_size) min_choice_size = n;
	choice_size_sum += n;
	choice_size2_sum += double(n)*n;
	choices_taken++;
}

void Moving_pI_mI() {
	if(ply_count<2) {
		const int a = active_side*16; // a rabbit
		int p = (next_rand()&7)+9; // second row
		if(active_side == Gold) p = 80-p;
		else p += 10;
		move_in(p,a);
		++population[active_side];
		random_completion();
		return;
	}
	ulong move_hash[16384] = {0};
	int mlsize[4] = {0};
	Move m;
	int n = 0;
	int max_value = -20000;

	recommended_move = m;
	ml[0][mlsize[0]++] = m; // start with the empty move
	hash_insert(move_hash,hash_key); // no null move

	for(int len=1; len<=4; len++) {
		for(int i=mlsize[len-1]; --i>=0; ) {
			m = ml[len-1][i];
			if(m.size==len) {
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
				continue;
			}

			m.make();
			while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
				if(hash_find(move_hash,hash_key)) continue;

				int maxGoldheight = 0;
				for(int a = 7; a>=0; --a) if(living[a]) {
					if(9-position[a]/9>maxGoldheight) maxGoldheight = 9-position[a]/9;
				}
				int maxSilverheight = 0;
				for(int a = 16+7; a>=16; --a) if(living[a]) {
					if(position[a]/9>maxSilverheight) maxSilverheight = position[a]/9;
				}
				const int value = active_side==Gold? 16*maxGoldheight-maxSilverheight:
					16*maxSilverheight-maxGoldheight;
				if(value>=max_value) {
					if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
					else if(next_rand()%(++n)==0) {	recommended_move = m; }
				}

				hash_insert(move_hash,hash_key);
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
			}
			m.undo();
		}
	}
	if(n>max_choice_size) max_choice_size = n;
	if(n<min_choice_size) min_choice_size = n;
	choice_size_sum += n;
	choice_size2_sum += double(n)*n;
	choices_taken++;
}

void Moving_pI() {
	if(ply_count<2) {
		const int a = active_side*16; // a rabbit
		int p = (next_rand()&7)+9; // second row
		if(active_side == Gold) p = 80-p;
		else p += 10;
		move_in(p,a);
		++population[active_side];
		random_completion();
		return;
	}
	ulong move_hash[16384] = {0};
	int mlsize[4] = {0};
	Move m;
	int n = 0;
	int max_value = -20000;

	recommended_move = m;
	ml[0][mlsize[0]++] = m; // start with the empty move
	hash_insert(move_hash,hash_key); // no null move

	for(int len=1; len<=4; len++) {
		for(int i=mlsize[len-1]; --i>=0; ) {
			m = ml[len-1][i];
			if(m.size==len) {
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
				continue;
			}

			m.make();
			while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
				if(hash_find(move_hash,hash_key)) continue;

				int value = -10000;
				for(int a = active_side*16+7; a>=active_side*16; --a) if(living[a]) {
					const int height = active_side? position[a]/9: -position[a]/9;
					if(height>value) value = height;
				}
				if(value>=max_value) {
					if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
					else if(next_rand()%(++n)==0) {	recommended_move = m; }
				}

				hash_insert(move_hash,hash_key);
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
			}
			m.undo();
		}
	}
	if(n>max_choice_size) max_choice_size = n;
	if(n<min_choice_size) min_choice_size = n;
	choice_size_sum += n;
	choice_size2_sum += double(n)*n;
	choices_taken++;
}

void Mover() {
	if(ply_count<2) {
		random_completion();
		return;
	}
	ulong move_hash[16384] = {0};
	int mlsize[4] = {0};
	Move m;
	int n = 0;

	recommended_move = m;
	ml[0][mlsize[0]++] = m; // start with the empty move
	hash_insert(move_hash,hash_key); // no null move

	for(int len=1; len<=4; len++) {
		for(int i=mlsize[len-1]; --i>=0; ) {
			m = ml[len-1][i];
			if(m.size==len) {
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
				continue;
			}

			m.make();
			while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
				if(hash_find(move_hash,hash_key)) continue;
	
				if(next_rand()%(++n)==0) {
					recommended_move = m;
				}

				hash_insert(move_hash,hash_key);
				if(len<4) {
					if(mlsize[len]==16384) { cout << '!'; return; }
					ml[len][mlsize[len]++] = m;
				}
			}
			m.undo();
		}
	}
	if(n>max_choice_size) max_choice_size = n;
	if(n<min_choice_size) min_choice_size = n;
	choice_size_sum += n;
	choice_size2_sum += double(n)*n;
	choices_taken++;
}

void Stepping_pS_mS() { // Score = R + P*(C+1)
	if(ply_count<2) {
		for(int a = 7; a>=0; --a) { // fill in the 2nd row with rabbits
			int p = a+19; // second row
			if(active_side == Gold) p = 90-p;
			move_in(p,a+active_side*16);
			++population[active_side];
		}
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7fffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;

			int Goldscore = 0, P = 0, C = 0;
			for(int a = 15; a>=0; --a) if(living[a]) {
				P += species[a];
				if(a<8) { Goldscore += cube(9-position[a]/9); ++C; }
			}
			Goldscore += P*(C+1);
			int Silverscore = P = C = 0;
			for(int a = 31; a>=16; --a) if(living[a]) {
				P += species[a];
				if(a<24) { Silverscore += cube(position[a]/9); ++C; }
			}
			Silverscore += P*(C+1);
			const int value = active_side==Gold? Goldscore*65536L-Silverscore:
				Silverscore*65536L-Goldscore;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pmS() { // Score = R + P*(C+1)
	if(ply_count<2) {
		for(int a = 7; a>=0; --a) { // fill in the 2nd row with rabbits
			int p = a+19; // second row
			if(active_side == Gold) p = 90-p;
			move_in(p,a+active_side*16);
			++population[active_side];
		}
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7fffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;

			int Goldscore = 0, P = 0, C = 0;
			for(int a = 15; a>=0; --a) if(living[a]) {
				P += species[a];
				if(a<8) { Goldscore += cube(9-position[a]/9); ++C; }
			}
			Goldscore += P*(C+1);
			int Silverscore = P = C = 0;
			for(int a = 31; a>=16; --a) if(living[a]) {
				P += species[a];
				if(a<24) { Silverscore += cube(position[a]/9); ++C; }
			}
			Silverscore += P*(C+1);
			const int value = active_side==Gold? Goldscore-Silverscore:
				Silverscore-Goldscore;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pF_mF() { // Flooder
	if(ply_count<2) {
		for(int a = 7; a>=0; --a) { // fill in the 2nd row with rabbits
			int p = a+19; // second row
			if(active_side == Gold) p = 90-p;
			move_in(p,a+active_side*16);
			++population[active_side];
		}
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7fffffffL;
		int max_value2= -0x7fffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			int Goldadvance = 0;
			for(int a = 7; a>=0; --a) if(living[a]) {
				Goldadvance += (1L)<<(3*(8-position[a]/9));
			}
			int Silveradvance = 0;
			for(int a = 16+7; a>=16; --a) if(living[a]) {
				Silveradvance += (1L)<<(3*(position[a]/9-1));
			}
			const int value = active_side==Gold? Goldadvance: Silveradvance;
			const int value2= active_side==Gold? -Silveradvance: -Goldadvance;
			if(value>max_value || (value==max_value && value2>=max_value2)) {
				if(value>max_value || value2>max_value2) {
					n = 1; max_value = value; max_value2 = value2; recommended_move = m;
				}
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pmF() { // Flooder
	if(ply_count<2) {
		for(int a = 7; a>=0; --a) { // fill in the 2nd row with rabbits
			int p = a+19; // second row
			if(active_side == Gold) p = 90-p;
			move_in(p,a+active_side*16);
			++population[active_side];
		}
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7fffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			int Goldadvance = 0;
			for(int a = 7; a>=0; --a) if(living[a]) {
				Goldadvance += (1L)<<(3*(8-position[a]/9));
			}
			int Silveradvance = 0;
			for(int a = 16+7; a>=16; --a) if(living[a]) {
				Silveradvance += (1L)<<(3*(position[a]/9-1));
			}
			const int value = active_side==Gold? Goldadvance-Silveradvance:
				Silveradvance-Goldadvance;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pmK_mF() { // = Stepping +-Killer -Flooder
	if(ply_count<2) {
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7fffffffL;
		int max_value2= -0x7fffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;

			int Goldadvance = 0;
			for(int a = 7; a>=0; --a) if(living[a]) {
				Goldadvance += (1L)<<(3*(8-position[a]/9));
			}
			int Silveradvance = 0;
			for(int a = 16+7; a>=16; --a) if(living[a]) {
				Silveradvance += (1L)<<(3*(position[a]/9-1));
			}
			const int value2 = active_side==Gold? -Silveradvance:
				-Goldadvance;
			const int value = population[active_side]-population[active_side^1];

			if(value>max_value || (value==max_value && value2>=max_value2)) {
				if(value>max_value || value2>max_value2) {
					n = 1; max_value = value; max_value2 = value2; recommended_move = m;
				}
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pmK_pmF() { // = Stepping +-Killer +-Flooder
	if(ply_count<2) {
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7fffffffL;
		int max_value2= -0x7fffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;

			int Goldadvance = 0;
			for(int a = 7; a>=0; --a) if(living[a]) {
				Goldadvance += (1L)<<(3*(8-position[a]/9));
			}
			int Silveradvance = 0;
			for(int a = 16+7; a>=16; --a) if(living[a]) {
				Silveradvance += (1L)<<(3*(position[a]/9-1));
			}
			const int value2 = active_side==Gold? Goldadvance-Silveradvance:
				Silveradvance-Goldadvance;
			const int value = population[active_side]-population[active_side^1];

			if(value>max_value || (value==max_value && value2>=max_value2)) {
				if(value>max_value || value2>max_value2) {
					n = 1; max_value = value; max_value2 = value2; recommended_move = m;
				}
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pK_mK() { // = Stepping +Killer -Killer
	if(ply_count<2) {
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7ffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			const int value = population[active_side]*65536L-population[active_side^1];
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}


void Stepping_pmK() { // = Stepping Attacking-Defending Killer
	if(ply_count<2) {
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7ffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			const int value = population[active_side]-population[active_side^1];
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pI_mI() {
	if(ply_count<2) {
		const int a = active_side*16; // a rabbit
		int p = (next_rand()&7)+9; // second row
		if(active_side == Gold) p = 80-p;
		else p += 10;
		move_in(p,a);
		++population[active_side];
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -0x7ffffffL;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			int maxGoldheight = 0;
			for(int a = 7; a>=0; --a) if(living[a]) {
				if(9-position[a]/9>maxGoldheight) maxGoldheight = 9-position[a]/9;
			}
			int maxSilverheight = 0;
			for(int a = 16+7; a>=16; --a) if(living[a]) {
				if(position[a]/9>maxSilverheight) maxSilverheight = position[a]/9;
			}
			const int value = active_side==Gold? 16*maxGoldheight-maxSilverheight:
				16*maxSilverheight-maxGoldheight;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_mI_pI() {
	if(ply_count<2) {
		const int a = active_side*16; // a rabbit
		int p = (next_rand()&7)+9; // second row
		if(active_side == Gold) p = 80-p;
		else p += 10;
		move_in(p,a);
		++population[active_side];
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -20000;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			int maxGoldheight = 0;
			for(int a = 7; a>=0; --a) if(living[a]) {
				if(9-position[a]/9>maxGoldheight) maxGoldheight = 9-position[a]/9;
			}
			int maxSilverheight = 0;
			for(int a = 16+7; a>=16; --a) if(living[a]) {
				if(position[a]/9>maxSilverheight) maxSilverheight = position[a]/9;
			}
			const int value = active_side==Gold? maxGoldheight-16*maxSilverheight:
				maxSilverheight-16*maxGoldheight;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pmInfiltrator() {
	if(ply_count<2) {
		const int a = active_side*16; // a rabbit
		int p = (next_rand()&7)+9; // second row
		if(active_side == Gold) p = 80-p;
		else p += 10;
		move_in(p,a);
		++population[active_side];
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -20000;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			int maxGoldheight = 0;
			for(int a = 7; a>=0; --a) if(living[a]) {
				if(9-position[a]/9>maxGoldheight) maxGoldheight = 9-position[a]/9;
			}
			int maxSilverheight = 0;
			for(int a = 16+7; a>=16; --a) if(living[a]) {
				if(position[a]/9>maxSilverheight) maxSilverheight = position[a]/9;
			}
			const int value = active_side==Gold? maxGoldheight-maxSilverheight:
				maxSilverheight-maxGoldheight;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_Defending_Infiltrator() {
	if(ply_count<2) {
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -10000;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			int value = -10000;
			for(int a = (active_side^1)*16+7; a>=(active_side^1)*16; --a) if(living[a]) {
				const int height = active_side? -position[a]/9: position[a]/9;
				if(height>value) value = height;
			}
			value = -value;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_pI() { // = attacking Infiltrator
	if(ply_count<2) {
		const int a = active_side*16; // a rabbit
		int p = (next_rand()&7)+9; // second row
		if(active_side == Gold) p = 80-p;
		else p += 10;
		move_in(p,a);
		++population[active_side];
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -10000;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			int value = -10000;
			for(int a = active_side*16+7; a>=active_side*16; --a) if(living[a]) {
				const int height = active_side? position[a]/9: -position[a]/9;
				if(height>value) value = height;
			}
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepping_UltimateLookout() {
	if(ply_count<2) {
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size!=len-1) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		int max_value = -10000;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;

			int value = -10000;
			if(goal_count[active_side^1]==0) {
				value = 0;
				if(goal_count[active_side]>0)
					value = 10000;
			}
			else if(len>1) continue;
			if(value>=max_value) {
				if(value>max_value) { n = 1; max_value = value; recommended_move = m; }
				else if(next_rand()%(++n)==0) {	recommended_move = m; }
			}
		}
		m.undo();
	}
}

void Stepper() {
	if(ply_count<2) {
		random_completion();
		return;
	}
	Move m;
	int n;
	recommended_move = m;
	for(int len=1; len<=4; len++) {
		if(recommended_move.size==len) { continue; }
		m = recommended_move;
		m.make();
		n = 0;
		while(active_side==Gold? m.level_next<Gold>(len): m.level_next<Silver>(len)) {
			if(m.size==4 && hash_key==last_hash_key) continue;
			if(next_rand()%(++n)==0) {
				recommended_move = m;
			}
		}
		m.undo();
	}
}

// -------------------------------------------------------------------

int cause[5];
int side[3];
int length[512];
int minlength = 10000, maxlength, lengthsum, length2sum;
int player[4];

void collect() {
	++length[ply_count-1];
	if(ply_count>maxlength) maxlength = ply_count;
	if(ply_count<minlength) minlength = ply_count;
	lengthsum += ply_count;
	length2sum += ply_count*ply_count;
	++cause[end_cause];
	++side[winner];
	++player[winner^(game_count&1)];
	//if(end_cause==OpposingGoal) cout << ' ' << game_count << '!';
}

void show_data() {
	cout << game_count << " games in "
		<< (clock()/CLOCKS_PER_SEC)
		<< " s.  Player1: " << player[0]
		<< " ,  Player2: " << player[1] << endl;

	cout << "Gold: " << side[Gold]
		<< " ,  Silver: " << side[Silver]
		<< " ,  none: " << side[2] << endl;

	cout << "Goal: " << cause[Goal]
		<< " ,  OpposingGoal: " << cause[OpposingGoal]
		<< " ,  NoMove: " << cause[NoMove]
		<< " ,  Repetition: " << cause[Repetition]
		<< " ,  TooLong: " << cause[TooLong] << endl;

//	for(ply_count=0; ply_count<512; ++ply_count)
//		cout << length[ply_count] << ' ';

	const double m = double(lengthsum)/game_count;
	const double m2 = double(length2sum)/game_count;
	cout << minlength << " <= mean length = " << m
		<< ", sd = " << sqrt(m2 - m*m)
		<< " <= " << maxlength << endl;

	if(choices_taken) {
		const double m = double(choice_size_sum)/choices_taken;
		const double m2 = double(choice_size2_sum)/choices_taken;
		cout << min_choice_size
			<< " <= " << "mean choice size = " << m
			<< ", sd = " << sqrt(m2-m*m)
			<< " <= " << max_choice_size << endl;
	}
}

// -------------------------------------------------------------------

int main() {
	init_globals();
	for(game_count = 0; game_count < 100000; ) {
		new_game();
		do {
			//cout << '(' << seen.size() << ',' << twice.size() << ") ";
			if((ply_count&1)==(game_count&1)) Player1;
			else Player2;
			play(); // play the recommended move
			//if(game_count==352)
			//{ cout << endl << recommended_move << endl; print_board(); cin.get(); }
		} while(!game_over());
		collect(); // collect statistics about the game
		++game_count;
		//cout << game_count << ' ';
		if(game_count%Silence==0) show_data();
	}

	return 0;
}