(Late) MathILy-Er Wrap-Up: Combinatorial Game Theory

I should have written this post around two weeks ago, when MathILy-Er actually ended, but I didn’t, and I’m tempted to rationalize this late update by claiming I was reflecting on my experiences but in reality I was too busy for reflection anyway. Anyway, here it is.

Following up from my previous post about MathILy-Er, the summer program was five weeks of intense mathematics at Willamette University, Salem, Oregon, the expository details of which you can read in the linked post. Here I want to talk more about our two final weeks at MathILy-Er, called ‘Branch class’, and a general discussion of what I took away from my experience (in the next post).

MathILy-Er had two Branch class topics this summer: combinatorial game theory (CGT) and non-Euclidean geometry. Which class you were assigned to depended on the instructors’ evaluation of your particular interests and skills (and, to a slightly lesser extent, on your preference if you had any). I had no strong preference and was assigned to CGT. So what is CGT? (Perhaps the question should be, what do I think CGT is after two weeks of study?) CGT concerns itself with special kinds of games, in which:

• there are two players, ‘H’ and ‘V’ (the reason behind these letters is a long story)
• they make moves in alternate turns
• there is no randomness, only the players can affect the game
• they both have access to all information about the state of the game (e.g. where the ‘pieces’ are, how the ‘boards’ are arranged, how many moves have been made, etc.)
• there is at least one state in which H wins, and there is at least one state in which V wins, but there are no states in which both players win; infinite loops of states must be specially handled

It is likely that these characteristics are incomplete or can be made more precise because we came up with them in class, rather than using an external reference, but in any case they were sufficient for our purposes. (In fact, at no point during MathILy-Er were we allowed to use external references, which meant that we came up with tons of our own definitions and names for concepts that had already been defined and named in past mathematical research, and even our instructors took great care to use our names and definitions in whatever work we did and avoid giving us hints to things we hadn’t found out yet. Along with immensely helping us truly figure math out ourselves—‘learn from within’, if you will—this style of learning is actually really fun because you can be imaginative, to say the least, with names.)

Games that fall into the realm of what we discussed include chess, Go, Reversi/Othello, and a variety of common so-called ‘strategy games’, but we didn’t talk about those in much detail. A game that is central to CGT (for reasons that are kind of hard to explain in a short blog post) is Nim (which we called ‘zougxwuouang’). We also talked about the popular boredom-buster ‘Dots and Boxes’ where players connect adjacent dots in a grid, and if a player makes a box, they ‘own’ it; at the end of the game whichever player owns the most boxes wins. (Spoiler: Dots and Boxes is an incredibly hard game to completely figure out. Professional research has produced an entire, three-digit-page-number book on it which even our instructors could only get three-fourths of the way through.)

What do we want to do with games in CGT? The most pressing question is if there is a winning strategy. (A winning strategy is a strategy that a player can follow and always win, no matter what the other player does.) Sometimes there is a winning strategy for the player who moves first, and sometimes for the player who moves second; sometimes player ‘H’ always wins no matter whether he goes first or second, and sometimes player ‘V’ always wins no matter which position she plays in. Strange. Once we know who wins, we might want to evaluate game boards with some measure of how good the state is for a certain player. Of course, this is math, so we want to come up with a general value system that works for all states of all games, and crazily enough, we can abstract a game by only talking about values of positions and moves and then things get really strange. There are positive values and negative values and zero values and a parallel number line whose values are neither of the three and have funny addition; there’s a positive value smaller than all rational positive values, and a positive value smaller than that, and a positive value smaller than that… there are infinite values that are eerily similar to finite ones, and you can keep adding them to get ever-larger infinities…

Two weeks of CGT was enough to get me decidedly piqued about it. I think it’s extremely interesting and I especially like it because it forces you to wrap your head around the most weird things (there’s a parallel number line where 3 + 5 = 6? the number that was supposed to be before infinity is actually after it? what?) and get really intimate with abstractions (let’s play a game in which on every turn, you choose a game to play from a list whose values…). And there’s no way spending two weeks focusing on hard math could not be fun.

But that’s only the math part. I feel that the meta part was just as significant.