Nim is a two player game in which players alternate making moves. Initially the players are given several piles of sticks. Each pile can have any number of sticks in it$.$ On each turn a player can remove any number of sticks from one pile. The player must remove a minimum of one stick from the pile or may remove the whole pile. The player who picks up the last stick loses.

i$)$ Initially there are three piles with number of sticks equal to $(1,2,2).$ Draw the

complete search tree for this game. Note, piles of $($a$,$ b$,$ c$)$ and $($a$,$ c$,$ b$)$ are treated as

the same states, e$.$g$.(1,2,1)$ is the same as $(1,1,2).$

ii$)$ Assume two players, min and max, play this stone game. Max plays first. With a

utility function values:

$=0$ if min wins the game

$=1$ if max wins the game

Apply the minimax algorithm to the search tree to assign utility functions to all states

in the search tree

iii$)$ If both min and max play a perfect game, who will win? Explain your answer.