gsesearchengine.cpp

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

// 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;//记录同一层节点中的最小值
	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;
		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;
		
		//--------遍历队列中同一层的走法,找出走法的最佳值--------
		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;
		}
		//-------------------------------------------------------


		//---------------将好的走法的子节点入队列----------------
		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)
			{
				//产生子节点
				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;
					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;
				}

				//将子节点入队列
				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:
	//得出最佳走法队列
	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];
		}
	}
}