25,161
edits
Changes
Created page with "'''Home * Knowledge * Endgame Tablebases * Thompson's Databases''' FILE:PlayingChessWithGod.jpg|border|right|thumb| Play Chess with God <ref>CD, Chess..."
'''[[Main Page|Home]] * [[Knowledge]] * [[Endgame Tablebases]] * Thompson's Databases'''
[[FILE:PlayingChessWithGod.jpg|border|right|thumb| Play Chess with God <ref>CD, Chess Endgames, Vol 4, issued by [[Ken Thompson]], 1991, hosted by [http://www.spinroot.com/gerard/ Gerard Holzmann], Cover art in dependence on [[Arts#Michelangelo|Michelangelo's]] [https://en.wikipedia.org/wiki/The_Creation_of_Adam The Creation of Adam]</ref> <ref>[http://research.swtch.com/chess research!rsc: Play Chess with God] by [https://plus.google.com/+RussCox-rsc/posts Russ Cox], January 18, 2008</ref> ]]
'''Thompson's Databases''',<br/>
a set of up to 5-men and pawnless 6-man databases created by [[Ken Thompson]] using the [[Endgame Tablebases#DTC|depth to conversion (DTC)]] metric. Inspired by [[David Levy|David Levy's]] [[ACM 1974]] discussion and [[David Levy#ScotchVersusVodka|bets]] on perfectly playing [[Rook Endgame#KRPKR|KRPKR]] <ref>[http://www.computerhistory.org/chess/ken_thompson.oral_history_highlight.102645439/index.php?iid=orl-4334446157d96 Highlights Kenneth Thompson Oral History] March 7, 2005 Video © 2005 [[The Computer History Museum]]</ref> , Thompson started in the mid 70s to apply [[Retrograde Analysis|retrograde analysis]] with [[Belle]] <ref>[http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_sri-unix.458_net.chess.txt QUEEN vs. ROOK] by [http://www.highbeam.com/doc/1G1-62632443.html 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]], [https://en.wikipedia.org/wiki/Walter_Browne Walter Browne]</ref> . Advised by chess endgame expert [[John Roycroft]], he finished the 5-men databases in the mid 80s.
=Four CDs=
As soon as [https://en.wikipedia.org/wiki/CD-ROM 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, [https://en.wikipedia.org/wiki/Huffman_coding Huffman-encoded] [https://en.wikipedia.org/wiki/Computer_file 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|ply]] [[Search|search]], and the conversion of DTC values to reasonable [[Score|scores]] that do not conflict with real [[Checkmate#MateScore|mates]], made Thompson's Databases difficult to apply deep inside the search, but only suitable as [[Oracle|oracle]] at or near the [[Root|root]]. These database issues were addressed by [[Steven Edwards]] with his [[Edwards' Tablebases|approach]], relying on [[Endgame Tablebases#DTM|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 <ref>[[Ernst A. Heinz]] ('''1999'''). ''Endgame Databases and Efficient Index Schemes for Chess.'' [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]], [http://people.csail.mit.edu/heinz/ps/edb_index.ps.gz ps]</ref> .
=Index Scheme=
For none pawn endgames, taking advantage of the [[Chessboard#FourFoldSymmetry|fourfold symmetry]] of the [[Chessboard|chessboard]], Thompson confines the white king to the a8-d8-d5 octant by [[Horizontal Mirroring|horizontal]], [[Vertical Flipping|vertical]], or [[Diagonal Mirroring|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 <ref>[[Eugene Nalimov]], [[Guy Haworth]], [[Ernst A. Heinz]] ('''2000'''). ''[http://centaur.reading.ac.uk/4562/ Space-Efficient Indexing of Chess Endgame Tables]''. [[ICGA Journal#23_3|ICGA Journal, Vol. 23, No. 3]]</ref> . In endgames with pawns, where only [[Horizontal Mirroring|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 (Database)|ChessBase]], [[Fritz]], [[Shredder]] and [[Chess Genius]] [[GUI|GUIs]] at the [[Root|root]]. They were tried by some earlier versions of [[DarkThought]] and [[Zugzwang (Program)|Zugzwang]] inside the [[Search Tree|tree]] <ref>[https://www.stmintz.com/ccc/index.php?id=26055 Re: is there any program using ken thompson databases in the tree ?] by [[Ernst A. Heinz]], [[CCC]], September 06, 1998</ref> .
=See also=
* [[Edwards' Tablebases]]
* [[Nalimov Tablebases]]
* [[David Levy#ScotchVersusVodka|Scotch Versus Vodka]]
* [[Syzygy Bases]]
=Selected Publications=
==1986 ...==
* [[John Roycroft]], [[Ken Thompson]] ('''1986'''). ''Queen and Pawn on a2 against Queen''. Chess Endgame Consultants and Publishers, London
* [[John Roycroft]], [[Ken Thompson]] ('''1986'''). ''Queen and Pawn on a6 against Queen''. Chess Endgame Consultants and Publishers, London
* [[John Roycroft]], [[Ken Thompson]] ('''1986'''). ''Queen and Pawn on b7 against Queen''. Chess Endgame Consultants and Publishers, London
* [[Jaap van den Herik]] ('''1986'''). ''Roycroft's 5-Man Chess Endgame Series''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]] (review)
* [[Ken Thompson]] ('''1986'''). ''Retrograde Analysis of Certain Endgames''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]], [http://pdos.csail.mit.edu/~rsc/thompson86endgame.pdf pdf]
* [[Ken Thompson]] ('''1986'''). ''An Example of QPvQ''. [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]]
* [[Jaap van den Herik]], [[Bob Herschberg]] ('''1987'''). ''The KBBKN Statistics: New Data from Ken Thompson''. [[ICGA Journal#10_1|ICCA Journal, Vol. 10, No. 1]]
==1990 ...==
* [[Ken Thompson]] ('''1990'''). ''KQPKQ and KRPKR Endings''. [[ICGA Journal#13_4|ICCA Journal, Vol. 13, No. 4]]
* [[Ken Thompson]] ('''1991'''). ''Chess Endgames Vol. 1.'' [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]
* [[Ken Thompson]] ('''1991'''). ''New Results for KNPKB and KNPKN Endgames''. [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]
* [[John Roycroft]] ('''1991'''). ''A Postscript to the Computer's Involvement''. [https://en.wikipedia.org/wiki/British_Chess_Magazine Britisch Chess Magazine], Vol. 111, No. 2
* [[Lewis Stiller]] ('''1991'''). ''Some Results from a Massively Parallel Retrograde Analysis.'' [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
* [[John Roycroft]] ('''1991'''). ''A Use for Endgame Databases?'' [[ICGA Journal#14_4|ICCA Journal, Vol. 14, No. 4]]
* [[Ken Thompson]] ('''1996'''). ''6-Piece Endgames''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]
* [[Ken Thompson]] ('''1997'''). ''6-Piece Endgames''. [[Advances in Computer Chess 8]]
==2000 ...==
* [[Ken Thompson]] ('''2000'''). ''The Longest: KRNKNN in 262''. [[ICGA Journal#23_1|ICGA Journal, Vol. 23, No. 1]]
* [[John Tamplin]], [[Guy Haworth]] ('''2001'''). ''[http://centaur.reading.ac.uk/4561/ Ken Thompson's 6-man Tables]''. [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=26052 is there any program using ken thompson databases in the tree ?] by [[Thorsten Czub]], [[CCC]], September 06, 1998
* [https://groups.google.com/d/msg/rec.games.chess.computer/4_BXB207jNk/WSZDpGTvSrEJ Re: End Game Tablebase Files (5-Man) For Crafty] by [[Ernst A. Heinz]], [[Computer Chess Forums|rgcc]], Novemver 20, 1998
* [https://www.stmintz.com/ccc/index.php?id=107781 Ken Thompson's Endgame DBs....Still no copyright?] by [[John Merlino]], April 25, 2000
* [http://www.talkchess.com/forum/viewtopic.php?t=40316 A question about Thompson endgame databases] by [http://www.talkchess.com/forum/profile.php?mode=viewprofile&u=881 Ruxy Sylwyka], [[CCC]], September 08, 2011
=External Links=
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_sri-unix.458_net.chess.txt QUEEN vs. ROOK] by [http://www.highbeam.com/doc/1G1-62632443.html 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]], [https://en.wikipedia.org/wiki/Walter_Browne Walter Browne]
* [http://cm.bell-labs.com/who/ken/chesseg.html Play Chess with God - 6-Piece Database] by [[Ken Thompson]], 2000
* [http://en.chessbase.com/post/can-you-play-this-endgame- Can you play this endgame?], [[ChessBase|ChessBase News]], December 07, 2001
* [http://kirr.homeunix.org/chess/egtb/thompson/ Index of /chess/egtb/thompson] hosted by [[Kirill Kryukov]]
* [http://www.computerhistory.org/chess/ken_thompson.oral_history_highlight.102645439/index.php?iid=orl-4334446157d96 Highlights Kenneth Thompson Oral History] March 7, 2005 Video © 2005 [[The Computer History Museum]]
* [http://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/ Can We Solve Chess One Day? | Gödel's Lost Letter and P=NP] by [[Mathematician#RJLipton|Dick Lipton]], May 12, 2010
=References=
<references />
'''[[Endgame Tablebases|Up one level]]'''
[[FILE:PlayingChessWithGod.jpg|border|right|thumb| Play Chess with God <ref>CD, Chess Endgames, Vol 4, issued by [[Ken Thompson]], 1991, hosted by [http://www.spinroot.com/gerard/ Gerard Holzmann], Cover art in dependence on [[Arts#Michelangelo|Michelangelo's]] [https://en.wikipedia.org/wiki/The_Creation_of_Adam The Creation of Adam]</ref> <ref>[http://research.swtch.com/chess research!rsc: Play Chess with God] by [https://plus.google.com/+RussCox-rsc/posts Russ Cox], January 18, 2008</ref> ]]
'''Thompson's Databases''',<br/>
a set of up to 5-men and pawnless 6-man databases created by [[Ken Thompson]] using the [[Endgame Tablebases#DTC|depth to conversion (DTC)]] metric. Inspired by [[David Levy|David Levy's]] [[ACM 1974]] discussion and [[David Levy#ScotchVersusVodka|bets]] on perfectly playing [[Rook Endgame#KRPKR|KRPKR]] <ref>[http://www.computerhistory.org/chess/ken_thompson.oral_history_highlight.102645439/index.php?iid=orl-4334446157d96 Highlights Kenneth Thompson Oral History] March 7, 2005 Video © 2005 [[The Computer History Museum]]</ref> , Thompson started in the mid 70s to apply [[Retrograde Analysis|retrograde analysis]] with [[Belle]] <ref>[http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_sri-unix.458_net.chess.txt QUEEN vs. ROOK] by [http://www.highbeam.com/doc/1G1-62632443.html 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]], [https://en.wikipedia.org/wiki/Walter_Browne Walter Browne]</ref> . Advised by chess endgame expert [[John Roycroft]], he finished the 5-men databases in the mid 80s.
=Four CDs=
As soon as [https://en.wikipedia.org/wiki/CD-ROM 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, [https://en.wikipedia.org/wiki/Huffman_coding Huffman-encoded] [https://en.wikipedia.org/wiki/Computer_file 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|ply]] [[Search|search]], and the conversion of DTC values to reasonable [[Score|scores]] that do not conflict with real [[Checkmate#MateScore|mates]], made Thompson's Databases difficult to apply deep inside the search, but only suitable as [[Oracle|oracle]] at or near the [[Root|root]]. These database issues were addressed by [[Steven Edwards]] with his [[Edwards' Tablebases|approach]], relying on [[Endgame Tablebases#DTM|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 <ref>[[Ernst A. Heinz]] ('''1999'''). ''Endgame Databases and Efficient Index Schemes for Chess.'' [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]], [http://people.csail.mit.edu/heinz/ps/edb_index.ps.gz ps]</ref> .
=Index Scheme=
For none pawn endgames, taking advantage of the [[Chessboard#FourFoldSymmetry|fourfold symmetry]] of the [[Chessboard|chessboard]], Thompson confines the white king to the a8-d8-d5 octant by [[Horizontal Mirroring|horizontal]], [[Vertical Flipping|vertical]], or [[Diagonal Mirroring|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 <ref>[[Eugene Nalimov]], [[Guy Haworth]], [[Ernst A. Heinz]] ('''2000'''). ''[http://centaur.reading.ac.uk/4562/ Space-Efficient Indexing of Chess Endgame Tables]''. [[ICGA Journal#23_3|ICGA Journal, Vol. 23, No. 3]]</ref> . In endgames with pawns, where only [[Horizontal Mirroring|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 (Database)|ChessBase]], [[Fritz]], [[Shredder]] and [[Chess Genius]] [[GUI|GUIs]] at the [[Root|root]]. They were tried by some earlier versions of [[DarkThought]] and [[Zugzwang (Program)|Zugzwang]] inside the [[Search Tree|tree]] <ref>[https://www.stmintz.com/ccc/index.php?id=26055 Re: is there any program using ken thompson databases in the tree ?] by [[Ernst A. Heinz]], [[CCC]], September 06, 1998</ref> .
=See also=
* [[Edwards' Tablebases]]
* [[Nalimov Tablebases]]
* [[David Levy#ScotchVersusVodka|Scotch Versus Vodka]]
* [[Syzygy Bases]]
=Selected Publications=
==1986 ...==
* [[John Roycroft]], [[Ken Thompson]] ('''1986'''). ''Queen and Pawn on a2 against Queen''. Chess Endgame Consultants and Publishers, London
* [[John Roycroft]], [[Ken Thompson]] ('''1986'''). ''Queen and Pawn on a6 against Queen''. Chess Endgame Consultants and Publishers, London
* [[John Roycroft]], [[Ken Thompson]] ('''1986'''). ''Queen and Pawn on b7 against Queen''. Chess Endgame Consultants and Publishers, London
* [[Jaap van den Herik]] ('''1986'''). ''Roycroft's 5-Man Chess Endgame Series''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]] (review)
* [[Ken Thompson]] ('''1986'''). ''Retrograde Analysis of Certain Endgames''. [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]], [http://pdos.csail.mit.edu/~rsc/thompson86endgame.pdf pdf]
* [[Ken Thompson]] ('''1986'''). ''An Example of QPvQ''. [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]]
* [[Jaap van den Herik]], [[Bob Herschberg]] ('''1987'''). ''The KBBKN Statistics: New Data from Ken Thompson''. [[ICGA Journal#10_1|ICCA Journal, Vol. 10, No. 1]]
==1990 ...==
* [[Ken Thompson]] ('''1990'''). ''KQPKQ and KRPKR Endings''. [[ICGA Journal#13_4|ICCA Journal, Vol. 13, No. 4]]
* [[Ken Thompson]] ('''1991'''). ''Chess Endgames Vol. 1.'' [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]
* [[Ken Thompson]] ('''1991'''). ''New Results for KNPKB and KNPKN Endgames''. [[ICGA Journal#14_1|ICCA Journal, Vol. 14, No. 1]]
* [[John Roycroft]] ('''1991'''). ''A Postscript to the Computer's Involvement''. [https://en.wikipedia.org/wiki/British_Chess_Magazine Britisch Chess Magazine], Vol. 111, No. 2
* [[Lewis Stiller]] ('''1991'''). ''Some Results from a Massively Parallel Retrograde Analysis.'' [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
* [[John Roycroft]] ('''1991'''). ''A Use for Endgame Databases?'' [[ICGA Journal#14_4|ICCA Journal, Vol. 14, No. 4]]
* [[Ken Thompson]] ('''1996'''). ''6-Piece Endgames''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]
* [[Ken Thompson]] ('''1997'''). ''6-Piece Endgames''. [[Advances in Computer Chess 8]]
==2000 ...==
* [[Ken Thompson]] ('''2000'''). ''The Longest: KRNKNN in 262''. [[ICGA Journal#23_1|ICGA Journal, Vol. 23, No. 1]]
* [[John Tamplin]], [[Guy Haworth]] ('''2001'''). ''[http://centaur.reading.ac.uk/4561/ Ken Thompson's 6-man Tables]''. [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=26052 is there any program using ken thompson databases in the tree ?] by [[Thorsten Czub]], [[CCC]], September 06, 1998
* [https://groups.google.com/d/msg/rec.games.chess.computer/4_BXB207jNk/WSZDpGTvSrEJ Re: End Game Tablebase Files (5-Man) For Crafty] by [[Ernst A. Heinz]], [[Computer Chess Forums|rgcc]], Novemver 20, 1998
* [https://www.stmintz.com/ccc/index.php?id=107781 Ken Thompson's Endgame DBs....Still no copyright?] by [[John Merlino]], April 25, 2000
* [http://www.talkchess.com/forum/viewtopic.php?t=40316 A question about Thompson endgame databases] by [http://www.talkchess.com/forum/profile.php?mode=viewprofile&u=881 Ruxy Sylwyka], [[CCC]], September 08, 2011
=External Links=
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_sri-unix.458_net.chess.txt QUEEN vs. ROOK] by [http://www.highbeam.com/doc/1G1-62632443.html 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]], [https://en.wikipedia.org/wiki/Walter_Browne Walter Browne]
* [http://cm.bell-labs.com/who/ken/chesseg.html Play Chess with God - 6-Piece Database] by [[Ken Thompson]], 2000
* [http://en.chessbase.com/post/can-you-play-this-endgame- Can you play this endgame?], [[ChessBase|ChessBase News]], December 07, 2001
* [http://kirr.homeunix.org/chess/egtb/thompson/ Index of /chess/egtb/thompson] hosted by [[Kirill Kryukov]]
* [http://www.computerhistory.org/chess/ken_thompson.oral_history_highlight.102645439/index.php?iid=orl-4334446157d96 Highlights Kenneth Thompson Oral History] March 7, 2005 Video © 2005 [[The Computer History Museum]]
* [http://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/ Can We Solve Chess One Day? | Gödel's Lost Letter and P=NP] by [[Mathematician#RJLipton|Dick Lipton]], May 12, 2010
=References=
<references />
'''[[Endgame Tablebases|Up one level]]'''
