Author: Anthony Bailey
Date: 23:01:17 10/09/99
Go up one level in this thread
On October 08, 1999 at 09:26:20, guy haworth wrote: > I think the prospect of generating subsets of KQPKQP relevant to the > GKasp-World > game is remote because of the availability of the key EGT-workers, not because > of the intractibility of the problem. > > It's therefore worth discussing 'in principle'. Thanks for the input... I find the problem a very interesting one. I wish I had enough spare time to code the thing rather than just talk about coding it - but it's still enjoyable to discuss. > I agree that it is probably not too dangerous to assume P=Q (so that's MOD 1 > to any existing code). The problem is that the EGT will not represent > 'absolute truth' or have enduring value for the chess world. Yes, this specialisation would have been a test-case only. I presume that the complete set of six-piece but pawnless tablebases will become available before the ones with pawns, because of the greater availability of compression through use of board symmetries. So one could perhaps use this square-by-square technique as a temporary stop-gap to generate the six-piece EGTBs that feature pawns when the pawnless ones are within the reach of traditional approaches and current hardware but the pawnful ones are not. >Each database needs an index scheme to ensure that the range of position-index >numbers is not much greater than 4x that for KQQKQ. Just as the chef's secret >is in the sauce, the key to efficiency - which Eugene Nalimov has mastered - is >in the programming of these indexes. I assume that kqqkq takes advantage of the "two queens" symmetry; this is also available to kqqkq plus a particular square occupied by a pawn. There seems to be room to save a further five-sixths of the whole space by using board symmetries in vanilla kqqkq (i.e. one piece can be on a triangle of ten squares rather than on a full board of sixty-four), and this saving is not available for the kqqkq case with a particular square occupied by a pawn. If I'm right there, and kqqkq makes the maximum use of symmetries, I think kqqkq plus particular pawn has to be a bit more than six times as big. That seems to suggest that one would have to move away from using six bits per square to manage the job with 1Gb RAM; (2^6)^5 * (2 for side to move) / (2 for the qq symmetry) = 1Gb positions exactly. Using 64 * 63 * 62 * 61 * 60 < 2^30 for the basic encodings would give a little breathing space in the 1Gb of RAM though. This fine tuning may be more trouble than it is worth though; a bit more RAM than 1Gb is clearly enough, and since so many of the lines reduce quickly, perhaps it isn't so bad to page to disk a little? >So, in summary, I believe that the relevant subset of KQPKQP is computable with >today's 32-bit architecture and available computers - but the coding effort is >not. Yes, that's the conclusion I've been reluctantly coming to as well. A pity, but at least it seems that the thought experiment was vaguelly successful. (c: - 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.