Tuesday, September 4, 2007

One Jump Ahead

Earlier this summer checkers had been solved. This was solved using what is known as a "weak" solve. It was not a complete tablebase of all the positions, which would be a strong solve. But rather, using a combination of an opening database, deep enough searching to get to the tablebases and significant enough tablebases, they could essentially guarantee a draw in every game.

The process of how this was started is published in a book titled: One Jump Ahead by Jonathon Schaeffer, the computer programmer and researcher that was in charge of the Chinook Project.

While chess and checkers only share an 8x8 board, there are many similarities in how each are programmed. How a program "thinks" about a position.

The whole opening's problem that is oft discussed here, is vital in checkers. What often separates a master from a grandmaster is the ability to deal with unpublished information. Both the master and grandmaster have the entirety of published information at their fingertips, and many games are documented from opening move to draw at the end, with critical moves having been documented with a * so you don't forget. Grandmasters collect cooks, different moves that are perfectly good, but unpublished, so that you have to be dependent on ability instead of move list memory.

This also tells the stories of the elite of the checkers playing universe. From Dr. Marion Tinsley, who according to computers made less than 20 mistakes in his entire tournament career. To Asa Long who one the US championship in 1922 and 1984 a sixty-two year span. A world record according to Guinness. And a remarkable group of characters that had honed checkers to an amazing edge, an edge so fine with a player so perfect, that it drove a researcher to solve the game.

Besides the concept to openings and cooks. The program actually became worse before it became better. Though not documented per se in the book, it is talked about obtusely when Marion Tinsley described the program as not playing as well, even though by every reasonable measure the program had been improved. I personally attribute this to the nature of the game. As the program was improving it was following more and more documented lines. This was dramatically less interesting to the grandmaster who already knew all of this. It was the new lines that had been discovered by an extremely good, but maybe not exhaustive program, that made "checkers fun again" for Dr. Tinsley.

At any rate, and y'all know what a PITA I am when giving reviews, this is oddly enough a real page turner. For those interested in games, and chess, and improvement (who US???), it is a very very good read. A bit pricey, but well worth it.

1 comment:

chess addict said...

Hi! would you mind if we exchange link in our chess site. I have also a chess blog and I wanted to have some link in other chess sites. Just inform me in my blog if that would be okay. Thank you so much.