Question

Alice is taking Artificial Intelligence from Professor Bob. To earn extra credit, Bob offers to play the following game. Alice and Bob both put all the coins they have on a table. Alice goes first, and can pick up either one or two coins. Bob goes second and can pick on either one or two coins. The process repeats until there are no coins left. Whoever picks up the last coin wins.

1.Suppose that upon emptying their pockets, they discover that they have 5 coins. Draw a complete game tree, including actions and rewards (from Alice's perspective) for this game.
2.Does Alice have a winning strategy (i.e., can she force a win)? If so, what is this strategy?
3.(Extra credit) Suppose that the game is changed so that at the end, whoever wins gets to keep all the coins they picked up. (The remainder are paid in taxes.) The loser gets nothing. What is the maximum total win that Alice can force? What about Bob?

Answer 1

Alice has a winning strategy in the coin game by ensuring that she always leaves 4 coins after her first move. For the extra credit portion, the maximum total win for Alice or Bob depends on strategic choices related to the remaining coins and turn order.

Step-by-step explanation:

Artificial Intelligence Game Strategy

Alice and Bob's game has a simple structure and can be analyzed by constructing a game tree. The game tree will display all possible moves and outcomes starting from the initial state of 5 coins on the table:

1. Alice takes 1, leaves 4 coins (Bob can win by creating a state with 1 coin on Alice's turn).
2. Alice takes 2, leaves 3 coins (Bob can take 1, leaving 2 coins, which guarantees him a win).The rewards are win or lose state from Alice's perspective.If Alice wants to win, her strategy is to leave 4 coins after her first move, putting Bob in a position where any move he makes Alice can always force a win. This guarantees Alice's victory as she uses the winning strategy by always taking a number of coins that leaves Bob with a state of 1 coin on his turn.The extra credit changes the game slightly. In this scenario, Alice can maximize her win by adapting her choices to the coin amount, aiming to end with few coins left on the table.The maximum total win that Alice can force also depends on who goes first in the modified game. Bob's strategy will adjust similarly, aiming to be the one to collect the most by ensuring he picks the last coin.