• Advertisement

Archived

This topic is now archived and is closed to further replies.

Nim XOR Problem

This topic is 5032 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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).

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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 */

Share this post


Link to post
Share on other sites

  • Advertisement