3
$\begingroup$

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?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Does the search tree also convey that MAX has lost? $\endgroup$
    – Sid
    Commented Oct 29, 2012 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
    Commented Oct 29, 2012 at 7:18
0
$\begingroup$

(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.

Improve this answer
$\endgroup$
1
  • $\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$
    – John L.
    Commented Apr 27, 2019 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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