Saturday, July 21, 2007

Checkers solved

This article shows, I suspect, the risk of what happens when a journalist either doesn't fully understand the subject (and thus isn't sure what questions to ask, especially followup questions) or isn't familiar enough with it to anticipate readers' questions.

The Chinook program can play a perfect game of checkers once the number of pieces on the board gets below a certain point (10 checkers). The article says "It can't lose" after that, based on an exhaustive database. It's literally looked at every position with 10 or fewer checkers still on the board. But is any such position always a draw? Obviously not. I think--speculating, I haven't read the full paper--that what they're getting at is this.

There must be some combinations of pieces in which one side can force a win; e.g. 9 white, 1 black, I doubt Chinook could force a draw playing black. (Or perhaps so, by forcing a "no legal moves for black" situation, or if checkers has a 3-fold repetition rule like chess.)

But--if earlier play were strong enough to ensure that such grossly unbalanced positions don't come up in play--the discussion is academic.

And given a large enough database, good enough heuristic rules and position evaluations, and enough time to 'back up' the results farther up the game tree (this position is a loss for black, so a position that turns into this one is also a loss for black), it may be possible (duh, apparently is) possible to keep material balanced enough & positioning strong enough that forced-loss positions can be avoided when the exhaustive database finally kicks in.

Solving chess is going to take longer, of course. And at one time the ability to play chess was generally regarded as prima facie evidence of artificial intelligence--until, of course, the first chess-playing programs were demonstrated, and it was obvious that what they were doing was nothing like what people do when playing chess. But why should they? They're not people, they have different strengths and abilities. They're very good at numbercrunching--thus, computer chess involves lots of number crunching. They're good at database searching--thus, computer checkers (and chess) involves lots of database searching.

okay, this is what happens when I blog first thing in the morning.... i'm rambling.

No comments: