// AlphaBetaSearch.cpp: implementation of the CGSESearchEngine class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "EightNum.h"
#include "GSESearchEngine.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CGSESearchEngine::CGSESearchEngine()
{
	m_iPly=0;
	m_pMG=new CMoveGenerator;
	m_pEval=new CEveluation;
}

CGSESearchEngine::~CGSESearchEngine()
{
}

CGSESearchEngine::SearchAGoodMove(BYTE byBoard[][3])
{
	int i;
	int iPly=0;
	int iSmallest;//記錄同一層節(jié)點(diǎn)中的最小值
	int iTemp;
	queue<CHESSMOVE> tempQueue;
	int iCount;
	int iNodes=0;
	CHESSMOVE cmLast;//得到目標(biāo)狀態(tài)的最后一個(gè)走法
	CHESSMOVE cmTemp;
	CHESSMOVE cmParent;
	CHESSMOVE cmParentBackUp;
	bool bIsOver=0;//是否已得出目標(biāo)狀態(tài)

	iCount=m_pMG->CreatePossibleMove(byBoard,m_iPly,0);

	//已得出目標(biāo)狀態(tài)
	if(!iCount)
	{
		m_pMG->m_MoveList[m_iPly][iNodes].npParent=cmParentBackUp.npMe;
		m_pMG->m_MoveList[m_iPly][iNodes].npMe.byPly=m_iPly+1;
		m_pMG->m_MoveList[m_iPly][iNodes].npMe.byNum=iNodes;
		memcpy(m_pMG->m_MoveList[m_iPly][iNodes].byBoard,byBoard,9);
		cmLast=m_pMG->m_MoveList[m_iPly][iNodes];
		bIsOver=1;

		goto GetBestMove;
	}

	for(i=0;i<iCount;i++)
	{
		m_pMG->m_MoveList[m_iPly][i].npMe.byPly=m_iPly;
		m_pMG->m_MoveList[m_iPly][i].npMe.byNum=i;
		memcpy(m_pMG->m_MoveList[m_iPly][i].byBoard,byBoard,9);
		m_queueMove.push(m_pMG->m_MoveList[m_iPly][i]);
	}

	while(!m_queueMove.empty())
	{
		iPly=m_queueMove.front().iPly;
		
		//--------遍歷隊(duì)列中同一層的走法,找出走法的最佳值--------
		iSmallest=10;
		while(iPly==m_queueMove.front().iPly)
		{
			MakeMove(m_queueMove.front().byBoard,m_queueMove.front());
			iTemp=m_pEval->Eveluate(m_queueMove.front().byBoard);
			if(iTemp<iSmallest)
				iSmallest=iTemp;
			UnMakeMove(m_queueMove.front().byBoard,m_queueMove.front());
			tempQueue.push(m_queueMove.front());
			m_queueMove.pop();

			if(m_queueMove.empty())
				break;
		}
		//-------------------------------------------------------


		//---------------將好的走法的子節(jié)點(diǎn)入隊(duì)列----------------
		iNodes=0;
		while(iPly==tempQueue.front().iPly)
		{
			cmParent=tempQueue.front();
			cmParentBackUp=cmParent;
			MakeMove(cmParent.byBoard,cmParent);
			iTemp=m_pEval->Eveluate(cmParent.byBoard);
			if(iTemp==iSmallest)
			{
				//產(chǎn)生子節(jié)點(diǎn)
				iCount=m_pMG->CreatePossibleMove(cmParent.byBoard,m_iPly+1,cmParent.byDirect);

				//已得出目標(biāo)狀態(tài)
				if(!iCount)
				{
					m_pMG->m_MoveList[m_iPly+1][iNodes].npParent=cmParentBackUp.npMe;
					m_pMG->m_MoveList[m_iPly+1][iNodes].npMe.byPly=m_iPly+1;
					m_pMG->m_MoveList[m_iPly+1][iNodes].npMe.byNum=iNodes;
					memcpy(m_pMG->m_MoveList[m_iPly+1][iNodes].byBoard,cmParent.byBoard,9);
					cmLast=m_pMG->m_MoveList[m_iPly+1][iNodes];
					bIsOver=1;

					goto GetBestMove;
				}

				//將子節(jié)點(diǎn)入隊(duì)列
				for(i=0;i<iCount;i++)
				{
					m_pMG->m_MoveList[m_iPly+1][i+iNodes].npParent=cmParentBackUp.npMe;
					m_pMG->m_MoveList[m_iPly+1][i+iNodes].npMe.byPly=m_iPly+1;
					m_pMG->m_MoveList[m_iPly+1][i+iNodes].npMe.byNum=i+iNodes;
					memcpy(m_pMG->m_MoveList[m_iPly+1][i+iNodes].byBoard,cmParent.byBoard,9);
					m_queueMove.push(m_pMG->m_MoveList[m_iPly+1][i+iNodes]);
				}
				iNodes+=iCount;
			}
			UnMakeMove(cmParent.byBoard,cmParent);
			tempQueue.pop();

			if(tempQueue.empty())
				break;
		}
		//-------------------------------------------------------

		m_iPly++;
	}

GetBestMove:
	//得出最佳走法隊(duì)列
	if(bIsOver)
	{
		memcpy(cmTemp.byBoard,cmLast.byBoard,9);
		MakeMove(cmTemp.byBoard,cmLast);
		m_stackBestMove.push(cmTemp);
		m_stackBestMove.push(cmLast);
		while(memcmp(cmLast.byBoard,byBoard,9))
		{
			m_stackBestMove.push(m_pMG->m_MoveList[cmLast.npParent.byPly][cmLast.npParent.byNum]);
			cmLast=m_pMG->m_MoveList[cmLast.npParent.byPly][cmLast.npParent.byNum];
		}
	}
}