Friday, March 18, 2011

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

5 comments:

  1. red-blue hackenbush has only numerical values but is NP-hard.

    ReplyDelete
  2. Thanks for taking the time to read and respond to old questions! :) This is an interesting fact; I assume it's not known whether it's PSPACE-hard, however?

    ReplyDelete
  3. Yes. It is not known whether or not red-blue Hackenbush is PSPACE-hard.

    ReplyDelete
  4. Hmmm. I suppose the Hackenbush graph needs to be planar, so a reduction wouldn't be as easy to construct as it might initially seem. Hmmm.

    ReplyDelete
  5. I think the Hackenbush graph as originally described does not need to be planar. The Col graph, as originally described, does need to be planar. However, even without this restriction, the complexity of Col is not known. The complexity of Snort however is known to be PSPACE-complete on general graphs. The complexity of Col is interesting because the game is "relatively" cold in that making a move often reserves many spaces for the opponent. Do you know of any PSPACE-completeness results for cold games? I, for one, do not.

    ReplyDelete