Author: Andrew Williams
Date: 03:04:59 06/08/03
Go up one level in this thread
On June 08, 2003 at 04:53:02, Geoff wrote: >Hi > >I haven't so far come across a proper explanation of how EGTB's work in >principle. Can anyone explain it in a sentence or two please ? > >I will have a stab at how I think it might work. > >Typically, for 5 or less pieces each position is stored in the table with just >the board position and a mate in x moves figure. The program can then just read >these figures for each possible move and navigate its way to a shortest mate. >But there are some more detailed questions such as > >1) What format is each position stored in ? >Does it just store position for say white and infer info for black ? > In principle, you use a six-bit number for each piece. So long as you always store these numbers in the same order (ie most valuable pieces first and less valuable pieces later), you can create a position signature which consists of n x 6 bits, where n is the total number of pieces on the board. You might then record one byte per position, where the range of numbers is -128 to +127. You could use zero for DRAW and the rest of the numbers to represent mate in X for either white (+ve) or black (-ve) or something. You might reasonably have two files, one for WTM positions, and one for BTM positions. >2) Does it store the whole position or use some symmetry tricks ? > I think much of the art of producing EGTBs is identifying symmetry and other tricks. >3) How were the tables created in the first place, quite a tricky algoritm I >would imagine !! > Please note, I've never tried to do this myself, but this is my understanding of "retrograde analysis": Generate all constellations of 3 pieces on the board (approx 64x63x62). For each position, check: is the side who is on move mated? if so, record that fact and then: Generate all positions which are "one move away" from this position - ie those positions which could have led to our mateD-in-zero position with just one move. These positions are mate-in-one positions. Eventually you will have a list with all of them. Now take each one and generate moves which could have led to the position: With each one, see if there are *any* moves available that do not lead to a mate-in-one position that you've already stored. If they all lead to such positions, then you have a mateD-in-one position. Record that fact and move on to the next mate-in-one position. Eventually, you'll have a list of all the mateD-in-one positions, to go with your mate-in-one positions and mateD-in-zero positions. Now your task is to go through the mateD-in-one positions list and check each one as above. >Without sitting down and trying to do the maths I had naively assumed that the >tables would all fit in 10 Megs or so. It is surprising, well to me at least >that the tables are so big > Nope. Your maths is a bit off there. In the above example, the numbers I have used (ie 63x63x62) are exaggerated: Obviously, two Kings can't be touching, so in some cases that would be 64x56x62. Also, if the third piece is a pawn, there are only 48 legal homes for a pawn: 64x56x47 (if the second king has only 56 squares, that means the first is on a square which could be occupied by a pawn). If you imagine a 5-piece example, without considering tricks like those, they would require 64x63x62x61x60x2 bytes (x2 becaue you need wtm and btm). That's over 100GB. As well as using all sorts of clever tricks to reduce this, the Nalimov TBs are compressed. AW
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.