퍼즐 게임 환경에서 교착상태의 발견

Abstract

대부분의 퍼즐 게임에서 교착상태 문제는 플레이어를 목표상태에 도달하지 못하도록 만드는 중요한 문제 중 하나이다. 기존의 탐색 기법들은 교착상태를 발견하기 위한 알고리즘을 수행하는데 너무 많은 시간이 걸리거나 모든 교착상태를 발견할 수 있다는 보장이 없다. 본 논문에서는 이러한 문제점을 해결하기 위하여 그래프 기법과 Local search 기법, Pruning 기법을 적용한 새로운 발견 기법인 Cycle Detection을 제안한다. Cycle Detection은 퍼즐 게임의 현재 상태를 그래프 기법을 사용하여 표현하고 탐색 노드의 개수를 최소화하여 수행하며 교착상태를 발견한다. 본 기법의 성능 평가를 위해 실제 퍼즐게임 환경에서 알고리즘을 수행하였으며 실험 결과를 통해 기존의 방법과 비교하여 성능향상을 확인하였다.The presence of deadlock that prevents the game player from reaching the goal state is one of well-known problems in most puzzle games. Existing deadlock detection techniques take too much time to perform algorithms detecting the deadlock, or can not guarantee that the algorithms detect all the deadlock. In this paper, we introduce Cycle Detection, a new detection technique using Graph, Local search and Pruning techniques for solving these problems. Cycle Detection presents current state of puzzle games in a graph, detects deadlock by minimizing the number of detected nodes. We performed this algorithm in real puzzle game environment in order to evaluate performance of our algorithm. As a result, we identified significant performance improvement compared to existing deadlock detection techniques.