1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Nim game tree

  1. Dec 6, 2015 #1
    1. The problem statement, all variables and given/known data
    Capture.PNG

    2. Relevant equations
    Tree data structures.
    I think it might also have something to do with minimax algorithm, but it was only mentioned once and never discussed extensively in class so I doubt it is required.

    3. The attempt at a solution

    If both players play as well as they can, the game will end in a draw. Player 1 will always have the option of choosing to draw rather than lose.
    Capture.PNG
    However I can't find a function that given n sticks will tell me who will win. For 5, 10 and other multiples of 5, player 2 necessarily wins but what about the other cases? How can I find a single formula that will necessarily tell me who will win, given that they play well?
     
  2. jcsd
  3. Dec 7, 2015 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Misunderstanding: you can't end in a draw.
     
  4. Dec 7, 2015 #3
    "The player who removes the last match wins, except if there is only one match left, in which case the game is a draw." All the paths that end in 1 in the game tree are draws.
     
  5. Dec 7, 2015 #4

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Oops, sloppy reading... o:)
    I remember something about analyzing games like this: start from the end situation and work backwards...
    Your "multiples of 5" points that way. So player 2 will always work towards multiples of 5. So will 1. That way you have pinned down "playing well". Apparently you really want the other to start when playing this game, unless n is a multiple of 5 plus 2 or 3.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Nim game tree
  1. Binary trees (Replies: 1)

  2. Hashtag game. (Replies: 1)

  3. Recursion Tree (Replies: 3)

  4. Parse tree (Replies: 3)

Loading...