우리는 도망자-추적자 게임 풀이에 관심이 많다. 도망자가 추적자를 피해 미로를 탈출하는 게임이다. 도망자가 추적자를 유인하기도 하고 벽을 이용해 교묘히 피하기도 한다. 경험에 의하면 수작업으로 풀기에는 매우 어려운 단계들도 있었다. 게임을 풀기 위한 방법으로 모델 체킹 기법을 사용하였다. 모델 체킹은 게임의 모든 상태 공간을 넓이 우선 방식으로 철저하게 탐색하기 때문에 게임을 풀 수 있는 가장 짧은 경로인 최적의 답을 구할 수 있다. 다행히 풀이 과정에서 상태 폭발 문제는 일어나지 않았고, 게임 풀이 결과를 임베디드 시스템인 레고 마인드스톰에 응용하였다. 도망자, 추적자에 해당하는 두 대의 에이전트를 만들어 게임을 구현하고 실험하여 풀이가 정확한 지를 실제 확인할 수 있었다.

본 논문에서는 반례를 도달성 게임 풀이에 활용했다. 도달성 게임이란, 게임 규칙을 준수하면서 초기 상태에서 목표 상태로 가는 경로를 찾는 것이다. 게임의 초기 상태를 유한 상태 모델로 표현하고 목표 상태의 부정(오답)을 시제 논리식으로 표현해서 모델 검사기에 입력하면, 반례로 오답에 대한 부정 즉 정답을 출력한다. 다시 말해서 반례로 출력된 것이 문제를 해결하는 정답인 것이다. 이와 같은 아이디어를 푸쉬푸쉬 게임 풀이에 적용했다. 그 결과 크기가 작은 푸쉬푸쉬 게임의 경우 게임을 해결하는 최단 경로를 쉽게 찾아냈다. 그러나 게임의 크기가 큰 경우 제한된 시간(실험에서는 3시간)내에 찾아내지 못했다. 왜냐하면 게임의 크기가 커질 경우 검사해야할 상태의 수가 지수적으로 증가하는 상태 폭발 문제가 발생했기 때문이다. 상태 폭발 문제를 해결하기 위해 추상화 기법을 이용해서 검사해야 할 상태공간을 축소하였다. 상태 공간을 줄인 결과, 기존 모델체킹으로 해결하지 못했던 게임을 풀 수 있었다.