// othello code, originally by Jens Andersson <jensa@lysator.liu.se>, May 2001
// not very thoroughly tested -- be aware of possible bugs (argh)



// change this
#define ULONGLONG			unsigned __int64

#include <iostream>


// or to skip this, do #define assert(X)
#include <assert.h>

using std::cin;
using std::cout;
using std::endl;
using std::ostream;


#define PLAYER_BLACK_SYMBOL		"X"
#define PLAYER_WHITE_SYMBOL		"O"
#define PLAYER_NONE_SYMBOL		"-"

#define MSB_VALUE				0x8000000000000000

#define NUMBITS_MACRO(X) 0x##X##X##X##X##X##X##X##X

// returns number of bits that are 1 in an ULONGLONG, 0 to 64
inline int bitcount_in_ulonglong(ULONGLONG x) {
	x=(NUMBITS_MACRO(55) & x) + ((NUMBITS_MACRO(aa) & x)>>1);
	x=(NUMBITS_MACRO(33) & x) + ((NUMBITS_MACRO(cc) & x)>>2);
	x=(NUMBITS_MACRO(0f) & x) + ((NUMBITS_MACRO(f0) & x)>>4);
	return x % 255;
};

enum PlayerID { BLACK = 0, WHITE = 1 };

#define OTHER_PLAYER(X)		 (X == BLACK ? WHITE : BLACK)


class Move;
ostream& operator<< (ostream& ostr, const Move& move);

// a coordinate, _or_ a skipped move
class Move {
	bool _skip_move;
	int _x, _y;

public:
	Move() : _skip_move(true), _x(-1), _y(-1) { };
	Move(int x, int y) : _skip_move(false), _x(x), _y(y) { };

	Move(const Move& init) {
		_skip_move = init._skip_move;
		_x = init._x;
		_y = init._y;
	}

	Move& operator=(const Move& rhs) {
		// (assign to self is safe)
		_skip_move = rhs._skip_move;
		_x = rhs._x;
		_y = rhs._y;
		return *this;
	}

	bool isSkippedMove() const { return _skip_move; };
	int getX() const { assert(!_skip_move); return _x; };
	int getY() const { assert(!_skip_move); return _y; };

	bool operator!=(const Move& obj) {
		return !((_skip_move && obj._skip_move) || ((_x == obj._x) && (_y == obj._y)));
	}

	friend ostream& operator<< (ostream& ostr, const Move& move);
};

ostream& operator<<(ostream& theStream, const Move& move) {
	if (move._skip_move) {
		theStream << "NO";
	} else {
		theStream << ((char) ('A' + move._x)) << move._y+1;
	}
	return theStream;
};


class WeightedPositions;

// the board is represented as two 64-bit integers: mask and piece ownership
class Board {
friend WeightedPositions;	// for quick access to board representation

	ULONGLONG _mask;		// 0=free, 1=taken
	ULONGLONG _owner;		// 0=black, 1=white

	void setPos(int x, int y, PlayerID player) {
		assert((x>=0)&&(x<8)&&(y>=0)&&(y<8));

		int index = y*8 + x;
		ULONGLONG posmask = MSB_VALUE;
		if (index > 0) {
			posmask >>= index;
		}

		_mask |= posmask;
		if (WHITE == player) {
			_owner |= posmask;
		} else {
			_owner &= ~posmask;
		}
	}

public:
	Board() {
		_mask = 0;
		_owner = 0;
		setPos(3,3, BLACK);
		setPos(4,4, BLACK);
		setPos(3,4, WHITE);
		setPos(4,3, WHITE);

		assert(isBlack(3,3));		// assuring that stuff seems to work
		assert(isWhite(3,4));
		assert(isTaken(4,4));
		assert(!isTaken(0,0));
		assert(!isTaken(7,7));
		assert(!isBlack(3,4));
		assert(!isWhite(3,3));
	}

