A major 2018 achievement was the production of 7-man Syzygy ‘EGT’ endgame tables, both value-only ‘WDL’ win-draw-loss EGTs and depth EGTs to a metric notated as here. This resulted from a fine collaboration between Bojun Guo and Ronald de Man, evolving the latter’s code to resolve the issues of the larger 7-man challenge (CPW, 2018; de Man, 2018; Talkchess, 2018).
The ‘DTZ’ metric, Depth to the Zeroing of the ply-count, assumes the attacker minimises and the defender maximises the number of moves required to push a pawn, capture and/or mate while defending theoretical value. The metric does not give a depth to positions where the win can be frustrated by FIDE’s ‘50mr’ 50-move rule. ‘Depth’ is in winner’s moves or, better, plies.
De Man’s metric, in plies, improves on DTZ and . It recognises five outcomes, adding the finessed ‘frustrated win’ and ‘saved loss’ to the usual ‘win, draw or loss’ but assumes the ply-count is zero. It ascribes depths to the frustrated wins but adds 100 plies to some frustrated wins, those where it is necessary to distinguish them from wins not affected by the 50mr. However, when , may be the actual depth to ‘ply-count zero’ or one hundred plies more.
Bojun reports that most code changes needed to support larger values were made by Ronald: permutation and compression codes previously only supported depths 0–580. Integer-type ‘int64’ was required for calculating indexes for piece-encodings and blocks. The EGTs for KRBNKQN and unexpectedly KRBBPKQ, see Fig. 1, required 16 bits for their considerable depths: this in turn doubled the RAM needed, quite a hurdle. Finally, the Package-Merge algorithm (Moffat and Turpin, 1997) was used in the Huffman compression of EGTs to limit the code words to 32 bits.
Guo completed the 7-man EGT generation between May and August 2018. He used two Intel® platforms: a 4xE5-4669v4 (176 threads, 1 TB RAM) and an (384 threads, 1.5 TB RAM). Some code-optimisation brought a near-fivefold speed up to the generation process, largely because the memory-bandwidth limitations of the NUMA platforms were somewhat mitigated.
Guo’s new EGT files, published 9th September 2018, are available for download (Gunderson, 2018; Guo, 2018). The 7m EGTs add 16.7 TiB of files to the sub-7-man 150.1 GiB. Niklas Fiekas’ excellent site (de Man et al., 2018) as evolved now provides an interface to all sub-8-man EGTs plus ancillary maximal and statistical information (Haworth, 2018), see Fig. 1. There are 423,836,835,667,331 unique sub-8-man positions, including 6-1 positions but excluding those with castling rights. To guard file integrity, MD5sum digests (Rivest, 1992) are available although deprecated today as ‘cryptographically broken’ (CMU SEI, 2009). SHA-256 digests (NIST, 2018) are also available and recommended: they complement the basic internal non-cryptographic checksums.
Further thought is considering the independent verification of the new EGTs, going beyond the use of de Man’s tbverify code which has a lot in common with the code for generating the EGTs.
Fiekas’ interface (de Man et al., 2018) to the Syzygy EGTs: KRBBPKQ maximal win, histogram continued on right.
References
1.
CMU SEI (2009). https://www.kb.cert.org/vuls/id/836068. MD5 vulnerable to collision attacks.
2.
CPW (2018). https://www.chessprogramming.org/Syzygy_Bases. CPW on Syzygy EGTs.
3.
de Man, R. (2018). https://github.com/syzygy1/tb/issues/25. 7-man Syzygy EGT Github thread.
4.
de Man, R., Fiekas, N. & Guo, B. (2018). https://tinyurl.com/icga007. Fiekas’ interface to ‘Syzygy formatted’ de Man sub-7-man and Guo 7-man EGTs.
5.
Gunderson, S. (2018). http://tablebase.sesse.net/ Mirror site for downloading EGTs.
6.
Guo, B. (2018). ftp://ftp.chessdb.cn/pub/syzygy. EGT download site: sub-8-man EGTs.
7.
Haworth, G.McC. (2018). http://centaur.reading.ac.uk/80273/. This note plus data, checksum data and pgn files.
8.
Moffat, A. & Turpin, A. (1997). On the implementation of minimum redundancy prefix codes. IEEE Trans. on Communications, 45(10), 1200–1207. doi:10.1109/26.634683.
9.
NIST (2018). https://csrc.nist.gov/projects/hash-functions. NIST overview on hash functions.
10.
Rivest, R. (1992). https://www.ietf.org/rfc/rfc1321.txt. The MD5 Message Digest Algorithm. The Network Working Group RFC 1321.
11.
Talkchess (2018). http://talkchess.com/forum3/viewtopic.php?f=7&t=66797. Discussion of Development, Generation and Dissemination: Issues and Progress.