Complexity in Games

Yesterday I was talking with some friends and I mentioned in passing that video games like Age of Mythology (and RTS games in general) are more complicated than old games like chess. That seems pretty obvious on inspection but a lot of people resist it. Chess is a game for smart people while little kids play video games, right?

But consider how in chess you never have more than a couple hundred (or less?) moves to consider. You have 16 pieces. Some of them can't move. The pawns only have (at most) 2 options, the rooks only have 16 each, same for the bishops, and the king only has 4 options--all maximums unlikely to be achieved. The entire "space" of the board in chess can be represented with an 8x8 grits.

In contrast, even a very basic model of an RTS would require choosing several functions from an infinite dimensional vector space. Consider a simple model that says the winner is whoever the person who achieves a certain ratio of "active military score" where "active military score" is a function of your "aggressiveness" (a function you choose) and your "military score" which is a function of what units you have. The unit you have, of course, is a function of your economy and your economy (with say, three resources) is modeled as being a function of three "investment functions" you choose, one for each resource. Each of these functions you choose--the three investment ones, the military spending one, and the aggressiveness one are chosen from the space of all functions. Look at how much longer it takes to write even a very basic description of the game! And to teach someone chess might take 30 minutes, but to learn all the basics in Age of Mythology would take at least an hour.

Still, there is some truth to the fact that chess seems just as strategic. Even though the choices are much simpler in chess and the perfect strategy (one where you can't lose or would always win), if it exists, would be much easier to compute--chess has crossed a threshold where that perfect strategy still is impossible to compute. And thousands of books and billions of books haven't gotten the world particularly close to one. This, I think, illustrates a principle Stephen Wolfram talks about in his book A New Kind of Science. What he found was that even very simple computer simulations can exhibit very, very complex outputs. In fact, in technical terms, even very, very basic models can emulate ANY output of even the most advanced computer. (It's hard to put into words without using technical terms. Read more here.)

Chess is very simple. But it's complicated enough where it has crossed that threshold of complexity where its hard to tell complex systems apart.

The other factor is how both games are strategic. And in any strategic game, where its hard to predict what the other person is going to do, things get chaotic fast. This is the one sense RTSs might be simpler than chess. Chess, as far as I know, doesn't have that strictly defined of a meta-game. People can approach it with a lot of different strategies that can be hard to tell apart after just a few moves. In contrast, Age of Mythology has converged over the years toward one major meta-game, as far as I know, of rushing early and fighting it out by the end of the third age.

But even very, very simple games can become "complicated" because of their lack of a meta-game. Consider Texas hold 'em. If you don't bet on poker and just play the hands the game is completely deterministic--no one makes any choices. The strategic element comes from the choice that comes up a few times a game where you have four options: raise, check, fold, see. The sample space of choices is tiny. But because its so difficult to predict what others are going to do the game is "complicated."

Still, I don't think anyone who plays both games would argue that RTSs in general are harder to play. People make a lot more mistakes in RTSs. One mistake in chess can cost you the game--it's a big deal. In contrast, if you don't make a bad decision a minute in an RTS you need to get out more. It's more mentally exhausting to play Age of Mythology at any level than chess.

P != NP

A researcher at HP Labs claims to have proven that P is not equal to NP. If that doesn't make sense, see this explanation from MIT News.

It looks like a credible candidate for a proof because, as Greg notes, Stephen Cook, a Turing award winner and the first person to pose the problem, considers it "serious."

I always thought this was the most interesting Millennium Prize Problem, maybe because it involves theoretical CS, but also because it's the only problem I understand enough to explain to someone else, sort of.

More on why journalists need to study math

Usually when I write about why journalists need to make more math it's to correct a misleading statement about a statistic. This time, in a new twist, it's to correct Jeff Jacoby's subtle error in reasoning.

If you didn't read the Op-Ed, he's criticizing the National Popular Vote Compact, which will ensure the winner of the popular vote wins the presidential election when enough states ratify it. It's hard to understand Jacoby's argument because his point is (to translate) "you Democrats are so dumb, like I once was, then I became a conservative" with an imitation of Buckly-Hitchens flair.

But what I think he's saying is this: "Suppose the Democrat wins the popular vote, then MA will give it's electoral votes to them. But they almost certainly would have won the state. Now suppose the Republican wins the popular vote. There's a good chance that the Democrat won MA, so the outcome is to flip MA's 12 electoral votes in the Republican column." This is how the compact "nullifi[es] of [voter's] vote[s]."

That almost sounds like it makes sense. The compact, most likely, will make MA voters have less say in the election because it increases the chances that Republicans will win. Except that it doesn't.

What Jacoby forgot is that, while it's true that under the compact MA's electoral votes will never swing to a Democrat, it's possible votes in MA could swing Texas into the "D" column. In 2000, for instance, Gore's 787k margin of victory in MA also gave him a 545k margin of victory in the popular vote. If the compact were operative in Texas that would have flipped Texas' 34 electoral votes from Bush to Gore and Gore would have been president--thanks, of course, to MA Democrats. But under the compact, Jacoby assures us, MA Democrats would have nothing to gain.

(That only applies to a state's vote as a whole. The issue for a single voter is the probability that without their vote, under the compact, the popular vote is a tie or, under current law, neither candidate has 270 electoral votes without their state and the election in their state is a tie. For MA it's obvious the  tiny, tiny probability of the former is many, many orders of magnitude larger.)