?

Log in

No account? Create an account
An incredible story from the world of CS - Jim Huggins — LiveJournal
March 10th, 2007
08:08 pm
[User Picture]

[Link]

Previous Entry Share Next Entry
An incredible story from the world of CS
At the SIGCSE luncheon today, the featured speaker was Jonathan Schaeffer.  You've probably never heard of him; I hadn't.  Schaeffer is the man behind Chinook, the world's best checker-playing program.  And soon to be the only checker-playing program the world will ever need.

But I'm getting ahead of the story.

Schaeffer is an AI researcher.  He got started in AI in the early days of the field.  There was a lot of interest in the early days of AI in games as an interesting place to explore the nature of intelligence.  Games like checkers, chess, poker, and so on are intriguing.  The rules of these games are pretty simple, so it's easy to get a computer to play them.  But it's another thing altogether to get a computer to play them well.

The first approach that's taken in AI are what are called "weak methods": essentially, brute-force search, appropriately tailored, but without regarding to specific knowledge of the domain.  This is easy for simple games like Tic-Tac-Toe, which only has 765 different possible board configurations.  It's easy to develop a perfect strategy for the game, as any child discovers.  But checkers has roughly 5E18 (5 billion billion) possible configurations, which makes it much more difficult to find a brute-force solution.  (More on this later.)

For more complicated games like this, most brute-force machines do a form of look-ahead search: you compute n moves into the future, keeping in mind the alternating nature of the game, rate all of the board positions left at that point, and then choose the move which gives you the best chance of winning.  Obviously, the quality of your evaluation metric is critical, as is the value of n.  Larger n gives you better information, but at exponential cost.

In two-player games like chess and checkers, experts develop pre-determined strategies for the beginning of games (called "openings") and ends of games (called "endgames").  There are fewer states in these to explore than the vast middle-of-game state space, so that's where a lot of mid-level research goes into.

Anyways ... back to the story.

Schaeffer builds what he thinks is a great program ... and manages to talk some folks into letting it play in the U.S. checkers championship in 1990 against master-level players.  He ends up coming in second place, behind the reigning world champion.  The world champion agrees to play the machine in a master-level match ... and the world sits up and takes notice.

Go back to the link above and look for the story of the 1994 match between the man and machine, and you'll get a taste of the human pathos, the intrigue, the glory, the ignominy, the triumph and tragedy.  Listening to Schaeffer describe it was utterly incredible; you can see what this quest has cost him.

Ever since then, Schaeffer has been working on making the machine better ... in part with better algorithms, but largely by precomputing more and more openings and endgames.  Now, 18 years later, the quest is almost over.

In 3-5 months, Schaeffer expects to announce that Chinook is complete.  That is, their team of researchers and computers will have fully explored the 5E18 state space of checkers, and found the optimal move to make in every situation.  They already have half the proof done, for Black (the player who moves first).  That is, if Chinook goes first, it can't lose: it'll either draw (if you play it perfectly), or it might win (if you make a mistake), but you'll never beat it.  They're still finishing the details on what happens when Chinook plays White (the player who moves second).

That is utterly amazing.  It's taken 18 years to explore the state space fully, but it's almost done.  And a milestone in computer science will have been reached.

Current Mood: amazed

(Leave a comment)

My Website Powered by LiveJournal.com