// ==========================
//
//  Transposition Table 
//
// ==========================
//
// Enpassant and castling flags are added in later, since this made an update easier.
// There's nothing wrong with this, except the added chance of confusion.
//
// DATA
// HashEntry defined in search.h

struct HashPair
	{
	HashEntry Near, Far;
	};

unsigned int g_nHashSize = 0;
unsigned int HashFunction [128*16];
unsigned int HashFunction2 [128*16];
HashPair *TranspositionTable = NULL;

// --------------------------------------------------
// Allocate memory, sizeof (hashentry) * 2 ^ nBits
// --------------------------------------------------
void SetHashSizeBits ( int nBits )
{
 nBits--; // (Since it's a 2 level table, divide by 2)
 g_nHashSize = (2 << (nBits-1) ) - 1;
 if (TranspositionTable != NULL ) free ( TranspositionTable );
 TranspositionTable = (HashPair*) malloc ( (g_nHashSize + 5) * sizeof (HashPair));
 if (TranspositionTable == NULL )
	{
	 if (nBits > 15) SetHashSizeBits ( 15 );
	 return;
	}
 Clear_Hash ( );
}

// --------------------------------------------------
// Clear Hash Table by zeroing it out.
// --------------------------------------------------
void Clear_Hash ( )
{
ZeroMemory (TranspositionTable, sizeof (HashPair) * g_nHashSize);
Clear_PawnHash();
}

// --------------------------------------------------
//  Compute the Random Numbers of each piece on each square for the Hash Keys & Checksums
// --------------------------------------------------
void Create_HashFunction ( )
    {
	srand (33731);
	int i, x;

	for (i = 0; i <128; i++)
		{
		// xor together some 16-bit rands
		BPHashSq[i] = rand() ^ (rand()<<15) ^ (rand()<<25);
		WPHashSq[i] = rand() ^ (rand()<<15) ^ (rand()<<25);

        for (x = 0; x < 16; x++)
            {
			HashFunction  [i * 16 + x] = rand() ^ (rand()<<15) ^ (rand()<<25);
			HashFunction2 [i * 16 + x] = rand() ^ (rand()<<15) ^ (rand()<<25);
            }
		}

	srand (clock()); 
    }       

// --------------------------------------------------
//  Compute the Hash Value for an entire Board
// --------------------------------------------------
unsigned int Hash_Board (const SBoard &Board)
        {
		unsigned int sum = 0;
        int i;

		for (i = 20; i <= 100; i++)
			sum ^= HashFunction [ i * 16 + Board.Sq [i] ];

        if (Board.SideToMove == BLACK) sum ^= HashFunction [8 ];

        return sum;
        }

unsigned int  Hash_Board2 (const SBoard &Board)
        {
		unsigned int sum = 0;
        int i;

		for (i = 20; i <= 100; i++)
			sum ^= HashFunction2 [ i * 16 + Board.Sq [i] ];

        if (Board.SideToMove == BLACK) sum ^= HashFunction2 [8 ];

        return sum;
        }

// -------------------------
//  Incrementally update the Hash Value for the board from the last move
// -------------------------
long inline HashUpdate (int u1, int u2,  SBoard &Board)
    {
	 int Sq, oldpiece, newpiece;
        
		 // destination square
         Sq = (u1 & 255);
		 newpiece = Board.Sq [ Sq ];
		 Sq <<= 4;
		 oldpiece = (u2 & 255); 
         Board.HashKey  ^= HashFunction  [ Sq + newpiece ] ^ HashFunction  [ Sq + oldpiece ];
         Board.HashCheck ^= HashFunction2 [ Sq + newpiece ] ^ HashFunction2 [ Sq + oldpiece ];
 
		 // source square
         Sq = ((u1>>8)&255);
		 newpiece = Board.Sq [ Sq ];
		 Sq <<= 4;
		 oldpiece = ((u2>>8)&255); 
         Board.HashKey  ^= HashFunction  [ Sq + newpiece ] ^ HashFunction  [ Sq + oldpiece ];
         Board.HashCheck ^= HashFunction2 [ Sq + newpiece ] ^ HashFunction2 [ Sq + oldpiece ];

		 // extra castling squares?
        if ( (u1>>16) > 0 )
                { Sq = ((u1>>16)&255); newpiece = Board.Sq [ Sq ]; oldpiece  = ((u2>>16)&255);
				  Sq <<= 4;
                  Board.HashKey  ^= HashFunction  [ Sq + newpiece ] ^ HashFunction  [ Sq + oldpiece ];
                  Board.HashCheck ^= HashFunction2 [ Sq + newpiece ] ^ HashFunction2 [ Sq + oldpiece ];
                
				if ( (u1>>24) > 0 )
					{
					Sq = ((u1>>24)&255); newpiece = Board.Sq [ Sq ]; oldpiece = ((u2>>24)&255);
					Sq <<= 4;
					Board.HashKey ^= HashFunction  [ Sq + newpiece ] ^ HashFunction  [ Sq + oldpiece ];
					Board.HashCheck ^= HashFunction2 [ Sq + newpiece ] ^ HashFunction2 [ Sq + oldpiece ];
					}
                }
        
		// Switch Side To Move
		Board.HashKey ^= HashFunction   [8];
		Board.HashCheck ^= HashFunction2 [8];

		return Board.HashKey;
    }

