Author: Vincent Lejeune
Date: 03:08:45 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 ? I think all winning and losing positions are stored , remaining are draw ... the compression use the "godelian numbers" , i'm not a specialist , you can find more here http://fortuna.iasi.rdsnet.ro/ccc/ccc.php?art_id=292053 > >2) Does it store the whole position or use some symmetry tricks ? All possible symetries are used, without pawns : mirror, symetry in X and symetry in Y and symetry in diagonal you can find comments in crafty sources "egtb.cpp" such : // Enumeration: valid positions with 2 kings on board; white king restricted to // a1-d1-d4 triangle; also, if it's at a1-d4 half-diagonal, then black king // must be in a1-h1-h8 triangle > >3) How were the tables created in the first place, quite a tricky algoritm I >would imagine !! symetry is a bit tricky but search for mate-in-N is simple, the algo scan ALL possible positions, search the mate-in-one move then write this positions then scan again ALL possible positions search for all positions who can lead to mate in one then write this mate-in-2 ... and so on until there's no position who lead to mate ... > >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 I'm not an expert here too, let's take a KRPKR ending, possible positions is about 50*50*50*50*50*2 = 625 000 000 pos; about 1/3 is a mate (?)-> 200 Mpos one byte for mate length -> 200 Mbyte uncompressed !!! ;) > > regards Geoff
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.