팩맨

이 프로젝트는 인공지능 수업의 일환으로 진행한 UC Berkeley Pacman AI 프로젝트입니다. 이 과제의 핵심 목표는 **그래프 탐색(Graph Search)**의 기본이 되는 여러 알고리즘을 직접 구현하고, 이를 팩맨 게임 환경에 적용하여 실제 문제를 해결하는 것이었습니다.

search.py 파일에 범용 탐색 알고리즘들을 구현하고, searchAgents.py 파일에 팩맨의 특정 문제(Problem)들을 정의하고 해결하는 방식으로 진행했습니다.

1. 핵심 탐색 알고리즘 구현 (search.py)

먼저, 어떤 문제에도 적용할 수 있는 4가지 핵심 탐색 알고리즘을 구현했습니다.

• DFS (깊이 우선 탐색): Stack(스택) 자료구조를 사용하여 가능한 한 깊은 노드를 먼저 탐색하는 알고리즘입니다. 방문한 노드를 기록(explored)하여 무한 루프를 방지하는 그래프 탐색 방식으로 구현했습니다.
• BFS (너비 우선 탐색): Queue(큐) 자료구조를 사용하여 현재 노드에서 가장 가까운(얕은) 노드들을 먼저 탐색합니다. 이 방식은 경로의 비용이 모두 같을 때 최단 경로를 보장합니다.
• UCS (균일 비용 탐색): PriorityQueue(우선순위 큐)를 사용합니다. 각 경로의 ‘누적 비용(cost)‘을 우선순위로 하여, 항상 비용이 가장 적게 든 경로를 먼저 탐색합니다. 이를 통해 최단 비용의 경로를 보장합니다.
• A* (A-star) 탐색: UCS와 마찬가지로 PriorityQueue를 사용하지만, 우선순위를 ‘현재까지의 누적 비용($g(n)$)‘과 ‘목표까지의 추정 비용(휴리스틱, $h(n)$)‘의 합 ($f(n) = g(n) + h(n)$)으로 설정합니다. 정보에 기반한(informed) 탐색으로, UCS보다 훨씬 효율적으로 최적의 해를 찾아냅니다.

2. 팩맨 문제 정의 및 해결 (searchAgents.py)

단순히 알고리즘을 구현하는 것을 넘어, 팩맨이 직면한 복잡한 문제들을 ‘탐색 문제’로 모델링하고 해결했습니다.

📍 4개의 코너 방문 문제 (CornersProblem)팩맨이 맵의 네 귀퉁이에 있는 모든 점을 방문하는 경로를 찾는 문제입니다.

• 상태(State) 정의: 이 문제를 풀기 위해 상태 공간을 단순한 (x, y) 좌표가 아닌, (현재 위치, (방문한 코너 튜플))로 정의했습니다. 예를 들어, ((5, 5), (True, False, False, True))와 같이 현재 위치와 4개 코너의 방문 여부를 함께 기록했습니다.
• 목표(Goal) 정의: state[1]에 해당하는 튜플의 모든 값이 True가 되는 순간을 목표 상태로 설정했습니다. 후계자(Successor) 함수: 팩맨이 이동할 때마다, 새로 도착한 위치가 4개의 코너 중 하나인지 확인하고, 만약 코너라면 튜플의 해당 값을 True로 갱신한 새로운 상태를 생성하도록 구현했습니다.

💡 코너 문제 휴리스틱 (cornersHeuristic)

위의 코너 문제를 A* 탐색으로 풀기 위한 휴리스틱 함수를 직접 설계했습니다.

• 설계: 휴리스틱은 항상 실제 비용보다 낮거나 같아야 합니다(Admissible).
• 로직: ‘현재 위치’에서 ‘아직 방문하지 않은 모든 코너’까지의 맨해튼 거리(Manhattan Distance)를 각각 계산한 뒤, 그중 가장 큰(max) 값을 반환하도록 했습니다.
• 이유: 팩맨은 적어도 남아있는 코너 중 가장 먼 곳까지는 가야 모든 코너를 방문할 수 있으므로, 이 값은 항상 실제 남은 비용의 하한선이 되어 A*의 허용 가능한(admissible) 휴리스틱 조건을 만족합니다.

🍔 모든 음식 찾기 휴리스틱 (foodHeuristic)

맵에 흩어져 있는 모든 음식을 먹는 경로를 찾는 FoodSearchProblem을 위한 휴리스틱입니다.

• 로직: 코너 휴리스틱과 유사하게, ‘현재 위치’에서 ‘아직 먹지 않은 모든 음식’까지의 실제 미로 거리(mazeDistance)를 계산하고, 그중 가장 큰(max) 값을 반환했습니다.
• mazeDistance 활용: 맨해튼 거리와 달리, mazeDistance는 BFS를 기반으로 벽을 모두 고려한 실제 최단 거리를 반환해 주어 더 정확한 추정치를 제공합니다.

🎯 가장 가까운 음식 찾기 (ClosestDotSearchAgent)

모든 음식을 한 번에 찾는 것은 매우 복잡(NP-hard)하므로, ‘가장 가까운 음식을 찾아 먹는’ 과정을 반복하는 탐욕(Greedy) 알고리즘을 구현했습니다.

• findPathToClosestDot 구현: AnyFoodSearchProblem(어떤 음식이든 하나만 먹으면 성공)이라는 하위 문제를 정의했습니다.
• UCS 활용: 이 문제에 UCS를 적용하여, 현재 위치에서 가장 비용(거리)이 적게 드는 음식의 위치와 경로를 찾아 반환하도록 했습니다. (비용이 1로 동일하므로 BFS도 동일한 결과를 보장합니다.)