	// true iff a piece on x,y
	inline bool isTaken(int x, int y) const {
		assert((x>=0)&&(x<8)&&(y>=0)&&(y<8));

		int index = y*8 + x;
		ULONGLONG posmask = MSB_VALUE;
		if (index > 0) {
			posmask >>= index;
		}

		return (0 != (posmask & _mask));
	}

	// true iff a black piece is on x,y
	inline bool isBlack(int x, int y) const {
		assert((x>=0)&&(x<8)&&(y>=0)&&(y<8));

		int index = y*8 + x;
		ULONGLONG posmask = MSB_VALUE;
		if (index > 0) {
			posmask >>= index;
		}

		return (0 != (posmask & _mask)) && (0 != (posmask & ~_owner));
	}

	// true iff a white piece is on x,y
	inline bool isWhite(int x, int y) const {
		assert((x>=0)&&(x<8)&&(y>=0)&&(y<8));

		int index = y*8 + x;
		ULONGLONG posmask = MSB_VALUE;
		if (index > 0) {
			posmask >>= index;
		}

		return (0 != (posmask & _mask)) && (0 != (posmask & _owner));
	}

	// true iff a specified player's piece is on x,y
	inline bool isPlayer(int x, int y, PlayerID player) const {
		return (BLACK == player) ? isBlack(x,y) : isWhite(x,y);
	}

	// print the board, 0,0 is top left or "A1"
	void print() const {
		ULONGLONG tmp_mask = _mask;
		ULONGLONG tmp_owner = _owner;
		cout << " ABCDEFGH  (White " << PLAYER_WHITE_SYMBOL << ":" << nrOfWhite() << ", Black " << PLAYER_BLACK_SYMBOL <<": " << nrOfBlack() << ")" << endl;
		for (int y=0; y<8; y++) {
			cout << (char) ('1' + y);
			for (int x=0; x<8; x++) {
				if ((MSB_VALUE & tmp_mask) != 0) {
					if ((MSB_VALUE & tmp_owner) == 0) {
						cout << PLAYER_BLACK_SYMBOL;
					} else {
						cout << PLAYER_WHITE_SYMBOL;
					}
				} else {
					cout << PLAYER_NONE_SYMBOL;
				}
				tmp_mask <<= 1;
				tmp_owner <<= 1;
			}
			cout << endl;
		}
	}

	// returns number of white pieces, 0 to 64
	inline int nrOfWhite() const {
		return bitcount_in_ulonglong(_mask & _owner);
	}

	// returns number of black pieces, 0 to 64
	inline int nrOfBlack() const {
		return bitcount_in_ulonglong(_mask & ~_owner);
	}

	// returns number of pieces, 0 to 64
	inline int nrOfPieces() const {
		return bitcount_in_ulonglong(_mask);
	}

	// returns true iff no player can make a move
	inline bool isGameOver() const {
		for (int i=0; (i<64) && !isValidMove(Move(i % 8, i / 8), BLACK) && !isValidMove(Move(i % 8, i / 8), WHITE); i++) {
		};  // empty for

		return (64 == i);		// no more possible moves!
	}

	// performe a move, flipping pieces (does not in general check for move validity, not necessary)
	void doMove(const Move& theMove, PlayerID player) {
		if (theMove.isSkippedMove()) {		// allow skipped moves only if no possible move exist
			for (int i=0; i<64; i++) {
				if (isValidMove(Move(i % 8, i / 8), player)) {
					cout << " " << Move(i % 8, i / 8);
					Board copy(*this);
					copy.doMove(Move(i % 8, i / 8), player);
					copy.print();
					assert(false);		// player tries to skip even though he can move (unsure about rules for this)
				};
			}
			return;
		}

		int x = theMove.getX();
		int y = theMove.getY();
		assert(!isTaken(x, y));			// invalid move

		setPos(x, y, player);

		for (int dx = -1; dx <= 1; dx++) {
			for (int dy = -1; dy <= 1; dy++) {
				if (!((0 == dx) && (0 == dy))) {
					int i = 1;
					bool turn_ok = false;
					while ((x+dx*i >= 0) && (x+dx*i <= 7) && (y+dy*i >= 0) && (y+dy*i <= 7)) {
						if (isPlayer(x+dx*i, y+dy*i, player)) {
							turn_ok = true;
							break;		// break while
						} else if (!isTaken(x+dx*i, y+dy*i)) {
							break;		// break while
						}
						i++;			// was other, keep counting for potential score
					}
					if (turn_ok) {
						i--;
						while (i > 0) {
							setPos(x+dx*i, y+dy*i, player);
							i--;
						}
					}
				}
			}
		}

	}

