Checkers has been mathematically solved -- indeed it's the largest game that has been solved so far.

What does this mean? It means that a proof has been worked out, in conjunction with some intelligent brute force move checking, that shows that if played perfectly, the game will end in a draw. And indeed, Jonathan Schaeffer, the researcher behind this (and an amazing games/AI expert in other areas, such as Hold 'Em Poker), has released a new version of his AI player, called Chinook, that cannot be beaten. The best anyone can do against this player, no matter how smart they are, is draw. End of story.

If you're having trouble understanding this, think of tic-tac-toe, which also always ends in a draw if played perfectly. Now we know checkers is exactly the same way, although while a human can be easily taught to play tic-tac-toe perfectly, I doubt the same could be said about checkers. That would be my first question for Schaeffer: can an expert learn to play it perfectly, now that we know how it's done? Or is the solution just too complex for us humans?

Scientifically, this achievement is interesting because checkers is a hard problem, and Schaeffer managed (albeit during over a decade) to finally solve it. That means similar approaches can be used for other similarly hard problems. Non-scientifically, this is interesting because it says something about games. Notably, I found this quote in the linked article worth quoting:

David Levy, president of the International Computer Games Association in London, UK, says he isn't planning to play against Chinook. "There would be a certain inevitability about the result."

Well, yes. But does this mean that expert checker players will no longer have any interest in playing? Unless my question to Schaeffer above is answered in the affirmative, probably not. Discrete games like checkers and chess are fun for humans to play precisely because the human brain is incapable of playing it perfectly. I am assuming that this will continue to be, even with Schaeffer's accomplishment, but if indeed it's possible to learn perfect checkers play, the game is effectively dead, just as tic-tac-toe is for those who care to learn the patterns.

So the next question is: can this happen to chess? The answer is yes, and it probably will one day, although the problem is on a much greater scale. If I had to guess, I would say that chess, like checkers and tic-tac-toe, always ends in a draw when played perfectly. Of course, it could be like Connect Four instead (or vice versa), where the first play always wins when playing perfectly. But if chess is ever solved, it is even less likely that perfect play could be boiled down to some trainable patterns such that a human could emulate it.

I guess that's why we call these discrete, rule-based back-and-forths "games" -- because deep down we know that the fun is all based in human shortcomings. Non-discrete games like baseball would be "solved" too, in a way, if a perfect robot batter could be constructed, but that's one kind of perfect play that normal humans could never emulate.

And so if you do figure out how to play checkers perfectly, and if chess is next to go down, then comfort yourself by learning to play Go. That's by far the largest traditional board game that humans play, and it's possible that it won't be solved until quantum computing becomes the norm. (via bb)

Like my post about The Illusionist a few weeks ago, I'm about to reveal the ending of Christopher Nolan's The Prestige. If you haven’t seen it and don’t want the ending spoiled, stop reading now.

If The Illusionist and The Prestige are rival magicians, then the latter is Ricky Jay and the former is David Copperfield. This analogy holds in several ways, but the most relevant is that The Prestige is the better movie. I will admit up front that part of what makes The Prestige so enjoyable is how it compares to The Illusionist, but it also is engaging and fun in its own right. But like I did with The Illusionist, I'm going to put aside all comments about plot, character, and cinematography (all entertaining in both films to various degrees) and just talk about how The Prestige approaches magic on film.

Here are two things I said about The Illusionist:

1) [M]agicians, as in the real-life profession kind, probably wouldn’t like this movie.

2) The fact that the “real” magic in the movie wasn’t grounded in the actual craft destroyed my suspension of disbelief.

In both cases, I believe the opposite to be true in The Prestige. Let's start with the first quote.

I don't know any magicians personally, but I think they would enjoy watching this film. Unlike The Illusionist, which solely relied on special effects to depict its most complex magic tricks, The Prestige is all about the mechanics of the tricks. The fun of the movie is trying to guess how the two rival magicians Alfred Borden and Rupert Angier, played by Christian Bale and Hugh Jackman respectively, perform their respective flagship tricks where, in both cases, a man is instantly transported across a stage. In the meantime, and entertainingly, the rival magicians are constantly showing up at each other's shows in disguise and disrupting the other's tricks, often in a humorously cruel and physically harmful manner.

