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


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



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

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

CGSESearchEngine::~CGSESearchEngine()
{
}
void CGSESearchEngine::BoardCopy(BYTE desbyBoard[][3],BYTE srcbyBoard[][3])
{
	int i,j;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			desbyBoard[i][j]=srcbyBoard[i][j];
		}
	}
}

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

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

	//已得出目標狀態
	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;
		BoardCopy(m_pMG->m_MoveList[m_iPly][iNodes].byBoard,byBoard);
		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;
		BoardCopy(m_pMG->m_MoveList[m_iPly][i].byBoard,byBoard);
		m_queueMove.push(m_pMG->m_MoveList[m_iPly][i]);		//與另一個不同的m_queueMove
	}

	while(!m_queueMove.empty())
	{
		iPly=m_queueMove.front().iPly;
		
		//--------遍歷隊列中同一層的走法,找出走法的最佳值--------
		iSmallest=10;
		while(iPly==m_queueMove.front().iPly)
		{
			MakeMove(m_queueMove.front().byBoard,m_queueMove.front());
			iTemp=m_pEval->Evaluate(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;
		}
		//-------------------------------------------------------


		//---------------將好的走法的子節點入隊列----------------
		iNodes=0;
		while(iPly==tempQueue.front().iPly)
		{
			cmParent=tempQueue.front();
			cmParentBackUp=cmParent;
			MakeMove(cmParent.byBoard,cmParent);
			iTemp=m_pEval->Evaluate(cmParent.byBoard);
			if(iTemp==iSmallest)
			{
				//產生子節點
				iCount=m_pMG->CreatePossibleMove(cmParent.byBoard,m_iPly+1);

				//已得出目標狀態
				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;
					BoardCopy(m_pMG->m_MoveList[m_iPly+1][iNodes].byBoard,cmParent.byBoard);
					cmLast=m_pMG->m_MoveList[m_iPly+1][iNodes];
					bIsOver=1;

					goto GetBestMove;
				}

				//將子節點入隊列
				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;
					BoardCopy(m_pMG->m_MoveList[m_iPly+1][i+iNodes].byBoard,cmParent.byBoard);
					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++;
		//cout<<m_iPly<<"  ";
	}
	cout<<"sorry!con't find the solution!"<<"    ";

GetBestMove:
	//得出最佳走法隊列
	if(bIsOver)
	{
		BoardCopy(cmTemp.byBoard,cmLast.byBoard);
		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];
		}
	}
	
}