Col is one of three basic placement games on graphs along with Snort and Node Kayles. In all three, players take turns painting vertices their color, with a restriction based on what colors are neighboring. In Col, you can't paint a vertex adjacent to another vertex that already has your color. In Snort, you can't paint adjacent to a vertex in your opponent's color. In Node Kayles, you can't paint adjacent to either color. (That's not usually how Node Kayles is described, but this is equivalent.)
Winning Ways mentions these in its discussion of the computational complexity of games. (It's in Volume 1, chapter 7, "Hackenbush", under "NP-Hardness" as part of the chapter's Extras.) From Page 224 of the second edition:
"Even & Tarjan have shown that Generalized Hex is PSPACE-complete and Schaeffer [sic] has done the same for Generalized Geography, Generalized Kayles, Col and Snort."
Winning Ways is a fundamental work. In 2009, Alessandro Cincotti referenced this to state that Col was PSPACE-complete in his paper on a 3-player Col variant.
The sentence in Winning Ways is a reference to Thomas J. Schaefer's 1978 paper On the complexity of some two-person perfect-information games, which is probably the most important paper in Algorithmic CGT. In that paper, Node Kayles ("Generalized Kayles") is shown to be PSPACE-complete. And the same for Snort.
And not Col.
Like the others, Col is certainly in PSPACE: on a graph with n vertices and m edges, the height of the game tree is at most n and each player has at most n options on their turn. We can do an exponential-time traversal of the game tree using polynomial (in terms of n and m) bits to keep track of our work (Polynomial Space, PSPACE, sized) and determine the outcome class of the position in question.
The hardness was tricky, however. It seemed like an easy enough game, but Col is quite cold. Each position is equal to a number or a number plus *. For each player, the options might toggle the inclusion of that * and/or push the number towards the opponent's direction. There are no switches or otherwise hot positions where it is a significant benefit to play first. The lack of heat made it hard to find a reduction from another partisan games. Impartial games are automatically cold games, but reducing from impartial to partisan is a pretty tough paradigm shift. (It's not as bad to go the other way, e.g. the reduction from QSAT to Generalized Geography from Schaefer's paper.)
These inherent difficulties combined with the Winning Ways typo meant that Col's computational complexity went unsolved for a long time, despite the simplicity of its rules.
In 2009, Bob Hearn and Erik Demaine adapted Hearn's thesis into the book Games, Puzzles and Computation, which became a catapult to resolving the complexity of many other games that had eluded categorization, including Amazons and Konane. (This led to the coining of the term Algorithmic Combinatorial Game Theory, i.e. ACGT.) I met Bob Hearn a few years later and we agreed that solving Col was a big prize. Not only was it a long standing open problem, but the game seemed computationally hard and proving it would "cure" the hole and make the Winning Ways sentence true.
In 2013, 35 years after Schaefer's foundational paper, we got to work. Bob explained Constraint Logic, the main tool from his thesis, to me. We got the gadgets (mostly him) and everything slowly came together.
And then we got scooped. In early 2015, a team with Steve Fenner showed that Col was PSPACE-complete in Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.
The Col result is only a small part of Fenner, Grier, Messner, Schaeffer, and Thierauf's excellent paper, but it's an absolute gem of a proof. The reduction goes straight from Positive CNF and yields uncolored graphs! That means that these can be considered starting positions that are shown to be hard, an impressive feat! Finally, the question of Col's complexity was resolved, joining its cousins Node Kayles and Snort as PSPACE-complete.
We did continue our work. Part of the benefit of using Constraint Logic is that our reduction produced Col instances on planar graphs (though they certainly weren't uncolored). We also showed planar PSPACE-hardness of Fjords, NoGo, and Snort, which was an improvement on Schaefer's original non-planar case. With those additions, we got our paper out in 2018, one of my best publications.
Col remains an interesting ruleset in the short-lived history of ACGT. For a long time it was accidentally understood by many to be solved. Over 35 years after Node Kayles and Snort were solved, it was finally shown to be hard in two separate scenarios, independently proven in a short span. I'm very lucky that I got to be a part of such a cool "academic moment".
Currently the remaining "biggest" rulesets with unknown complexity are probably Clobber and Domineering. I know that advances are being made towards the complexity of at least one of these. Perhaps one day we'll see another race to the finish on another of the most highly-regarded games in CGT.
Edit notes: I originally had an image of the quote from Winning Ways, but it wasn't displaying properly, so I replaced the image with the quote.
No comments:
Post a Comment