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!

Game theory: nim

  1. May 23, 2013 #1
    1. The problem statement, all variables and given/known data

    • Two players: A and B.
    • Players can take 1 or 2 stones per turn.
    • The player who takes the last stone wins.
    The question is: is there any winning strategy with 5 stones?, does it change with 1000 stones?.

    2. Relevant equations

    None.

    3. The attempt at a solution

    If there are 5 stones player A has a winning strategy if he takes 2 stones in his first turn. 3 stones left, so B can take 1 or 2 but in any case there are available stones and A wins.

    If there are 1000 stones I don't know.
     
  2. jcsd
  3. May 23, 2013 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Try a few cases like 4,6,7,8,9 stones etc and see if you notice anything.
     
  4. May 23, 2013 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "Five stones" is pretty close to trivial. The first person takes 2 stones, leaving three. If the second person takes one stone, the first person takes the two remaining stones, winning. If the second person takes two stones, the first person takes the one remaining stone, winning.
     
  5. May 23, 2013 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Didn't the OP already observe that?
     
  6. May 23, 2013 #5

    phinds

    User Avatar
    Gold Member
    2016 Award



    The number of stones is irrelevant. There is a winning strategy. Period.

    It's been about 50 years since I knew the math on it but it's something like writing out the # of remaining stones in binary and then taking away a number of stones that does something (I forget what) the the form of the binary number.
     
  7. May 23, 2013 #6

    Zondrina

    User Avatar
    Homework Helper

    Presuming there are 1000 stones and player A gets to go first...

    It seems to me that player A can ensure a victory every time as long as he doesn't take 2 stones at a time on the first turn ( I tried several cases myself ).

    If player A only takes 1 stone on the first turn, he/she can force player B into the 5 stone scenario which you know is a guaranteed win. Just some stuff I was fiddling with.
     
  8. May 23, 2013 #7

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Not always. It depends on the starting state.

    But the OP's problem is a simple sub-version of the game of Nim. You don't need anything but a little reasoning to figure it out. Hopefully everyone will let the OP do that.
     
  9. May 23, 2013 #8

    phinds

    User Avatar
    Gold Member
    2016 Award

    You are right of course. If the starting state has the binary number in the requisite form and they both know the strategy, then the starter cannot win. Good point.

    EDIT: there IS still a winning strategy of course, just not for the starter in this case :smile:
     
  10. May 23, 2013 #9

    phinds

    User Avatar
    Gold Member
    2016 Award

    OH, I just realize that the OP is talking about a LIMITED form of NIM (yeah, LCKurtz, I see that you pointed that out --- I'm dense sometimes). That may not have a winning strategy for any number of starting stones. I think I remember now what the strategy that I was talking about is and it requires that you be able to remove up to half of the stones.
     
  11. May 23, 2013 #10

    Zondrina

    User Avatar
    Homework Helper

    I would also like to add to my previous post.

    If it gets down to it, player A can win if they can force player B ( Of course presuming a perfect game is played ) to allow them to take stones when there are only 4, 5, 7, or 8 stones left.
     
  12. May 23, 2013 #11

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hey everybody, enough with the hints and partial solutions. Let's wait for the OP to make some progress.
     
  13. May 23, 2013 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Well, there is always a winning strategy in such games, but whether it's the first or second player that has it available depends on the starting state. The set of positions can be partitioned into two sets. In one set, every legal move leads to a position in the other set; the player having to play from such a position should lose. In the other set, there exists at least one move which leads to a position in the first set; that move is the winning line.
    Viewed this way, it becomes a problem of control. You can often invert the criterion for a win (e.g. in Nim, whether the player to take the last stone wins or loses) without changing the essential strategy. Only a few positions in the endgame switch set.
     
  14. May 24, 2013 #13

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, he did. I just didn't read all of the post! It looks to me like the first player can win if he moves so as to always leave an odd number of stones. Until the last move: if there are 1 or 2 stones left take them all, of course.
     
  15. May 24, 2013 #14

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That is not a winning strategy. Consider N=7. You have just given your opponent a winning state if you take away two stones. This is not too much of a hint because we already know that N=5 is a state that has winning strategy.


    Hear, hear. There is a generic solution to the problem. Everyone, please give the OP time to find it.
     
  16. May 25, 2013 #15
    Thank you all for your help. I think I got the solution after trying with n= 4, 6, 7, 8, 9 and 10.

    When n=4 A takes 1, they remain 3 so B loses. A's winning strategy is 1 stone in his first turn.

    When n=6 then A doesn't have any WS whether he takes 1 or 2 stones. If he takes 1 there are 5 left, so B wins. If he takes 2 there are 4, so B takes 1 and wins the game, since A only can take up to 2, but in any case B is the winner.

    When n=7 then A does have a WS if he starts taking 1, so B must deal with n=6 which is the previous case.

    When n=8 then A has a WS. He takes 2 and n=6. Same case.

    When n=9 A doesn't have any WS. Regardless how many he takes in the first turn he cannot win (n=8 or n=7).

    When n=10 A has a WN taking 1.

    I think that the key is that A has a WS if the number of stones left that he has to confront isn't multiple of 3. If n=1000 A has to take 1 in his first movement, and then he has to follow the idea of multiple. Is it correct?.

    Thanks in advance.
     
  17. May 25, 2013 #16

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Correct. This is a trinary (base 3) rather than binary (base 2) problem.
     
  18. May 25, 2013 #17

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Well, it's not a ternary solution in the sense of standard Nim's binary solution. It is, as Ikastun says, just a modulo 3 criterion, which is simpler.
    To relate this to my earlier post, since each player has to take 1 or 2 stones, the second player in a pair of turns can always arrange that the total of the two turns is 3 (provided there were at least 3 left). Thus the value mod 3 becomes a relevant property. If the objective is to take the last stone then leaving a multiple of 3 wins; if the objective is to leave the last stone then leaving 1 mod 3 wins.
    We can make it a bit more like standard Nim by introducing multiple piles. You can take 1 or 2 stones, but only from one pile. I would guess a ternary solution analogous to that of standard Nim might apply.
     
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: Game theory: nim
  1. Game Theory (Replies: 4)

  2. Game Theory: Nim Sum (Replies: 0)

  3. Game Theory 2x2 Matrix (Replies: 1)

  4. Game theory (Replies: 2)

Loading...