### Combinatorial-Game Categories

#### Posted by Mike Shulman

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.

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.

## 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.