//
// For a Null Move
//
// Updates the Board to-play color, and the hashvalues
//
void inline BoardSwitchColor ( )
{
	SearchBoard.SideToMove ^=3;
    SearchBoard.HashKey   ^= HashFunction  [8];
    SearchBoard.HashCheck ^= HashFunction2 [8];
	SearchBoard.EnPassant ^= 128;
}

// --------------------------------------------------
//  Look up an entry and retrieve its info for the search
// --------------------------------------------------
//
// Return a Value if possible
//
void inline TT_CutOff ( HashEntry &TEntry, short &value, int &nextbest, const short &alpha, const short &beta, const int &ahead, const int &depth, const int &bPV)
{
	if ( ahead > 1 && (TEntry.depth >= depth || TEntry.mate!=0) ) // Don't grab values at root
		{
		// CheckMate value returned? then adjust the eval since the score depends on ply
		if (TEntry.mate !=0)
			{
			if (TEntry.eval < 0 ) 
				{TEntry.eval = -MATE + TEntry.mate + ahead; 
				 if (TEntry.depth < depth) 
					{if (TEntry.eval <= alpha && TEntry.failtype !=2) value = TEntry.eval;
					 return;
					}
				}
			if (TEntry.eval > 0 ) 
				{TEntry.eval =  MATE - TEntry.mate - ahead; 
				 if (TEntry.depth < depth) 
					{if (TEntry.eval >= beta && TEntry.failtype !=1) value = TEntry.eval;
					 return;
					}
				}
			}
		if (TEntry.failtype == 0) value = TEntry.eval;
        else if (TEntry.failtype == 2 && TEntry.eval >= beta) value = TEntry.eval;
        else if (TEntry.failtype == 1 && TEntry.eval <= alpha) value = TEntry.eval;
		}
}

// Return a Best Move if it looks good. 
void inline TT_BestMove ( HashEntry &TEntry, short &value, int &nextbest, const short &alpha, const short &beta, const int &ahead, const int &depth, const int &bPV)
{
	// Is the best move from a search to a decent depth
	if ( (TEntry.depth >= (depth-2) || TEntry.mate!=0) ) 
		{
		// Don't take best move from a "fail low" since no best move exists
		// Unless the boundaries are similar, then take the best move so we don't do internal iterative deeping
		if (TEntry.failtype == 1 && SearchBoard.SideToMove == WHITE && alpha < (TEntry.eval-80)) return;
		if (TEntry.failtype == 2 && SearchBoard.SideToMove == BLACK && beta > (TEntry.eval+80)) return;		
		// Don't take best move from a "fail high" if it was for a window with a significantly lesser bound (so it uses internal iterative deepening instead)
		// This takes care of some degenerate cases where there's a mate in 1 (or more) but a non-mating best move is searched deeply first instead.
		if (TEntry.failtype == 0 || (alpha != (beta-1) && bPV == FALSE)
			|| ( TEntry.failtype == 2 && (SearchBoard.SideToMove == BLACK || (TEntry.eval+150) >= beta))  
			|| ( TEntry.failtype == 1 && (SearchBoard.SideToMove == WHITE || (TEntry.eval-150) <= alpha)) )	nextbest = TEntry.bestmove;
		}
}


void inline TT_Lookup ( const unsigned int &nHashCheck, HashPair &TEntry, short &value, int &nextbest, const short &alpha, const short &beta, const int &ahead, const int &depth, const int &bPV)
{
	// hashing off
	if (bHashing == FALSE) return; 

	if (TEntry.Near.checksum == nHashCheck) 
		{
		TT_CutOff ( TEntry.Near, value, nextbest, alpha, beta, ahead, depth, bPV);
		if (value!= NOVALUE ) 
			{TEntry.Near.age = g_ucAge;  // set age to current since this entry was useful
			 return;}
		if (TEntry.Far.checksum  == nHashCheck) TT_CutOff ( TEntry.Far, value, nextbest, alpha, beta, ahead, depth, bPV);
		if (value!= NOVALUE ) return; // Check if there's a cutoff in the far table for this position
		TT_BestMove ( TEntry.Near, value, nextbest, alpha, beta, ahead, depth, bPV);
		return;
		}
	if (TEntry.Far.checksum  == nHashCheck) 
		{
		TT_CutOff ( TEntry.Far, value, nextbest, alpha, beta, ahead, depth, bPV);
		TT_BestMove ( TEntry.Far, value, nextbest, alpha, beta, ahead, depth, bPV);
		}
}

