Jump to content

Generalised Bachet and Nim game

- - - - -

This topic has been archived. This means that you cannot reply to this topic.
2 replies to this topic

#1
Guest_chris_thief_*

Guest_chris_thief_*
  • Guests
Hello people. I hope someone could help me find a strategy for a little computer game I have to make . It'a a game played by two players, one being the computer. I have to find the perfect strategy for the computer, so that it always wins. The text of the game is as follows:

There are N stacks each having p[i] objects. Alternately, two players A and B extract from a single stack no more than k objects. The player performing the last move is the winner of the game.

I have done some research on the Nim game and Nim-like games, but i haven't found about this specific variant of it.
Wikipedia says "The only difference is that as a first step, before computing the Nim-sums, we must reduce the sizes of the heaps modulo k + 1. "
So , it's just like the strategy of Nim..but we divide every stack size by k+1 , and then XOR the results..and that would be the nim sum?
How does the nim-sum influence the next computer move?

Any help or suggestion, or link would be appreciated..i have been trying to resolve this problem for 2 weeks now, without any help :(

#2
Guest_kevinplayschess_*

Guest_kevinplayschess_*
  • Guests

chris_thief said:

There are N stacks each having p[i] objects. Alternately, two players A and B extract from a single stack no more than k objects. The player performing the last move is the winner of the game.

I have done some research on the Nim game and Nim-like games, but i haven't found about this specific variant of it.
Wikipedia says "The only difference is that as a first step, before computing the Nim-sums, we must reduce the sizes of the heaps modulo k + 1. "
So , it's just like the strategy of Nim..but we divide every stack size by k+1 , and then XOR the results..and that would be the nim sum?

No, we modulo the results, in c++ the modulo opperator is %, so the number of blocks to take away is p%(++k), if I remember correctly, though, the outcome of this bame depends on who goes first, so the computer can't always win unless you set up so that the computer always comes first or second.

#3
Guest_kinjkangan_*

Guest_kinjkangan_*
  • Guests
Great info all of the time!