	// returns number of pieces gained for a certain move.
	// returns 1 if breakearly is true and the true number is greater than 0 (useful for move validity check)
	int getGainForMove(const Move& theMove, PlayerID player, bool breakEarly = false) const {
		int x = theMove.getX();
		int y = theMove.getY();

		int gain = 0;
		for (int dx = -1; dx <= 1; dx++) {
			for (int dy = -1; dy <= 1; dy++) {
				if (!((0 == dx) && (0 == dy))) {
					int i = 1;
					while ((x+dx*i >= 0) && (x+dx*i <= 7) && (y+dy*i >= 0) && (y+dy*i <= 7)) {
						if (isPlayer(x+dx*i, y+dy*i, player)) {
							gain += i-1;
							if ((breakEarly) && (gain > 0)) {
								return 1;		// if it's >0, that's enough
							}
							break;		// break while
						} else if (!isTaken(x+dx*i, y+dy*i)) {
							break;		// break while
						}
						i++;			// was other, keep counting for potential score
					}

				}
			}
		}
		return gain;
	}

	inline bool isValidMove(const Move& theMove, PlayerID player) const {		//int x, int y, PlayerID player) {
		if (theMove.isSkippedMove()) {
			return true;				// not correct -- player should have no other option.
		}								// however, shouldn't matter in the current program

		if (isTaken(theMove.getX(), theMove.getY())) {		// obviously invalid move
			return false;
		}

		return (getGainForMove(theMove, player, true) > 0);		// do quick eval of gain (breakearly is true)
	}


};



// a player has its color set before each game, and should then be prepared
// to provide moves for different boards
class Player {
protected:
	PlayerID _playerID;
public:

	virtual Move getMove(const Board & board) = 0;
	virtual void setColor(PlayerID player) { _playerID = player; };
};


// this player asks a human about what to do
class HumanPlayer : public Player {
public:
	virtual Move getMove(const Board & board) {
		board.print();
		char xpos_char;
		int xpos, ypos;
		do {
			cout << "Player " << ((BLACK == _playerID) ? PLAYER_BLACK_SYMBOL : PLAYER_WHITE_SYMBOL) << " to move." << endl;
			cout << "X: ";
			cin >> xpos_char;
			cout << "Y: ";
			cin >> ypos;
			ypos--;
			xpos = xpos_char - 'A';
		} while ((xpos <0) || (xpos>7) || (ypos<0) || (ypos>7) || !board.isValidMove(Move(xpos, ypos), _playerID));

		return Move(xpos, ypos);
	}
};


// this player randomly picks one of the valid moves
class RandomPlayer : public Player {
public:
	virtual Move getMove(const Board & board) {
		int bestMove = -1;
		int nrOfGood = 0;
		for (int i=0; i<64; i++) {
			if (board.isValidMove(Move(i % 8, i / 8), _playerID)) {
				nrOfGood++;
				if ((rand() % nrOfGood) == 0) {
					bestMove = i;
				}
			}
		}

		if (0 == nrOfGood) {
			return Move();		// no possible moves, have to skip!
		}

		return Move(bestMove % 8, bestMove / 8);
	}
};


