2
$\begingroup$

I am studying with Game theory right now. In Nim game, in any turn, a player can move any number of stones from any one pile. I am wondering what might be the winning strategy of first player if in any move, a player can pick any number of stones from one or more piles? In this case, how the xor = 0 rule will work? Both are playing optimally.

$\endgroup$
3
$\begingroup$

The answer assumes that you have to take the same amount of stones from each pile that you choose. Otherwise the first player always wins as long as the piles are not all empty.

The rule "xor = 0" doesn't work. In particular, there is a winning position with xor = 0 (easy exercise; be creative).

In order to analyze the game, you can compute which positions are winning and which are losing recursively (surely you have been shown how to do that in your course). Then you can look at which positions are winning and which are losing, and try to guess a rule; you will then need to prove that your rule works.

In this particular case, however, the analysis will be quite difficult. The case of two piles is known as Wythoff's game, and is already pretty non-trivial to analyze.

$\endgroup$
  • $\begingroup$ Thanks! Your answer has pushed me to intuitively think on it :) $\endgroup$ – Kaidul Islam Apr 30 '16 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.