We are designing a rational agent that is going to be able to play the following game. “1-2 steal marbles “. Initially, there are 6 marbles on the board. One of the players can choose to remove 1 or 2 marbles leaving 5 or 4, after that the other player can do the same, choosing to take again one or two marbles from the board. The process continue until there is only one marble in the board. The player who wins is the one the leaves the last marble on the board. (For example: If there are 3 marbles and it’s my turn , then I will choose to remove 2 to leave one in the board to win)

QUESTION

We are designing a rational agent that is going to be able to play the following game.

“1-2 steal marbles “.

Initially, there are 6 marbles on the board.

One of the players can choose to remove 1 or 2 marbles leaving 5 or 4, after that the other player can do the same, choosing to take again one or two marbles from the board. The process continue until there is only one marble in the board. The player who wins is the one the leaves the last marble on the board. (For example: If there are 3 marbles and it’s my turn , then I will choose to remove 2 to leave one in the board to win)

1. Formulate the problem

2. Describe the decision tree adding the maximizer and minimizer levels of the tree and assigning values to the objective function.

3 Write the algorithm in pseudocode(adapting it to this problem) or in a high-level language

4 Comment the results.

5. Can we use the same algorithm for 10000 marbles?. Explain the pros and cons of using this algorithm

ANSWER