A New CGT Blog and some complexity thoughts.

Oops, I missed an extra week in there. For some reason, these papers don't get graded unless I look at them... ;)

Fraser Stewart has a wonderful (relatively) new blog up at: http://combinatorialgametheory.com/.

I will continue with more regular posts! I promise!

I've been thinking a lot about the dichotomy of game complexity. Are there any rulesets with symmetric starting positions where the complexity of the game is NP-complete? (Usually they are PSPACE-hard or in P.)

If you drop the symmetric aspect, then it's easy to design games that are NP-complete. Take, for example, the following coloring game on graphs. Starting positions consist of a single red-colored vertex and a connected, uncolored graph. The red vertex is then connected to each vertex in the uncolored graph. In addition, there are some number, k, of additional uncolored vertices, each connected only to a single blue-colored vertex.

Play proceeds as in Col, meaning on their turn, a player chooses an uncolored vertex that is also not adjacent to a vertex of their own color, then paints that vertex. This game is NP-complete because the blue player is essentially trying to find a maximum independent set on the connected uncolored graph, with size greater than k.

Not all starting positions are symmetric, however. Col doesn't fit this description, because the starting positions in Col are uncolored and thus are symmetric.

EDIT (3/29/12): Corrected some spelling.

Game Description: Col

Col is another "classic" game that was first deeply analyzed by John H. Conway. It is a game that is inherently a graph game, but is often played on a whole piece of paper divided up into regions by drawn shapes. Each turn, a player chooses a blank region and paints it their own color. You may not choose a region that is adjacent to any other regions of the same color. (You can see some turns of the game in this very descriptive wikipedia page.) I'm sure whenever my future children are learning to draw in the lines, I'll try to coax a few games of Col out of them.

Col has an amazing, but beautiful property for evaluation: each position has a value equal to either a number or a number plus star. No Ups, Downs, *k's (for k > 1), etc. The elegant proof is based completely on the simplicity of the game value, showing that all left options are less-than-or-equal-to all right options for any game. With this Col fact, you can inductively assert that game values of the form {x | x + *} cannot exist (when x is a number). The only remaining options are numbers and numbers plus a star. Check out pages 47 and 48 of Winning Ways for all the details.

I was recently asked whether I knew the computational complexity of Col. I don't know that this analysis exists, but it could be that it is not computationally hard since the different game values have the nice property above. So far I don't know of any relationship between game value ranges and computational complexity (aside from impartial games with only values of 0 and *---those are solvable in Polynomial-Time because you never have a choice on your turn).