A* 알고리즘을 이용한 하노이 타워 풀기

 

A* 알고리즘을 이용해서 일반적으로는 길찾기를 많이 합니다.  A* 알고리즘은 적절한 에너지 함수만 제공해준다면, 최적의 해를 적은 노드 탐방으로 찾을 수 있는 장점이 있습니다.

 

그러나 적절한 에너지 함수를 제공할 수 없는 경우에는, A* 알고리즘은 상당히 많은 시간을 소모할 수 있고, 또한 최적의 해를 찾을 수 없을 수도 있습니다.

 

1) 에너지 함수가 실제 소요되는 것보다 상대적으로 너무 적을 때에는 많은 노드를 탐방하게 됩니다.

2) 에너지 함수가 실제 소요되는 것보다 더 많을 가능성이 아주 조금이라도 있다면, 최적의 해를 찾는다는 보장을 할 수 없습니다.

 

제가 A* 알고리즘을 조금 더 관심있게 보고 있는 것은 바로 2)항 때문입니다.  게임 AI 로직에서 최적의 해를 꼭 찾아야한다고 볼 수 없습니다.

 

요즘 또 관심있게 보고 있는 것이 딥러닝(Deep Learning)입니다.  이 화두가 또 언제 사그라들지는 모르겠지만, 빅데이터와 관련해서도 앞으로 전망이 꽤 있을 것이라 생각합니다.

 

제가 관점을 가지는 부분도 딥러닝입니다.  사실 우리가 무언가를 판단할 때, 순간적인 판단과 그와 엮인 순차적인 방법을 생각합니다.  그런데 A* 알고리즘은 유용한 순차적인 방법을 제공할 수 있지 않을까 하네요.  또한 에너지 함수를 딥러닝과 같이 학습을 할 수 있게 한다면, 적절한 에너지 함수를 제공할 수 있을 것이라고 생각합니다.  뭐 이 이야기는 각설하고,

 

하노이 타워는 3개의 기둥을 가지고 있는 경우에는 제일 빠른 해가 이미 결정되어 있습니다.

하노이 타워는 4개의 기둥 이상이라면, 아직은 열려있는 문제입니다.  이 문제를 풀기 위해서는 휴리스틱 알고리즘과 최적의 해를 찾으려면, 무언가 다른 방법이 필요하겠죠.  저는 여기서 A* 알고리즘을 채용해보았습니다.

 

그동안은 제가 텍스트 모드로 프로그램을 제작해왔는데, 이번에는 윈도즈로 작성을 해보았습니다.

 

 

 

하노이 타워의 원 문제인 3개의 기둥일 때입니다.  8개의 디스크가 있을 때, 우리는 255번의 움직임으로 디스크를 왼쪽에서 오른쪽으로 옮길 수 있습니다.

 

 

 

4개의 기둥에 8개의 디스크를 움직였을 때의 결과입니다.  총 33번의 움직임으로 이 디스크들을 다 옮길 수 있습니다.  그런데, 이것을 계산하기 위해서는 꽤 많은 시간을 소모합니다.  A* 알고리즘에서 61,793개의 노드를 탐색했으니까요.  원인은 당연히 에너지 함수에 있다고 생각했습니다.  (사실 거의 근접한 에너지 함수를 쓴다고 해도, 하노이 타워의 경우에는 꽤 많은 노드를 탐색할 수밖에 없습니다.)

 

에너지 함수는 애시당초 다음과 같이 설정했었습니다.  이 방법을 SImple이라고 이름 붙였습니다.

1) 목적지 기둥의 디스크는 에너지 0

2) 목적지 기둥외의 디스크들은 에너지 1

 

그래서 초기 상태에서는 8개의 디스크가 첫번째 기둥에 있었기 때문에 에너지 함수값은 8이 됩니다.  이 방법은 너무나 비슷한 값의 에너지 함수들을 가지고 있기 때문에, 상당히 많은 노드를 탐색해야 합니다.  그래서 새로운 에너지 함수를 만들었습니다.

 

k개의 기둥에 n개의 디스크가 있을 때, n < k 라면 2n-1번의 디스크 이동횟수가 필요하다는 기본적인 원리를 이용했습니다.  n >= k 인 경우에는 더 많은 이동횟수가 필요하지만, 일단 이것은 무시했습니다.

 

목적지 기둥에 가장 큰 디스크부터 차례로 쌓여있는 것은 더 이상 이동할 필요가 없지만, 더 큰 디스크가 밑에 없는 상태에서 작은 디스크들만 있는 경우에는 반드시 작은 디스크들은 다른 기둥에 갔다가 와야 합니다.

 

이 두가지 원리를 적용한 에너지 함수 방법을 Complex라고 이름 붙였습니다.

1. 목적지 기둥에서는 가장 큰 디스크가 차례로 있는 것들은 에너지 0

2. 그 외의 디스크들은 에너지 2

3. 목적지 기둥외의 디스크들의 수가 m이라면, 이 기둥의 에너지는 2m-1

 

 

 

