Skip to main content
gamedev.net
🔒 Locked

Nim XOR Problem

Started by Xalzar May 10, 2004 at 1:55 AM 3 replies 650+ views
Original Post
Xalzar
Xalzar
Hi all, this is my first post though I've been browsing these forums for a long time. I've never really had anything to ask. I'm sure there's a lot of you coders familier with the game of Nim. I'm going to make it as a basic first game, I'm doing a console version first so I can work out the kinks, and I've got it all working fine for two players, but it's playing against the computer I'm having trouble with. The idea is to have the computer win every time. I've read a lot about xoring and have made a few attempts, but the computer doesn't always pick the right amount to take away. ok, a, b and c are the piles of stones. Take is how much it should take. x is there to make things simpler. Here's a part of the code: int a=3, b=5, c=8, take, x; x = a^b^c; if ((a^x) <= a) { take = a^x; take = a - take; } if ((b^x) <= b) { take = b^x; take = b - take; } if ( (c^(a^b^c)) <= c) { cout << (c^x); take = c - (c^x); } [edited by - Xalzar on May 10, 2004 2:57:41 AM]
Beer Hunter
Beer Hunter
Your code doesn''t seem to track which stack you''re removing the stones from. It does make a difference.
Other than that, I see no problems. Your example suggests removing two stones from pile C, which is the right move to make (3 xor 5 xor 6 = 0).
Xalzar
Xalzar
Sorry about that messy code...

Ok it all works pretty good until it comes to the winning move. It doesn''t go down to 0, it goes down to 1. eg

a=0 b=3 and c=3 and its my go. i take 2 from b, and so its 0 1 3. it should now take 3 from c, but it takes 2.

x=a^b^c;

but (x^c) = 1, not 0. I don''t think I have a solid understanding of xoring...
Beer Hunter
Beer Hunter
Ah, I see what you mean. I''m more familiar with the rules of Nim where you win by taking the last stone. The XOR rule works perfectly for that. You''re playing by the rules where you lose by taking the last stone. The winning strategy is similar, but needs a little more work. First, calculate a move according to the XOR rule. If that would leave only piles of stones with 0 or 1 stone in them, change the number of stones you leave between 0 and 1. In code: 

bool all_0_or_1(int a, int b, int c)
{
    return (a == 0 || a == 1) &&
           (b == 0 || b == 1) &&
           (c == 0 || c == 1);
}

...

int a=0, b=1, c=3, x, leave, take;

x = a^b^c;

if ((a^x) < a) {
    leave = a^x;
    if (all_0_or_1(leave, b, c)) leave = 1 - leave;
    take = a - leave;
}

/* And simililarly for b and c */
Xalzar
Xalzar
Thanks a lot Beer Hunter - it works fine now.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.