Author: Bruce Moreland
Date: 22:19:31 02/02/03
Go up one level in this thread
On February 02, 2003 at 21:41:03, Mike Hood wrote: >To quote the words of a cynic during the Chessbase commentary on Kasparov-DJ >Game 4: "I doubt whether more than 1% of all positions in the tablebases have >been checked independently. And a mathematical proof of their correctness is not >easy at all." > >Let's forget the cynicism for a moment. I personally have no doubt in the >accuracy of the tablebases, based on my empirical observations of a few >positions extrapolated to the millions of other positions. My question is: Is a >mathematical proof of tablebase accuracy at all possible? The algorithm works via induction. It's not like these positions have been gathered together and some human has said, "I think that's a mate in 38". How these things works is that all possible positions are examined, and positions where one side is mated *now* are marked (apparently legal piece configuration, with one side to move, in check, and unable to get out of check). These are called "mated in 0" positions. Once this is done, all positions with each side to move are examined, and if any of them can reach a mated in 0 position, these are marked as "mate in 1". Now, we look at everything again and search for positions where all possible moves lead to "mate in 1" positions. These are marked as mated in 2. Now, we try to reach "mated in 2", these are "mate in 2". Next is a bit different, because we look for cases where it is impossible to avoid *either* "mate in 2" or "mate in 1". These are "mated in 3". And so on, until no progress is made. The rest of the postions are proven to be draws. It's a little trickier if it's possible to convert to a won ending, if you are trying to make a "distance to mate" database. You have to be careful of this idea of "no progress", because there are gaps. There might be a mate in 105 in KBP vs KN, but there might not be a mate in 95. This is because the mate in 105 might involve immediate conversion to a KBN vs KN, and yes, such positions do exist. It is possible that there are bugs. It would be possible to all but prove that there are no bugs, by comparing two sets of tables that have been created with different generators. I don't think that anyone has bothered to do this. I would strenuously object if someone tried to adjudicate a game against me due to a result from an endgame database, if they couldn't show me that the endgame database was correct and in perfect compliance with FIDE rules. bruce
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.