Complex 에너지 함수를 적용했을 때의 결과입니다.  이동횟수는 당연히 같은 값이 나오지만, 탐색한 노드 수는 18,937개입니다.  첫번째 방법보다 엄청나게 줄어든 것을 알 수 있습니다.

좀 더 복잡하게 만들면, 더 좋은 결과를 내겠죠.  예를 들어서 n >= k 일 때의 에너지 함수를 적용하면요.

 

기둥수가 늘어나고, 디스크 갯수가 늘어남에 따라서 A* 알고리즘이 탐색해야하는 노드들의 갯수는 기하급수적으로 늘어납니다.  기둥이 5개이고, 디스크가 10개일 때는 다음과 같습니다.

 

 

 

A* 알고리즘이 탐색한 노드의 갯수가 무려 206,851 개나 됩니다.  사실 시간도 꽤 걸립니다.

 

 

 

다음은 핵심이 되는 프로그램 소스 부분입니다.

 

[HanoiNode class]

class HanoiNode : public PQueue::Node
{
public:
	HanoiNode(char *cdisks, int cvalue) : value(cvalue), visited(false)
	{
		disks = new char[numDisks];
		memcpy(disks, cdisks, numDisks*sizeof(char));
		est = 0;
		if( method == 0 )
		{
			for( int i = 0 ; i < numDisks ; i++ ) est += disks[i] != 1;
		}
		else if( method == 1 )
		{
			int i;
			int k = 0;
			est = 0;
			for( i = numDisks-1 ; disks[i] == 1 && i >= 0 ; i-- ) ;
			for( ; i >= 0 ; i-- ) est+=2, k |= 1<<disks[i];
			for( i = 0 ; i < numPegs ; i++ )
			{
				if( i != 1 && (k & (1<<i)) ) est--;
			}
		}
	}

	virtual ~HanoiNode()
	{
		if( disks ) delete[] disks;
	}

	virtual bool Compare(const Node *node)
	{
		const HanoiNode *cnode = (const HanoiNode *)node;
		return( value+est <= cnode->value+cnode->est );
	}

	static void SetHanoi(int np, int nd, int m)
	{
		numPegs = np;
		numDisks = nd;
		method = m;
	}

public:
	static int numPegs, numDisks, method;
	char *disks;
	int value, est;
	HanoiNode *from;
	int cmd[2];
	bool visited;
	HanoiNode *next;
};

 

위 노드는 앞에 게시물에 올려드린 PQueue 클래스에서 정의된 노드를 상속받은 것입니다.

 

[SolveHanoi()]

void SolveHanoi(void *args)
{
	HanoiParams *param = (HanoiParams *)args;
	param->numNodes = 0;
	param->numResult = 0;

	PQueue queue;
	HanoiNode *hash[HASHSIZE];

	HanoiNode::SetHanoi(param->numPegs, param->numDisks, param->method);

	memset(hash, 0, sizeof(hash));

	char *disks = new char[param->numDisks];
	memset(disks, 0, param->numDisks*sizeof(char));

	HanoiNode *node = new HanoiNode(disks, 0);
	param->numNodes++;
	queue.Add(node);
	AddHash(hash, node);
	node->from = (HanoiNode *)0;

	while( queue.IsEmpty() == false )
	{
		node = (HanoiNode *)queue.GetTop();
		node->visited = true;

		if( node->est == 0 ) break;

		for( int i = 0 ; i < param->numPegs ; i++ )
		{
			int c;
			for( c = 0 ; node->disks[c] != i && c < param->numDisks ; c++ ) ;
			if( c == param->numDisks ) continue;

			for( int j = 0 ; j < param->numPegs ; j++ )
			{
				if( i == j ) continue;

				int d;
				for( d = 0 ; node->disks[d] != j && d < c ; d++ ) ;
				if( d < c ) continue;

				memcpy(disks, node->disks, param->numDisks*sizeof(char));
				disks[c] = j;
				HanoiNode *t = FindHash(hash, disks);
				if( !t )
				{
					t = new HanoiNode(disks, node->value+1);
					param->numNodes++;
					queue.Add(t);
					AddHash(hash, t);
					t->cmd[0] = i;
					t->cmd[1] = j;
					t->from = node;
				}
				else if( t->visited == false && node->value + 1 < t->value )
				{
					t->value = node->value+1;
					queue.Add(t);
					t->cmd[0] = i;
					t->cmd[1] = j;
					t->from = node;
				}
			}
		}
	}

	int resultNum = 0;
	param->result = new int[node->value*2];
	for( HanoiNode *t = node ; t->from ; t = t->from, resultNum++ )
	{
		param->result[resultNum*2+0] = t->cmd[0];
		param->result[resultNum*2+1] = t->cmd[1];
	}
	param->numResult = resultNum;

	delete[] disks;

	for( int i = 0 ; i < HASHSIZE ; i++ )
	{
		while( hash[i] )
		{
			HanoiNode *t = hash[i];
			hash[i] = t->next;
			delete t;
		}
	}
}