// MoveGenerator.cpp: implementation of the CMoveGenerator class.
//
//////////////////////////////////////////////////////////////////////


#include "EightNum.h"
#include "MoveGenerator.h"

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

CMoveGenerator::CMoveGenerator()
{
	m_nMoveCount=0;
	m_iCurPly=0;
	m_pEval=new CEvaluation;
}

CMoveGenerator::~CMoveGenerator()
{

}

int CMoveGenerator::CreatePossibleMove(BYTE byBoard[][3],int iPly)
{
	CHESSMOVE cm;
	int i,j;
	int iCount=0;
	int iSmallest=10;
	int iTemp;
    
	//清空隊列
	while(!m_queueMove.empty())
		m_queueMove.pop();

	if(m_iCurPly!=iPly)
		m_nMoveCount=0;
	m_iCurPly=iPly;

	//找到空格所在位置
	cm.iPly=iPly;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(byBoard[i][j]==0)
			{
				cm.cpFrom.x=i;
				cm.cpFrom.y=j;
				goto Move;
			}

Move:
	//空格向上移
	if(i-1>=0)
	{
		cm.cpTo.x=i-1;
		cm.cpTo.y=j;

		MakeMove(byBoard,cm);
		iTemp=m_pEval->Evaluate(byBoard);
		UnMakeMove(byBoard,cm);

		if(iTemp<iSmallest)			//如果此種走法比先前的走法代價小，則存儲此種走法
		{
			m_queueMove.push(cm);    //存儲此種走法
			iSmallest=iTemp;

			//已達到目標狀態
			if(!iSmallest)
			{
				AddMove(cm,iPly);
				return 0;
			}
		}
	}

	//空格向右移
	if(j+1<3)
	{
		cm.cpTo.x=i;
		cm.cpTo.y=j+1;

		MakeMove(byBoard,cm);
		iTemp=m_pEval->Evaluate(byBoard);
		UnMakeMove(byBoard,cm);

		if(iTemp<iSmallest)
		{
			m_queueMove.push(cm);
			iSmallest=iTemp;

			//已達到目標狀態
			if(!iSmallest)
			{
				AddMove(cm,iPly);
				return 0;
			}
		}
	}

	//空格向下移
	if(i+1<3)
	{
		cm.cpTo.x=i+1;
		cm.cpTo.y=j;

		MakeMove(byBoard,cm);
		iTemp=m_pEval->Evaluate(byBoard);
		UnMakeMove(byBoard,cm);

		if(iTemp<iSmallest)
		{
			m_queueMove.push(cm);
			iSmallest=iTemp;

			//已達到目標狀態
			if(!iSmallest)
			{
				AddMove(cm,iPly);
				return 0;
			}
		}
	}

	//空格向左移
	if(j-1>=0)
	{
		cm.cpTo.x=i;
		cm.cpTo.y=j-1;

		MakeMove(byBoard,cm);
		iTemp=m_pEval->Evaluate(byBoard);
		UnMakeMove(byBoard,cm);

		if(iTemp<=iSmallest)		//why only this place use "=" differing from other three places
		{
			m_queueMove.push(cm);
			iSmallest=iTemp;

			//已達到目標狀態
			if(!iSmallest)
			{
				AddMove(cm,iPly);
				return 0;
			}
		}
	}

	while(!m_queueMove.empty())
	{
		MakeMove(byBoard,m_queueMove.front());
		if(m_pEval->Evaluate(byBoard)==iSmallest) //僅生成代價最小的節點
		{
			iCount++;
			AddMove(m_queueMove.front(),iPly);
		}
		UnMakeMove(byBoard,m_queueMove.front());
		m_queueMove.pop();
	}

	return iCount;		//返回當前狀態具有最小代價的擴展節點數
}

void CMoveGenerator::AddMove(CHESSMOVE cm,int iPly)
{	
	m_MoveList[iPly][m_nMoveCount]=cm;
	m_nMoveCount++;
}

void CMoveGenerator::MakeMove(BYTE byBoard[][3],CHESSMOVE cm)
{
	BYTE byTemp;

	byTemp=byBoard[cm.cpFrom.x][cm.cpFrom.y];
	byBoard[cm.cpFrom.x][cm.cpFrom.y]=byBoard[cm.cpTo.x][cm.cpTo.y];
	byBoard[cm.cpTo.x][cm.cpTo.y]=byTemp;
}

void CMoveGenerator::UnMakeMove(BYTE byBoard[][3],CHESSMOVE cm)
{
	MakeMove(byBoard,cm);
}

bool CMoveGenerator::IsValidMove(BYTE byBoard[][3], int x,int y)
{
	int i,j;

	//找到空格所在位置
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(byBoard[i][j]==0)
				goto Next;

Next:
	if(abs(x-i)+abs(y-j)==1)
		return 1;

	return 0;
}

/*int CMoveGenerator::Existed(CHESSMOVE m_MoveList[][800],CHESSMOVE cm,int iPly)
{   
		for(int j=0;j<=800;j++)
		{
			if(!memcmp(m_MoveList[iPly][j].byBoard,cm.byBoard,9))
                 return 1;
		}
		return 0;
}*/