The Illusionist was based on one "magic" trick that was more of a Shyamalanian twist ending; The Prestige bases its two big tricks on the actual craft magicians use, making it more fun to puzzle out during the film. Even though I figured out how the two Transporting Man tricks were done well before the reveal at the end of the film, it didn't matter because 1) it made sense in the logic of the film; 2) it didn't remove the tension from the plot; and 3) I wasn't entirely sure about one of the tricks until it was explicitly revealed, since it relied on a bit of science-fiction.

Before I move on to the second quote, let me discuss the operation of the two tricks. The secret to Borden's Human Transporter is grounded in the mundane -- throughout the entire movie, we are led to believe that there is only one magician, but in fact Borden has an identical twin. The twins have been sharing wives, mistresses, dismembered fingers, etc. all their lives, alternately playing Borden and disguising himself as his assistant Fallon. Their entire lives are essentially built around the performance of the Human Transporter trick. Angier's trick is grounded in science-fiction: he hires Nikola Tesla (pictured above, played by David Bowie) to devise a machine for him that creates exact duplicates of whatever is placed in the machine. Thus, every night Angier performs his trick, he creates an exact duplicate of himself which he kills off beneath the stage where blind stagemen are staffing the apparati, unaware of the nightly massacre.

Which brings us to the second quote. In The Illusionist, I was annoyed at how I had to suspend disbelief that the computer effects I was seeing were actually mundane magic tricks. I far preferred suspending my disbelief in The Prestige to believe that Nikola Tesla could have invented a matter duplication machine. What made this especially believable and interesting is that 1) Tesla was indeed a scientific genius; 2) he did in fact spend time in Colorado Springs working on ideas that the scientific community found to be bizzare; 3) he had fascinating visions of the future, such that all electricity would be based on wireless energy; and 4) the machine that Tesla creates in the film leads to all sorts of interesting philisophical problems. While his actual science came nowhere near creating a matter duplication machine, it was real enough to work within the context of the film. Plus, the addition of Tesla allowed his real-life rivalry with Thomas Edison to serve as a foil to the magicians' rivalry. Lastly, it says something interesting about the tenuous relationship between magic and science, perhaps embodied in the real world by Ricky Jay and in the film by the engineer Cutter, played by Michael Caine.

The Prestige is by no means a great film, but I thoroughly enjoyed deconstructing the tricks as the film progressed. If the reveal had only been the trick behind Borden's Transporter, it would've been mere Shyamalan. Instead, with the addition of Angier's soul-selling foray into science fiction, it climbs to a higher plane. A 2006 magician movie that David Mamet could be proud of.

Last minute thought: There is one hiccup in the set-up of the tricks in the film that a quick visit to the IMDB message boards brought up. Did Borden grow up with a twin all his life, or did he use another version of Tesla's machine to create his twin? I'm inclined to go with the former, since Bale is considered in the film to be the more ethical magician, but that does lead to a coincidence involving Tesla. If it's the latter, then why did Borden not know how Angier performed his trick? Any thoughts?

Last second thought: Continuing to read through the IMDB comments, I'm satisified with my original theory. Borden used Tesla to create a machine purely for show, whereas Angier convinced him to take the morally unsound step to make the actual duplication device. A coincidence, yes, but when it comes to Tesla, a reasonable one.

Last night, I was faced with An Inconvenient Truth, mediated by the soothing drawl of Al Gore. Here's why you should see this movie:

• It's not boring.
• Seriously, it's quite visceral and compelling.
• It presents the Global Warming problem using elegant and thorough infographics.
• It unquestionably settles three issues which have unfairly been considered as in scientific doubt:
  1. This is an alarming problem right now, not just 100 years from now.
  2. There is incredibly strong evidence that not only does Global Warming exist, but that the "nature is cyclical" argument is frighteningly not comforting in our present situation.
  3. Some believe that since the planet has seen extreme temperatures in the past, there's no need for us to change our way of life to avoid what's inevitable. Gore particularly emphasizes that this perspective is both immoral and unethical. By not taking measures now, we will be in effect responsible for future Katrinas, and on a much grander scale.
• Al Gore is a funny and informative lecturer.

The film could've used 10% fewer shots of Al Gore pondering, contemplating his past, etc., but the point of these scenes got across: Gore has spent a significant part of his life on this issue, he truly cares about it, and he thinks you should, too.