python编程语言调试、讲解program程序、Python编程辅导

日期：2020-11-01 11:27

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)