Recall what we previously learned.

a$.$ What$$s the difference between a world state, a state description?

b$.$ Why is this distinction between world state and state description useful?

c$.$ What is a search node?

d$.$ Why is this distinction between search node and states useful?

$2.$ Consider the problem of solving two $8-$puzzles, you move one tile of any one puzzle each time.

a$.$ If your goal is solving both two puzzles, give a complete problem formulation includes state,

action, initial state, successor function, Goal state test, and path cost.

b$.$ How large is the reachable state space? Give an exact numerical expression. Note: only half of

all impossible states are reachable.

c$.$ Suppose we MODIFY the problem and the game become an adversarial game as follows: the

two players take turns moving; a coin is flipped to determine the puzzle on which to make a

move in that turn; and the winner is the first to solve just ONE puzzle. Which algorithm can be

used to choose a move in this setting?

d$.$ Assume two players playing that game following $($c$),$ after N turns, one of the puzzle now require

only one move to be completely solved. Who has better chance to win? The player just finished

the move in the N$-$th turn or the player is going to make a move in the coming turn $($N$+1)?$ Why?

e$.$ Someone will eventually win if both play perfectly. Is that true? Explain why.

$3.$ Which of the following are true and which are false? Give brief explanations.

a$.$ In a fully observable, turn$-$taking, zero$-$sum game between two perfectly rational players, it does not

help the first player to know what strategy the second player is using$$that is$,$ what move the second

player will make, given the first player$$s move.

b$.$ In a partially observable, turn$-$taking, zero$-$sum game between two perfectly rational players, it does

not help the first player to know what move the second player will make, given the first player$$s move.

c$.$ A perfectly rational backgammon agent never loses.