The death of checkers: My Times Year in Ideas piece

A couple of weeks ago, the New York Times Magazine published its 2007 “Year in Ideas” issue — their annual compendium of the year’s most interesting and offbeat research. I wrote up five of their scientific and technological entries. The entire issue is online here for free, but I’m also archiving my pieces here for posterity’s sake.

This one is about “the death of checkers” — the story of the scientist who solved the game. Reinhard Hunger did the awesome illustration that is thumbnailed above; check out the full-size version on the Times’ site!

The Death of Checkers

Checkers has been around for more than 400 years, has been enjoyed by billions of players and has taught generations of young children the joy of strategy.

And now it’s all over. This July, Jonathan Schaeffer, a computer scientist at the University of Alberta in Canada, announced that after running a computer program almost nonstop for 18 years, he had calculated the result of every possible endgame that could be played, all 39 trillion of them. He also revealed a sober fact about the game: checkers is a draw. As with tic-tac-toe, if both players never make a mistake, every match will end in a deadlock.

One upshot is that Schaeffer now possesses software that can play unbeatable checkers. Indeed, go to his Web site and you can play online yourself, providing you’re prepared to lose again and again and again — or maybe, just maybe, fight to a draw, assuming you, too, play with the crystalline perfection of a silicon brain.

Schaeffer did not solve checkers by replicating human intuition or game-playing ability. Rather, he employed what’s known as a “brute force” attack. He programmed a cluster of computers to play out every possible position involving 10 or fewer pieces. At the peak of his labors, he had 200 computers working around the clock on the problem, both in Alberta and down in California. (The data requirements were so high that for a while in the early ’90s, more than 80 percent of the Internet traffic in western North America was checkers data being shipped between two research institutions.)

The brute-force method is slow, which is its big limit. Schaeffer says he suspects you couldn’t use it to solve chess, because that game — with between 10 to the 40th and 10 to the 50th possible arrangements of pieces — is far more complicated than checkers, which has 5 × 10 to the 20th positions. “Chess won’t be solved in my lifetime,” he predicts. “We need some new breakthrough in technology to do that. CLIVE THOMPSON


blog comments powered by Disqus

Search This Site


Bio:

I'm Clive Thompson, a writer on science, technology, and culture. This blog collects bits of offbeat research I'm running into, and musings thereon.

Currently, I'm a contributing writer for the New York Times Magazine and a columnist for Wired magazine. I also write for Fast Company and Wired magazine's web site, among other places. Email or AOL IM me (pomeranian99) to say hi or send in something strange!

More of Me

Twitter
Tumblr
Flickr


Recent Entries

Teleportation, the last battle, and the Creator talks: How the world ends inside an online game

My latest Wired magazine column: Troll taming at Whitehouse.gov

Apparently NASA is filled with Joss Whedon fans

Incredibly weird, inch-wide single-celled creatures discovered rolling across the sea floor

In praise of the 3-hour game: My latest Wired News video-game column

» visit the Collision Detection archives

Clive Thompson's Tumblr
a bunch of stuff

March 25, 2009 » 05:10 PM
I had to ask! I was investigating getting DirecTV for my new office when I saw this pop-up window …

March 22, 2009 » 08:54 PM
““From an acoustical perspective, music is an overstructured language, which the brain invented and which the brain loves to hear.”” - Basics - In One Ear and Out the Other - NYTimes.com

March 20, 2009 » 04:48 PM
“No wonder young people find mainstream journalism uninviting; it would almost be more frightening if they embraced what passes for news today.” - The Death and Life of Great American Newspapers (Page 2)

March 19, 2009 » 01:12 PM
Printing The NYT Costs Twice As Much As Sending Every Subscriber A Free Kindle

March 18, 2009 » 08:44 PM
“Growth for the sake of growth is the ideology of the cancer cell.” — Edward Abbey” - Via Thor Muller’s twitter stream.

» visit my Tumblr

Recent Comments

Photos

» see all of my photos on Flickr

Collision Detection: A Blog by Clive Thompson