Given the following game, I need to determine a winning strategy and find the set of positions in the kernel. I figure the best way to do so would be with Grundy numbers.
Rules:
- The game consists of two players who make moves in an alternate fashion
- A move consists of adding either 2, 3, or 5 cents to the pile (which is initially empty).
- The player who's move brings the pile to a square value (4,9,16,25,36) or forces the pile's value to exceed 40 cents wins.
Now, obviously, all the winning states are kernels (4,9,16,25,36, and "over 41") and therefore have Grundy numbers of zero. However, I am not exactly sure how to find the other nodes in the kernel and the Grundy numbers of the non-kernel nodes.
Go backward :
If from a position, you can reach a node in the kernel, it is not in the kernel. And if a node is not in the kernel, you can reach a node in the kernel from it.
So 40,39,38,37 are not in the kernel (by adding 5, you reach 41+) but 35 is (because you can only go to 37,38 and 40 that are not). Go on like that !