Game Description: Cookie Cutter

One thing I remembered I hoped to do with this blog was describe different combinatorial games. In honor of Paul Ottaway who made many comments the other week concerning adding misere games, I would like to talk about a game presented by him, Cookie Cutter. If there are other games you would like me to talk about, I would be glad to do so. Just let me know!

Cookie cutter is an impartial game that is deliciously reminiscent of Chomp. The state of this game is an n-by-m grid of squares---some of which may have already been cut out of the board---and an i-by-j cutter that is used throughout the game. During a player's turn, they may overlay the cutter anywhere on the board (without turning it) so that it overlaps at least one non-cut square (cookie). The cutter does not need to be totally contained within the n-by-m cookie grid (it can stick out over the side). All cookies under the cutter are then removed from the grid, and play passes to the next player. If no cookies are left, then the game is over and the player who cannot make a move loses.

This is similar to Chomp not only in that it makes me hungry to think about it, but also that Chomp is a misere instance of this game where the cutter is just as big as the square grid and it must cover up the bottom-right cookie each turn.

Perhaps this is a bit of a stretch, and some of the patterns Paul notices in his master's thesis are actually more reflective of Kayles.

This relationship is more clear in games with one row of cookies and a cookie cutter of odd width (say k). In this case, the first player may either cut up to k cookies off one end or remove k cookies and split the row into two parts. If k = 3, that's a lot like Kayles on a line graph. There you can either chop up the line into two parts, removing 3 nodes from between the two pieces, or cut two or three nodes off one of the ends. The difference? You can't remove just one node on an end.

It turns out that this form of Cookie Cutter results in periodic nimbers based on the size. For a row of cookies of size k, and an odd cookie cutter of width i, the Grundy value of the game is: k (mod (i+1)). This simple periodicity is due to the ability to remove one node from the end of a game, missing in Kayles.

Cookie cutter is only one of three games explored in Paul's masters thesis. His analysis naturally carries beyond the one-row version of the game.