// this player picks the move which gives the best immediate gain
class GreedyPlayer : public Player {
public:
	virtual Move getMove(const Board & board) {
		int bestMove;
		int bestScore = 0;
		int atThisScore = 0;
		for (int i=0; i<64; i++) {
			if (!board.isTaken(i % 8, i / 8)) {
				int thisGain = board.getGainForMove(Move(i % 8, i / 8), _playerID);
				if ((thisGain > 0) && (thisGain >= bestScore)) {
					if (thisGain > bestScore) {
						atThisScore = 1;
					} else {
						atThisScore++;
						if (rand() % atThisScore != 0) {
							continue;		// continue for
						}
					}
					bestScore = thisGain;
					bestMove = i;
				}
			}
		}

		if (0 == bestScore) {
			return Move();		// no possible moves, have to skip!
		}

		return Move(bestMove % 8, bestMove / 8);
	}
};


// evalfunction should calculate how good a certain board is for a specified
// player.  high values are good.  values returned must be in the range [-(INT_MAX-1), INT_MAX-1].
class EvalFunction {
public:
	virtual int calcEstimate(const Board& scenario, PlayerID playerID) {
		int score = scenario.nrOfBlack() - scenario.nrOfWhite();
		if (WHITE == playerID) {
			score = -score;
		}
		if (64 == scenario.nrOfPieces()) {			// end game estimate, not strictly correct
			score = (score < 0) ? -1000 : 1000;		// certain win/loss
		}
		return score;
	}
};



ostream& operator<< (ostream& ostr, const WeightedPositions& wp);

// a simple type of evalfunction, with 4 parameters.  every piece gives 2 points,
// parameters decide extra score for corners, near-corners, edges and "diagonal almost-corners".
class WeightedPositions : public EvalFunction {

	int _a, _b, _c, _d;
public:
	ULONGLONG	evals;

	WeightedPositions() : _a(rand() % 10 - 3), _b(rand() % 10 - 3), _c(rand() % 10 - 3), _d(rand() % 10 - 3), evals(0) { };

	WeightedPositions(int a, int b, int c, int d) : _a(a), _b(b), _c(c), _d(d){ };

	virtual int calcEstimate(const Board& scenario, PlayerID playerID) {
		evals++;
		int score = scenario.nrOfBlack() - scenario.nrOfWhite();
		if (WHITE == playerID) {
			score = -score;
		}
		if (64 == scenario.nrOfPieces()) {				// end game estimate, not strictly correct
			score = (score < 0) ? -10000 : 10000;		// certain win/loss
			return score;
		}


		ULONGLONG mask = scenario._mask;			// 0=free, 1=taken
		ULONGLONG mine;					// current player's pieces
		ULONGLONG opponents;			// his opponent's pieces
		if (BLACK == playerID) {
			mine = ~scenario._owner & mask;
			opponents = scenario._owner & mask;
		} else {
			mine = scenario._owner & mask;
			opponents = ~scenario._owner & mask;
		}
		
		ULONGLONG corners =      0x8100000000000081;
		ULONGLONG edges =        0x3C0081818181003C;
		ULONGLONG near_corners = 0x4281000000008142;
		ULONGLONG diag_corners = 0x0042000000004200;

		score = 2*score + _a * (bitcount_in_ulonglong(mine & corners) - bitcount_in_ulonglong(opponents & corners)) 
			+ _b * (bitcount_in_ulonglong(mine & near_corners) - bitcount_in_ulonglong(opponents & near_corners)) 
			+ _c * (bitcount_in_ulonglong(mine & edges) - bitcount_in_ulonglong(opponents & edges)) 
			+ _d * (bitcount_in_ulonglong(mine & diag_corners) - bitcount_in_ulonglong(opponents & diag_corners));
		return score;
	}

	// "breed" this parameter set with another, producing a third as result
	virtual WeightedPositions mixWith(const WeightedPositions& other) const {
		int new_a = rand() % 2 == 0 ? _a : other._a;
		int new_b = rand() % 2 == 0 ? _b : other._b;
		int new_c = rand() % 2 == 0 ? _c : other._c;
		int new_d = rand() % 2 == 0 ? _d : other._d;
		return WeightedPositions(new_a, new_b, new_c, new_d);
	}

	// mutate the parameter set by adjusting each parameter randomly up/down
	virtual void mutate() {
		_a += (rand() % 5) - 2;
		_b += (rand() % 5) - 2;
		_c += (rand() % 5) - 2;
		_d += (rand() % 5) - 2;
	}

