Author: Vincent Diepeveen
Date: 15:29:54 09/09/02
Go up one level in this thread
On September 09, 2002 at 16:20:34, GuyHaworth wrote: >V > >May I recommend, without bias, Nalimov, Haworth and Heinz (2000), ICGA v23.3, >"Space-Efficient Indexing of Endgame Tables for Chess". >ICGA_J is available from all good ICGA websites - see www.icga.org newly in >development. > > >There is a similar publication in the Adv. Comp. Games 9 book (2001): ditto re >ICGA_J websites. that's the book i referred to in my other posting here. it's useless to me. talking about optimizations i do not care for. > >Those papers step you through a generally-applicable description of Nalimov >indexing including: > >a) Kings not adjacent - hence the 462/1806 > >b) N Like Men treated with generality - no 'side table' needed that's unreadable crap pseudo code. >c) "unblockable checks" not indexed - but you obviously want to skip this i am for now not interested in STM dependant optimizations >d) generalised treatment of castling rights and e.p. castling is not interesting obviously, a game where both opponents play to win, will always have castled or lost castling rights long before they get into endgames. > >The ideas that Eugene has not used, at least in public, yet are: > >e) endgames with Pawns partitioned up front by Pawn position > - but watch out for the fact that you equate a1 and h1 by 'mirroring' > - this is becoming necessary if you don't use 64-bit addressing 64 bits is a good advice for everyone with regard to EGTBs. everything i do is 64 bits in egtbs. >f) using DTZ rather than DTC or DTM metric - smaller depths involved > - just delays having to go beyond a byte/entry in uncompressed EGT > [ - however only 'DTR' guarantees you don't incur the avoidable 50m-draw ] as you should know by now i'm a factor 10 more efficient here by using win/draw/loss only. obviously mate in 61 i consider a mate too. that's a small price for a factor 50 in size (compresses better than DTM/DTZ/DTC. >g) replacing 'broken' values by 'last unbroken' values to aid compression win/draw/loss as i said you have just 3 choices no weird values :) >The 'neatest' properly retrograde (as per Ken Thompson) algorithm is by Wu and >Beale (IS and ICGA_J) but this has not been used in a major way on Western Chess >EGTs. >If your index-range calculations are right, and I've not seen these figures >before so that's a "first", 3Tera _is_ 3Tera and you can't compress the index >below that. >You can however compress the physical EGT when generated. about 150GB i estimate it at for all up to 6 men. uncompressed the 5 men if you calculated right are a bit less than 7 gigabyte *uncompressed*, which is already less than nalimov compressed and the outcome of the game is the same! > >It is an open question as to whether avoiding indexing "unblockable check >positions" is sufficient 'value' in the context of 'g' ... and in the context of >a possible requirement to build a fast inverse-index function which does >Pos(Index) rather than Index(Pos). > >A second open question is whether it is better to place all the sntm men first - >as then all successors of a position will be in the same partition of the EGT >(in the absence of pre-placed Pawns). The idea of placing the two Kings first >goes back to the 462/1806 economy but that can be effected anyway when placing >the 2nd King later. >That's most of the 'future agenda' on EGT-generation afaik. >Good luck. >g >PS: I am in the market for reasonable request of and information for the ICGA >website. It would be a great idea to put the icga articles online, though that generates a bit less income for the icga, it would make the ICGA a very serious organization also for those who want to start programming gameplaying, as a return many might register to the icga, i'm positive on that. It's a great idea to put articles online there. For sure whatever i write will be open to put on your homepage for that, also loads of other stuff needs to be published there then which doesn't fit in a few pages of the paper (logfiles and such).
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.