// --------------------------------------------------
//  Store info from the search in a Hash Entry
// --------------------------------------------------
void inline TT_Write ( HashEntry &TEntry, const unsigned int &nHashCheck, const short &value, const int &nextbest, const short &alpha, const short &beta, const int &ahead, const int &depth)
{
	TEntry.checksum = nHashCheck;
	/*if (value == DRAWSCORE) TEntry.eval = NOVALUE; else*/ TEntry.eval = value;
	TEntry.bestmove = nextbest;
	TEntry.age = g_ucAge;
    TEntry.depth = depth;

	if (value <= alpha) TEntry.failtype = 1;
	else if (value >= beta)  TEntry.failtype = 2;
	else TEntry.failtype = 0;

	if ( abs(value) > 9900)
		{
		TEntry.mate = MATE - abs(value) - ahead;
		}
	else TEntry.mate = 0;
}

void inline TT_Store ( const unsigned int &nHashCheck, HashPair &TEntry, const short &value, const int &nextbest, const short &alpha, const short &beta, const int &ahead, const int &depth)
{
	if (bHashing == FALSE || (SearchBoard.GameTime - SearchBoard.LastReversible) >= 100) return; 

	if (depth >= TEntry.Near.depth || TEntry.Near.age != g_ucAge)
		{
		TT_Write (TEntry.Near, nHashCheck, value, nextbest, alpha, beta, ahead, depth);
		}
	else TT_Write (TEntry.Far, nHashCheck, value, nextbest, alpha, beta, ahead, depth);                              
}

// ============================================
//
// Draw By Repetition functions (uses hash values)
//
// ============================================
unsigned int RepNum[ MAX_MOVES + 1 ];

// Calculate Hash From Board
void AddRepBoard (const SBoard &Board )
        {
		if (Board.GameTime < MAX_MOVES)
			RepNum[ Board.GameTime ] = Hash_Board (Board) ^ HashFunction[Board.EnPassant] ^ HashFunction[Board.WCastle + (Board.BCastle<<3)];
        }

void inline AddRepBoard ( const unsigned int &hashV, const SBoard &Board )
        {
		if (Board.GameTime < MAX_MOVES)
			RepNum[ Board.GameTime ] = hashV;
        }

// Check for repeated board from last unreversible move
// (only checks every other move, because side to move must be the same)

// with Hashvalue passed
int inline DrawByRepetition ( unsigned int hashV, const SBoard &Board)
        {
		int repeats = 0;
		int i = Board.LastReversible - 1;
		if ((i&1) != (Board.GameTime&1)) i++;

		int nEnd = Board.GameTime;
		if (nEnd >= MAX_MOVES) nEnd = MAX_MOVES-1;
        while (i < nEnd)
			{
			 if (RepNum[i] == hashV)
				{
				 repeats++;
				}
			 i+=2;
			}
                
        return repeats;
        }

// Compute Hashvalue from the board
int DrawByRepetition ( SBoard &Board )
        {
        unsigned int value = Hash_Board (Board) ^ HashFunction[Board.EnPassant] ^ HashFunction[Board.WCastle + (Board.BCastle<<3)];
		return DrawByRepetition ( value, Board );
        }

// Draw by Insufficent Material 
// (technically a mate is possible with King + Minor versus King + Minor, but so unlikely I ignore it.)
int inline NoMatingMaterial ( const SBoard &Board )
{
	if  ( (Board.nBPawns + Board.nWPawns) == 0)
		if  ( (Board.WMat < 400 && Board.BMat < 400) || (Board.BMat + Board.WMat) == KNIGHTSV)  return 1;
	return 0;
}

// ----------------
// Get the entry in the transposition table for Board, return TRUE on success, FALSE on fail
// ----------------
int GetTTEntry ( SBoard &Board, HashEntry &TEntry)
	{
	unsigned int nHashKey = Hash_Board  ( Board );
	unsigned int nHashCheck = Hash_Board2 ( Board);
	nHashKey = nHashKey ^ HashFunction[Board.EnPassant] ^ HashFunction[Board.WCastle + (Board.BCastle<<3)];
	TEntry = TranspositionTable [ nHashKey & g_nHashSize ].Near;
	if (TEntry.checksum == nHashCheck) return TRUE;
	TEntry = TranspositionTable [ nHashKey & g_nHashSize ].Far;
	if (TEntry.checksum == nHashCheck) return TRUE;
	return FALSE;
	}
