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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

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.