Assignment about Adversarial search and CSPs

Exercise 1:

Consider a zero-sum game of two players that starts with a stack of 7 tokens. During the game, different stacks will be created. Each play should divide a stack into two different stacks (not empty and of different sizes). For example,

if there are two stacks of 2 and 4 tokens, the only possible move is to divide the stack of 4 tokens into two stacks of 1 and 3 tokens. If a player cannot do any move, the player loses. We call the two players Max and Min. If the player Max wins, the utiliy value is 1 and if Min looses, the value will be -1. Apply alpha-beta to this game. Max starts to play. Who will win?

Exercise 2:

We are interested here in the following game: at the start we have 11 matches and each of the two players can in turn remove 1, 2 or 3 matches. The losing player is the one who

pick up the last match.

a) Give a utility function suitable for this game

b) The first player called MAX is asking for your help. How many matches do you recommend him to pick at the beginning. Justify your question by drawing the search tree and applying the appropriate algorithm.