python ProgrammingDebug ,Help With program Programming,Python Programming
R Programming| C/C++ Programming
Assignment 3: Rook Jumping Maze
1
Starting at the circled cell in the upper-left corner of a board, 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 (no diagonal move is allowed).
Implement the requested following assignment parts. For each programming part, submit one
Python file (with the specified name), including all functions and modules you implemented. For
part 7, submit a pdf file containing answers to all questions asked. Submit all 7 files (6 python
files and 1 pdf file) as a compressed file on Canvas.
Part 1: (part1.py)
Generate and print a random n-by-n Rook Jumping Maze (RJM) ( 5 ≤ n ≤ 10 ) where there is a
legal move (jump) from each non-goal state.
Let array row and column indices be (rmin
, ..., rmax ) and ( cmin
, ..., cmax ), respectively, where
rmax − r 1 c 1 n . The RJM is represented by a 2D array of jump numbers. min + = max − cmin + =
A cell's jump number is the number of array cells one must move in a straight line horizontally or
vertically from that cell. The start cell is located at (r , c ) . For the goal cell, located at min min
(rmax
, cmax
) , let the jump number be zero. For all non-goal cells, the randomly generated jump
number must allow a legal move. In the example 5-by-5 maze above, legal jump numbers for
the start cell are {1, 2, 3, 4} , whereas legal jump numbers for the center cell are {1, 2} . In
general, the minimum legal jump number for a non-goal cell is 1, and the maximum legal jump
number for a non-goal cell (r, c) is the maximum of rmax − r, r − r , c c, c c . This min max − − min
defines a directed graph where vertices are cells, edges are legal jumps, and the outdegree is 0
for the goal cell vertex and positive otherwise.
Input Format: an integer 5 ≤ n ≤ 10
Output Format:
● Initially prompt the user with "Rook Jumping Maze size (5-10)?".
● Given valid input, print the randomly generated RJM 2D-array of jump numbers, with
jump numbers separated by a single space.
1 Neller, T. W., DeNero, J., Klein, D., Koenig, S., Yeoh, W., Zheng, X., ... & Poole, D. (2010, July). Model
AI assignments. In First AAAI Symposium on Educational Advances in Artificial Intelligence.
Sample Transcripts (input underlined):
Rook Jumping Maze size (5-10)? 6
5 2 1 1 1 2
4 3 4 3 1 5
5 2 3 1 4 1
3 1 2 1 4 1
3 4 1 1 4 5
4 3 4 5 2 0
Rook Jumping Maze size (5-10)? 10
6 2 4 6 6 8 3 7 2 5
3 7 1 6 2 6 8 8 8 5
8 8 7 4 3 6 5 6 5 2
1 8 1 6 1 4 5 7 5 1
7 5 6 4 5 4 1 7 4 9
3 8 4 2 3 3 3 6 4 9
8 3 1 2 3 5 1 4 5 4
5 8 3 1 7 2 7 3 5 9
9 1 4 5 7 5 7 6 8 2
4 6 3 7 6 2 5 9 1 0
Part 2: (part2.py)
Generate and print a random 5-by-5 RJM where there is a legal move from each non-goal state.
Then, for each cell, compute and print the minimum number of moves needed to reach that cell
from the start cell, or "--" if no path exists from the start cell, i.e. the cell is unreachable.
There are many features of a good RJM. One obvious feature is that the maze has a solution,
i.e. one can reach the goal from the start. One simple measure of maze quality is the minimum
number of moves from the start to the goal. For simplicity, we will limit our attention to these.
Using breadth-first search, or some other suitable graph algorithm, compute the minimum
distance (depth = number of moves) to each cell from the start cell. Create an objective function
(a.k.a. energy function or RJM Evaluation) that returns the negated distance from start to goal,
or a large positive number (e.g. 1000000) if no path from start to goal exists. Then the task of
maze generation can be reformulated as a search through changes in the maze configuration
so as to minimize this objective function (which we will get to in the next parts of the
assignment).
Input Format: (no input)
Output Format:
● Print a randomly generated 5-by-5 RJM 2D-array of jump numbers, with jump numbers
separated by a single space.
● Print "Moves from start:" on a single line.
● Print the 2D-array of corresponding cell depths (minimum number of moves from start)
separated by spaces. For unreachable cells, print "--". For other cells, print the depth
right-justified in a width of two characters.
● Print the output of your objective function (RJM Evaluation) on a single line.
Sample Transcripts:
2 2 2 4 3
2 2 3 3 3
3 3 2 3 3
4 3 2 2 2
1 2 1 4 0
Moves from start:
0 3 1 4 2
7 5 5 6 4
1 4 2 2 3
5 6 4 -- 3
-- 4 3 4 5
-5
3 3 2 4 3
2 2 2 1 1
4 3 1 3 4
2 3 1 1 3
1 1 3 2 0
Moves from start:
0 4 -- 1 5
2 -- 3 5 4
4 4 3 3 5
1 3 2 3 4
4 3 3 2 --
1000000
Part 3: (part3.py)
Using a form of stochastic local search called Hill Descent (the reverse of stochastic hill
climbing), search the space of 5-by-5 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 RJM and evaluate it
according to the Rook Jumping Maze Evaluation function. 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 RJM Evaluation function.
● 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 RJM 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 jbest ← j .
For a given number of iterations:
j′ ← step(j)
if e(j′) ≤ e(j)
j ← j′
if e(j′) ≤ e(j ) best
jbest ← j
return jbest
Here we implement stochastic hill descent allowing sideways moves for the given number of
iterations. 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 RJM 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
Part 4: (part4.py)
Using a form of stochastic local search called Hill Descent with Random Restarts, search the
space of 5-by-5 RJMs for a given number of iterations and print the best maze evaluated
according to the objective function specified by RJM 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 is to restart
search periodically. Using the provided definition, we may describe our modified algorithm as
follows:
Let j be chosen at random, and jbest ← j .
For a given number of searches:
For a given number of iterations:
j′ ← step(j)
if e(j′) ≤ e(j)
j ← j′
if e(j′) ≤ e(j ) best
jbest ← j
Let j be chosen at random
return jbest
Here we implement hill descent with random restarts allowing sideways moves.
Input Format:
● a positive integer number of iterations for hill descent optimization
● a positive integer number of hill descents
Output Format:
● Initially prompt the user with "Iterations? " and "Hill descents? ".
● After all hill descents, print the RJM with the best (minimum) objective function
evaluation according to the RJM Evaluation output specification.
Sample Transcripts (input underlined):
Iterations? 10000
Hill descents? 1
2 1 1 4 3
2 2 3 1 4
3 2 2 3 3
3 3 1 1 3
4 1 3 4 0
Moves from start:
0 2 1 2 6
6 3 2 4 5
1 12 10 2 11
7 4 9 8 5
14 13 3 3 15
-15
Iterations? 1000
Hill descents? 10
3 4 3 4 3
2 2 3 3 2
4 1 1 2 1
3 2 1 2 3
3 3 4 4 0
Moves from start:
0 15 7 1 14
4 4 5 3 13
11 10 9 10 12
1 3 8 2 13
-- 16 6 2 17
-17
Part 5: (part5.py)
Using a form of stochastic local search called Hill Descent with Random Uphill Steps, search the
space of 5-by-5 RJMs for a given number of iterations and print the best maze evaluated
according to the objective function specified by RJM 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 part, you will modify hill descent to allow uphill steps with a given fixed
probability p . Using the provided definitions, we may describe our modified algorithm as follows:
Let j be chosen at random, and jbest ← j .
For a given number of iterations:
j′ ← step(j)
if e(j′) ≤ e(j) or with probability p
j ← j′
if e(j′) ≤ e(j ) best
jbest ← j
return jbest
Note: With p = 0 , this degenerates to pure hill descent. With p = 1 , algorithm degenerates to
random walk. Here we implement stochastic hill descent allowing sideways moves. Additionally
we accept all neighboring uphill steps with some small probability p .
Input Format:
● a positive integer number of iterations for hill descent optimization
● a probability for the acceptance of an uphill step
Output Format:
● Initially prompt the user with "Iterations? " and "Uphill step probability? ".
● After the hill descent iterations, print the RJM with the best (minimum) objective function
evaluation according to the RJM Evaluation output specification.
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? 0.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
Part 6: (part6.py)
Using a form of stochastic local search called Simulated Annealing, search the space of 5-by-5
RJMs for a given number of iterations and print the best maze evaluated according to the
objective function specified by RJM Evaluation.
One problem with Hill Descent with Random Uphill Steps is that all uphill steps are equally
likely. A small uphill step would generally be more desirable than a large uphill step. The local
minima escape strategy of simulated annealing concerns a temperature schedule, called an
annealing schedule, that gradually shifts search from a free random walk to a final descent,
while favoring smaller uphill steps over larger ones.
The practical application of simulated annealing here involves very few modifications to Hill
Descent with Random Uphill Steps. Using the definitions of hill descent, we may describe our
modified algorithm as follows:
Let j be chosen at random, and jbest ← j .
Let T ← T0 where T0 is the initial temperature.
For a given number of iterations:
j′ ← step(j)
if e(j′) ≤ e(j) or with probability e
(e(j) − e(j′))/T
j ← j′
if e(j′) ≤ e(j ) best
jbest ← j
T ← T × d , where d is the iteration temperature decay
return jbest
Thus, simulated annealing in this form takes three parameters: number of iterations, initial
temperature, and temperature decay rate. Note the acceptance probability for uphill steps is
e . When the temperature is high, this is close to and acceptance of any uphill
(e(j) − e(j′))/T e 1
0 =
step is very likely. As the temperature drops to zero, this approaches e so any uphill step
∞ ≈ 0
would be rejected.
Input Format:
● a positive integer number of iterations for hill descent optimization
● a positive floating-point initial temperature
● a positive floating-point geometric decay rate (usually chosen slightly less than 1.0)
Output Format:
Initially prompt the user with "Iterations? ", "Initial temperature? ", and "Decay rate? ".
After the simulated annealing 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? 10000
Initial temperature? 100
Decay rate? 1.0
2 4 3 1 2
3 1 3 3 2
4 2 2 2 3
4 3 3 3 1
1 4 3 4 0
Moves from start:
0 4 1 5 6
7 -- -- 6 --
1 3 -- 4 2
9 -- 2 11 10
8 4 -- 5 11
-11
Iterations? 10000
Initial temperature? 1
Decay rate? 0.99
1 3 1 3 3
4 3 3 2 4
1 1 2 3 2
2 3 2 2 4
3 1 4 2 0
Moves from start:
0 1 8 9 2
1 12 6 11 2
17 18 19 16 20
4 2 5 10 3
14 13 7 15 21
-21
Part 7: (report.pdf)
In maximum two pages, summarize your observations and learnings from this assignment in a
few paragraphs. In your summary make sure that you answer questions like the following list:
● What happens if we don’t allow for sideways moves? (relates to part 3)
● What is the impact of the allowed number of consecutive sideways moves on the
hill-descent algorithm? (relates to part 3)
● Keeping the number of allowed sideways moves constant (say 10000), what is the effect
of the number of restarts? (relates to part 4)
● Is the probability of taking an uphill step the same as the probability of escaping a local
minimum? Why or why not? (relates to part 5)
● For a fixed maze with a fixed number of iterations (say 10000), what is the best
annealing schedule? Run multiple simulations with different annealing functions and
compare and contrast them. (relates to part 6)