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 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!)

Quiz Time!

I asked my students the following questions in class. We've covered outcome classes, but are not quite at game values yet.

Let X be the Domineering position that is two empty squares tall.

Let Y be the Domineering position that is four empty squares tall.

Find a Domineering position, G, such that X + G is in P (Zero) but Y + G is in L (Positive)

That one's not too tough. Neither is the next one:

Find G such that X + G is in R (Negative) but Y + G is in P.

This one's nice:

Find G such that X + G is in N (Fuzzy) but Y + G is in L.

My first solution for this one had a composite (sum) game for G, but I've since found a non-composite solution:

Find G such that X + G is in R, but Y + G is in L.

If you know a bunch about the values of Domineering positions, I guess these are relatively simple. If not (or if you are good at forgetting), perhaps they require a bit of extra time to consider.

Impossible Game States

While preparing some old work to go into my thesis two years ago, I realized a potential hole in my construction: could the Atropos boards described always occur in the midst of a game? I had built some convoluted board pieces, then glued them together in PSPACE reductions. But could these monstrosities actually be the state of a half-played game? Atropos has a requirement that players must play adjacent to the last play (if possible, otherwise you may play anywhere). Thus, some game states are impossible to reach.

Here, the lone red circle and the green and blue to the right are disjoint sections that could not have occurred without a colored circle surrounded by colored circles.

Does this ever happen with other games? Naturally, we need to consider a game that has regular starting position(s). Assuming we always start from a full n-by-m grid in Chomp, we will never see a board that is missing cookies in the wrong places.

A cookie in Chomp cannot be missing when any cookies up and to the right are also present.

Some games aren't quite so clear-cut. In Domineering, we would never have a board with an odd number of checkers covered. However, we might have that board as a piece of a more complex partition of boards, so it could be a legitimate subsection!

Consider Alice and Bob, who sit down to play a game of Chess. After a while, Bob thinks he is winning, and gets up to find a snack in another room. He returns and looks at the game board, realizing that he is actually in a bad state. What happened? Perhaps Alice switched pieces around, or perhaps Bob does not correctly recall the position of pieces. If Bob knows that no pawns have reached the opposite edge of the board, does Bob have any chance to prove that the current board state is illegal?

Are there any games where it is difficult to determine whether the game is in an impossible state?

Playing without Giving away your Strategy

Perhaps you are about to play a series of three games of cram against an opponent in the final round of a cram tournament. Your scored better than your opponent in the tournament thus far and must play first in the first and third games. The winner of the tournament will be the player that wins 2 of those 3 games.

While playing the first game, you can see that you are losing, but suddenly realize there is an really good strategy for winning from the start as long as you go second. Since this tournament uses initial 8 x 8 boards, you can use a symmetry strategy to mimic the other player's moves! Great! The next game is yours!

Unfortunately, you also realize the strategy is easy to follow. As soon as you use it against your opponent, they will be able to implement it themselves in the final game and win.

Is there a way to implement the symmetric-play strategy but disguise it at all? In general, is there a way to mask the fact that you are using a simple strategy to win?

In Nim, it is difficult to follow someone making the correct moves if you do not know how to evaluate the game boards. If it was plainly obvious what the other player was doing (perhaps XOR is your favorite math operator) then perhaps you would pick up on it quickly.

I tried this once, keeping a "turn behind" in the symmetric-play strategy. I kept making the play my opponent had made two turns ago, whenver possible. As I recall, it got messed up and I had to ditch it part way through. Is there any good way to keep this going? I feel this would be more difficult for an opponent to follow... if it works!

Game Description: Domineering

First, thanks to people who suggested I add rows to the game table page. Please suggest more games to add for rows!

In the past two weeks, I have gotten more chances to play games with Wittenberg students over lunch. This turns out to be one of the best ways to try out new games! Exploring them with other newbies is very helpful and the right attitude can add a non-competitive spin to the discovery of good strategies. Unfortunately, since these students have not been studying combinatorial games, I usually wind up with an unfair advantage. Not always, though. This is the best: getting beaten by missing a great strategy that gets pointed out by someone else! Seeing the realization of that great move in a student as they make it is wonderful!

Unfortunately, next I have to admit that I had never played Domineering before. Domineering is the guiding example for many basic combinatorial game aspects, yet I had never pulled out the dominoes and checkerboard before with another player. Actually, I don't even own dominoes; I had to borrow the set from our Math lounge.

Domineering is a partisan game between two players where each turn a domino is placed over two adjacent (share a side, not a corner) squares. The Left player must place dominoes vertically while Right must place them horizontally. You may not place dominoes on squares already occupied by a domino. Assuming normal play, the first player who cannot place a domino loses.

Domineering is a wonderful example for combinatorial games and game positions. It is used as the first guiding example in Lessons in Play, mostly because simple game values can be easily found. Good moves are sometimes very easy to spot, even long before the game ends. Perhaps most important, as the game continues, it clearly decomposes into smaller subgames that add together.

Still, while playing with students lately, one of them quickly became bored. "I wish we could play the pieces either way," she said (or something like that).

"That game's called Cram," I said. "I've also never played that one. Wanna give it a go?"

