How to deal with moves that affect more than one existng pile in Grundy?

Revision en1, by mohamedeltair, 2017-09-22 20:11:18

When the subgames are independent, dealing with them is easy, you try to calculate grundy for each sub game, either you derive a dynamic programming solution or see if the grundies follow specific pattern then just code the pattern directly (this is useful if the limits are very high), finally you xor the grundies.

But suppose a game like this: you have n piles and each pile has number of stones greater than 0, in a move you pick a number of stones to remove, this number will be subtracted from any pile which has a number of stones greater than or equal the number you have picked, as you see here one move affects more than one existing pile, how to think in these situations ?

Tags game theory, #algorithms


  Rev. Lang. By When Δ Comment
en1 English mohamedeltair 2017-09-22 20:11:18 759 Initial revision (published)