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

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

ReplyDeleteThanks 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?

ReplyDeleteYes. It is not known whether or not red-blue Hackenbush is PSPACE-hard.

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

ReplyDeleteI 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