퍼즐환경에서 최적해 발견을 위한 휴리스틱 트리탐색 알고리즘

Abstract

퍼즐 게임 환경에서 에이전트가 시작 상태로부터 목표 상태에 도달하기 위한 경로를 찾는 방법으로 트리 탐색 기법을 사용한다. 대표적인 트리탐색 기법으로 Brute-force 탐색과 휴리스틱(heuristic) 탐색이 있다. Brute-force 탐색의 경우 노드의 확장 과정에서 목표 상태와 가까워졌는지 확인할 수 없기 때문에 문제에 대한 해를 제공하지만 너무 많은 노드를 확장하게 되므로 소모적인 방법이다. 반면 휴리스틱 탐색은 휴리스틱 평가 함수(evaluation function)를 통해 우선순위를 평가하여 가장 바람직한 자식 노드로 확장시켜 나가는 탐색 방법이다. 따라서 좋은 휴리스틱 평가 함수를 설계하는 것이 휴리스틱 탐색의 효율을 높일 수 있다. 탐색 과정에서 발생할 수 있는 Dead-end 및 교착상태(deadlock) 상태는 목표 상태에 도달하지 못하게 만드는 주요 원인이다. 되추적(backtracking)과정은 Dead-end 상태를 극복하는 좋은 방법이지만, 교착상태 발생 시 불필요한 되추적 과정이 반복되어 많은 비용을 소모하게 된다.본 논문에서는 퍼즐 게임 환경에서 허용 가능한 수준의 자원을 사용하여 목표 상태의 발견을 위한 알고리즘에 대하여 소개한다. 뿐만 아니라 체계적(systematic) 탐색 방법과 비체계적(nonsystematic) 탐색 방법을 비교 실험하여 최적 해를 발견위한 트리 탐색 알고리즘에 대하여 연구 하였다. 본 연구에서는 퍼즐 게임인 Prime Miner에서 휴리스틱 탐색의 성능을 측정하였고, 기존의 탐색 방법과 비교하여 성능 향상을 확인 하였다.