I'm posting late on Wednesday. I'll have to learn to post while eating lunch in the future...
I've gotten a number of emails from people reading the blog, and perhaps I should clarify something about the complexity of games.
For playing Chess, the game is of a set size, and thus there are a constant number of possible move options each turn (it's a big constant). The input size is always bounded above: we know how big the game board is and what the maximum number of each piece there can be, etc. We can come up with an algorithm that will take a maximum amount of time (and space) to determine whether a player has a winning strategy.
When we talk about games (and problems in general) being "complete", this means refers to how the amount of time (and space) needed for a solving algorithm to finish increases as the size of the problem grows. With Chess, the board never gets bigger. There are only so many different configurations we can have on that 8x8 board.
Hex is a bit different. There is a standard size (11 x 11) but it's easy to see how this game extends to any given size: just increase the size of the board. Thus, assuming we can play on variable-sized boards, it makes sense to talk about the complexity of this game. Using this, it was shown that Hex is PSPACE-complete.
I've stated this before, but I haven't made it clear that I am considering the generalized, extendable versions of these games. I am, and I will likely continue to do so. There's a problem with this, however: I don't always know how those extensions work.
I claimed at one point that Chess is EXPTIME-complete, but I have no idea how Chess is generalized to an n x n board. I know only that there is a generalization and that it leads to the requirement of an exponential-time algorithm to solve it (I have a lot of reading to do).
Aside from this, though, does anyone actually play n x n Chess? I've seen a few variants: a hexagon-based variant and a weird three-player version, but I've never seen anyone play on a board larger than 8 x 8.
(Thanks to Aviezri Fraenkel for reading and mentioning this. I still have a lot of emailed comments to get to!)
A Domino-Covering Problem
2 weeks ago