#include <iostream>
#include <map>
#include <functional>
#include <string>
#include <ctime>
using namespace std;
#include "Matrix.h"

// print number of moves considered and time used and calculate first move
#define ANALYSE

class TicTacToe {
public:
	enum Side {EMPTY, HUMAN, COMPUTER};
	typedef matrix<Side> Board;
	typedef Board::row_index row_index;
	typedef Board::column_index column_index;
	enum PositionVal {HUMAN_WIN=-1, DRAW, COMPUTER_WIN, UNCLEAR};

	class Position {
	public:
		Position(const Board& theBoard): board(theBoard) {
		}
		bool operator<(const Position& rhs) const;
	private:
		Board board;
	};

	typedef map<Position, PositionVal> MapType;
	typedef MapType::const_iterator MapItr;

	TicTacToe(): board(3, 3)
	#ifdef ANALYSE
	, movesConsidered(0)
	#endif
	{
		clearBoard();
	}
	PositionVal chooseMove(Side d, row_index& bestRow, column_index& bestColumn,
		PositionVal alpha=HUMAN_WIN, PositionVal beta=COMPUTER_WIN, int depth=0);
	bool playMove(Side s, row_index row, column_index column);
	void clearBoard();
	void getMove();
	bool boardIsFull() const;
	bool isAWin(Side s) const;
	const Board& getBoard() const {
		return board;
	}
	void clearTrans() {
		transpositions.clear();
	}
	#ifdef ANALYSE
	int getTransSize() const {
		return transpositions.size();
	}
	int getAndResetMovesConsidered() {
		int i(movesConsidered);
		movesConsidered=0;
		return i;
	}
	#endif
private:
	MapType transpositions;
	Board board;
	void place(row_index row, column_index column, Side piece=EMPTY) {
		board[row][column]=piece;
	}
	bool squareIsEmpty(row_index row, column_index column) const {
		return board[row][column]==EMPTY;
	}
	PositionVal positionValue() const;
	#ifdef ANALYSE
	int movesConsidered;
	#endif
};

#ifdef ANALYSE
class StopWatch {
public:
	StopWatch();
	void start();
	void stop();
	void reset();
private:
	bool running;
	clock_t start_time;
	clock_t total_time;
friend ostream& operator<<(ostream& o, const StopWatch& sw);
};
#endif

TicTacToe::PositionVal TicTacToe::positionValue() const {
	 return isAWin(COMPUTER) ? COMPUTER_WIN :
			  isAWin(HUMAN) ? HUMAN_WIN :
			  boardIsFull() ? DRAW :
			  UNCLEAR;
}

TicTacToe::PositionVal TicTacToe::chooseMove(Side s, row_index& bestRow, column_index& bestColumn,
					     PositionVal alpha, PositionVal beta, int depth) {
#ifdef ANALYSE
	++movesConsidered;
#endif
	static const int MAX_TABLE_DEPTH(5);
	Position thisPosition(board);
	if (depth>=3 && depth<=MAX_TABLE_DEPTH) {
		MapItr itr(transpositions.find(thisPosition));
		if (itr!=transpositions.end())
			return (*itr).second;
	}
	Side opp(s==COMPUTER ? HUMAN : COMPUTER);
	PositionVal simpleEval(positionValue());
	if (simpleEval!=UNCLEAR)
		return simpleEval;
	PositionVal bestValue(s==COMPUTER ? alpha : beta);
	for (row_index row(0); alpha<beta && row<board.numrows(); ++row)
		for (column_index column(0); alpha<beta && column<board.numcols(); ++column)
			if (squareIsEmpty(row, column)) {
				place(row, column, s);
				row_index dr;
				column_index dc;
				PositionVal reply(chooseMove(opp, dr, dc, alpha, beta, depth+1));
				place(row, column, EMPTY);
				if (s==COMPUTER && reply>bestValue || s==HUMAN && reply<bestValue) {
					bestValue=reply;
					if (s==COMPUTER)
						alpha=bestValue;
					else
						beta=bestValue;
					bestRow=row;
					bestColumn=column;
				}
			}
	if (depth>=3 && depth<=MAX_TABLE_DEPTH)
		transpositions[thisPosition]=bestValue;
	return bestValue;
}

bool TicTacToe::playMove(Side s, row_index row, column_index column) {
	if (row<0 || row>=board.numrows() || column<0 || column>=board.numcols()
		|| board[row][column]!=EMPTY)
		return false;
	board[row][column]=s;
	return true;
}

void TicTacToe::clearBoard() {
	for (row_index row(0); row<board.numrows(); ++row)
		for (column_index column(0); column<board.numcols(); ++column)
			board[row][column]=EMPTY;
}

bool TicTacToe::boardIsFull() const {
	for (row_index row(0); row<board.numrows(); ++row)
		for (column_index column(0); column<board.numcols(); ++column)
			if (board[row][column]==EMPTY)
				return false;
	return true;
}

