0
$\begingroup$

A version of the game of Nim is used to illustrate the minmax strategy in Rosen's Discrete Mathematics and Its Applications, 3ed, chapter 11 p. 768. I understand the +1 and -1 labels here. However, why is there not a [121] node at the second level? (question 1)

n1

However, I had trouble understand this part (question 2):

n2

Say if I start from the rightmost node [21] in the second level. The first player will seek to win, and thus will choose one of the two +1 options in the level below. The second player will be forced to pick up the last stone and thus lose. So shouldn't the value of this node [21] be +1 instead?

Say if I start from the rightmost node [1] of the third level, the first player must pick up the only stone there is. So shouldn't the value of this node be -1 in this case?

I am so confused by the stated Theorem 3. Please help.

$\endgroup$
8
  • $\begingroup$ You ask why there isn't a 121 node? What is the difference between having taken a single stone from the first pile that has two stones versus having taken a single stone from the second pile that has two stones? Hardly anything... in both cases you are left with one pile with two stones, and two piles with one stone each. Why then should we bother writing them as separate cases? $\endgroup$
    – JMoravitz
    Commented Jan 29, 2020 at 15:03
  • $\begingroup$ I see! Can you help me with the other question? $\endgroup$
    – J. Doe
    Commented Jan 29, 2020 at 15:06
  • $\begingroup$ "Say if I start from the right most node..." For this tree, the game began at the root node of 221. Having traveled from that root node to 21 the first player took his turn to empty one of the piles of two stones. It is now the second player's turn. The second player now has the choice as to which play to make and will choose to empty the remaining pile of two stones which leaves just a single pile with a single stone in it for the first player's turn. The first player has no legal moves remaining and thus loses. It is the second players choice where to continue from 21. $\endgroup$
    – JMoravitz
    Commented Jan 29, 2020 at 15:10
  • $\begingroup$ @JMoravitz, theorem 3 states that: The value of a vertex of a game tree tells us the payoff to the first player if both players follow the minmax strategy and play starts from the position represented by this vertex. I am trying to understand it, and the numbering of the second picture. $\endgroup$
    – J. Doe
    Commented Jan 29, 2020 at 15:27
  • 1
    $\begingroup$ Try rewording it to "...and play continues from the position represented by this vertex." You seem to have taken the phrase "starts from" to imply that the first player is the next to act when that is not necessarily the case. Vertices pictured as squares in the image are ones where the first player is next to act. Vertices pictured as circles in the image are ones where the second player is next to act. $\endgroup$
    – JMoravitz
    Commented Jan 29, 2020 at 15:48

1 Answer 1

Reset to default
1
$\begingroup$

As per @JMoravitz's explanation in the comment, theorem 3 should be understood as:

The value of a vertex of a game tree tells us the payoff to the first player if both players follow the minmax strategy and play continues from the position represented by this vertex.

This is supported by the wording of the inductive step of the theorem's proof, which suggests that a continuation of the game and not a reset. A continuation retains the players' turns.

n3

If starts entails maintaining the players' turns, then everything is fine. I am still bothered by the use of starts here, and feel that it is rather misleading in this context.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .