Return to my Checkers pages
Go to my home page
Copyright 1997, Jim Loy
You may print this and show it to others. But, this article will eventually be part of a book that I am writing. So, please do not distribute it widely.
A reader of these pages wrote:
>> We have just read the following assertion from your Checker Info page:
>>
> There is a widespread misconception about checkers, that it is a dead
> game because it is "solved,"
> that a super-computer can play perfect checkers the way that the ship's
> computer plays chess on
> Star Trek. It can be shown that CHESS can't be solved with any computer
> smaller than the entire
> universe. Roughly the same is true of checkers, even though it is more
> limited than chess.
>>> Has the claim that chess is computationally intractable been proven? If
> so, please provide us with citations. Also, if,
> as you intimate, CHECKERS is also computationally intractable, please
> provides us with these citations as well.
>
> If you cannot provide citations or explicit proof, please refrain from
> making such claims in the future.
> Are you appealing to a known mathematical result
Here's my response:
>Very amusing. I will continue to make such claims. Many people claim that it is solved, and none of them has a speck of accurate documentation. Are you claiming that it is solved?
>The games that have been solved (go-moku (similar to Pente) is a surprise, as it was solved recently) have been solved by examining the entire game tree. This complete game tree is so huge in chess (and other games like go), that it is easy to demonstrate that a computer larger than the entire universe would be required to solve it. There are several sources for the size of that game tree, some of which may be somewhat inaccurate, depending on the way they came up with their numbers. I don't have any of those sources handy. The efforts of various programmers to solve certain kinds of endings in chess have added a subjective verification to that claim.
>Well, the entire game tree in checkers is vastly smaller than in chess. But, again it is fairly easy to show that the entire game tree cannot be studied on any computer in the forseeable future. But, the smaller game tree in checkers makes it marginally possible that it can be solved without studying the entire tree. If certain lines can be shown to be forced, and those lines can be shown to be draws or wins, it just may be possible to solve the game without studying the whole tree. A massive attempt at that is being done at the University of Alberta (the Chinook project). Although they are nowhere near solving it yet, their program plays world-class checkers, perhaps better than any living human player, which lends some support to the idea that checkers may be solvable.
>Othello (Reversi) is a simpler game than checkers (not much simpler, actually). It too has not been solved. And, it too can be shown to have a game tree that is too large for any forseeable computer to study. Othello just may be solvable, without studying the entire tree.
>In my response, above, I say "The entire game tree cannot be studied on any computer in the forseeable future." By "forseeable future" I do not mean that it would require a computer a thousand times bigger and faster. That kind of computer is easily forseeable. No, the game tree in checkers would require much bigger powers of ten than that. Again, I don't have documentation at my finger-tips.
That generated this response from the reader:
>> [first email message] --a bunch
> of us were reading your web page on Mike's PC and I decided to write a
> response, there and then.>> > You write:
>> The games that have been solved ... have been solved by examining the
> entire game tree. This complete game tree is so huge in chess ... that
> it is easy to demonstrate that a computer larger than the entire
> universe would be required to solve it. There are several sources for
> the size of that game tree, some of which may be somewhat inaccurate,
> depending on the way they came up with their numbers. I don't have any
> of those sources handy. The efforts of various programmers to solve
> certain kinds of endings in chess have added a subjective verification
> to that claim.>> > What we would like to know is:
> > (1) Is there an agreed-upon method for generating the game tree?
> > (2) According to this method---if, indeed, there is one--what is the size
> (in terms of branching nodes) of the tree?
> > (3) What is the size of the universe?
> > Your claim requires that you know the answer to all three questions. In
> all seriousness, if you don't know the answers, stick to flying aces.
My next response:
>What are flying aces?
>1. A game (decision) tree is the data structure that a game-playing program uses to make a decision. You might want to study a book on artificial intelligence. In most games, the entire tree is too large, so the program studies a much smaller tree. The structure of a game tree is fairly well defined in the artificial intelligence literature.
>2. As I said in my previous message, I don't have the size of the tree at my finger-tips. And, I'm not sure where I've got that info. I've seen it in 3 or 4 different publications, but I don't know which ones. A person could estimate the size of the tree by estimating the number of possible chess positions. This too has been done several times, and this is where the number is somewhat inaccurate, as many of the possible positions are not really possible, as they cannot come from other possible positions. This number is mainly found in chess-trivia books, and I've seen it in several books. Again, I'm not sure which books.
>3. Cosmologists tell us that the universe began 10-15 billion years ago. That makes the maximum size of the universe 10-15 billion light-years. This is roughly the size of the universe that was used in a couple of computer books that estimated the size of the game tree of chess. A computer this size is, of course, chock full of computer hardware. The books also mentioned a length of time that this fictional computer would be working on the problem, and I forget the length of time. It was a long time, I assume it was in the billions of years, but I'm not sure. Anyway, the idea of all that was to show that no mere planet-sized computer could solve chess.
After checking with Jonathan Schaefer (of Chinook), I added this clarification:
>I guess I must clarify some things. The number of chess positions possible (as calculated in several chess books, a couple of which are chess encyclopedias which probably quote from other sources) is greater than the number of atoms in the universe (assuming that it is 10-15 billion light-years in diameter). So roughly, the complete game tree would not fit on a computer the size of the universe. But, the entire game tree does not have to be on the computer at once. And many positions are not important. Some experts in artificial intelligence think that a very large computer (larger than any in existence, but certainly smaller than a planet) may be able to solve chess by calculating for a few thousand years, maybe for hundreds of years.
>The size of the game tree in checkers seems to be roughly the square root of the size of the game tree in chess. That is still fairly huge, and the AI experts are undecided about whether checkers can be solved in the forseeable future.
>I was informed that gomoku was not solved by studying the entire game tree. Instead, a clever trick was used, one which cannot be applied to chess or checkers.
>Also, I stated that Othello is simpler than checkers. According to my rough estimates, the entire game tree in Othello is somewhat smaller than the one in checkers. But, AI experts consider Othello to be more difficult to solve than checkers. I assume that there are more trivial positions (and maybe more redundancy) in the checkers game tree.
Comment: For me, the interesting part of this exchange is that someone demands (in effect) that I not report what I have heard about certain subjects, unless I can prove the claims, or produce the sources. Sometimes, I deeply regret not being able to find and report the original sources. Sorry, sometimes I must rely on my memory. At other times I can indeed prove what I say, but choose not to (especially on demand).