Combinatorial-Game Categories

November 16, 2009

Posted by Mike Shulman

$MathML-enabled post (click for more details).$

I just got back from the category theory Novemberfest at CMU, which was plenty of fun. One especially nice talk was by Geoff Cruttwell, who talked about axiomatizing the structure that exists on Joyal’s category of combinatorial (Conway) games. It turns out that the category of (finite) games is initial among such “combinatorial-game categories,” which implies a clever way to construct invariants of games. And naturally, the question of a terminal object is related to ill-founded or infinite games.

$MathML-enabled post (click for more details).$

Recall that a (finite) combinatorial game, as defined by John Conway, is a pair $\{L\mid R\}$ where $L$ and $R$ are finite sets of games. (We interpret $L$ as the set of games (or game-positions) that would result from the possible moves for the left-player, and $R$ likewise for the right-player. A player with no possible moves loses.)

For now, this is to be interpreted as a well-founded inductive definition. Thus, we have to start with the game $0 = \{\emptyset \mid \emptyset\}$ (which is lost by the first player to move), and then we can make $1 = \{0 \mid \emptyset \}$ and $-1 = \{\emptyset \mid 0\}$ and $∗ = \{0\mid 0\}$ , and so on. For any game $G = \{L\mid R\}$ we define $-G = \{-R \mid -L\}$ , the result of switching the roles of the two players for the entire game-play. And for $G$ and $H$ we define $G+H$ to be the game with $G$ and $H$ placed side-by-side, where each player can choose which game to move in at every turn. Finally, we say $G\le H$ if Left has a winning strategy when playing second in the game $-G+H$ .

The nice observation (due to Joyal) is that this preorder on games can be boosted up to a category of games, in which the objects are games and the morphisms $G\to H$ are strategies for Left to win $-G+H$ when playing second. The identity maps are the “copycat” trick whereby anyone can play chess with two Grand Masters at once and still win one of the games. To compose a strategy $\alpha$ for $-G+H$ with a strategy $\beta$ for $-H+K$ and get a strategy $\alpha\beta$ for $-G+K$ , the idea is to imagine games of $-H$ and $H$ also happening in your head while you actually play $-G+K$ . Suppose your opponent moves in $K$ . Then $\beta$ tells you how to respond in $-H+K$ . If it told you to move in $K$ , fine, do that. If it told you to move in $-H$ , imagine that your opponent copied that move in the virtual game of $H$ in your head, so that then $\alpha$ tells you how to respond in $-G+H$ . If it tells you to move in $-G$ , fine, do that in the real world. If it told you to respond in $H$ , then copy that move back over to $-H$ in your head, and so on until you get a useful move.

