Author: GuyHaworth
Date: 13:20:34 09/09/02
Go up one level in this thread
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.
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
c) "unblockable checks" not indexed - but you obviously want to skip this
d) generalised treatment of castling rights and e.p.
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
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 ]
g) replacing 'broken' values by 'last unbroken' values to aid compression
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.
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.
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.