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