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 :(
Generalised Bachet and Nim game
Started by
Guest_chris_thief_*
, Apr 12 2007 04:21 PM
2 replies to this topic
#1
Guest_chris_thief_*
Posted 12 April 2007 - 04:21 PM
Guest_chris_thief_*
|
|
|
#2
Guest_kevinplayschess_*
Posted 06 June 2007 - 05:19 PM
Guest_kevinplayschess_*
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?
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_*
Posted 21 June 2007 - 04:10 AM
Guest_kinjkangan_*
Great info all of the time!


Sign In
Create Account

Back to top









