More on Sprague-Grundy Exercises, Including Solutions.

Revision en3, by sirknightingfail, 2018-11-09 22:40:49

This is a follow-up blog to this talk

I realized that the previous post doesn't exactly explain how to actually work out the solutions to the Sprague-Grundy problems, or how to code them. Within this follow-up blog, I shall attempt to explain some of my thought process on working through Sprague-Grundy and similar problems, as well as including some code.

First, some pseudo-code of calculating the Sprague-Grundy, and how to find the MEX.

Recursive Sprague-Grundy

However, this implementation is inefficient, as it's not memoized, and we might recompute Sprague-Grundy of certain games quite a lot. Usually, if the game is just in terms of stack size, we can just go in increasing order to evaluate, since each move reduces the stack size, and we would have stored the values for smaller stacks into an array.

Consider a game where we're given a set S of numbers by which we can reduce the size of a pile. The following outlines how to use an array to calculate the Sprague-Grundy of a single pile.

Array Sprague-Grundy

Now, since we've computed the Sprague-Grundy for any given pile, we can determine who wins given a list of piles in the starting position in linear time. The S-Nim problem on kattis is basically these.

Sometimes, a turn on a game results in a combination of games of the same type. This is usually a strong indication for the usage of Sprague-Grundy. As an example, let us consider the Cuboid Slicing Game.

Each move can result in up to 8 different games of the same type. We consider any 0-volume cuboid as a losing position, as no further moves can be made upon it.

However, calculating the set of all possible next games might seem intimidating, but we can compute the Sprague-Grundy of game combinations using the Sprague-Grundy of the original games!

Let us first consider a pseudo-code of the recursion.

Inside the Sprague-Grundy

Converting this recursive definition to a solution that runs fast enough is left as an exercise. Additionally, some constant-factor optimizations may be needed.

Some further problems I could find are as follows:

Game of Cards

One of the techniques mentioned in the previous post can be used for this problem: 717D - Dexterina’s Lab

In addition, there are a few problems on ProjectEuler that these concepts are also applicable to.

Now, for solutions, or outlines of such, to the problems from the previous blog:

The Simplest Subtraction Game
Slightly More Complicated
One more for the road
Tags sprague-grundy, impartial games

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English sirknightingfail 2018-12-08 09:03:45 2706 finished up for posting (published)
en3 English sirknightingfail 2018-11-09 22:40:49 1982
en2 English sirknightingfail 2018-11-08 22:13:01 265
en1 English sirknightingfail 2018-11-08 21:48:49 4187 Initial revision (saved to drafts)