General Game Playing
General
Artificial
Intelligence

Exercise 5.3 - Sequential Plans

Consider the 8-puzzle introduced in the notes. The initial state of the game is shown below on the left, and the ideal arrangement is shown on the right.

1
3
4
2
5
7
8
6
1
2
3
4
5
6
7
8

Recall that there are 4 feasible actions - up, down, left, right - and any of these actions is legal so long as the empty tile remains within the 3x3 grid. The reward for a state is the sum of rewards for each tile, with 10 points being awarded for each numbers tile in its ideal position and 20 points being awarded if the empty cell is in its proper position.


1. Which of the following sequential plans is legal?
a. [right,right,down,down]
b. [right,right,right,down]
c. [right,down,right,down]
2. Which of the following sequential plans is terminal?
a. [right,down,up,left]
b. [right,down,right,down]
c. [down,down,right,down]
d. [right,down,left,down]
3. Which of the following sequential plans is minimal?
a. [right,right,right,down]
b. [right,down,right,down,left,right]
c. [right,down,right,down,left]
d. [right,left,right,down,right,down]
4. Which of the following sequential plans is optimal?
a. [right,down,up,left]
b. [right,left,right,down,right,down]
c. [right,down,right,down]
d. [right,down,down,down]