CGT Class description

There were some issues and comments from Monday's post that I still have to look into. I will! Fear not!

I wanted to run the latest iteration of a game class description here:

Combinatorial Games are an avenue to model basic decision-making and computation. In this course, we will look at computational and mathematical basics of combinatorial game theory, analyzing such games as Chess, Go, Checkers, Domineering and Amazons as well as many others! Topics will include basic algorithm design, strategy analysis, games as a number system, impartiality, parity and a dip into computational complexity.

I mentioned in a previous post that this class is intended for undergrads, and will only require both basic programming and discrete math pre-requirements. Is this a good description?

Different Game Sums

Previously there had been some discussion about different methods for summing games. Normally, given two games G1 = {L1 | R1} and G2 = {L2 | R2}, we use the disjunctive sum to describe making one move:

Disjunctive:
G1 + G2 =

{ { L + G2 : L \in L1} U { G1 + L: L \in L2} |
{R + G2: R \in R1} U {G1 + R: R \in R2} }

Informally, a player may choose one of the subgames, and make one of the moves available to them normally on that summand.

Lots of the discussion of last month concerned "where to apply misereness" to a game. I was trying to apply it to the game objects themselves, while it is usually applied to the play of a game instead. Paul Ottaway stepped in and said this was okay while evaluating games using the short disjunctive sum. When taking the short disjunctive sum, a player does not need to choose a subgame on which they have a move, but if none legal move exists, they immediately lose.

This is not as immediately obvious to define in the above set-notation, so let's give it a try:
(Warning: Attempted Ascii Brackets ahead! Update: Ascii Brackets removed!)

Short Disjunctive: (Update: fixed spacing issue. Did I get it right, though?)
G1 + G2 = { Left | Right } where
if either L1 = null or L2 = null, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2} U { | 0}
otherwise, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2}
and
if either R1= null or R2=null, Right = {R + G2: R \in R1} U {G1 + R: R \in R2} U {0 | }
otherwise, Right = {R + G2: R \in R1} U {G1 + R: R \in R2}

(Did I do that right?)

Alternatively, one may want to consider the sum where each player chooses to make a move on each of the available game boards. This is called the conjunctive sum of games:

Conjunctive:
G1 + G2 = { { l1 + l2 | r1 + r2} : l1 \in L1, l2 \in L2, r1 \in R1, r2 \in R2}

This may seem simpler, but after getting used to the disjunctive sum, it likely seems much more complicated from a gamester's point of view. Perhaps we will cover these sums more in the future!

Are there sums I missed? Please let me know!

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.

Talking about Stubborn Matchmaker tomorrow

Wednesdays often require short posts. This one perhaps more so than others.

Tomorrow, I will be talking about some of my thesis work on the impartial game Stubborn Matchmaker. The game is based on pairing candidates in a Stable Matching environment where both sets have a universal preference. The game ends when the matching is stable (the ith candidate on the left is matched to the ith on the right, for all i).

In case you're in the Wittenbergish area (central-western Ohio), feel free to stop by at 4pm for the talk, which will be in room 320 in the Science Center.

Perhaps someone out there will have an answer to how the patterns we see in the game actually work!

-Kyle

Locality of Plays

When I'm looking at a game for the first time, before I think about strategies and analysis there are two properties I first consider. First, is the game partisan or impartial? Second, can moves be made anywhere, or not? The answers to these help package the game into one of four buckets.

Though I may not have that many game complexity results under my belt, I can't even fathom how else to begin hoping to prove a relationship between games. Those shown links between relationships are always amazing to me.

Consider the computational complexity of determining who will win a game and then narrow your gaze further towards those games which are PSPACE-complete (no one has complained yet that I talk too much about this...). The basic PSPACE problem of satisfying quantified boolean formulae (QBF) is the setting for a game: players alternate choosing boolean values for the variables, starting with 1 and going up to n. In the end, if the formula is satisfied, then "there exists" player wins, otherwise the "for all" player wins. To say this differently (and more correctly), if the last (nth) quantifier is "there exists" then the last player wins exactly if the formula is satisfied. If it is instead "for all", then the last player wins exactly if it is not satisfied.

This game falls into the impartial-and-restricted box: the identity of the current player doesn't matter, but moves are restricted in that you can't choose the value of any variable: only the next one in the list.

Thomas Schaefer made a big jump in his collection of game complexity results (On the Complexity of Some Two-Person Perfect-Information Games) by showing that Kayles is PSPACE-complete. Yes, it is true that both games are impartial, but he uses the QBF game to show that Kayles is hard, despite the fact that general Kayles does not enforce any restrictions on where a player can move.

