Thompson's Databases

From Chessprogramming wiki
Jump to: navigation, search

Home * Knowledge * Endgame Tablebases * Thompson's Databases

Play Chess with God [1] [2]

Thompson's Databases,
a set of up to 5-men and pawnless 6-man databases created by Ken Thompson using the depth to conversion (DTC) metric. Inspired by David Levy's ACM 1974 discussion and bets on perfectly playing KRPKR [3] , Thompson started in the mid 70s to apply retrograde analysis with Belle [4] . Advised by chess endgame expert John Roycroft, he finished the 5-men databases in the mid 80s.

Four CDs

As soon as CD-ROM technology became affordable, Thompson made his entire set of 5-men databases publicly available on 4 CDs, starting in 1991, containing a compressed, Huffman-encoded file for each material configuration where the materially weaker and hence potentially losing side enjoys the right to move.

Issues

Thompson's Databases contain exact results if the weaker side to move actually loses, but doesn't discriminate between draws and wins of the apparently weaker side. Due to the Huffman-encoding, multiple random file accesses were necessary. The accordantly slow access time in conjunction with the need for the stronger side to perform an 1-ply search, and the conversion of DTC values to reasonable scores that do not conflict with real mates, made Thompson's Databases difficult to apply deep inside the search, but only suitable as oracle at or near the root. These database issues were addressed by Steven Edwards with his approach, relying on depth to mate (DTM), a complete coverage of all positions with both sides to move, and his so-called tablebase as data vectors by means of a single file access [5] .

Index Scheme

For none pawn endgames, taking advantage of the fourfold symmetry of the chessboard, Thompson confines the white king to the a8-d8-d5 octant by horizontal, vertical, or diagonal reflections, and further enumerates 462 legal two king configurations, considering the extra symmetry if the white king resides on the long diagonal. The like men of the same type economy was not used [6] . In endgames with pawns, where only horizontal mirroring might be applied, Thompson's Databases confine one piece to either to the queen side or king side flank, and further discards squares on both backranks for pawns.

Applications

Thompson's Databases (5-men) were used in older versions of ChessBase, Fritz, Shredder and Chess Genius GUIs at the root. They were tried by some earlier versions of DarkThought and Zugzwang inside the tree [7] .

See also

Selected Publications

1986 ...

1990 ...

2000 ...

Forum Posts

External Links

References

  1. CD, Chess Endgames, Vol 4, issued by Ken Thompson, 1991, hosted by Gerard Holzmann, Cover art in dependence on Michelangelo's The Creation of Adam
  2. research!rsc: Play Chess with God by Russ Cox, January 18, 2008
  3. Highlights Kenneth Thompson Oral History March 7, 2005 Video © 2005 The Computer History Museum
  4. QUEEN vs. ROOK by Warren Stenberg and Edware J. Conway, reprinted from the January, 1979 issue of the Minnesota Chess Journal, The Usenet Oldnews Archive, Compilation Copyright (C) 1981, 1996 Bruce Jones, Henry Spencer, David Wiseman » ACM 1978, Belle, Walter Browne
  5. Ernst A. Heinz (1999). Endgame Databases and Efficient Index Schemes for Chess. ICCA Journal, Vol. 22, No. 1, ps
  6. Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2000). Space-Efficient Indexing of Chess Endgame Tables. ICGA Journal, Vol. 23, No. 3
  7. Re: is there any program using ken thompson databases in the tree ? by Ernst A. Heinz, CCC, September 06, 1998

Up one level