movegenerator.cpp

本程序采用全局择优的启发式搜索算法来解决人工智能中的八数码难题。

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

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

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

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

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

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->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++;
			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;
}