Instructions: Starting at the circled square in the upper-left corner, find a path to the goal square marked G.  From each numbered square, one may move that exact number of squares horizontally or vertically in a straight line.  How many moves does the shortest path have?

Solution (select to reveal): [19 moves: RDLRUDRLRLUDLDRRUDD]

Summary Rook Jumping Mazes - With Rook Jumping Maze generation as the fun central challenge, students integrate techniques from uninformed search, stochastic local search, and machine learning. 
Topics Breadth-first search, hill descent, random restarts, random uphill steps, simulated annealing, reinforcement learning
Audience Introductory AI students; material also would fit well with CS2 breadth-first search, since hill descent is easily accessible.
Difficulty All exercises can be completed within 2 weeks.  The basic track of exercises can be completed in ~100 lines of Java code.
Strengths Fun application for breadth-first search and stochastic local search.  Rook Jumping Mazes are very simple to define, interesting to solve, and, although the concept is more than a century old, the puzzle is novel to most people.  Such simplicity, engagement, and novelty benefit the exercise experience.
Weaknesses Text-based and non-graphical, although image files are available to support GUI 5x5 maze development.
Dependencies Basic track dependencies: CS2 (graphs, trees), uninformed search (breadth-first search), stochastic local search (hill climbing/descent, simulated annealing)
Variants One can easily create variants by changing maze tiling, topological constraints, and movement constraints.  Possibilities are described in detail below.

Rook Jumping Maze Generation

Each exercise below may be used to guide students through a process for the creation of Rook Jumping Mazes.  Through the process, students gain experience with uninformed graph search and stochastic local search.

Exercise Description Prerequisite Exercise
Maze Representation - generate and print a random Rook Jumping Maze (RJM)  
Maze Evaluation - breadth-first search from start state, printing state depths (including goal state depth) Maze Representation
Hill Descent - stochastic local search in space of maze configurations, stepping to random neighboring configuration if the minimum goal state depth does not decrease Maze Evaluation
Hill Descent with Random Restarts  - multiple applications of Hill Descent Hill Descent
Hill Descent with Random Uphill Steps - same as Hill Descent but allowing uphill steps with a small probability Hill Descent
Simulated Annealing - similar to Hill Descent with Random Uphill Steps, but with better, more complex uphill step policy Hill Descent with Random Uphill Steps
Maze Evaluation II - opportunities for creative maze design any of the four previous stochastic local searches above
Restart Bandit - restart period is posed as an n-armed bandit problem, with an ε-greedy/softmax strategy for parameter tuning Hill Descent with Random Restarts
Restart SARSA - SARSA learning of restart policy based on iteration since restart and current maze utility Hill Descent with Random Restarts

Different subsets of these exercises may be chosen according to different desired goals/emphases.  For example:
Basic track:
Maze Representation, Maze Evaluation, Hill Descent, Hill Descent with Random Restarts
Stochastic Local Search track: Maze Representation, Maze Evaluation, Hill Descent, Hill Descent with Random Restarts, Hill Descent with Random Uphill Steps, Simulated Annealing
Machine Learning track: Maze Representation, Maze Evaluation, Hill Descent, Hill Descent with Random Uphill Steps, Simulated AnnealingRestart Bandit, Restart SARSA
Creativity track: Maze Representation, Maze Evaluation, Hill Descent, Hill Descent with Random Uphill Steps, Maze Evaluation II



Variations

Creating variations of the these exercises is simple.  One may create variations of the simple Rook Jumping Maze in many ways.

One may vary tiling of the maze, using different regular tilings, e.g. triangular or hexagonal.  Semiregular and other tilings present different interesting possibilities at the risk of yielding movement instructions that are difficult for many to grasp.

Additional topological constraints may be added or removed, such as allowing toroidal wrap-around grid boundaries, or creating additional graph connectivity as in the abstract strategy board game Surakarta.  Simple means of adding constraints include the addition of impassable walls between tiles, impassable tiles, or tiles which may be passed over but cannot be a move destination.

Movement constraints may be varied as well. With the addition of diagonal moves, the Rook Jumping Maze becomes a Queen Jumping Maze. Abbott's "no-U-turn" rule increases state complexity so that the current state must be described as the product of the row, the column, and the previous move direction.

Many rich possibilities for creative variants exist, so it is not difficult to craft a unique (i.e. not easily plagiarized) assignment experience for your students.


Additional Resources


Todd Neller