b$.$ Wythoff's game is a two$-$player game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile must be equal.

The game ends when one person removes the last counter or counters, thus winning.

A state of this game can be represented by a pair $(n,m)$ where $n$ represents the number of counters in the first pile and $m$ corresponds to the number of counters in the second pile.

i$)$ Draw the complete search tree for this game if the initial state is $(3,1).$ For a more compact representation, you can merge nodes of the search tree if they represent the same state in the same turn of a player.

$[6$ Marks$]$

ii$)$ Assume two players, min and max, play this game. Max plays first. With a utility function specified as:

$=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 nodes in the search tree.

$[4$ Marks$]$

Assume we have run the minimax algorithm on some game. A null utility is computed for the initial node where it is the MAX player$$s turn.

i$)$ Is the MIN player guaranteed to win? Explain. $[2$ Marks$]$

ii$)$ Provide two conditions that would allow the max player to win. Hint: one condition on how the MIN player plays and one condition on the utilities on some nodes.