Thursday, February 25, 2010

The Big Game

My friend Michael just pointed me to a great article in the New York Review of Books. In The Chess Master and the Computer, former world chess champion Gary Kasparov discusses the battle for chess supremacy between humans and artificial intelligence. He writes:
It was my luck (perhaps my bad luck) to be the world chess champion during the critical years in which computers challenged, then surpassed, human chess players. Before 1994 and after 2004 these duels held little interest. The computers quickly went from too weak to too strong. But for a span of ten years these contests were fascinating clashes between the computational power of the machines (and, lest we forget, the human wisdom of their programmers) and the intuition and knowledge of the grandmaster.
I recommend the article to anyone interested in such things. Reading it inspired me to play some checkers against a computer for the first time in years. There's a fine Java checkers program online at It's amusing, then infuriating, how easily this little free program can crush a mere human each and every time.

I think it was in the 80s that my brother (the MIT prof) informed me that a computer had been programmed to beat the best checkers player in the world. But it wasn't until a couple years ago that computers completely solved the game:
... if black moves first, and both sides play per­fect­ly, the game ends in a draw. To reach this con­clu­sion, doz­ens of com­put­ers have been play­ing the game with state-of-the-art ar­ti­fi­cial in­tel­li­gence tech­niques al­most con­tin­u­ously since 1989...

Check­ers has about 500 bil­lion pos­si­ble po­si­tions and is the most chal­leng­ing pop­u­lar game that com­put­ers have solved to date.
And last year, for the first time, a computer bested a pro Go player.