Hill Descent

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, 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. 

Given a number of iterations from the user, first generate a random 5-by-5 Rook Jumping Maze (RJM) according to the Rook Jumping Maze Representation specification and evaluate it according to the Rook Jumping Maze Evaluation specification. Then for the given number of iterations:

• For a random, non-goal cell, change the jump number to a different, random, legal jump number.
• Re-evaluate the objective function according to the Rook Jumping Maze Evaluation specification.
• If the objective function has not increased (worsened), accept the change and store the RJM if its evaluation is the best (minimum) evaluated so far. Otherwise, reject the change and revert the cell to its previous jump number.

Finally, print the RJM with the best (minimum) objective function evaluation according to the Rook Jumping Maze Evaluation output specification.

More formally, let jump function j be a mapping from cells to legal jump numbers, or 0 in the case of the goal cell.  Let objective function (or energy function) e be a function we seek to minimize over jump functions.  Let step be a function that takes a jump function j, and generates a "neighboring" jump function j' by making a single, stochastic change:  function step chooses from non-goal cells with equal probability, and for that cell c chooses j'(c) from all legal jump numbers not equal to j(c) with equal probability.  For all other cells, j'(c) = j(c).  Then we may describe our algorithm as follows:

• Let j be chosen at random, and j_best ← j.
• For a given number of iterations:
•  j' ← step(j)
• if  e(j') £ e(j)
• j ← j'
• if  e(j) £ e(j_best)
• j_best ← j
• return j_best

Possible background readings include:

• Russell and Norvig. Artificial Intelligence: A Modern Approach, 3rd edition, Chapter 4 through section 4.1.1 (hill-climbing search).  Here we implement stochastic hill descent (the reverse of stochastic hill climbing) allowing sideways moves.
• Hoos & Stützle. Stochastic Local Search: Foundations and Applications, section 1.5 (Stochastic Local Search)
• Wikipedia article on "Hill climbing", where we here focus on stochastic hill descent (the reverse of stochastic hill climbing).  Here, we accept all neighboring, non-uphill steps with equal probability, and we reject all neighboring uphill steps.

Input Format:  a positive integer number of iterations for hill descent optimization

Output Format:

• Initially prompt the user with "Iterations? ".
• After the hill descent iterations, print the RJM with the best (minimum) objective function evaluation according to the Rook Jumping Maze Evaluation output specification.

Sample Transcripts (input underlined):

Iterations? 100
1 4 2 2 2 
3 2 1 3 3 
2 2 1 2 2 
3 1 2 2 4 
1 4 2 3 0 

Moves from start:
 0  1  8  8  9 
 1  8  7  2 -- 
--  6  8  7 10 
 3  5  6  4  7 
 2  2 --  3 11 

-11

Iterations? 1000
1 2 1 2 2 
4 3 1 2 4 
4 2 1 3 1 
1 3 2 2 3 
2 4 1 1 0 

Moves from start:
 0  1  8  2  7 
 1 10  9 10  2 
 4  2 10  3  5 
12  7 11 11  6 
13  3 14 15 16 

-16

Iterations? 10000
1 4 2 3 2 
3 3 1 3 2 
3 3 2 2 4 
1 1 3 3 1 
3 2 3 3 0 

Moves from start:
 0  1 12  7 13 
 1 16 15  2 17 
 5  3 13  6  4 
 9 10 11  8 18 
 2  2 14  3 19 

-19

Questions:

1. Empirically, how does the objective function evaluation of the average generated maze vary with the number of iterations?
2. Why should we allow sideways moves?  That is, how might sideways moves help stochastic local search?

Todd Neller