#include "LookUpTable.h"
#include <irrlicht.h>
#include "TestWin.h"
#include "Muele.h"
#include <time.h>
#include "Symmetry.h"

using namespace irr;

CLookUpTable::CLookUpTable()
{
	boardSizeX = 3;
	boardSizeY = 3;
	boardSizeZ = 1;
	winFieldCount = 3;
	boardFieldsCount = boardSizeX * boardSizeY * boardSizeZ;

	pBoard  = new char[boardFieldsCount];
	pSymmetry = new CSymmetry( boardSizeX, boardSizeY, boardSizeZ );
	
	createTables();
	learn();
}

/********************************************************************/

CLookUpTable::~CLookUpTable(void)
{
	delete   pSymmetry;
	delete[] pBoard;
}

/********************************************************************/

void CLookUpTable::createTables()
{
	if ( !lookUpTableStates.empty() ) return;

	memset(pBoard, 0, boardFieldsCount );

	CTestWin testWinPlayer1( pBoard , NULL, boardSizeX, boardSizeY, boardSizeZ, PLAYER_1, winFieldCount, 1);
	CTestWin testWinPlayer2( pBoard , NULL, boardSizeX, boardSizeY, boardSizeZ, PLAYER_2, winFieldCount, 1);
	
	int playerCount[3] = {0, 0, 0};

	register char field = boardFieldsCount - 1;
	
	while( true ) 
	{
			(*(pBoard + field))++;

			if ( *(pBoard + field) == PLAYER_2 + 1 )
			{
				playerCount[PLAYER_2]--;
				*(pBoard + field) = -1;
				if ( field == 0  ) break;
				field--;
			} 
			else
			{
				playerCount[*(pBoard + field)]++;
				if ( *(pBoard + field) == 2 ) 
					playerCount[PLAYER_1]--;

				field++;
				if ( field == boardFieldsCount )
				{
					field--;

					if ( ( playerCount[PLAYER_1] == playerCount[PLAYER_2] + 1 || playerCount[PLAYER_1] == playerCount[PLAYER_2] ) )
					{
						bool winPlayerOne = testWinPlayer1.testWin();
						bool winPlayerTwo = testWinPlayer2.testWin();

						if ( !(winPlayerOne && winPlayerTwo) )
						{
							unsigned long board = reduceBoardToLong(pSymmetry->getSymmetry(pBoard));

							if ( lookUpTableStates.binary_search(board) == -1 )
							{
								lookUpTableStates.push_back( board );
								lookUpTableStates.sort();
								lookUpStateValues.push_back( 0.5 );
							}

						}
					}
				}
			}
	} // while
	lookUpTableStates.sort();
}

/********************************************************************/

int CLookUpTable::getBestMove(char *pGameBoard, char player)
{
	double bestStateValue = -10000.0;
	int bestFieldNumber;
	s32 arrayPosition;

	for ( int i = 0; i < boardFieldsCount; i++ )
		if ( *(pGameBoard + i) == EMTY_FIELD )
		{
			pGameBoard[i] = player;
			arrayPosition=lookUpTableStates.binary_search(reduceBoardToLong(pSymmetry->getSymmetry(pGameBoard)));
			if ( bestStateValue < lookUpStateValues[arrayPosition] )
			{
				bestStateValue = lookUpStateValues[arrayPosition];
				bestFieldNumber = i;
			}
			pGameBoard[i] = EMTY_FIELD;
		}
	return bestFieldNumber;
}

/********************************************************************/

double CLookUpTable::getStateValue(char *pBoard)
{
    return lookUpStateValues[lookUpTableStates.binary_search(reduceBoardToLong(pBoard))];
}

/********************************************************************/

inline unsigned long CLookUpTable::reduceBoardToLong(const char *pBoard)
{
	unsigned long boardState = 0;

	for ( int j = 0; j < boardFieldsCount; j++ )
	{
		boardState<<=2;
		boardState|=pBoard[j];
	}

	return boardState;
}

/********************************************************************/

