movegenerator_tt.cpp

八数码难题源代码

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

#include "stdafx.h"
#include "EightNum.h"
#include "MoveGenerator_TT.h"

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

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

CMoveGenerator_TT::CMoveGenerator_TT()
{
	m_nMoveCount=0;
	m_iCurPly=0;
	m_pEval=new CEveluation;
	m_pTT=new CTranspositionTable;
}

CMoveGenerator_TT::~CMoveGenerator_TT()
{
	delete m_pEval;
	delete m_pTT;
}

int CMoveGenerator_TT::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->Eveluate(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->Eveluate(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->Eveluate(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->Eveluate(byBoard);
		UnMakeMove(byBoard,cm);

		if(iTemp<=iSmallest)
		{
			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->Eveluate(byBoard)==iSmallest)
		{
			iCount++;

			if(!m_pTT->LookUpHashTable(byBoard))
			{
				AddMove(m_queueMove.front(),iPly);
				m_pTT->EnterHashTable(byBoard);
			}
		}
		UnMakeMove(byBoard,m_queueMove.front());
		m_queueMove.pop();
	}

	return iCount;
}