※ 이 글은 "UC Berkeley CS188 Intro to AI"의 "Project 1: Search"를 해결하는 과정을 정리한 글입니다.
Varying the Cost Function
너비 우선 탐색(Breadth First Search, BFS)은 목표지점으로 가는 최단 경로를 찾을 수 있지만, 최단 경로와 최고의 경로는 다를 수 있습니다. mediumDottedMaze와 mediumScaryMaze 같은 경우를 고려해봅시다.
cost function을 변화한다면 팩맨이 다른 경로를 탐색할 수 있게 만들 수 있습니다. 예를 들어 유령이 많은 지역에서 움직일 때 많은 비용을 책정할 수 있고 먹을 것이 많은 지역에서 움직일 때 적은 비용을 책정할 수 있습니다. 팩맨을 합리적으로 움직이려면 이와 같은 다양한 조건들에서의 움직임을 정의해주어야 합니다.
search.py 파일에 들어있는 uniformCostSearch 함수 안에 균일 비용 탐색 (Uniform Cost Search, UCS) 알고리즘을 구현하십시오. 알고리즘 구현에 유용하게 사용할 수 있는 데이터 구조는 util.py 파일 내부에서 확인할 수 있습니다. 구현이 완료되었다면 서로 다른 3개의 게임에서 균일 비용 탐색이 적용된 팩맨이 잘 움직이는 지를 확인해야 합니다. 각각의 게임에서는 cost function들만 다르게 설정되어 있습니다.
- python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
- python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
- python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
알고리즘이 잘 구현되었다면 StayEastSearchAgent에서는 매우 작은 비용을, StayWestSeatchAgent에서는 기 매우 큰 비용을 얻을 수 있을 것입니다.
'UC Berkeley CS188 Intro to AI > [Pacman Project 1] Search' 카테고리의 다른 글
| [Search_4] A* search (1) (0) | 2022.05.22 |
|---|---|
| [Search_3] Varying the Cost Function (2) (0) | 2022.05.21 |
| [Search_2] Breadth First Search (2) (0) | 2022.05.19 |
| [Search_2] Breadth First Search (1) (0) | 2022.05.18 |
| [Search_1] Finding a Fixed Food Dot using Depth First Search (2) (0) | 2022.05.17 |