Author: Anthony Bailey
Date: 10:34:34 09/15/99
Go up one level in this thread
Using existing tools with minimal tweaks and the right kinds of inputs to yield some useful results is clearly a good strategy. A kqqkqq tablebase would certainly be useful to the World Team for this match. Thankyou, Eugene Nalimov. However, much of the current analysis concerns whether or not White can force a promotion at all. Also, complete analysis is not required. If one can e.g. show a line that avoids any position involving a promoted queen that is even plausibly winnable for White, then a drawing variation for Black has been found. Therefore, we do not need to backtrack from won and lost positions only. We could e.g. backtrack from positions evaluated by a shallow move search. We would use as many ply as we could get away with, but it seems that five or six would almost certainly be sufficient to cover the interesting cases, even more so if the kqqkqq tablebase were available. Even a lesser search could yield a database that was useful in practice. So: suppose we generate a database of the positions resulting from one player having promoted one of their pawns to a queen, and attach one of (say) six evaluations to each of these definitely won for White, probably won for White, probably drawn, definitely drawn, probably won for Black, or definitely won for Black. For the purposes of the World team, anything better for Black than probably drawn is definitely worth aiming for and anything worse than probably drawn is certainly not; one could thus reduce the evaluations to a set of two or three if one made particular decisions about how to treat the "probably drawn" case. An important point here is that once the (presumably _relatively_ trivial; something that feeds the relevant positions into the correct Crafty routines would suffice) software to generate parts of such a database as disk files is written, the task can be distributed amongst many machines if necessary. For this reason, I hope it might be plausible to generate a database like this. The useful starting databases to build are: Black to move, white king and queen anywhere, second white queen on g8, black king and queen anywhere, black b-pawn either missing or on b7 through b2, black d-pawn either missing or on d6 through d2. Approximately 0.65 "Giga-positions". White to move, white king and queen anywhere, white pawn on any of g5 through g7, black king and queen anywhere, black b-pawn either missing or on b7 through b2, second black queen on d1. Approximately 0.328 "giga-positions". White to move, white king and queen anywhere, white pawn on any of g5 through g7, black king and queen anywhere, second black queen on d1, black d-pawn either missing or on d6 through b2. Approximately 0.281 "giga-positions". By a giga-position I mean 2^30 positions. That's approx 10^12 positions in total to evaluate using a shallow search, with no dependencies between the evaluations and hence as much parallelisation amongst different processors and machines as you want, practical administration issues aside. Plausible? If so, one can then backtrack from a complete "probably" database like this on disk to build the tablebases that cover the earlier relevant positions using almost standard methods; and these are smaller than monsters such as kqqkqq. The most useful tablebase to build would be kqpkq(p)(p) for the special case where the White pawn is on g7, and Black pawns are a b-pawn either missing or on b7 through b2, and a d-pawn either missing or on d6 through d2. That would seem to be less than 2 x 64 x 64 x 64 x 64 x 6 x 7 = 1409286144 positions, about 75% of the size of the kqpkq database. From there one can go on to separately generate the equally sized tablebases for White pawn on g6 and White pawn on g5. This would provide a complete solution to the endgames of interest. It would contain some positions based on highly probable evaluations rather than lines backtracked to checkmate, but it seems it would still be a tremendous help to the World Team. Now, I am interested in the answer to two questions. For the sake of intellectual curiosity: is such an approach viable in theory, given the current state (i.e. available disk, RAM and processor speeds) of highish-end computer technology? For the sake of helping the World to draw with the World Champion: is such an approach plausible in practice, given the available resources? I know that it is much easier to talk about writing new software than to actually write it, and to talk about distributing a task amongst many computers than actually distributing it! (c: Thanks for any comment and insight. I'm very new to this stuff and so would appreciate explanations of my mistakes almost as much as positive assessments. - Anthony.
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.