TL;DR
This paper introduces a novel curriculum for introductory AI courses centered around the classic game Pac-Man. By using a consistent, engaging domain, the authors demonstrate a more effective way to teach foundational AI concepts like search, multi-agent systems, and probabilistic inference, leading to increased student engagement and improved learning outcomes.
What Problem Does This Paper Address?
Introductory AI courses often present a fragmented collection of topics, making it difficult for students to grasp how different AI concepts connect and apply to real-world problems. This incoherence can lead to disengagement and a superficial understanding of the material. The authors sought to create a more unified and engaging learning experience by using a single, compelling domain – Pac-Man – to illustrate a broad range of AI techniques.
Methods
The core of the paper describes a series of four integrated programming projects designed to teach key AI concepts:
- State-Space Search: Students implement algorithms like depth-first, breadth-first, uniform-cost, and A* search to solve navigation and Traveling Salesman Problem (TSP)-like challenges within Pac-Man mazes.
- Multi-Agent Search: This project introduces minimax and expectimax algorithms for adversarial and stochastic search, requiring students to design evaluation functions for limited-depth search.
- Probabilistic Tracking: A novel Pac-Man variant is introduced where Pac-Man hunts unobserved ghosts that provide noisy location observations. Students implement exact and approximate inference for Hidden Markov Models and Dynamic Bayes Nets.
- Reinforcement Learning: Students implement model-based and model-free reinforcement learning algorithms, including value iteration, Q-learning, and Q-learning with linear function approximation, applied to gridworld and Pac-Man.
A key methodological aspect is the extensive use of scaffolding code, providing students with graphics, game mechanics, and utility classes to focus on AI implementation rather than software engineering. Visualization is heavily integrated, allowing students to see their algorithms in action, aiding debugging and understanding. The projects also emphasize generality, requiring students to implement algorithms against abstract interfaces that can be applied to multiple problem instances beyond Pac-Man.
Datasets
The paper does not discuss traditional datasets for training or evaluation. Instead, it introduces and utilizes the Pac-Man environment itself as a dynamic benchmark. This environment is adapted to create specific problem instances for each project, including:
- Simple maze navigation and all-dots search problems.
- A TSP-like problem for finding paths through all food dots.
- A multi-agent adversarial/stochastic game with parameterized ghost behaviors.
- A probabilistic tracking scenario with unobserved ghosts and noisy observations.
- A gridworld environment (from Russell and Norvig's textbook) and a simulated robot controller for reinforcement learning.
- An 8-puzzle for testing search algorithm generality.
Key Insights and Ideas
- The Power of a Unified Domain: Using a single, engaging domain like Pac-Man significantly enhances student motivation and helps them see the connections between disparate AI topics.
- Scaffolding is Crucial for Focus: Providing substantial starter code allows students to concentrate on the core AI concepts rather than getting bogged down in implementation details.
- Visualization as a Debugging and Learning Tool: Visualizing algorithm execution provides immediate feedback, making debugging easier and deepening conceptual understanding.
- Generality is Key: Requiring students to apply algorithms to multiple problem instances (beyond Pac-Man) reinforces the idea that AI techniques are broadly applicable.
- Optional Contests Drive Engagement: Well-designed, optional contests that extend the core projects foster creativity and allow advanced students to showcase their talents without penalizing others.
- Absolute Grading Promotes Collaboration: Shifting from relative to absolute grading significantly increased informal collaboration and peer support.
Key Results
The paper reports overwhelmingly positive responses from students, with 65% citing the course projects as the best aspect of the course. The introduction of these projects led to a dramatic increase in course enrollment (69% in the first semester, over 100% increase in three years). Student ratings for the course's usefulness and effectiveness have also consistently increased. The authors also note that over ten universities have adopted these Pac-Man projects.
Limitations and Future Work
- Potential for Domain Over-Reliance: While the authors emphasize generality, there's an inherent risk that students might over-specialize in the Pac-Man domain and not fully appreciate the broader applicability of the algorithms. The paper addresses this by requiring solutions for other problem instances.
- No Contest for Probabilistic Tracking: The authors mention that there is currently no contest extension for the probabilistic tracking project, as they focus student energy on an integrative multi-agent contest. Future work could involve developing such a contest.
- Further Integration: The authors express interest in supporting other universities in adopting and extending these projects, suggesting a future of broader integration and refinement of the Pac-Man curriculum across the AI education landscape. They also aim to continue improving and expanding the coverage of AI topics within the Pac-Man framework.
Summary updated