// AlphaBetaAndTT.cpp: implementation of the CAlphaBeta_TTEngine class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AlphaBeta_TTEngine.h"

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

CAlphaBeta_TTEngine::CAlphaBeta_TTEngine()
{

}

CAlphaBeta_TTEngine::~CAlphaBeta_TTEngine()
{

}

CAlphaBeta_TTEngine::SearchAGoodMove(BYTE position[][9])
{
	memcpy(CurPosition,position,90);

	CalculateInitHashKey(CurPosition);//計(jì)算初始棋盤的哈希值
	m_nMaxDepth=m_nSearchDepth;
	AlphaBeta(m_nMaxDepth,-20000,20000);
	m_umUndoMove.cmChessMove=m_cmBestMove;
	m_umUndoMove.nChessID=MakeMove(&m_cmBestMove);	

	memcpy(position,CurPosition,90);
}

int CAlphaBeta_TTEngine::AlphaBeta(int nDepth, int alpha, int beta)
{
	int score;
	int Count,i;
	BYTE type;
	int side;

	i=IsGameOver(CurPosition,nDepth);
	if(i!=0)
		return i;
	
	//察看當(dāng)前節(jié)點(diǎn)是否在置換表中有有效數(shù)據(jù)
	side=(m_nMaxDepth-nDepth)%2;
	score=LookUpHashTable(alpha,beta,nDepth,side); 
	if(score!=66666) 
		return score;//命中，直接返回表中的值

	//葉子節(jié)點(diǎn)取估值
	if(nDepth<=0)
	{
		score=m_pEval->Eveluate(CurPosition,side,m_nUserChessColor);
		EnterHashTable(exact,score,nDepth,side);//將求得的估值放進(jìn)置換表
		return score;
	}

	Count=m_pMG->CreatePossibleMove(CurPosition,nDepth,side,m_nUserChessColor);
	if(nDepth==m_nMaxDepth)
	{
		//在根節(jié)點(diǎn)設(shè)定進(jìn)度條
		m_pThinkProgress->SetRange(0,Count);
		m_pThinkProgress->SetStep(1);
	}

    int eval_is_exact=0;//數(shù)據(jù)類型標(biāo)志

	for(i=0;i<Count;i++)//對(duì)當(dāng)前節(jié)點(diǎn)的下一步每一可能的走法
	{
		if(nDepth==m_nMaxDepth)
			m_pThinkProgress->StepIt();//走進(jìn)度條

		Hash_MakeMove(&m_pMG->m_MoveList[nDepth][i],CurPosition);//產(chǎn)生該走法所對(duì)應(yīng)子節(jié)點(diǎn)的哈希值
		type=MakeMove(&m_pMG->m_MoveList[nDepth][i]);			 //產(chǎn)生子節(jié)點(diǎn)
		
		score=-AlphaBeta(nDepth-1,-beta,-alpha);//遞歸搜索子節(jié)點(diǎn)

		Hash_UnMakeMove(&m_pMG->m_MoveList[nDepth][i],type,CurPosition);//恢復(fù)當(dāng)前節(jié)點(diǎn)的哈希值 
		UnMakeMove(&m_pMG->m_MoveList[nDepth][i],type);				   //撤銷子節(jié)點(diǎn)
        if(score>=beta)//beta剪枝
		{
			EnterHashTable(lower_bound,score,nDepth,side);//將節(jié)點(diǎn)下邊界存入置換表
            return score;//返回下邊界
        }

		if(score>alpha)
		{
			alpha=score;    //取最大值
			eval_is_exact=1;//設(shè)定確切值標(biāo)志
			if(nDepth==m_nMaxDepth)
				m_cmBestMove=m_pMG->m_MoveList[nDepth][i];
		}
	}

	//將搜索結(jié)果放進(jìn)置換表
    if(eval_is_exact) 
		EnterHashTable(exact,alpha,nDepth,side);	  //確切值
    else 
		EnterHashTable(upper_bound,alpha,nDepth,side);//上邊界

	return alpha;//返回最佳值/上界
}