1
$\begingroup$

I'm having trouble figuring out why the 1s and 0s are where they are in this game tree for the game Nim:

Minimax Game Tree from, Luger Artificial Intelligence Structures and Strategies for  Complex Problem Solving

There is a statement in the book that explains the numbers but it's still not clear to me,

In implementing minimax, we label each level in the search space according to whose move it is at that point in the game, MIN or MAX.

In the example, MIN is allowed to move first. Each leaf node is given a value of 1 or 0, depending on whether it is a win for MAX or for MIN. Minimax propagates these values up the graph through successive parent nodes according to the rule:

If the parent state is a MAX node, give it the maximum value among its children. If the parent is a MIN node, give it the minimum value of its children.

If I was to draw the tree by hand how would I know where to put the 1s and 0s?

$\endgroup$
  • 1
    $\begingroup$ This isn't the game of nim. $\endgroup$ – Yuval Filmus Apr 9 '17 at 17:45
  • $\begingroup$ @YuvalFilmus This is the quote that is underneath that game tree; "Exhaustive minimax for the game of nim." $\endgroup$ – cod3min3 Apr 10 '17 at 2:03
  • $\begingroup$ Well, it just isn't the game of nim. You can look nim up on Wikipedia. $\endgroup$ – Yuval Filmus Apr 10 '17 at 4:59
  • $\begingroup$ @YuvalFilmus Then it's probably a mistake in the book. $\endgroup$ – cod3min3 Apr 10 '17 at 14:24
1
$\begingroup$

The graph contains all positions reachable from the initial position. The values are determined as follows:

  • A leaf (a node with no children) is labeled 0 if it is MAX's turn to play, and 1 if it is MIN's turn to play.
  • A non-leaf belonging to MAX gets the maximum of the labels of its children.
  • A non-leaf belonging to MIN gets the minimum of the labels of its children.

Hopefully you can now read the book and understand why we're doing the computation in this way.

$\endgroup$

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.