void CLookUpTable::learn()
{
	if ( lookUpTableStates.empty() ) return;

	register char *pMoves  = new char[boardFieldsCount];
	register char *pSaveBoard  = new char[boardFieldsCount];

	CTestWin testWinPlayer1( pBoard , NULL, boardSizeX, boardSizeY, boardSizeZ, PLAYER_1, winFieldCount, 1);
	CTestWin testWinPlayer2( pBoard , NULL, boardSizeX, boardSizeY, boardSizeZ, PLAYER_2, winFieldCount, 1);

	char actualPlayer;
	int move, saveMove;
	s32 arrayPosition;

	unsigned long gamesCount = 10000;
	double startAlpha = 0.5;
	double positiveReward = 0.8;
	double negativeReward = 0.2;
	double alpha; // stepsiize param.
	bool draw;
	unsigned drawCount = 0, win1Count = 0, win2Count = 0;
    	
	srand( (unsigned)time( NULL ) );

    for ( int i = gamesCount; i > 0; i--)
	{
		memset(pMoves, 0, boardFieldsCount );
		memset(pBoard, 0, boardFieldsCount );
		actualPlayer = PLAYER_1;
		draw = false;

		// play one complete game
		for ( move = 0;  ; move++ )
		{
			alpha = 0.1;// * i / gamesCount;

			// If actual player can win, take the winning move.
			if ( actualPlayer == PLAYER_1)
			{
				for ( int j = 0; j < boardFieldsCount; j++ )
					if ( pBoard[j] == EMTY_FIELD )
					{
						pBoard[j] = PLAYER_1;
						if ( testWinPlayer1.testWin() )
						{
							pMoves[move] = j;
							win1Count++;
							goto wonGame;
						}
						pBoard[j] = EMTY_FIELD;
					}
			}
			else 
			{
				for ( int j = 0; j < boardFieldsCount; j++ )
					if ( pBoard[j] == EMTY_FIELD )
					{
						pBoard[j] = PLAYER_2;
						if ( testWinPlayer2.testWin() )
						{
							pMoves[move] = j;
							win2Count++;
							goto wonGame;
						}
						pBoard[j] = EMTY_FIELD;
					}
			}
			
//			if ( rand() % ( ( boardFieldsCount ) - ( move )   ) == 0 )
			if ( rand() % ( ( boardFieldsCount / 2 )  ) == 0 )
			{  
				// exploring move
				int randomField;
				for ( int j = 0; j < boardFieldsCount; j++ )
				{
					//randomField =(rand()%(boardFieldsCount));
					randomField =(rand()%(boardFieldsCount));
					if ( *(pBoard + randomField) == EMTY_FIELD )
					{
						pBoard[randomField] = actualPlayer;
						pMoves[move] = randomField;
						goto weiter;
					}
				}
				for ( int j = 0; j < boardFieldsCount; j++ )
					if ( *(pBoard + j) == EMTY_FIELD) 
					{
						pBoard[j] = actualPlayer;
						pMoves[move] = j;
						break;
					}
				weiter:;
			}
			else
			{  // normal move
				int bestMove = getBestMove(pBoard, actualPlayer);
				pBoard[bestMove] = actualPlayer;
				pMoves[move] = bestMove;
			}

			if ( actualPlayer == PLAYER_1)
			{
				//if ( testWinPlayer1.testWin() ) break;
				actualPlayer = PLAYER_2;
			} else 
			{
				//if ( testWinPlayer2.testWin() ) break;
				actualPlayer = PLAYER_1;
			}
			if ( move == boardFieldsCount - 1) 
			{
				// draw
				draw = true;
				drawCount++;
				break;
			}
		} // play one complete game loop
		
		wonGame:;
		
        // ----------------------
		// learn game
		//if ( ((move % 2) + 1 == actualPlayer) /*|| draw*/  )
		{
			saveMove = move;
			memcpy( pSaveBoard, pBoard, boardFieldsCount );

			double playerReward = positiveReward;
			if ( draw) playerReward = 0.51;// positiveReward;

			// --------------------------------------------------
            // reward the winner
			// set final state for winner directly to reward
			arrayPosition = lookUpTableStates.binary_search(reduceBoardToLong(pSymmetry->getSymmetry(pBoard) ));
			//if ( lookUpStateValues[arrayPosition] != playerReward )
			{
				lookUpStateValues[arrayPosition] = playerReward;

				pBoard[pMoves[move]] = EMTY_FIELD;
				move--;
				pBoard[pMoves[move]] = EMTY_FIELD;
				move--;
			
				// reward other states based on distance
				for ( ;move >= 0; move-=2 )
				{
					arrayPosition = lookUpTableStates.binary_search(reduceBoardToLong(pSymmetry->getSymmetry(pBoard)));
					lookUpStateValues[arrayPosition] = lookUpStateValues[arrayPosition] + ( playerReward - lookUpStateValues[arrayPosition])*alpha;
					playerReward=lookUpStateValues[arrayPosition];

					pBoard[pMoves[move]] = EMTY_FIELD;
					if ( move  )pBoard[pMoves[move - 1]] = EMTY_FIELD;
				}
			}
			
			// --------------------------------------------------
			// reward the looser
			// restore game
			move = saveMove;
			memcpy( pBoard, pSaveBoard, boardFieldsCount );
			
			playerReward = negativeReward;
			if ( draw) playerReward = 0.51;// positiveReward;

			// delete last move of winner
			pBoard[pMoves[move]] = EMTY_FIELD;
			move--;

			// set final state of the looser directly to reward
			arrayPosition = lookUpTableStates.binary_search(reduceBoardToLong(pSymmetry->getSymmetry(pBoard)));
			
			//if ( lookUpStateValues[arrayPosition] != playerReward )
			{
				lookUpStateValues[arrayPosition] = playerReward;
					
				pBoard[pMoves[move]] = EMTY_FIELD;
				move--;
				pBoard[pMoves[move]] = EMTY_FIELD;
				move--;
			
				// reward other states based on distance
				for ( ;move > 0; move-=2 )
				{
					arrayPosition = lookUpTableStates.binary_search(reduceBoardToLong(pSymmetry->getSymmetry(pBoard)));
					lookUpStateValues[arrayPosition] = lookUpStateValues[arrayPosition] + ( playerReward - lookUpStateValues[arrayPosition])*alpha;
					playerReward=lookUpStateValues[arrayPosition];

					pBoard[pMoves[move]] = EMTY_FIELD;
					pBoard[pMoves[move - 1]] = EMTY_FIELD;
				}
			}
		} // learn game
	}
	
	delete[] pMoves;
	delete[] pSaveBoard;
}

