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!

Game Description: Clobbineering

The first time I taught a games class, my student Will Herrmann combined the games Clobber and Domineering into the excellent ruleset Clobbineering.

If you're familiar with both of these games, perhaps the rules are already clear to you. In case they're not, a turn consists of either making a legal clobber move with the checkers on the board or placing a domino on two empty spaces a la domineering. Thus, the player that clobbers with the black checkers is playing dominoes vertically, while the red-or-white checker clobber-player plays dominoes horizontally.

This is enough to make the game states quite difficult to analyze. Often times the game will seem like it's over in one player's favor, but then there's a really sneaky move that changes everything.

My usual strategy is to concentrate on clobbering to open up domineering plays for myself for later that don't allow my opponent to play dominoes. I don't have any better considerations than that; if my opponent catches the drift, I'm generally in trouble!

Game Description: Odd Scoring

Oops, I previously talked about Odd Scoring without giving a descriptive post. Let me fix that now!

One of my students presented this game in my first-year seminar to the class last semester. Here are the rules.

There are a total of an even number of horizontally-set spaces, with one marker placed at the far-right space. Both players keep their own score, which starts off at 0. Each turn, a player moves the marker 1, 2 or 3 spaces to the left, then adds to their score that number of spaces moved. Once the marker is in the far-left space, the player with an odd score wins.

Some interesting points:

* exactly one player will have an odd score, because there are an odd number of moves the marker will make in total.
* you really only need to keep track of the parity of the players' score. Having 9 and 3 points are the same.
* this is not strictly a combinatorial game; the last player to move may not be the winner!

Even though this game is not quite combinatorial, can it be considered all-small? Whenever one player has a move, the other also has a move. However, in some cases this is a move where the game ends, but the last player to move still loses. Consider the following game state:

_X_ ___ ___ ___ ___ ...

Left: 0 Right: 1

What is the value of this position? That definition may change whether this game is considered all-small or not! This may not be consistent with the definition of "points" considered earlier this week!

Combinatorializing Games: How do points actually work?

We've talked recently about combinatorializing connection games, but what about point-based games. Here's a general definition of a point-based game:

Players make moves and earn points during the game. This continues until there are no possible moves. When all moves have been made, the player with the most points wins.

What makes this not-quite-combinatorial is that it is not necessarily the case that the last player to move is the one who wins the game.

Flume is an example of such a game. Players score "a point" for each piece they play, and at the end the player with the most of their pieces on the board wins. Since there are an odd number of spaces, there will be no tie.

What happens, then, if you add two games of Flume together? What if you add a game of Flume to a game of Hex?

The way I've always envisioned these games working is as follows. Let's say the game ends with the left and right players each with their point totals (called left-points and right-points, respectively). Then a new game immediately starts with value: left-points - right-points, the winner of which wins the whole thing.

Thus, if you play a game of Flume and at the end the left player (Blue) played 9 disks while the right player (Red) played 16, then the result is game of value: -7, which the right player should win.

Is this how the "combinatorialization" is usually conceived? Is there another good way to handle this?

EDIT: Fixed a typo in the title. (Feb. 10, 2012)

Game Sum Demonstration Videos

A few weeks back, my aide, Ernie, and I played some game sums as demonstrations. Of special note, you may not have agreed with the non-all-smalling of Hex, and that may make you want to watch the last three!

Here are the links to videos:

Domineering + Clobber [6:32]

Domineering + Checkers (Draughts) [5:24] (Warning: this one is unsatisfying!)

Domineering + NoGo [4:14]

Y + NoGo [7:32] (Using the non-all-small Y)

Hex + NoGo [4:27] (Using the non-all-small Hex)

Hex + Clobber [13:16] (Using the all-small Hex!)