Rook Jumping Maze Evaluation II
Rook Jumping Maze Instructions:
Starting at the circled cell in the upper-left corner, find a path to the goal
cell marked “G”. From each numbered cell, one may move that exact
number of cells horizontally or vertically in a straight line. How many
moves does the shortest path have?
Solution (select to reveal): [19 moves:
RDLRUDRLRLUDLDRRUDD]
Problem: Define a better maze evaluation function and
argue why it leads to improved maze quality. Compare and contrast the
results obtained with your new evaluation function versus the previous
evaluation function using the same stochastic local search technique for each.
There are many features of a good Rook Jumping Maze (RJM). Previously,
we evaluated RJMs according to solvability and the shortest distance to the
goal. However, there are many other features that may be considered as
well. Here, we describe a few:
- Black holes* - A black hole is a dead-end. Define a
reachable cell to be a cell one can reach from the start through a
sequence of legal moves. Define a reaching cell to be a cell
from which one can reach the goal through a sequence of legal moves. A
cell is part of a black hole if it is a reachable, non-reaching cell.
- White holes* - Some puzzlers seek to trace backwards from the
goal to the start. A white hole is a back-tracing dead end. A
cell is part of a white hole if it is an unreachable, reaching cell.
- Start and goal positions - Is anything gained/lost by allowing
the position of the start and/or goal cell to vary?
- Shortest solution uniqueness - How does knowledge that there is a
unique shortest solution affect the maze solving experience?
- Forward/backward decisions - Sometimes there is only a single
legal "forced" move from a cell. How do the number of forward
decisions affect the maze solving experience? This is related to a
game-tree branching
factor. Initial forced moves are especially noticeable. For
back-tracing puzzlers, consider also the number of backward decisions, i.e.
the number of cells for which there are multiple possible predecessors.
- Same jump clusters - Same jump clusters are sets of cells that
all have the same jump number and reach each other without leaving the
cluster. For example, consider the maze above. The two leftmost 3s of
the second row and the 3 of the bottom row form a 3-jump cluster.
How do same-jump clusters affect the maze solving experience? Are some
better than others?
- Solution direction variability - Again, consider the maze above.
Part of the shortest solution begins at the second 3 in the third row and
proceeds right-left-right-left. How does such back-and-forth within
the same row or column affect the maze solving experience?
Select one or more of the features above that you consider most important,
compute measures for maze evaluation, and seek to improve upon the previous RJM
evaluation function. Generate sets of puzzles using the old and
new evaluation functions, compare and contrast the puzzles, and argue why your
new evaluation function improves the average quality of your mazes.
*The descriptive maze terms "black hole" and "white hole" were coined by maze
designer Adrian Fisher.
Possible background readings include:
Todd Neller