#include <iostream>
#include <string>
using namespace std;

class Board {
	int boardstate[9];		// describes the state of the board
	int boardhistory[9];		// note: 0 is a board position, so 9 is 'no event'
	
	public:
	Board() { for(int i = 0; i < 9; i++) { boardstate[i] = 0; boardhistory[i] = 9; } }
	void reset() { for(int i = 0; i < 9; i++) { boardstate[i] = 0; boardhistory[i] = 9; } }
	void draw();
	int history(int index) { if (index >= 0 && index < 9) { return boardhistory[index]; } else { return 9; } }
	int last();
	int state(int coord) { if (coord >= 0 && coord < 9) { return boardstate[coord]; } else {return 0; } }
	void change(int player, int coord) { boardstate[coord] = player; boardhistory[this->last() + 1] = coord; }
	bool wouldwin(int, int);
	int endgame();
	void undo();
};

class Player {
	bool is_ai;
	int player_num, player_score;
	
	public:
	Player(int n): player_num(n), player_score(0), is_ai(false) {}
	int score() { return player_score; }
	void won();
	void set_ai(bool ai) { is_ai = ai; }
	void go(Board&);		// ask for valid move, perform move
};

inline char mark(int num) {
	switch (num) {
		case 1: return 'X'; break;
		case 2: return 'O'; break;
		default: return ' '; break;
	}
}

int main() {
	Board board;
	Player player1(1), player2(2);
	bool again = true;
	string play_again;
	int games = 1;
	
	do {
		// New game
		system("clear");
		cout << "Tic-Tac-Toe\n\nGame " << games << endl;
		cout << "Player 1 score: " << player1.score() << endl;
		cout << "Player 2 score: " << player2.score() << endl << endl;
		
		// Determine if any players are AI
		int ai = 0; player1.set_ai(false); player2.set_ai(false);
		do { cout << "How many human players? "; cin >> ai; } while (ai < 1 || ai > 2);
		if (ai == 1) {
			do { cout << "Which player is AI? "; cin >> ai; } while (ai < 1 || ai > 2);
			if (ai == 1) { player1.set_ai(true); } else { player2.set_ai(true); }
		}
		
		// Begin game loop
		while (board.endgame() == 0) {
			// go Player 1
			board.draw();
			player1.go(board);
			if (board.endgame() != 0) { break; }
			
			// go Player 2
			board.draw();
			player2.go(board);
		}
		
		board.draw();
		switch ( board.endgame() ) {
			case 1: player1.won(); break;
			case 2: player2.won(); break;
			case 3: cout << "Draw!\n"; break;
		}
		games++;
		board.reset();
		cout << "New game? ";
		cin >> play_again;
		if (play_again[0] == 'n' || play_again[0] == 'N') { again = false; }
	} while (again);
	
	return 0;
}

void Board::draw() {
	system("clear");
	cout << " " << mark(boardstate[0]) << " | " << mark(boardstate[1]) << " | " << mark(boardstate[2]) << endl
	     << "-----------" << endl
	     << " " << mark(boardstate[3]) << " | " << mark(boardstate[4]) << " | " << mark(boardstate[5]) << endl
	     << "-----------" << endl
	     << " " << mark(boardstate[6]) << " | " << mark(boardstate[7]) << " | " << mark(boardstate[8]) << endl << endl;
}

int Board::endgame() {
	/* returns...
	   0 if unfinished
	   1 if player 1 won
	   2 if player 2 won
	   3 if draw */
	
	// check horizontals and verticals
	for(int i = 0; i < 3; i++) {
		if ( ( (boardstate[3*i] == boardstate[3*i+1]) && (boardstate[3*i] == boardstate[3*i+2]) && (boardstate[3*i] != 0) )
		  || ( (boardstate[i] == boardstate[i+3] ) && (boardstate[i]  == boardstate[i+6]) && (boardstate[i] != 0) ) )
			{ return boardstate[4*i]; }
	}
	
	// check diagonals
	if ( ( (boardstate[0] == boardstate[4]) && (boardstate[0] == boardstate[8]) && (boardstate[0] != 0) )
	  || ( (boardstate[2] == boardstate[4]) && (boardstate[2] == boardstate[6]) && (boardstate[2] != 0) ) )
		{ return boardstate[4]; }
	
	// check for draw
	bool draw = true;
	for (int i = 0; i < 9; i++) { if (boardstate[i] == 0) { draw = false; } }
	if (draw) { return 3; }
	
	// if none of these conditions are met, the game is not over
	return 0;
}

bool Board::wouldwin(int player, int coord) {
	Board hypothetical = *this;
	hypothetical.change(player, coord);
	if (hypothetical.endgame() == player) { return true; }
	return false;
}

