Adventures with Prolog: Entering the Dungeon Lord's Lair

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.


  1. Assignment One: Prolog
  2. Assignment Two: Epilog

Prolog Resources

  • Implementations (all are free for purposes of this class):