bool TicTacToe::isAWin(Side s) const {
	row_index row;
	column_index column;
	for (row=0; row<board.numrows(); ++row) {
		bool iswin(true);
		for (column=0; column<board.numcols(); ++column)
			iswin=(iswin && board[row][column]==s);
		if (iswin)
			return true;
	}
	for (column=0; column<board.numcols(); ++column) {
		bool iswin(true);
		for (row=0; row<board.numrows(); ++row)
			iswin=(iswin && board[row][column]==s);
		if (iswin)
			return true;
	}
	bool iswin(true);
	for (row=0, column=0; row<board.numrows() && column<board.numcols(); ++row, ++column)
		iswin=(iswin && board[row][column]==s);
	if (iswin)
		return true;
	iswin=true;
	for (row=0, column=board.numcols()-1; row<board.numrows() && column>=0; ++row, --column)
		iswin=(iswin && board[row][column]==s);
	return iswin;
}

bool TicTacToe::Position::operator<(const Position & rhs) const {
	for (row_index i(0); i<board.numrows(); ++i)
		for (column_index j(0); j<board.numcols(); ++j)
			if (board[i][j]!=rhs.board[i][j])
				return board[i][j]<rhs.board[i][j];
	return false;
}

void printBoard(const TicTacToe& obj, char compSide, char humanSide) {
	const TicTacToe::Board& b(obj.getBoard());
	string streep(b.numcols(), '-');
	cout<<streep<<endl;
	for (TicTacToe::row_index row(0); row<b.numrows(); ++row) {
		for (TicTacToe::column_index column(0); column<b.numcols(); ++column)
			if (b[row][column]==TicTacToe::COMPUTER)
				cout<<compSide;
			else if (b[row][column]==TicTacToe::HUMAN)
				cout<<humanSide;
			else
				cout<<' ';
		cout<<endl;
	}
	cout<<streep<<endl;
}

void doCompMove(TicTacToe& t, bool firstMove) {
	TicTacToe::row_index bestRow;
	TicTacToe::column_index bestCol;
#ifndef ANALYSE
	static int gameNum(0);
	if (!firstMove)
#else
	StopWatch sw;
	sw.start();
#endif
		t.clearTrans();
		t.chooseMove(TicTacToe::COMPUTER, bestRow, bestCol);
#ifndef ANALYSE
	else {
		++gameNum;
		bestRow=gameNum%3;
		bestCol=(gameNum/3)%3;
	}
#else
	sw.stop();
	cout<<"Tijdsduur: "<<sw<<endl;
	cout<<"Transposition table size is: "<<t.getTransSize()<<endl;
	cout<<"Moves considered: "<<t.getAndResetMovesConsidered()<<endl;
#endif
	cout<<"Computer plays: ROW = "<<bestRow<<" COL = "<<bestCol<<endl;
	t.playMove(TicTacToe::COMPUTER, bestRow, bestCol);
}

void playGame(bool compGoesFirst) {
	TicTacToe t;
	char compSide(compGoesFirst ? 'x' : 'o');
	char humanSide(compGoesFirst ? 'o' : 'x');
	if (compGoesFirst)
		doCompMove(t, true);
	while (!t.boardIsFull()) {
		TicTacToe::row_index row;
		TicTacToe::column_index col;
		do {
			printBoard(t, compSide, humanSide);
			cout<<endl<<"Enter row and col (starts at 0): ";
			cin>>row>>col;
		} while (!t.playMove(TicTacToe::HUMAN, row, col));
		cout<<endl;
		printBoard(t, compSide, humanSide);
		cout<<endl;
		if (t.isAWin(TicTacToe::HUMAN)) {
			cout<<"Human wins!!"<<endl;
			break;
		}
		if (t.boardIsFull()) {
			cout<<"Draw!!"<<endl;
			break;
		}
		doCompMove(t, false);
		if (t.isAWin(TicTacToe::COMPUTER)) {
			cout<<"Computer wins!!"<<endl;
			break;
		}
		if (t.boardIsFull()) {
			cout<<"Draw!!"<<endl;
			break;
		}
	}
	printBoard(t, compSide, humanSide);
}

#ifdef ANALYSE
StopWatch::StopWatch(): running(false), total_time(0) {
}

void StopWatch::start() {
	if (!running) {
		running=true;
		start_time=clock();
	}
}

void StopWatch::stop() {
	if (running) {
		running=false;
		total_time+=clock()-start_time;
	}
}

void StopWatch::reset() {
	total_time=0;
	if (running) {
		start_time=clock();
	}
}

ostream& operator<<(ostream& o, const StopWatch& sw) {
	clock_t res(sw.running?clock()-sw.start_time:sw.total_time);
	return o<<static_cast<double>(res)/CLK_TCK<<" sec";
}
#endif

int main() {
	bool compGoesFirst(true);
	cout<<"Welcome to TIC-TAC-TOE"<<endl;
	while (true)	{
		playGame(compGoesFirst);
		cout<<"Play again (y/n)? ";
		char again;
		cin >> again;
		if (again=='n')
			break;
		compGoesFirst=!compGoesFirst;
	}
	return 0;
}