[Solved]: Winning strategy of Nim game when picking from multiple piles is allowed

Problem Detail: 

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.

Asked By : Kaidul Islam

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56823

3.2K people like this

 Download Related Notes/Documents