Now the question is: where do the first-player strategies show up? You can’t compose two first-player strategies, but you can compose a first-player winning strategy on $-G+H$ with a second-player strategy on either side; thus the first-player strategies form an endo-profunctor on the category $Games$ . What properties does this profunctor satisfy? Well, if $x$ is one of the left-options of $H$ , and I have a second-player winning strategy for Left in $-G+x$ , then I can get a first-player winning strategy for Left in $-G+H$ by saying “first play $x$ to get to $-G+x$ , then play the given strategy.” And dually, of course. Finally, there’s also a way to get a second-player winning strategy from a bunch of first-player winning strategies. In order to state these in terms of the category $Games$ , we also need to remember the “diproduct” operation that takes two finite sets of objects $L$ and $R$ and produces the object $\{L\mid R\}$ . Package all of this structure up with some axioms and you get a combinatorial game category. (According to Peter Freyd, in the absence of hyphens, adjectives associate to the right. So maybe these should be “combinatorial-game categories.” (-: )

Now the really nifty thing Geoff told us is that the category $Games$ is the initial combinatorial-game category. That means if you have any other cgc $D$ , you get a unique combinatorial-game functor $Games\to D$ , and therefore you get invariants of combinatorial games in $D$ . For example, he described a way to get a cgc structure on $C\times C$ whenever $C$ has finite products and coproducts. If $C$ is the poset $\mathbf{2} = \{0\le 1\}$ , then the invariant $Games\to \mathbf{2}\times \mathbf{2}$ sends a game to its outcome, which is two bits of information that tells you (1) who wins if Left goes first and (2) who wins if Right goes first. This is strongly reminiscent to me of the cobordism hypothesis in functorial field theory: the objects we want to describe invariants of (games, resp. manifolds) can be organized into some kind of category (a combinatorial-game category, resp. a pointed symmetric monoidal $n$ -category with duals) which is an initial object in the category of such categories. Thus, any other category of that sort gives us canonical invariants of the objects we were interested in to begin with. (There must be other examples of this sort of thing.)

Finally, the question was raised at the end of the talk, what about terminal objects? A coalgebraically-minded person might guess that the category of possibly infinite or ill-founded games would probably be a terminal object somewhere. Geoff pointed out that it wouldn’t be in cgc’s, but rather in a dual sort of notion, where rather than having structure that lets you build up a strategy from its constituents, you have structure that would let you break down a strategy into its constituents. This sounds like quite a neat idea, but as I think about it some more I don’t know how to compose strategies for infinite games. It seems like in an infinite game you might bounce back and forth forever between $H$ and $-H$ without ever getting a move to play in $-G+K$ . If it did work, though, it might give another sort of coalgebra in Cat.

Posted at November 16, 2009 7:08 PM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2111

39 Comments & 0 Trackbacks

Re: Combinatorial-Game Categories

Interesting. Is the definition of combinatorial game category written down anywhere?

Related to this, a couple of years ago I described a related result (here and here), classifying a different category of games as an initial model. In this I was very much inspired by the work of Cockett and Seely.

Posted by: Robin Houston on November 16, 2009 9:32 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

Awesome, glad you liked the talk Mike. I should point out this is joint work with Robin Cockett, who did the first of this type of thing - as linked above by Robin Houston.

Robin - I’m working on the paper right now. I might write up a version of my talk so people can have the notes online (this was a chalk-talk), which in particular would have the definition of a combinatorial game category. It’s similar to Cockett and Seely’s polarized game categories, but with a single “diproduct” rather than a polarized product and a polarized sum.

Your result looks quite interesting, I will have to look at it some more!

Posted by: Geoff Cruttwell on November 16, 2009 11:08 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

Re-reading those posts of mine now, it’s not obvious to me that they would be wholly comprehensible to anyone but myself. If anything’s unclear, let me know and I’ll do my best to clarify.

Posted by: Robin Houston on November 17, 2009 12:10 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

What is the meaning of $\multimap$ as a binary operation on games? Is $G \multimap H = -G + H$ ?

Posted by: Mike Shulman on November 17, 2009 2:35 AM | Permalink | PGP Sig | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

Hi Mike,

The category of Conway games is compact closed, and in that category indeed $G\multimap H$ is $-G + H$ .

The category I’m talking about actually has a non-degenerate symmetric monoidal closed structure. Let me give two answers to your question, one intuitive and one algebraic:

Intuitive

These games are played between two parties: O, who always plays first, and P.

The game $G\otimes H$ is played as follows: O plays a move in one of the two games, and then P must respond in the same game that O just played in. So O can “switch boards” at any time, whereas P is constrained to playing on the board that O has chosen.
The game $G\multimap H$ is the other way around: here P can switch boards at any time, whereas O is constrained to play on the board chosen by P. The opening move (by O) is played in H. Notice that this means the polarity of G-moves is reversed: when playing $G\multimap H$ , the O-moves of G are played by P, and vice versa.

Algebraic

Using the “lift-product category” notation, we can define

\otimes

and

\multimap

by mutual recursion. Let

G = \prod_{i\in I}\uparrow G_i

and

H = \prod_{j\in J}\uparrow H_j

, then:

$G\otimes H = [\prod_{i\in I}\uparrow(H\multimap G_i)]\times[\prod_{j\in J}\uparrow(G\multimap H_j)]$
$G\multimap H = \prod_{j\in J}\uparrow(G\otimes H_j)$

Posted by: Robin Houston on November 17, 2009 10:35 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

Do you know if anyone has looked at what happens in multiplayer games? It seems like negation ought to get replaced with a family of operations on the players which form something like a permutation group, but I have never seen the details worked out.

Posted by: Neel Krishnaswami on November 18, 2009 4:29 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

Having written the above, it occurs to me that I didn’t even mention the symmetric monoidal closed structure on the game category in this pair of posts, where I’m just treating it as an lp-category.

What prompted your question?

Posted by: Robin Houston on November 17, 2009 10:58 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

What prompted your question?

In the post you linked to, you wrote

the claim is that a morphism $X\to Y$ in $\mathbf{LP}$ is a total strategy for the game $X\multimap Y$ , where the trees $X$ and $Y$ are regarded as games.

I wasn’t able to interpret that without knowing what $X\multimap Y$ means. Thanks for your explanation!

Posted by: Mike Shulman on November 17, 2009 4:58 PM | Permalink | PGP Sig | Reply to this

Beyond direct sum of games; Re: Combinatorial-Game Categories

As a boy in Brooklyn Heights, I “invented” and many of my friends playing compositions of Monopoly, Chess, Checkers, and Poker. Only one of us went on to Master (nearly IM) in Chess namely Tournamaent Master Benjamin Nethercot. Several of us went on in Mathematics and Physics, such as Dr. Michael Salamon (NASA Discipline Scientist for Fundamental Physics).

I do not know how to express the strategies that emerged in playing games that were NOT merely direct sums of games. That is, a “move” would be offering a contract: “I’ll not take your rook’s knight this turn, if you only draw two cards in that poker hand, and I’ll sell you one free landing on Boardwalk for $500 Monopoly cash.”

The issue of whether chess is finite or infinite changed with revised tournament rules.

A key rule in Monopoly, for instance, is that no player may lend or give money or property to any other player. First order loophole is: “I collect paper, and like that $1 bill you have, I’ll give you $500 for it” – and 2nd order loopholes are the sort of offers I mentioned, which, if accepted, result in contracts. Once I created a corporation which eliminated all players from a Monopoly game, including myself.

Michael Salamon received his B.S. in Physics at MIT in 1972 and his Ph.D. in Physics from U.C. Berkeley in 1981. He remained at U.C. Berkeley as a Research Physicist until 1988, when he took a faculty position at the University of Utah, where he continued his research in high energy particle and gamma-ray astrophysics for thirteen years. He moved to NASA Headquarters in 2001 to take the position of Discipline Scientist for Fundamental Physics in the (then) Division of Astronomy and Physics of the Office of Space Science. He is also the NASA HQ Program Scientist for LISA, Planck, GP-B, and WMAP.

Posted by: Jonathan Vos Post on November 17, 2009 12:10 AM | Permalink | Reply to this

Re: Beyond direct sum of games; Re: Combinatorial-Game Categories

A key rule in Monopoly, for instance, is that no player may lend or give money or property to any other player. First order loophole is: “I collect paper, and like that $1 bill you have, I’ll give you $500 for it” – and 2nd order loopholes are the sort of offers I mentioned, which, if accepted, result in contracts.

But the loophole in the loophole is that such contracts are unenforceable, in the rules of Monopoly® that I know.

Posted by: Toby Bartels on November 17, 2009 5:47 AM | Permalink | Reply to this

I’ll take my bat and ball home if…; Re: Beyond direct sum of games; Re: Combinatorial-Game Categories

Correct. Enforceability comes from the combination with other games, and embedding in the social network which has social contract broader than games.

In many household, the player in whose home the game is played has special status for enforcement (i.e. play fair or I’ll tell my father to throw you out). Similarly, many homes have pseudo-rules beyond Monopoly official rules.

Regardless of how I saw things at ages 10 through 16, how indeed do we model the supergame in which multiple games are played at once, and deals transcend the boundaries of any single game?

Posted by: Jonathan Vos Post on November 18, 2009 1:10 AM | Permalink | Reply to this

Re: I’ll take my bat and ball home if…

how indeed do we model the supergame in which multiple games are played at once, and deals transcend the boundaries of any single game?

Well, the games that you played as a child are certainly one way to look at it. And to play those games for practical purposes, you just specify that contracts are enforceable (in the metagame if not in the original games). If the range of possible contracts is spelt out ahead of time, this may even be subject to the analysis of combinatorial game theory.

However, in real life (more the subject of game theory than of combinatorial game theory), contracts are not enforceable in the final analysis. Even the idea that, if push comes to shove, the police will take away what the court has ruled is not your property, is itself part of the game and subject to revolution.

Posted by: Toby Bartels on November 18, 2009 2:01 AM | Permalink | Reply to this

Re: I’ll take my bat and ball home if…

Short follow-up: “enforcement” need be no more than the evolution under repeated play with meta-strategies such as “tit-for-tat.” We have good models of that, and good Nash Equilibrium models of the games combined by various operators into combinations of games. Is it not significant that games as simple as Rock-Paper-Scissors have been proven Chaotic when played with unlimited numbers of repetitions?

Posted by: Jonathan Vos Post on November 18, 2009 6:31 PM | Permalink | Reply to this

Re: I’ll take my bat and ball home if…

“enforcement” need be no more than the evolution under repeated play with meta-strategies such as “tit-for-tat.” We have good models of that, and good Nash Equilibrium models of the games combined by various operators into combinations of games.

Yes, but now we really are leaving the realm of combinatorial game theory!

Posted by: Toby Bartels on November 18, 2009 8:29 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

Here’s something else that really interests me about Conway games. As observed by Joyal and Moerdijk, the class of well-founded extensional relations (that is, “sets” in the sense of material set theory) is the initial algebra for the “powerclass” functor that sends every class $X$ to the class $P_s(X)$ of subsets of $X$ . Dually, the class of ill-founded extensional relations is the terminal coalgebra of $P_s$ . Similarly, I believe that the well-founded and ill-founded Conway games can be identified with the initial algebra and terminal coalgebra, respectively, for the functor $X\mapsto P_s X\times P_s X$ .

Posted by: Mike Shulman on November 17, 2009 2:35 AM | Permalink | PGP Sig | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

What luck! This reminds me of a question I had a while back which I never had the brains to answer for myself:

Per Joyal, the surreal numbers arise as the decategorification of the category Game. That is, we can call games $G$ and $H$ equivalent if there exist strategies $f: H\rightarrow G$ and $g: G\rightarrow H$ . Then we get an ordering on the equivalence classes of games: $[H] \leq [G]$ if and only if $f: H\rightarrow G$ exists. The surreal numbers are the abelian group formed by these equivalence classes, much like the natural numbers are the decategorification of FinSet.

In his book On Numbers And Games, Conway points out that the real numbers $\mathbb{R}$ can be constructed as a subset of the surreals. We have to eliminate the infinite and the infinitesimal quantities which arise when constructing the surreals, so, Conway says, we should call $x$ real when $-n < x < n$ for some integer $n$ , and $x$ falls into the equivalence class of the game

$\{x - 1, x - \frac{1}{2}, x - \frac{1}{4}, \ldots | x + 1, x + \frac{1}{2}, x + \frac{1}{4}, \ldots\}.$

These conditions boil down to requirements for the existence of strategies. Left has to be able to win when playing second in the game $-N + X$ , and so forth.

In the surreals, building negative integers is as easy as building positive dyadic rationals (both involve using two colours in Hackenbush chains, or equivalently, plus- and minus-signs in sign-expansion notation). So, might there be an alternate way to categorify fractions and subtractions in here somewhere?

Posted by: Blake Stacey on November 17, 2009 4:48 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

Interesting question! I just want to note briefly that the surreal numbers are not the decategorification of the category $Game$ , but of its subcategory $Surreal$ (or, following Conway, $Number$ )—not every game is equivalent to a surreal. For instance, the game $\{0\mid 0\}$ is not, since it is a first-player win, while all surreal numbers are either zero (second-player win), positive (Left wins), or negative (Right wins).

Posted by: Mike Shulman on November 17, 2009 6:07 AM | Permalink | PGP Sig | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

Correct, of course — if I recall, the games which aren’t equivalent to surreals become what Knuth’s book calls “pseudo-numbers”.

Posted by: Blake Stacey on November 17, 2009 7:46 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

Yes: not to beat a dead horse, but the condition that a game be a number is that no left option is greater than a right option, and that all options are themselves numbers. Highly recursive way to set up the definition as you can see; makes me think it might be hard to “coalgebraize” numbers.

You can add and subtract games, but as far as I know there is no multiplication of games that restricts to multiplication of numbers.

I sympathize with Minhyong’s lament about the comments coming in so fast!

Posted by: Todd Trimble on November 17, 2009 12:00 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

Conway’s definition of multiplication (ONAG, p. 5) is moderately hairy:

$xy = \{x^L y + xy^L - x^L y^L, x^R y + xy^R - x^R y^R | x^L y + xy^R - x^L y^R, x^R y + xy^L - x^R y^L\}.$

The left set gets contributions from like sets, and the right set gets contributions from opposite kinds. For example, $0 \cdot 1$ is $\{|\} \cdot \{0 | \emptyset\}$ , so the left-hand contributions to the left set are

$\emptyset \cdot \{0|\} + 0 \cdot \{0\} - \emptyset \cdot \{0\} = \emptyset + 0 \cdot \{0\} - \emptyset \cdot \{0\} = \emptyset.$

The other contributions work out similarly: everything ends up being the empty set, so the answer is $\{\emptyset | \emptyset\} = 0$ .

Conway motivates this definition from the observation that, because $x - x^L \gt 0$ and $y - y^L \gt 0$ , then if multiplication makes any sense at all, we should have $(x - x^L)(y - y^L) \gt 0$ and thus $xy \gt x^L y + xy^L - x^L y^L$ .

Posted by: Blake Stacey on November 17, 2009 4:00 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

A few years ago, Jim Dolan and I started to work out a similar notion of composing strategies for games (with simply a first and second player, no left or right) that resulted in a closed cartesian category; the invariant of who wins was given by an exponential-preserving functor to $\{0,1\}$ . I'll try to dig it up if anybody's interested.

I should note that Jim was almost certainly inspired by something that somebody else was doing, perhaps precisely what Mike is talking about here.

Posted by: Toby Bartels on November 17, 2009 5:36 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

I’ll try to dig it up if anybody’s interested.

I’m interested!

Posted by: Mike Shulman on November 17, 2009 6:09 AM | Permalink | PGP Sig | Reply to this

Re: Combinatorial-Game Categories

the discussions that i had with toby (and some other people) about cartesian closed categories of games were mostly just rediscovering ideas that other people had already worked out.

i have one somewhat silly question that i’d like to ask here.

the basic example that i first became interested in was the free cartesian closed category on one object x (where “cartesian closed” is taken to mean that finite products and exponentials exist). it’s a fun exercise to describe this category and to give it a combinatorial-game interpretation. decategorifying by taking isomorphism classes gives the free “products-exponentials algebra” on one generator x. this can be thought of as the ordinal “epsilon-nought”. an element of epsilon-nought can be notated as a sort of tree, the “move-tree” of the corresponding game. if you replace each edge of the tree by the generator x and subject the tree to a stiff westerly breeze then the resulting picture looks like a usual simplified products-exponentials expression with products represented by juxtaposition and exponents represented as superscripts to the right.

(i don’t have facilities at hand right now to produce an example picture to illustrate what i mean here. also, it’s not necessary to try to remember whether westerly means “from the west” or “to the west” because fortunately it means both.)

determining the “value” of a game given its move-tree can then be reduced to mere arithmetic: simply substitute 0 for x, and the resulting value of the products-exponentials expression is the value of the game (to the second player).

the silly question that i’d like to ask here is: what about substituting other numbers for x besides x=0? is there any interesting conceptual interpretation of the numerical value obtained from a game by substituting x=k where k is some fixed nonzero number?

(in the limit as k approaches positive infinity, the order structure on the values reproduces the ordinal structure of epsilon-nought, in effect interpreting the products-exponentials expressions as “orders of infinity” in the sense of du bois-reymond.)

the products-exponentials expression f(g) for a game g is equal to the product, over all the possible first moves m, of x^(f(g_m)), where g_m is the game obtained from g by having the first player select the first move m and then regarding the original second player as the new first player. i made some attempt to interpret the logarithm of f(g) as a sort of “recursive partition function” with respect to a statistical mechanical model of the game g, with k interpreted as a temperature, but i never got this idea to actually work out.

Posted by: james dolan on November 17, 2009 12:16 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

well, i guess that the base k logarithm of f(g) can be interpreted as the value in “hereditary base k notation” of the “hereditary numeral” corresponding to the move-tree of the game g, as used in goodstein’s theorem. i think that i was looking for a different sort of interpretation though.

Posted by: james dolan on November 18, 2009 9:02 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

It’s hard to imagine any finite value other than zero having any kind of meaning here. But as we know zero is special, maybe it’s worth considering an infinitesimal neighborhood of zero and looking at the derivatives of f(g) w.r.t. x. You certainly start getting combinatorial structure as you differentiate, though I can’t see any obvious meaning.

Posted by: Dan Piponi on November 20, 2009 3:20 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

I wouldn’t really expect anything other than zero to produce something very interesting, game-theoretically. It seems like putting in zero is akin to saying “can you define a function/al of a given sort built from a type $X$ , even when you don’t know whether the type $X$ contains any elements?” Putting in other numbers would be like saying that you know the type does have some elements.

Posted by: Mike Shulman on November 20, 2009 4:46 AM | Permalink | PGP Sig | Reply to this

Re: Combinatorial-Game Categories

Not just akin, it’s precisely the problem of determining whether there is a function with the given type. You can convert (a finite) game tree to a type and then automatically generate an element of that type, if it exists, using a tool like djinn. The result is either a demonstration that this is a losing game, or a function that can be interpreted as describing how to win.

Posted by: Dan Piponi on November 20, 2009 8:07 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

There was a great discussion at this café in 2006 prompted by Trimble and Dolan’s characterisation of the free cartesian-closed category as a category of games. (The characterisation is actually much older, as discussed in the comments at that entry, especially this comment).

Posted by: Robin Houston on November 17, 2009 10:49 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

I'll try to dig it up if anybody's interested.

Robin reminds me that there was a post on the Café about this, a few months after I stopped talking to Jim about it, so you should just look at that.

Posted by: Toby Bartels on November 17, 2009 8:14 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

$MathML-enabled post (click for more details).$

This is strongly reminiscent to me of the cobordism hypothesis in functorial field theory: the objects we want to describe invariants of (games, resp. manifolds) can be organized into some kind of category (a combinatorial-game category, resp. a pointed symmetric monoidal $n$ -category with duals) which is an initial object in the category of such categories. Thus, any other category of that sort gives us canonical invariants of the objects we were interested in to begin with.

There’s another side of this coin, of course. Yes, representations of quantum groups give invariants for tangles as the initial category. But also tangles provide a diagrammatic language with which to prove things about representations of quantum groups.

So, could it be profitable to reason about a combinatorial-game category using $Games$ as a language? I suppose what would you’d want is a naturally occurring combinatorial-game category which you’d never suspected of having anything to do with games.

Posted by: David Corfield on November 17, 2009 8:56 AM | Permalink | Reply to this

Re: Combinatorial-Game Categories

It seems that there is some hope here for answering some old open questions. “Snaky achievement” is my personal favorite, due to its apparent simplicity and the ingenuity of the existing proofs. First a picture of a winning game for black:

.

A 2-dimensional “polyomino achievement game” is a generalization of tic-tac-toe or connect-four played on an infinite grid. Two players (white and black) alternately mark cells on the board. If the first player (black) can mark a set of cells congruent to a given
polyomino then he wins the game. The second player (white) wins if she can prevent the victory of black indefinitely. Often we restrict the size of the board!
A polyomino is called a winner on a certain board if black wins.

For 2d boards of any size all polyominoes are known to be losers except for 11 small ones and one for which the question is open: snaky, the 6-square polyomino pictured above. I wonder if the categorical approach can prove existence of strategies, without actually constructing them?

The proofs that demonstrate a polyomino to be a loser are very nice: white picks a (secret) paving of the board by dominoes, and whenever black plays in one half of a domino white answers by playing in the other half. For each of the loser polyominoes there is a
paving of dominoes for which every copy of the losing polyomino contains at least one whole domino!
Here is a paving strategy for white, shown defeating an attempt to make the polyomino outlined in green:

This paper seems to represent the most recent results.

Posted by: stefan on November 17, 2009 10:11 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

P.S. From my description above, you can immediately find 9 of the 11 known “winner” polyominoes. For the other two, see the references in the linked paper.

Posted by: stefan on November 17, 2009 10:21 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

The notes for my talk are now available at
http://pages.cpsc.ucalgary.ca/~gscruttw/CGCNovTalk.pdf.

Posted by: Geoff Cruttwell on November 19, 2009 10:36 PM | Permalink | Reply to this

Re: Combinatorial-Game Categories

Greetings !

I have invented a ’ combinatorial ’ game that might interest you.

You can view this paper and pencil game at:

http://connectcapture.blogspot.com/

——————————–

Rick Nordal - Vancouver, BC, Canada

Posted by: Rick Nordal on September 16, 2011 8:54 PM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

November 16, 2009