search tree

Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player alternatively thereafter does the same to some single stack when it is his turn to play. The game proceeds until each stack has either just one penny or two—at which point continuation becomes impossible. The player who first cannot play is the loser. Show, by drawing a game tree, whether any of the players can always win.

Why is the state 6-1 not going to 3-3-1?If we have 6-1 pennies we can remove 3 pennies from the 6 stack and we have 3-3-1 pennies.So why isn't 3-3-1 not a child of 6-1?


Because - according to the rules above - each player must divide a stack into two stacks that must be unequal.

  • $\begingroup$ Does the search tree also convey that MAX has lost? $\endgroup$ – Sid Oct 29 '12 at 5:43
  • 1
    $\begingroup$ The search tree shows whether a player that can always win. If the first move is made by MIN, then MAX has a winning strategy: whatever MIN plays on the first round, MAX can choose to go to 4-2-1 configuration, then MIN has a forced move to 3-2-1-1 and MAX can finally win going to 2-2-1-1-1 $\endgroup$ – Vor Oct 29 '12 at 7:18

(b) Assume two players, min and max, play nim (as described above). Min plays first.

If a terminal state in the search tree developed above is a win for min, a utility function of zero is assigned to that state. A utility function of 1 is assigned to a state if max wins the game.

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

  • $\begingroup$ While this answer describes how to determine whether any of the players can always win, it does not answer the actual (much easier) question. $\endgroup$ – Apass.Jack Apr 27 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.