[Search_7] Eating All The Dots (1)

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

 

Eating All The Dots

이번에는 가능한 가장 적게 움직이면서 팩맨이 모든 음식을 먹을 수 있도록 만드는 어려운 난이도의 탐색 문제를 풀어야 합니다. 이를 위해서는 searchAgents.py 파일 안에 있는 FoodSearchProblem과 같이 음식을 먹을 수 있도록 하는 새로운 탐색 문제의 정의가 필요합니다. 가장 간단한 해결 방법은 모든 음식을 먹는 길을 정의하는 것입니다. 이번 과제에서는 유령이나 파워 알약 등을 고려하지 않고 오직 벽, 음식 그리고 팩맨의 위치 정보만 고려합니다. 만약 이전에 해결했었던 탐색 문제에서의 탐색 알고리즘을 정확하게 작성하였다면, null 휴리스틱을 사용하는 A* 탐색 알고리즘을 그대로 사용하더라도 testSearch에 대한 최적의 답을 빠르게 찾을 수 있을 것입니다.
- python pacman.py -l testSearch -p AStarFoodSearchAgent

 

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

python pacman.py -l testSearch -p AStarFoodSearchAgent 시작 시 출력 화면

 

위의 AStarFoodSearchAgent 는 아래의 명령어를 줄인 단축 명령어입니다.
- python pacman.py -l testSearch -p SearchAgent -a fn=astar,prob=FoodSearchProblem, heuristic=foodHeuristic

 

python pacman.py -l testSearch -p SearchAgent -a fn=astar,prob=FoodSearchProblem,heuristic=foodHeuristic 시작 시 실행되는 게임 화면

python pacman.py -l testSearch -p SearchAgent -a fn=astar,prob=FoodSearchProblem,heuristic=foodHeuristic 시작 시 출력 화면

 

겉보기에 단순해 보이는 tinySearch에서 균일 비용 탐색(Uniform Cost Search, UCS) 알고리즘의 실행 속도가 생각보다 느리다는 것을 확인할 수 있을 것입니다. 참고로, 5057개의 탐색 노드를 확장한 후 27의 길이를 가진 길을 찾는데 2.5초가 소요되어야 할 것입니다.

 

이번 문제는 A* 탐색에서 구현한 코드가 필요하기 때문에, 이번 문제를 풀기 전에 A* 탐색 문제를 먼저 수행하여야 합니다.

searchAgents.py 파일 안에 있는 FoodSearchProblem의 일관적 휴리스틱인 foodHeuristic을 완성하십시오. 그런 다음 trickySearch에서 아래와 같은 명령어를 시도해 보십시오.
- python pacman.py -l trickySearch -p AStarFoodSearchAgent

 

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

python pacman.py -l trickySearch -p AStarFoodSearchAgent 실행 시 출력 화면

 

UCS 탐색 알고리즘은 16000개 이상의 노드를 탐색하는데 13초 정도 걸려서 최적의 해답을 찾아내었습니다.

단순하지 않고 나쁘지 않은 일관성 있는 휴리스틱은 1점을 받을 수 있을 것입니다. 휴리스틱이 반드시 모든 goal state에서는 0을 반환하고 절대로 음수 값을 반환하지 않게 만드십시오. 휴리스틱에 따라 확장된 노드가 얼마나 되느냐에 따라 아래와 같은 점수를 받을 것입니다.

 

확장되는 노드에 따른 점수 표

 

만약 구현된 휴리스틱이 일관적이지 않을 경우 점수를 받지 못하니 조심하십시오. mediumSearch를 짧은 시간 안에 해결할 수 있겠습니까? 만약 그것이 가능하지 않다면 구현된 휴리스틱은 일관성이 있지 않음을 나타냅니다.