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: Using a form of stochastic local search called Hill Descent with Random Uphill Steps, search the space of 5-by-5 Rook Jumping Mazes (RJMs) for a given number of iterations and print the best maze evaluated according to the objective function specified by Rook Jumping Maze Evaluation.
One problem with pure hill descent is that stochastic local search may become trapped in local minima, where every local step is uphill, making things worse. One escape strategy allows uphill steps with some small probability. Thus, with some probability, any local minimum can be escaped. In this exercise, you will modify hill descent to allow uphill steps with a given fixed probability p.
Using the definitions of hill descent, we may describe our modified algorithm as follows:
Note: With p = 0, this degenerates to pure hill descent. With p = 1, this degenerates to random walk.
Possible background readings include:
Input Format:
Output Format:
Sample Transcripts (input underlined):
Iterations? 20000 Uphill step probability? 0 1 4 3 1 1 3 2 3 2 1 2 2 1 3 1 2 1 3 2 1 1 4 1 4 0 Moves from start: 0 1 5 12 13 1 3 9 2 14 7 5 8 6 15 3 4 4 3 16 2 2 10 11 17 -17
Iterations? 20000 Uphill step probability? .01 3 3 2 2 3 2 2 2 2 4 4 1 1 3 1 4 3 3 1 4 2 3 1 3 0 Moves from start: 0 2 9 1 3 6 12 7 13 5 3 11 10 2 4 1 3 8 14 2 16 18 17 15 19 -19
Iterations? 20000 Uphill step probability? 1 3 4 2 4 2 1 3 3 3 4 1 1 1 2 2 3 3 3 3 4 3 1 1 3 0 Moves from start: 0 8 9 1 10 4 5 8 3 6 5 6 7 8 11 1 7 8 2 8 3 6 7 2 12 -12
Questions: