Author: GuyHaworth
Date: 04:15:38 03/26/03
Go up one level in this thread
Presumably you are talking about 1_bit/position prior to a compression process
(which can reduce EGT-size to less than 1_bit/position).
There are two data-stores that you might be referring to:
a) the generated EGT(able) itself
- in which case it is a stm wins/does_not_win EGT, passably useful
b) a work-array during the EGT-generation process
- used by Thompson (DTC), Wu/Beal (DTC/M) and latterly Nalimov (DTM)
Thompson and Wu/Beal both 'unmove' from a 'frontier' of positions which had
their depths set in the previous cycle of the algorithm.
Usefully, all positions given a depth in a cycle ... are given the same depth.
Wu/Beal demonstrate that their efficient algorithm can be used for the DTM(ate)
metric - by deferring the promulgation of DTM=m depths until cycle ~m. Nalimov
also does this now.
I'm sure that the bitvector approach can also be applied to the DTZ(eroing
move-count move) metric, but this has not been demonstrated yet.
A work-array of 1_bit/position is created during a cycle and records whether a
position is in the new 'frontier set' or not. It is used to direct which
positions in the EGT are to be given a 'depth' [related to the cycle number] and
to drive the next cycle.
The old 'frontier set' bit-array is scanned serially, e.g., off disc.
Some juggling of multiple disc-drives and the mapping of files to disc-drives
can assist here to make the disc-I/O faster.
Also, I suspect that 'in flight' compression/decompression can perhaps speed up
the I/O at the cost of otherwise-idle GHz. The bitvectors are usually sparse.
I am not sure whether Nalimov generates his EGTs without 'unmove code', or
whether there is some there now. The ICGA_J EN/EH/GMH paper of 1999 was correct
at the time KxxKxx were generated (x = B/N/Q/R) but is perhaps out of date now
re Nalimov's current algorithm.
However, it does include generic algorithms for coding the 'sub-index' for 'L
Like Men'.
Papers worth consulting are therefore:
Nalimov, E.V., Haworth, G.McC. and Heinz, E.A. (2000). Space-Efficient Indexing
of Endgame Databases for Chess. ICGA Journal, Vol. 23, No. 3, pp. 148-162.
Nalimov, E.V., Haworth, G.McC. and Heinz, E.A. (2000). Space-Efficient Indexing
of Endgame Databases for Chess. Advances in Computer Games 9, (eds. H. J. van
den Herik and B. Monien). Institute for Knowledge and Agent Technology (IKAT),
Maastricht, The Netherlands. ISBN 9-0621-6576-1.
... one a small update of the other
Thompson, K. (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol.
9, No. 3, pp. 131-139.
Thompson, K. (1996). 6-Piece Endgames. ICCA Journal, Vol. 19, No. 4, pp.
215-226.
... with useful examples of what _not_ to do.
Wu, R. and Beal, D.F. (2001). Computer Analysis of some Chinese Chess Endgames.
Advances in Computer Games 9, (eds. H. J. van den Herik and B. Monien), pp.
261-273. Institute for Knowledge and Agent Technology (IKAT), Maastricht, The
Netherlands. ISBN 9-0621-6576-1.
Wu, R. and Beal, D.F. (2001). Solving Chinese Chess Endgames by Database
Construction. Information Sciences, Vol. 135, Nos. 3-4, pp. 207-228.
Wu, R. and Beal, D.F. (2001). Fast, Memory-Efficient Retrograde Algorithms. ICGA
Journal, Vol. 24, No. 3, pp. 147-159.
... all covering much the same ground.
- guy
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.