[Search_5] Finding All the Corners (1)

※ 이 글은 "UC Berkeley CS188 Intro to AI"의 "Project 1: Search"를 해결하는 과정을 정리한 글입니다.

 

Finding All the Corners

A* 탐색 알고리즘의 진정한 힘은 좀 더 도전적인 탐색 문제를 통하여 명확하게 드러날 것입니다. 이제 새로운 문제를 만들고 새로운 문제에 적용하기 위한 휴리스틱을 구상해야 할 시간입니다.

 

corner mazes는 각 코너마다 4개의 점이 있습니다. 새로운 탐색 문제는 미로에서 모든 코너들을 지날 수 있는 최단 경로를 찾는 것입니다. tinyCorners와 같은 몇몇의 미로에서 확인할 수 있듯이, 가장 짧은 길은 항상 가장 가까운 음식으로 가는 길이 아닐 수 있음을 명심해야 할 것입니다. 참고로, tinyCorners에서 최단 경로는 28번의 움직임이 필요합니다.

 

참고로 이번 문제는 너비 우선 탐색 (Breadth First Search, BFS)에서 구현한 코드가 필요하기 때문에, 이번 문제를 풀기 전에 너비 우선 탐색 문제를 먼저 수행하여야 합니다.

 

searchAgents.py 파일안에 있는 CornersProblem 탐색 문제를 구현하십시오. 이를 위해서는 4개의 코너에 모두 도달을 했는지를 추적하는데 필요한 모든 정보를 표현할 수 있는 상태 표현을 선택 후 사용하여야 합니다. 이제 팩맨은 아래의 문제를 해결해야 합니다.

- python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs, prob=CornersProblem

 

python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem 실행 시 시작되는 게임 화면

python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem 실행 시 출력 화면

 

- python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs, prob=CornersProblem

 

python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem 실행 시 시작되는 게임 화면

python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem 실행 시 출력 화면

 

전체 점수를 받기 위해서는, 상관없는 정보(유령의 위치, 추가적인 음식의 위치 등)를 표현하지 않은 추상적 상태 표현을 정의해야만 합니다. 하지만 팩맨의 GameState를 탐색 상태로 사용해서는 안됩니다. 만약 사용하였다면 구현된 코드는 매우 느리게 작동할 것입니다.

 

구현된 코드의 게임 상태를 위해서 참조해야 하는 것은 시작할 때의 팩맨의 위치와 4 코너의 위치입니다.

 

mediumCorners에 이전에 구현했었던 breadthFirstSearch를 적용시켜보니 탐색 노드는 2000개 이하로 확장되었음을 확인할 수 있었습니다. 하지만 휴리스틱을 사용한다면 탐색하는데 요구되는 양을 더욱 줄일 수 있을 것입니다.