Thomas E. Allen, Andrew A. Ward, Judy Goldsmith, and Nahom Muluneh
| Summary | Use Prolog to navigate a maze, avoiding or overcoming obstacles and enemies and accumulating treasure. |
| Topics | Prolog, planning, introductory logic programming. |
| Audience | Undergraduate students in an introductory AI class. |
| Difficulty | For students unfamiliar with Prolog, this is a very challenging assignment. It is broken into two pieces to amortize the difficulty of getting started in the language and shifting from imperative paradigms to declarative. |
| Strengths | The D&D setting amuses students and gives them a sense of accomplishment. Practical (or at least programming) application of logic, resolution, and knowledge representation. |
| Weaknesses | Prolog. It's a very finicky language. And "intuitive programmers" can't. |
| Dependencies | Understanding of recursion, resolution, list processing in Prolog. Prolog implementations are available for most major operating systems. |
| Variants | Can change theme from "dungeon" to treasure hunt, zombie apocalypse, etc. Can change number and names of props. |
Our Artificial Intelligence survey course includes units on Propositional Logic, Predicate Logic, Situation Calculus, and Resolution. As an application of this material, we introduce Prolog. Our students, mostly undergraduate juniors and seniors, have had success with Python and C++. Often, however, they find Prolog bewildering. “How do I write a loop?” they ask us. “How do I assign X a new value?!”
We present an assignment with a theme inspired by Tolkien and “D&D” style role-playing games: Students' implement a simple maze and a character that navigates through it, avoiding enemies and obstacles and searching for treasure. In the first assignment, students only implement the maze and show that their character can navigate through it in a manner that does not involve infinite recursive descent. In the second, we introduce treasure guarded by enemies. By breaking the assignment in two, and going through solutions of the first part, students are more likely to succeed in the second part, and thus feel a sense of accomplishment. The assignment is also easily adapted from semester to semester to incorporate different themes and challenges.