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. |
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 Annealing,
Restart Bandit, Restart
SARSA
Creativity track: Maze Representation,
Maze Evaluation, Hill Descent,
Hill Descent with Random Uphill Steps,
Maze Evaluation II
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.