/*

    File: tictactoe.cpp

    Copyright (C) 2000-2008 Christopher Moore (christopher.e.moore@gmail.com)
	  
    This software 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 the Free Software Foundation, Inc., 51
    Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <assert.h>

/*
plus one to all the states tracing back from X win to start 
minus one for an O win
*/

//the # of states is 3^(3*3) = 3^9
int scores[3*3*3*3*3*3*3*3*3];

int ipow(int x,int y) {
	int z = 1;
	for (int i = 0; i < y; i++) z *= x;
	return z;
}

int getplace(int state, int place) {
	return (state / ipow(3,place)) % 3;
}

//returns the new state
int setplace(int state, int place, int team) {
	assert(!getplace(state,place));
	return state + ipow(3,place) * team;
}

//returns a free place to play at the given state
int freeplace(int state) {
	for(;;) {
		int place = rand() % 9;
		if (!getplace(state,place)) return place;
	}
}

#define numberof(x)	(sizeof(x)/sizeof(*(x)))

//this one is tough.  try for all 3 in a rows
int getwinner(int state) {
	static int wins[][3] = {
		{0,1,2}, {3,4,5}, {6,7,8},	//leftright
		{0,3,6}, {1,4,7}, {2,5,8},	//updown
		{0,4,8}, {2,4,6}		//diagonal
	};
	for (int team = 1; team <= 2; team++) {
		for (int i = 0; i < numberof(wins); i++) {
			int num = 0;
			for (int j = 0; j < 3; j++) {
				num += getplace(state, wins[i][j]) == team;
			}
			if (num == 3) return team;
		}
	}
	return 0;
}

//convert from team to score
int getscore(int team) {
	switch (team) {
	case 0: return 0;
	case 1: return 1;
	case 2: return -1;
	default: assert(false);
	}
}

int placeat(int i, int j) { return i + 3 * j; }

int printstate(int state) {
	for (int j = 0; j < 3; j++) {
		for (int i = 0; i < 3; i++) {
			int team = getplace(state, placeat(i,j));
			printf("%c ", team == 0 ? '.' : (team == 1 ? 'X' : 'O'));
		}
		printf("\n");
	}
	printf("\n");
}

//x always goes first
// indicies go 0=none, 1=X, 2=O
void rungame() {
	int state = 0;	//index to the score array.  
	int trace[9];
	int winner = 0;
	int turn = 0;
	for (; turn < 9; turn++) {
		int team = (turn & 1) + 1;	//0 = x, 1 = o
		int place = freeplace(state);	//place to play
		state = setplace(state,place,team); 	//set it
		trace[turn] = state;	//keep track of the state at this turn 
		winner = getwinner(state);
		if (winner) break;
	}
	//convert from 0,1,2 to 0,-1,1
	int score = getscore(winner);
	if (turn == 9) turn--;
	for (; turn >= 0; turn--) {
		scores[trace[turn]] += score;
	}
}

int main(int argc, char **argv) {
	memset(scores, 0, sizeof(scores));

	int max = 100;
	if (argc > 1) max = atoi(argv[1]);
	for (int iter = 0; iter < max; iter++) {
		rungame();
		printf("%d", iter);
		int sum = 0;
		for (int j = 0; j < 9; j++) sum += abs(scores[setplace(0,j,1)]);
		if (!sum) sum++;
		for (int j = 0; j < 3; j++) {
			for (int i = 0; i < 3; i++) {
				printf("\t%f", (double)scores[setplace(0,placeat(i,j),1)]/(double)sum);
			}
		}
		printf("\n");
	}
}