Consider the 8-puzzle with the initial state shown below, and assume that there are exactly two steps left in the game, i.e. the game ends after exactly two additional actions.
1
2
3
4
5
6
7
8
1.
What is the player's reward in this state?
2.
What is the utility of this state?
3.
How many nodes are in the game tree?
4.
How many distinct states are in the game tree?
5.
What is the maximum number of nodes examined by compulsive deliberation during this game?