transpositiontable.cpp

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

// TranspositionTable.cpp: implementation of the CTranspositionTable class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "TranspositionTable.h"

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

CTranspositionTable::CTranspositionTable()
{
	InitHashKey();
}

CTranspositionTable::~CTranspositionTable()
{

}

//生成32位随机数
LONG CTranspositionTable::Rand32()
{
    return rand()^((LONG)rand()<<15)^((LONG)rand()<<30);
}

void CTranspositionTable::InitHashKey()
{
	int i,j,k;
	
	srand((unsigned)time(NULL));
	
	//填充随机数组
	for(i=0;i<10;i++)
		for(j=0;j<3;j++)
			for(k=0;k<3;k++)
				m_nHashKey32[i][j][k]=Rand32();
}

void CTranspositionTable::EnterHashTable(BYTE byBoard[][3])
{
	int iPos=CalHashKey(byBoard);

	if(m_byBoardList[iPos][0][0]>=9 || m_byBoardList[iPos][0][0]<0)
		goto Copy;

	while(m_byBoardList[iPos][0][0]<9 && m_byBoardList[iPos][0][0]>=0)
		iPos=(iPos+1)%1000;

Copy:
	memcpy(m_byBoardList[iPos],byBoard,9);
}

bool CTranspositionTable::LookUpHashTable(BYTE byBoard[][3])
{
	int iPos=CalHashKey(byBoard);

	if(m_byBoardList[iPos][0][0]>=9 || m_byBoardList[iPos][0][0]<0)
		return 0;

	if(memcmp(m_byBoardList[iPos],byBoard,9))
	{
		int iPosBU=iPos;

		while(memcmp(m_byBoardList[iPos],byBoard,9) && iPosBU!=iPos)
			iPos=(iPos+1)%1000;

		if(memcmp(m_byBoardList[iPos],byBoard,9))
			return 0;

		return 1;
	}

	return 1;
}

UINT CTranspositionTable::CalHashKey(BYTE byBoard[][3])
{
	UINT uiRet=0;

	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			uiRet+=m_nHashKey32[byBoard[i][j]][i][j];

	return uiRet%1000;
}