Project in a Nutshell
In the game of Pacman, finding the shortest path to collect all the pellets is a complex mathematical challenge. Traditionally, AI is given fixed rules (e.g., “go to the nearest pellet”).
Our approach: We created an AI that teaches itself to estimate a maze’s difficulty by observing thousands of games. It’s much like a human player who, with a single glance, “feels” which side of the board will take the longest to clear before even making a move.
How Does the AI Learn?
To make Pacman “intelligent,” we followed a three-step process based on the famous research environment from the University of California, Berkeley.
1. Observation (The Database)
We had a “perfect” (but very slow and heavy) AI play through 500 different mazes. For each game, we recorded:
- The position of the pellets.
- The exact number of steps it took to win.
This served as our “exercise book” containing optimal solutions.
2. Clues (The “Features”)
The AI doesn’t look at the screen the way we do. It analyzes key figures to understand the situation:
- Dispersion: Are the pellets clustered or scattered to the four corners?
- Distance: How far away is the furthest pellet?
- Mass: Where is the largest cluster of food located?
3. Intuition (The Predictive Model)
Using these clues, we trained a digital brain (a Regression model) capable of predicting the final score without having to play the game. This is known as a learned heuristic.
Results: Has Pacman Become an Expert?
We compared our AI to the classic method that mathematically tests all possibilities before making a single move.
| Method | Intelligence / Intuition | Thinking Effort | Result |
|---|---|---|---|
| Classic Method | No intuition | Huge (overthinks) | Perfect, but very slow. |
| Our AI (Learned) | Strong intuition | Very low (fast) | Near-perfect and ultra-fast. |
The Major Finding: Our AI manages to find the optimal path in the vast majority of cases while thinking 10 times less than the classic method. It now possesses an “internal compass.”
Key Takeaways
- Intuition can be calculated: You can transform an experienced player’s “feeling” into mathematical equations.
- Simple and Effective: Our simplest model (Linear Regression) performed better than complex models because it is more stable and less prone to interpretation errors.
- Real-time Savings: By allowing the AI to “guess” the distance instead of calculating it precisely, we free up power to handle other tasks, such as avoiding ghosts.
Conclusion
By modifying and expanding upon the original Berkeley project, we proved that an agent can become autonomous—not by following human-dictated rules, but by learning from its own experience. Pacman no longer just follows orders; he anticipates the complexity of his mission.
Project by: Zakary Dujardin & Maël Goareguer
Context: IFT-4102/7025 - Université Laval