Overview

Implemented a series of Pacman agents that can navigate maze environments efficiently and play competitively against ghost agents. The work combines classic search algorithms with adversarial decision-making to choose actions that maximize Pacman’s long-term reward.

Techniques & Concepts

• Search algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), Uniform Cost Search (UCS), and A* search for path planning.
• Heuristic design: Crafted admissible and consistent heuristics to improve A* performance.
• Adversarial search: Implemented minimax and expectimax agents for competitive and stochastic ghost behavior.
• Alpha–beta pruning: Optimized minimax search to explore deeper game trees within the same computation budget.
• Evaluation functions: Designed custom evaluation functions that balance survival, score, distance to food, and ghost proximity.

Result

Pacman agents can:

• Find shortest or cheapest paths through complex mazes.
• Play strongly against different ghost behaviors.
• Make decisions that trade off safety, score, and long-term outcomes.

What I Learned

• How to formalize game states, actions, and transition models.
• How search depth, branching factor, and heuristics impact performance.
• The differences between deterministic (minimax) and stochastic (expectimax) planning.