	friend ostream& operator<< (ostream& ostr, const WeightedPositions& wp);
};

ostream& operator<<(ostream& theStream, const WeightedPositions& wp) {
	theStream << wp._a << " " << wp._b << " " << wp._c << " " << wp._d;
	return theStream;
};


// this player uses negamax with alpha-beta cutoffs to decide the best move.
// it needs an evalfunction as parameter to evaluate the board.  max search
// depth is a constant.
class RationalPlayer : public Player {
	Move _bestMove;
	EvalFunction& _evalFunction;

	enum Constants { MAX_DEPTH = 4 };

	int searchTree(const Board & board, PlayerID player, int myBestAlpha, int hisWorstBeta, int depth) {
		if ((MAX_DEPTH == depth) || board.isGameOver()) {
			int score = _evalFunction.calcEstimate(board, player);
			return score;
		} else {
			bool noValidMoves = true;
			bool foundBetterMove = false;			// argh, realized new bug -- fixing
		
			int score;
			int atThisLevel = 0;

			for (int i=0; i<64; i++) {
				Move theMove(i % 8, i / 8);
				if (board.isValidMove(theMove, player)) {
					noValidMoves = false;
					Board scenario(board);
					scenario.doMove(theMove, player);

					score = -searchTree(scenario, OTHER_PLAYER(player), -hisWorstBeta, -myBestAlpha, depth+1);
					
					// always take a better move, randomize if an equally good move appears
					if ((score > myBestAlpha) || ((score == myBestAlpha) && (rand() % ++atThisLevel == 0))) {
						if (score > hisWorstBeta) {
							return hisWorstBeta+1;		// he won't let us get here, prune!  (+1 _important_!)
							// or: return score;
						}
						if (score > myBestAlpha) {
							myBestAlpha = score;
							atThisLevel = 1;
						}
						if (depth == 0) { _bestMove = theMove; }		// update best move if on base level

						foundBetterMove = true;
					}
				}
			}

			if (noValidMoves) {
				score = -searchTree(board, OTHER_PLAYER(player), -hisWorstBeta, -myBestAlpha, depth+1);
				if (score > myBestAlpha) {		// this was a better "move" than we had so far
					if (depth == 0) { _bestMove = Move(); }
					myBestAlpha = score;
					foundBetterMove = true;
				}
			}

			if (foundBetterMove) {
				return myBestAlpha;
			} else {
				return myBestAlpha - 1;		// we can't risk this being chosen as an equivalent move if we had no decent move!
			}
		}
	}

// this is a full search, and should therefore always give a move which is equally good as
// the one negamax provides
// *** not maintained, might be out-of-sync with searchTree ***
	int searchTreePlain(const Board & board, PlayerID player, int depth) {
		if ((MAX_DEPTH == depth) || board.isGameOver()) {
			int score = _evalFunction.calcEstimate(board, player);
			return score;
		} else {
			bool noValidMoves = true;
		
			int score;
			int ourBestScore = -INT_MAX;

			for (int i=0; i<64; i++) {
				Move theMove(i % 8, i / 8);
				if (board.isValidMove(theMove, player)) {
					noValidMoves = false;
					Board scenario(board);
					scenario.doMove(theMove, player);

					score = -searchTreePlain(scenario, OTHER_PLAYER(player), depth+1);
					if (score > ourBestScore) {		// Good, we'll take this one instead!
						if (depth == 0) { _bestMove = theMove; }
						ourBestScore = score;
					}
				}
			}

			if (noValidMoves) {
				score = -searchTreePlain(board, OTHER_PLAYER(player), depth+1);
				if (score > ourBestScore) {		// Good, we'll take this one instead!
					ourBestScore = score;
					if (depth == 0) { _bestMove = Move(); }
				}

			}

			return ourBestScore;
		}
	}


public:
	virtual Move getMove(const Board & board) {
		_bestMove = Move(9,9);		// init to invalid move
		int nScore = searchTree(board, _playerID, -INT_MAX, INT_MAX, 0);

		return _bestMove;
	};

