// TranspositionTable.cpp: implementation of the CTranspositionTable class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "TranspositionTable.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CTranspositionTable::CTranspositionTable()
{
	InitializeHashKey();//建立哈希表，創(chuàng)建隨機數(shù)組
}

CTranspositionTable::~CTranspositionTable()
{
	//釋放哈希表所用空間
	delete m_pTT[0];
	delete m_pTT[1];
}

void CTranspositionTable::CalculateInitHashKey(BYTE CurPosition[][9])
{
	int j,k,nChessType;

	m_HashKey32=0;
	m_HashKey32=0;
	//將所有棋子對應的哈希數(shù)加總
	for(j=0;j<10;j++)
		for(k=0;k<9;k++)
		{
			nChessType=CurPosition[j][k];
			if(nChessType!=NOCHESS)
			{
				m_HashKey32=m_HashKey32^m_nHashKey32[nChessType][j][k]; 
				m_HashKey64=m_HashKey64^m_ulHashKey64[nChessType][j][k]; 
			}
		}
}

void CTranspositionTable::Hash_MakeMove(CHESSMOVE *move, BYTE CurPosition[][9])
{
	BYTE nToID,nFromID;

	nFromID=CurPosition[move->From.y][move->From.x];
	nToID=CurPosition[move->To.y][move->To.x];

	//將要移動的棋子從中去除
	m_HashKey32=m_HashKey32^m_nHashKey32[nFromID][move->From.y][move->From.x]; 
	m_HashKey64=m_HashKey64^m_ulHashKey64[nFromID][move->From.y][move->From.x]; 

	if(nToID!=NOCHESS)//目標位置有棋子，也要從中去除
	{
		m_HashKey32=m_HashKey32^m_nHashKey32[nToID][move->To.y][move->To.x]; 
		m_HashKey64=m_HashKey64^m_ulHashKey64[nToID][move->To.y][move->To.x]; 
	}
	
	//將移動的棋子在目標位置的隨機數(shù)添入
	m_HashKey32=m_HashKey32^m_nHashKey32[nFromID][move->To.y][move->To.x]; 
	m_HashKey64=m_HashKey64^m_ulHashKey64[nFromID][move->To.y][move->To.x];
}

void CTranspositionTable::Hash_UnMakeMove(CHESSMOVE *move, BYTE nChessID, BYTE CurPosition[][9])
{
	BYTE nToID;

	nToID=CurPosition[move->To.y][move->To.x];
	
	//將移動棋子在移動前位置上的隨機數(shù)添入
	m_HashKey32=m_HashKey32^m_nHashKey32[nToID][move->From.y][move->From.x]; 
	m_HashKey64=m_HashKey64^m_ulHashKey64[nToID][move->From.y][move->From.x]; 

	//將移動棋子在現(xiàn)位置上的隨機數(shù)從哈希值當中去除
	m_HashKey32=m_HashKey32^m_nHashKey32[nToID][move->To.y][move->To.x]; 
	m_HashKey64=m_HashKey64^m_ulHashKey64[nToID][move->To.y][move->To.x]; 
	
	if(nChessID)
	{
		//將被吃掉的棋子所對應的隨機數(shù)恢復進哈希值
		m_HashKey32=m_HashKey32^m_nHashKey32[nChessID][move->To.y][move->To.x]; 
		m_HashKey64=m_HashKey64^m_ulHashKey64[nChessID][move->To.y][move->To.x]; 
	}
}

int CTranspositionTable::LookUpHashTable(int alpha, int beta, int depth, int TableNo)
{
	int x;
	HashItem* pht;

	//計算二十位哈希地址，如果讀者設定的哈希表大小不是1M*2的,
	//而是TableSize*2，TableSize為讀者設定的大小
	//則需要修改這一句為m_HashKey32%TableSize
	//下一個函數(shù)中這一句也一樣
	x=m_HashKey32 & 0xFFFFF;
	pht=&m_pTT[TableNo][x];//取到具體的表項指針

    if(pht->depth>=depth && pht->checksum==m_HashKey64)
	{
		switch(pht->entry_type)//判斷數(shù)據(jù)類型
		{
		case exact://確切值
			return pht->eval;

		case lower_bound://下邊界
			if(pht->eval>=beta)
				return pht->eval;

			break;

		case upper_bound://上邊界
			if (pht->eval<=alpha)
				return pht->eval;

			break;
        }
	}

	return 66666;
}

void CTranspositionTable::EnterHashTable(ENTRY_TYPE entry_type, short eval, short depth, int TableNo)
{
	int x;
	HashItem* pht;

	x=m_HashKey32 & 0xFFFFF;//計算二十位哈希地址
	pht=&m_pTT[TableNo][x]; //取到具體的表項指針

	//將數(shù)據(jù)寫入哈希表
	pht->checksum=m_HashKey64; //64位校驗碼
	pht->entry_type=entry_type;//表項類型
	pht->eval=eval;			   //要保存的值
	pht->depth=depth;		   //層次
}

void CTranspositionTable::InitializeHashKey()
{
	int i,j,k;
	
	srand((unsigned)time(NULL));
	
	//填充隨機數(shù)組
	for(i=0;i<15;i++)
		for(j=0;j<10;j++)
			for(k=0;k<9;k++)
			{
				m_nHashKey32[i][j][k]=Rand32();
				m_ulHashKey64[i][j][k]=Rand64();
			}

	//申請置換表所用空間。1M*2個條目，讀者也可指定其他大小
	m_pTT[0]=new HashItem[1024*1024];//用于存放取極大值的節(jié)點數(shù)據(jù)
	m_pTT[1]=new HashItem[1024*1024];//用于存放取極小值的節(jié)點數(shù)據(jù)
}

//生成64位隨機數(shù)
LONGLONG CTranspositionTable::Rand64()
{
    return rand()^((LONGLONG)rand()<<15)^((LONGLONG)rand()<<30)^
		((LONGLONG)rand()<<45)^((LONGLONG)rand()<<60);
}

//生成32位隨機數(shù)
LONG CTranspositionTable::Rand32()
{
    return rand()^((LONG)rand()<<15)^((LONG)rand()<<30);
}