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!)
Red, Yellow, and Green Hats
17 hours ago
The underlying issue here, of course, is that it's very hard to talk about the complexity of any single problem. Is chess more complicated than tic-tac-toe? Most people would say yes, but if you had a computer that was designed only to play chess, and could only play tic-tac-toe by translating each tic-tac-toe position into a chess position, the computer would find chess easier.
ReplyDeleteTo avoid such difficulties, computer scientists look at classes of problems, rather than individual problems. Each problem in the class has a certain size, and they look at how complexity increases in relation to size.
For example, you could easily imagine playing tic-tac-toe on boards of various sizes. Computer scientists can analyze how the complexity of tic-tac-toe varies with the size of the board.
Chess, on the other hand, doesn't generalize as easily to larger sizes, which makes it difficult to talk about the complexity.
I imagine there might be people out there who do play a generalized version of chess. If so, what is it? (And who are these people?)
ReplyDeleteAlso, Ben, please feel free to give yourself a big "First!" for being the first commenter to this blog :)
ReplyDelete