Friday, February 24, 2012

Game Description: Rule 60 Game

Urban Larsson gave a cool talk at Integers 2011 about combinatorial games based on cellular automata.

Unlike the Game of Life (which is an automata, but not a game in the "combinatorial" sense), Urban concocted actual two-player impartial rulesets based on Wolfram's rules 60 and 110. I'm not familiar with these, but I do think the two games are very interesting!

The Rule 60 Game is a ruleset that uses a pile of matches and a pile of tokens. On turn i, the current player may remove as many matches as they want on their turn (at least 1) and a number of tokens between 0 and the number of matches taken last turn (inclusive). Additionally, you may not take the last match unless you also remove the last token.

Consider the position with a heap of four tokens, a heap of two matches and that last turn there were three matches removed. What is the outcome class of this game?

As it turns out, this game is in Fuzzy. You can't end the game this turn by taking both matches) because you can't take all of the tokens. Thus, the current player has to take one match and either zero, one, two or three tokens. By taking three tokens, the resulting game is still in fuzzy, as the next player wins by taking both the last match and token. Taking zero, one or two tokens, however, leaves the opponent unable to move because they cannot legally take the last match. Any of these three positions are in Zero.

Urban has also created a game based on Automata rule 110. Although the relevance to automata-theory is a bit lost on me, these games are interesting nonetheless!

No comments:

Post a Comment