[Search_1] Finding a Fixed Food Dot using Depth First Search (1)

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

 

Finding a Fixed Food using Depth First Search

searchAgents.py 파일 안에는 미로에서의 경로를 계획하고 그 계획을 단계별로 실행할 수 있게끔 해주는 완벽하게 구현된 searchAgent를 찾을 수 있습니다. 하지만 계획을 세우기 위한 탐색 알고리즘들은 구현이 되어있지 않은데 이 알고리즘을 만드는 것이 해야 할 일입니다.

 

SearchAgent가 정확히 동작하는지는 아래의 명령어로 테스트를 할 수 있습니다.

- python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch

 

python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch 실행 시 시작되는 게임 화면

 

위의 명령어는 SearchAgent에게 search.py 에 구현되어 있는 tinyMazeSearh라는 탐색 알고리즘을 사용하라는 의미와 동일합니다. 아마 위의 명령어를 실행시킨다면 팩맨은 미로에서 길을 성공적으로 찾을 것입니다.

 

이제 구현되어 있는 탐색 함수를 사용하는 것이 아니라 계획하는 것을 실행할 새로운 탐색 함수를 작성해야 합니다. 탐색 알고리즘에 관한 의사 코드는 홈페이지의 강의 슬라이드에서 찾을 수 있습니다. 

 

탐색 함수를 작성하기 전 탐색 노드는 state 뿐만이 아니라 그 state에 도달하기 위한 길을 재구성하기 위해 필요한 정보들 또한 포함하고 있음을 기억해야 할 것입니다. 그리고 탐색 함수는 Agent를 시작 지점부터 목표지점까지 이끌어준 action 리스트를 반환해 줄 필요가 있습니다.

 

util.py 파일에는 스택, 큐, 우선순위 큐에 대한 데이터 구조가 구현되어 있는데 이것들을 사용하면 됩니다. 참고로 이곳에 구현되어 있는 데이터 구조들은 autograder와 호환되기 위해서 필요한 특정한 속성을 가지고 있기 때문에 나중에 autograder를 사용하기 위해서는 새로운 데이터 구조가 아닌 구현되어 있는 데이터 구조를 사용해야 합니다.

 

각각의 알고리즘은 매우 흡사한 모양을 가지고 있습니다. DFS, BFS, UCS, 그리고 A* 알고리즘은 어떻게 fringe를 관리하느냐에 대한 세부사항에서만 차이를 보입니다. 따라서 DFS를 정확하게 구현하는 것이 가능하다면 나머지는 간단하게 구현할 수 있을 것입니다.

 

하나의 구현은 특정한 알고리즘 큐 전략으로 구성된 하나의 탐색 함수를 요구합니다. 깊이 우선 탐색 알고리즘은 search.py 파일 안의 depthFirstSearch 함수 내부에 구현하면 됩니다. 알고리즘을 보다 완벽하게 구현하기 위해서 이미 방문한 적이 있는 state를 피하는 DFS의 그래프 탐색 버전을 작성해 보는 것도 좋습니다.

 

구현이 완료된 코드는 아래의 명령어에 대해서 빠르게 해결책을 찾아야 할 것입니다.

- python pacman.py -l tinyMaze -p SearchAgent

 

python pacman.py -l tinyMaze -p SearchAgent 실행 시 시작되는 게임 화면

python pacman.py -l tinyMaze -p SearchAgent 실행 시 출력 화면

 

- python pacman.py -l mediumMaze -p SearchAgent

 

python pacman.py -l mediumMaze -p SearchAgent 실행 시 시작되는 게임 화면

python pacman.py -l mediumMaze -p SearchAgent 실행 시 출력 화면

 

- python pacman.py -l bigMaze -z .5 -p SearchAgent

 

python pacman.py -l bigMaze -p SearchAgent 실행 시 시작되는 게임 화면

python pacman.py -l bigMaze -p SearchAgent 실행 시 출력 화면

 

코드를 실행하면 보이는 화면에서는 탐색한 states 들과 그것들을 탐색한 순서를 보여줍니다.(밝은 색은 먼저 탐색한 것을 의미합니다.) 만약 구현에 Stack을 사용하였다면 DFS 알고리즘을 mediumMaze에 적용시켰을 때 길이가 130이 나올 것입니다.(만약 246이 나왔다면 거꾸로 된 순서로 stack에 push 한 것입니다.) 만약 아니라면 깊이 우선 탐색에서 무엇이 잘못되었는지 다시 한번 생각해봐야 합니다.