// MTD_f.cpp: implementation of the CMTD_fEngine class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "MTD_fEngine.h"

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

CMTD_fEngine::CMTD_fEngine()
{

}

CMTD_fEngine::~CMTD_fEngine()
{

}

CMTD_fEngine::SearchAGoodMove(BYTE position[][9])
{
	int firstguess=0;

	memcpy(CurPosition,position,90);
	m_nMaxDepth=m_nSearchDepth;
	CalculateInitHashKey(CurPosition);//計(jì)算初始棋盤的哈希值

	//迭代深化調(diào)用 MTD(f)搜索
	for(m_nMaxDepth=1;m_nMaxDepth<=m_nSearchDepth;m_nMaxDepth++)
		firstguess=Mtdf(firstguess,m_nMaxDepth);
	MakeMove(&m_cmBackupBM);
	memcpy(position,CurPosition,90);
	return 0;
}

int CMTD_fEngine::Mtdf(int firstguess, int nDepth)
{
	int g,lowerbound,upperbound,beta;
	
	g=firstguess;
	//初始搜索范圍-20000 - 20000
	upperbound=20000;
	lowerbound=-20000;
	while(lowerbound<upperbound)
	{
		m_cmBackupBM=m_cmBestMove;
		//將窗口向目標(biāo)移動(dòng)
		if(g==lowerbound)
			beta=g+1;
		else 
			beta=g;
		g=FAlphaBeta(nDepth,beta-1,beta);//空窗探測
		if(g<beta)
			upperbound=g;
		else
			lowerbound=g;
	}

	return g;
}

int CMTD_fEngine::FAlphaBeta(int nDepth, int alpha, int beta)
{
	int current=-19999 ;
	int score;
	int Count,i;
	BYTE type;

	i=IsGameOver(CurPosition, nDepth);
	if(i!=0)
		return i;

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

	if(nDepth<=0)//葉子節(jié)點(diǎn)取估值
	{
		current=m_pEval->Eveluate(CurPosition,(m_nMaxDepth-nDepth)%2,m_nUserChessColor);
		EnterHashTable(exact,current,nDepth,(m_nMaxDepth-nDepth)%2);//將估值放入置換表
		return current;
	}

	Count=m_pMG->CreatePossibleMove(CurPosition,nDepth,(m_nMaxDepth-nDepth)%2,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)志設(shè)為 0

	for (i=0;i<Count;i++) 
	{
		if(nDepth==m_nMaxDepth)
			m_pThinkProgress->StepIt();//走進(jìn)度條

		Hash_MakeMove(&m_pMG->m_MoveList[nDepth][i],CurPosition);//產(chǎn)生子節(jié)點(diǎn)的哈希值
		type=MakeMove(&m_pMG->m_MoveList[nDepth][i]);			//產(chǎn)生子節(jié)點(diǎn)

		score=-FAlphaBeta(nDepth-1,-beta,-alpha);//遞歸搜索子節(jié)點(diǎn)
		
		Hash_UnMakeMove(&m_pMG->m_MoveList[nDepth][i],type, CurPosition); 
		UnMakeMove(&m_pMG->m_MoveList[nDepth][i],type); 

				
		if(score>current)
		{
			current=score;
			if(nDepth == m_nMaxDepth)
				m_cmBestMove = m_pMG->m_MoveList[nDepth][i];
			if(score>=beta)//beta剪枝
			{
				EnterHashTable(lower_bound, score, nDepth,(m_nMaxDepth-nDepth)%2);//將下邊界裝入置換表
				return current;
			}
			if(score>alpha)
			{
				eval_is_exact=1;//設(shè)定確切值標(biāo)志
				alpha=score;//保留最大值
			}
		}
	}

	//將搜索結(jié)果放入置換表
	if(eval_is_exact) 
		EnterHashTable(exact,alpha,nDepth,(m_nMaxDepth-nDepth)%2);
    else 
		EnterHashTable(upper_bound,current,nDepth,(m_nMaxDepth-nDepth)%2);

	return current;//返回極大值 /邊界
}