int Board::last() {
	int last = 0;
	for(int i = 0; i < 9; i++) {
		if (boardhistory[i] == 9) { last = i - 1; break; }
	}
	return last;
}

void Board::undo() {
	if (last() > 0) {
		boardstate[ boardhistory[this->last()] ] = 0;
		boardhistory[this->last()] = 9;
		boardstate[ boardhistory[this->last()] ] = 0;
		boardhistory[this->last()] = 9;
	}
}

void Player::go(Board &board) {
	if (is_ai) {
		// check for obvious situations: winning moves and blocking moves
		for(int i = 0; i < 9; i++) {
			if (board.state(i) == 0 && board.wouldwin(player_num, i))
				{ board.change(player_num, i); return; }
		}
		// check if any coordinate will block
		for(int i = 0; i < 9; i++) {
			if (board.state(i) == 0 && board.wouldwin(3 - player_num, i))
				{ board.change(player_num, i); return; }
		}
		
		// check for special situations
		if (player_num == 1) {
			if (board.last() == -1) { board.change(1, 4); return; }
			else if (board.last() == 1) {
				int lastmove = board.history(1);
				if (lastmove % 2 == 0 && lastmove != 4)
					{ board.change(1, 8 - lastmove); return; }
				else { board.change(1, (lastmove < 4 ? 0 : 8)); return; } }
			else if (board.last() == 3) {
				if (board.history(3) % 2 == 0 || board.state(4) == 1) {
					if (board.state(0) == 1) { board.change(1, 1 + board.state(1)); return; }
					if (board.state(2) == 1) { board.change(1, 1 + 2 * board.state(1)); return; }
					if (board.state(6) == 1) { board.change(1, 3 + 2 * board.state(3)); return; }
					if (board.state(8) == 1) { board.change(1, 5 + board.state(5)); return; }
		}	}	}
		else {
			if (board.last() == 0) {
				if (board.state(4) == 1) { board.change(2, 0); return; }
				else { board.change(2, 4); return; } }
			else if (board.last() == 2) {
				if (board.state(4) == 1 && board.state(8) == 1) { board.change(2, 2); return; }
				if ((board.state(0) == 1 && board.state(8) == 1)
				      || (board.state(2) == 1 && board.state(6) == 1))
					{ board.change(2, 1); return; }
				if (board.state(0) == 1 && (board.state(5) == 1 || board.state(7) == 1)) { board.change(2, 8); return; }
				if (board.state(2) == 1 && (board.state(3) == 1 || board.state(7) == 1)) { board.change(2, 6); return; }
				if (board.state(6) == 1 && (board.state(1) == 1 || board.state(5) == 1)) { board.change(2, 2); return; }
				if (board.state(8) == 1 && (board.state(1) == 1 || board.state(3) == 1)) { board.change(2, 0); return; }
				if (board.state(1) == 1 && board.state(3) == 1) { board.change(2, 0); return; }
				if (board.state(1) == 1 && board.state(5) == 1) { board.change(2, 2); return; }
				if (board.state(3) == 1 && board.state(7) == 1) { board.change(2, 6); return; }
				if (board.state(5) == 1 && board.state(7) == 1) { board.change(2, 8); return; }
		}	}
		
		// special conditions out of the way, proceed with threatening
		for(int i = 0; i < 9; i++) {
			if (board.state(i) == 0 && board.state(8 - i) == 0)
				{ board.change(player_num, i); return; }
		}
		
		// all strategy aside, pick any spot
		for(int i = 0; i < 9; i++) {
			if (board.state(i) == 0) { board.change(player_num, i); return; }
		}
	} else {
		bool again;
		string input;
		const char *r_p, *c_p;
		int row = 0, col = 0;
		do {
			again = false;
			do {
				cout << "Player " << player_num << ", \"row,col\": ";
				cin >> input;
				if (input == "undo") { break; }
				if (input.size() > 1) {
					r_p = input.substr(0, 1).c_str(); row = (int)*r_p - 48;
					c_p = input.substr(2, 1).c_str(); col = (int)*c_p - 48; }
			} while ( row < 1 || row > 3 || col < 1 || col > 3 );
			
			// take care of "undo"
			if (input == "undo") { board.undo(); board.draw(); again = true; }
			else {
				if (board.state(3*(row-1)+col-1) == 0) { board.change(player_num, 3*(row-1)+col-1); }
				else { board.draw(); again = true; }
			}
		} while (again);
	}
}

void Player::won() {
	player_score++;
	cout << "Player " << player_num << " (" << mark(player_num) << ") wins!\n";
}