We played Cram, then quickly analyzed end game scenarios. We played it a bunch more times, allowing backtracking near the end and generally figuring out how a lot of the game worked. The next time, we skipped the Domineering and went straight to Cram.

This contradicted my assumption that many people prefer proper partisan games over impartial games. Is there a general consensus between these two games?

Best Intro Game?

I just had a wonderful visit this weekend with my soon-to-be-in-laws and they described playing Candy Land with their grandkids. Although I never played much as a kid, I think it's a good introductory board game. The game has good visuals, both using the imagery of delicious candy, but also using colors instead of words or numbers to describe moving around the board. This definitely appeals to 3-5 year olds---whatever that age range is called---and is likely the first board game many American children play.

What about when it's time to play games in the classroom? What should a student's first game be then?

I'm focused on impartial games, and versions of Nim had popped up in my elementary and middle school classes. Basic Nim is a candidate for a good introductory game: it is both simple and (surprisingly) has a very sneaky trick to determine who is winning. This gives it a very satisfying quality: we learn about the rules of a game and some of it's underlying details and then, happily, we find a strategy to play the game well! This is unlike some other games that are more fun to play but might be disappointing to students because they don't reach this step.

The text Lessons in Play decides not to introduce impartial games until much later, instead beginning with Domineering. This is another nice game, due partly to its simplicity. Another key point here, though, is that this game uses pieces from other known games: a checkerboard and dominoes. This can lend a sense of creativity to students. "Use your imagination to create your own games from the pieces around you!"

I've also heard from people who swear by Hackenbush. This is a game where your turn consists of erasing an edge of a graph (usually drawn on a whiteboard) that corresponds to your color. After your turn, if there are any subgraphs not connected to a ground node, those are also erased. This game has the excellent feature that it is super customizable and doesn't need to use a parallel-to-the-ground board at all. Again, this sort of thinking outside the box can be very beneficial to students!

Note that both Domineering and Hackenbush have easy extensions to impartial games. Thus, that transition can be made easily.

What else do people prefer? Are these two the most common? Is there anyone out there who advises doing impartial games first?

Partisan Game states that are Impartial

Partisan games are those where the different players do not have the same options for moves (such as in Hex or Chess, but not like Nim). Some states of partisan games, however, mimic impartial games.

This is demonstrated clearly in the game of Domineering, where players alternate placing dominoes on a checkerboard, each taking up two spaces. The Left player must play dominoes vertically (meaning they take up one space and the space directly below that) while the Right must play them horizontally. No pieces are allowed to overlap on the same square of the board.

Some situations in Domineering behave like impartial games, however. Suppose the only free space to play on a board is three squares arranged in the following way: (forgive my ascii art)

XXXX
XOOX
XOXX
XXXX

(Legend: X means this space is covered by a domino. O means this space is uncovered.)

Here, either player may play, but afterwards there are no available plays on the board for anyone. This is much different from

XXXX
XOOX
XOOX
XXXX

where after one of the two players makes a move, they will then be the only one left able to play there. For example, if Left plays on the above board, the situation then becomes:

XXXX
XXOX
XXOX
XXXX

leaving Left able to play again but Right with no such options. With our top example, however, either may play here, but only that one play is left. This is equivalent to the Nim state where there is one pile with only one stick in it. Either player may move by taking that stick, but then no more moves are available.

In 2005, Gabriel Drummond-Cole found positions in Domineering (and Chess!) equivalent to a Nim pile with two sticks. These Domineering states are quite a bit more complicated than those above. The most simple he finds is:

XXXXXXXXX
XXXOXOXXX
XXOOOOOXX
XOOXOXOOX
XXOOXOOXX
XOOXOXOOX
XXOOOOOXX
XXXOXOXXX
XXXXXXXXX

The ascii art here shows its inability to describe what is really happening here (see the paper for better pictures). Gabriel goes on to describe more such situations and even detail the patterns that cause this. One interesting note in this instance is that the covered square in the exact middle can also be uncovered: the value is still equivalent to the Nim-heap with 2 sticks.

Gabriel points out a problem with his constructions, however: there is no way to reach this game state from an initial board! Notice the blocked spaces (X's) in the middle of the diagram: they are each just one blocked square surrounded by unblocked squares. Thus, no domino could have been placed there.

Constructing these situations is a large task, aided often by evaluating software such as Aaron Siegel's Combinatorial Game Suite. Gabriel laments he has "not been able to find any ordinary Domineering positions" equivalent to the Nim-heap of size 2.

Finding other partisan situations equivalent to Nim-heaps is a continuing study. A Nim-heap of size 3 is equivalent to a game with two heaps, of sizes 1 and 2. Thus, we see that we can already have an equivalent domineering game by appending our two boards together:

XXXXXXXXXXXX
XXXOXOXXXOOX
XXOOOOOXXOXX
XOOXOXOOXXXX
XXOOXOOXXXXX
XOOXOXOOXXXX
XXOOOOOXXXXX
XXXOXOXXXXXX
XXXXXXXXXXXX

Work on finding partisan states equivalent to a Nim heap of size 4 is the next big task, and I have heard of some potential results... :)