In his proof, Schaefer creates a reduction to Kayles that simulates the forcing, making players take specific nodes or immediately lose. This is one of those beautiful jumps that opens things up for everyone else. Personally, I would always look at Kayles first if I hoped to prove an unrestricted game to be complete for PSPACE.

Are there other excellent jump examples? Do you think other properties deserve this? I considered planarity, but it doesn't seem difficult to overcome this.

Initial Game Positions

Note: it's unlikely there will be a post on Wednesday, as I am traveling to Massachusetts for American Thanksgiving.

We know the following non-constructive result about Hex and Chomp: the first player has a winning strategy.

This only applies to games in the starting position, and for different reasons for both games (although they both go by the "strategy-stealing argument" monker). In Hex, we know that it is better to have more tiles of your color on the board, so it is naturally better to be playing first. In Chomp, we have a very special move from the first board. This move has, as children, all the other children of the initial position. Thus, if you go first, there are two possibilities: either one of those other children is a winning move (make it!) or none are, meaning that the special move is a winning move (make it!).

As mentioned, neither of these are constructive as in neither hint at the best strategy. They just mention that such a strategy exists. We've noticed a similar situation with Atropos (at least as far as brute force searches have allowed so far). A repeating pattern of winnability appears: boards with n open circles along a side have a winning strategy for the first player exactly when n is congruent to 0 or 3 modulo 4. The other two (1 and 2) have a winning strategy for the second player. This may seem a bit convoluted (especially since it's only been shown up through boards of size 11 or so) but it is the same as saying that the first player has a winning strategy when there's an even number of open circles on the initial board, and doesn't when there are an odd number.

In general, Atropos and Hex are difficult to analyze (both PSPACE-complete) and Chomp has resisted all efforts to figure out. Could it be that for many games, the complexity of those initial positions is just inherently easier than a general game state? To some, this is very disconcerting. In some cases, the general state argument is a bit distracting: it could be that a winning strategy exists from that initial position and is easy to describe. Complexity results come from reductions that don't usually say anything about the difficulty of the game in common positions.

Could it be, then, that this easiness comes from the size of information needed to describe those initial positions? In a game of Hex, to describe an intermediate state, you need to list the color (or lack of) for each hexagon. With an initial state, however, you only need to specify the size of the game board.

Have a great Thanksgiving! Also, if you will happen to be in the South-Central Ohio area next week, I will be giving a talk here at Wittenberg on Matchmaker on Thursday (Dec. 3). More info about that soon!

Emotional Machines like Partisan Games

There is a real difference between impartial and partisan games. I don't just mean that analysis is different, or that impartial games will always evaluate to Nimbers. I'm referring to something more basic:

People generally like playing Partisan games.

I can best present evidence by looking at the vast array of published partisan board games. It is hard to find published impartial games! Instead, published games are able to support some sort of mantra. I have my pieces and you have yours. I will build up my position and at some points there may even be a lack of interaction with whatever you're doing. We will race towards some winning condition. I will be able to see my strategy materialize, whether or not it is a good one.

All of these are aspects of partisan games that are missing in impartial-land. In that mystical place, every move forcibly interacts with your opponent. Your board strength is tied precisely into who is the current player and not in some separate position that you can see. Instead of racing towards a finish line, both players are the same racer, just worried about which leg will be forward when the ribbon is snapped.

I think it's natural that we don't like these sort of games. I'm looking forward to playing a World War 2 simulation game with my dad this thanksgiving, but I wouldn't be looking forward to it if after each turn we swapped teams!

In the past few years, I've made some off-hand comments (not here, in "real life") about people being bad logical machines, but instead good emotional machines. We often allow our emotions to make decisions for us instead of precisely reasoning through all the logical details. Sometimes this causes bad decisions to be made, but sometimes it lets us get to the heart of the matter and make decisions quickly. I'm in no way a psychologist, so I won't attempt to back this up with any data and keep blundering ahead.

Partisan games really clue into this emotional capability. "Well, at this point, there are lots of my tanks on the board and not many of the opposing tanks... I must be winning." We hope to be able to evaluate the strength of our board position and we can at least approximate this by taking a look at the game state. "Is it better to go first in Hex? Yes, it's better to have more of your pieces on the board." That is the basic response, and it turns out to be true, though an actual proof is somewhat more involved.

This is more difficult with impartial games. Near the beginning of a long game of Kayles on a complicated graph, I am not sure whether I'm winning or losing unless I check all the possible moves. Oof! That is a logical problem my brain doesn't want to have to work through. (At least, not on it's own.)

I may continue challenging my students to impartial games, but soon they're going to get sick and ask me to break out a Hex board.

P.S. Enjoy the greatest rivalry in sports this weekend!