	RationalPlayer(EvalFunction& evalf) : _evalFunction(evalf) { };
};



// a game is a certain number of rounds, where the first player always plays white.
class Game {
	Player& _player_white;
	Player& _player_black;
public:
	Game(Player& white, Player& black) : _player_white(white), _player_black(black) { }

// playGame() returns the number of won white games - black ones.
	int playGame() {
		int whiteWins = 0;
		int blackWins = 0;
		int games = 11;

		for (int i=0; i<games; i++) {
			Board board;
			bool isWhite = true;
			_player_white.setColor(WHITE);
			_player_black.setColor(BLACK);

			Move theMove;
			while (!board.isGameOver()) {
				if (isWhite) {
					theMove = _player_white.getMove(board);
				} else {
					theMove = _player_black.getMove(board);
				}
				board.doMove(theMove, (isWhite ? WHITE : BLACK));
				isWhite = !isWhite;
			}
			
			if (board.nrOfWhite() > board.nrOfBlack()) {
				whiteWins++;
			}
			if (board.nrOfBlack() > board.nrOfWhite()) {
				blackWins++;
			}
			cout << "Current : White wins: " << whiteWins << ", Black wins: " << blackWins << ", draws: " << i+1 - whiteWins - blackWins << endl;
		}
		cout << "In total: White wins: " << whiteWins << ", Black wins: " << blackWins << ", draws: " << games - whiteWins - blackWins << endl;
		return (whiteWins - blackWins);
	}
};


// 6 is minimum, and the code below is also adapted specially for 6 -- very beautiful
#define		PLAYERS_IN_POOL			6

int main(int argc, char* argv[])
{
	WeightedPositions	pool[PLAYERS_IN_POOL];
	int score[PLAYERS_IN_POOL];

// run "generations", where the two best players and variations stays and a random
// player appears in the following round.
	while (true) {
		cout << "------ Starting new generation ------" << endl << "Players in pool:" << endl;
		for (int q=0; q<PLAYERS_IN_POOL; q++) {
			score[q] = 0;
			cout << pool[q] << endl;
		}

		for (int i=0; i<PLAYERS_IN_POOL; i++) {
			for (int j=0; j<PLAYERS_IN_POOL; j++) {
				if (i != j) {
					cout << "Starting game of " << i << " vs " << j << endl;
					RationalPlayer p1(pool[i]);
					RationalPlayer p2(pool[j]);
					Game g(p1, p2);
					int whiteWinMore = g.playGame();
					score[i] += whiteWinMore;
				}
			}
		}
		int bestValue = -INT_MAX;
		int bestIndex;
		cout << "Generation tournament over, results:" << endl;
		for (int k=0; k<PLAYERS_IN_POOL; k++) {
			cout << pool[k] << " : score " << score[k] << endl;
			if (score[k] > bestValue) {
				bestValue = score[k];
				bestIndex = k;
			}
		}

		cout << "Generation winner: " << pool[bestIndex] << endl;
		score[bestIndex] = -INT_MAX;

		int secondBestValue = -INT_MAX;
		int secondBestIndex;
		for (int k2=0; k2<PLAYERS_IN_POOL; k2++) {
			if (score[k2] > secondBestValue) {
				secondBestValue = score[k2];
				secondBestIndex = k2;
			}
		}

		cout << "Generation runner-up: " << pool[secondBestIndex] << endl;
		score[secondBestIndex] = -INT_MAX;

		WeightedPositions winner = pool[bestIndex];
		WeightedPositions runnerUp = pool[secondBestIndex];
		
		WeightedPositions new1 = winner.mixWith(runnerUp);
		
		WeightedPositions new2 = winner;
		new2.mutate();
		
		WeightedPositions new3;

		WeightedPositions new4 = runnerUp;
		new4.mutate();

		pool[0] = runnerUp;
		pool[1] = winner;
		pool[2] = new1;
		pool[3] = new2;
		pool[4] = new3;
		pool[5] = new4;
	}

	return 0;
}