Wikispaces : chessprogramming - items matching description

CHREST

GerdIsenberg — Fri, 06 May 2016 20:34:02 GMT

CHUMP

Home * Knowledge * Cognition * CHREST

CHREST, (Chunk Hierarchy and REtrieval STructures)
a cognitive architecture that models human perception, learning, memory, and problem solving. It is distinctive in its emphasis on the importance of perception and attention, and in following human constraints such as limitations on short-term memory, chunking and processing speed. Fernand Gobet is principal investigator of CHREST, influenced by the earlier EPAM model, originally designed by Herbert Simon and Edward Feigenbaum ^[1] ^[2].

CHREST consists of a blending of ideas proposed in earlier computer models of different aspects of chess ^[3], Mater by Baylor and Simon ^[4], Perceiver by Barenfeld and Simon ^[5], and MAPP by Gilmartin and Simon ^[6] and originated from modeling work on chess expertise.

CHUMP

One application of CHREST was the pattern learning chess program CHUMP by Gobet and Peter Jansen ^[7] , where an eye movement simulator, the only part of the system where the rules of the game influence the learning process, scans the board, and directs its attention to pieces and squares it expects, given the current node in its discrimination net, attack, defense and proximity relations between pieces.

Architecture

An overview of the architecture of CHREST ^[8]

Publications

Fernand Gobet (1993). A Computer Model of Chess Memory. Proceedings of the 15th Annual Meeting of the Cognitive Science Society, pp. 463-468.
Fernand Gobet, Peter Jansen (1994). Towards a Chess Program Based on a Model of Human Memory. Advances in Computer Chess 7
Adriaan de Groot, Fernand Gobet (1996). Perception and memory in chess. Heuristics of the professional eye. Assen: Van Gorcum, The Netherlands. ISBN 90-232-2949-5. Chapter 9; A discussion: Two authors, two different views? word reprint.
Fernand Gobet, Herbert Simon (2000). Five Seconds or Sixty? Presentation Time in Expert Memory. Cognitive Science, Vol. 24, No. 4
Fernand Gobet, Peter Lane, Steve Croker, Peter C-H. Cheng, Gary Jones, Iain Oliver, Julian M. Pine (2001). Chunking mechanisms in human learning. Trends in Cognitive Sciences, Vol. 5, No. 6
Fernand Gobet (2001). Is Experts' Knowledge Modular? Proceedings of the 23rd Meeting of the Cognitive Science Society, pdf
Pertti Saariluoma, Tei Laine (2001). Novice construction of chess memory. Scandinavian Journal of Psychology, Vol. 42, No. 2
Fernand Gobet, Peter Lane (2004). CHREST tutorial: Simulations of human learning. CogSci 2004
Fernand Gobet (2005). Chunking Models of Expertise: Implications for Education. Applied Cognitive Psychology, Vol. 19, No. 2
Fernand Gobet (2007). Chunk hierarchies and retrieval structures: Comments on Saariluoma and Laine. Scandinavian Journal of Psychology, 42. pdf
Richard L. Smith, Fernand Gobet, Peter Lane (2007). An Investigation into the Effect of Ageing on Expert Memory with CHREST. UKCI 2007
Peter Lane, Fernand Gobet, Richard L. Smith (2008). Attention mechanisms in the CHREST cognitive architecture. Proc. of the 5th International Workshop on Attention in Cognitive Systems
Roy W. Roring III (2008). Reviewing Expert Chess Performance: A Production-Based Theory of Chess Skill. Ph.D. thesis, advisor Neil Charness, Florida State University
Richard L. Smith, Fernand Gobet, Peter Lane (2009). Checking chess checks with chunks: A model of simple check detection. ICCM 2009

External Links

CHREST from Wikipedia
CHREST Home
Design of CHREST
CHREST - Centre for Research in Development, Instruction and Training - University of Nottingham
Flora Purim - Open Your Eyes You Can Fly, YouTube Video
Flora Purim, George Duke, David Amaro, Alphonso Johnson, Airto Moreira, Leon "Ndugu" Chancler

References

^ Edward Feigenbaum (1959). An Information Processing Theory of Verbal Learning. RAND Paper
^ Edward Feigenbaum, Herbert Simon (1984). EPAMlike models of recognition and learning. Cognitive Science, Vol. 8, 305-336, pdf
^ Fernand Gobet (1993). A Computer Model of Chess Memory. Proceedings of the 15th Annual Meeting of the Cognitive Science Society, pp. 463-468
^ George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS
^ Herbert Simon, Michael Barenfeld (1969). Information-processing analysis of perceptual processes in problem solving. Psychological Review, Vol. 76, No. 5
^ Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46.
^ Fernand Gobet, Peter Jansen (1994). Towards a Chess Program Based on a Model of Human Memory. Advances in Computer Chess 7
^ Design of CHREST

What links here?

Page	Date Edited
Check	Feb 1, 2018
CHREST	May 6, 2016
Chump	Jan 31, 2016
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
Dictionary	Aug 24, 2017
Edward Feigenbaum	Jan 3, 2016
EPAM	Jul 15, 2017
Eye Movements	Jul 22, 2015
Fernand Gobet	May 11, 2017
Learning	Feb 20, 2018
MAPP	Jan 30, 2016
Perceiver	Nov 21, 2017
Peter Lane	Jan 1, 2016
William Chase	Jan 21, 2016

Up one Level

Chunking

GerdIsenberg — Mon, 12 Jun 2017 09:33:14 GMT

Home * Knowledge * Chunking

Chunking,
a term in cognitive science where individual units of information are structured into larger meaningful units to improve memory performance. The concept of chunking was first put forward in 1956 by psychologist George A. Miller in The Magical Number Seven, Plus or Minus Two, where he researched how many numbers we can reliably remember a few minutes after we've been told them only once.

Chunking in Chess

In chess and computer chess, chunking is about to recognize relevant patterns of a chess position. A chunk is a group of pieces, in some sense a semantic unit, a meaningful pattern that is recognized at a glance by a chess master. Reasoning about a position in terms of such chunks as atomic units, instead of individual pieces, reduces the complexity of a position from, say, 30 units to about 7 units, assuming that each chunk consists of 4 or 5 pieces. Pieces within a single chunk are closely related in terms of attack- and defense properties of the pieces as well as common color, type and proximity.

Chunking Hypothesis

In chess, the Chunking Hypothesis was researched in various cognitive experiments by Adriaan de Groot and others, where chess masters were able to reconstruct a chess position from a albeit unknown chess game almost perfectly after viewing it for only 5 sec, while players below the master level had sharp drop off in this ability. However, this result could not be attributed to the masters’ generally superior memory ability, since masters had almost the same difficulty to reconstruct the positions constructed by placing the same numbers of pieces randomly on the board.

Chess Patterns

Publications

1920 ...

I.N. Djakov (1926). Psihologia Shakhmatnoi Igry. (Chess psychology) edited by N.B. Petrovskij and P.A. Rudik, Moscow: Avtorov
I.N. Djakov (1927). Psychologie des Schachspiels. Walter de Gruyter, Berlin & Leipzig, reprinted 2001 Bigli-Press, amazon ^[1]

1940 ...

Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions, (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6.

1950 ...

George Armitage Miller (1956). The Magical Number Seven, Plus or Minus Two. Psychological Review, Vol. 101, No. 2, pdf
Edward Feigenbaum (1959). An Information Processing Theory of Verbal Learning. RAND Paper » EPAM

1960 ...

Adriaan de Groot (1965, 1978). Thought and Choice in Chess. Mouton & Co Publishers, The Hague, The Netherlands. ISBN 90-279-7914-6, amazon, google
Adriaan de Groot (1966). Perception and Memory versus Thought: Some Old Ideas and Recent Findings. Problem Solving: Research, Method, and Theory (ed. B. Kleinmuntz), pp. 19-50. John Wiley, New York.
Herbert Simon, Michael Barenfeld (1968). Information Processing in the Perception of Chess Positions. Carnegie Mellon University, Paper #127
Herbert Simon, Michael Barenfeld (1969). Information-processing analysis of perceptual processes in problem solving. Psychological Review, Vol. 76, No. 5

1970 ...

Albert Zobrist (1970). A Pattern Recognition Program which uses a Geometry-Preserving Representation of Features. Technical Report #85, pdf
James R. Slagle, Richard C. T. Lee (1971). Application of game tree searching techniques to sequential pattern recognition. Communications of the ACM, Vol. 14, No. 2
William Chase, Herbert Simon (1973). The Mind’s Eye in Chess. Visual Information Processing: Proceedings of the Eighth Annual Carnegie Psychology Symposium (ed. W. G. Chase), pp. 215-281. Academic Press, New York. Reprinted (1988) in Readings in Cognitive Science (ed. A.M. Collins). Morgan Kaufmann, San Mateo, CA.
William Chase, Herbert Simon (1973). Perception in chess. Cognitive Psychology, Vol. 4, No. 1, pdf ^[2]
Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5 » MAPP
Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, reprinted (1988) in Computer Chess Compendium
Albert Zobrist, Frederic Roy Carlson (1973). An Advice-Taking Chess Computer. Scientific American, Vol. 228, No. 6
Herbert Simon (1974). How big is a chunk? Science, Vol. 183, pdf

1975 ...

Ruslan Hajiev (1975). Experimental Studies of Human Decision-Making and its Simulation by Situation Control Technique.. (on the basis of a chess endgame). IJCAI 1975, Tbilisi, Georgia, USSR, pdf
Judith S. Reitman (1976). Skilled Perception in Go: Deducing Memory Structures from Inter-Response Times. Cognitive Psychology, Vol. 8, No, 3
Neil Charness (1976). Memory for Chess Positions: Resistance to Interference. Journal of Experimental Psychology: Human Learning and Memory, Vol. 2, No. 6, pp. 641-653 » MAPP
Peter W. Frey, Peter Adesman (1976). Recall Memory for Visually Presented Chess Positions. Memory & Cognition, Vol. 4, No. 5, 541-547
Jürg Nievergelt (1977). Information content of chess positions. ACM SIGART Newsletter 62, pp. 13-14. Reprinted as: Information content of chess positions: Implications for game-specific knowledge of chess players, pp. 283-289. Machine Intelligence 12 (eds. Jean Hayes Michie, Donald Michie, E. Tyugu). Clarendon Press, Oxford, 1991. ISBN 0-19-853823-5.
Ivan Bratko, Danny Kopec, Donald Michie (1978). Pattern-Based Representation of Chess Endgame Knowledge. The Computer Journal, Vol. 21, No. 2, pp. 149-153. pdf

1980 ...

Ivan Bratko and Donald Michie (1980). A Representation of Pattern-Knowledge in Chess Endgames. Advances in Computer Chess 2
Zdenek Zdráhal, Ivan Bratko, Alen Shapiro (1981). Recognition of Complex Patterns Using Cellular Arrays. The Computer Journal, Vol. 24, No. 3
Murray Campbell, Hans Berliner (1983). A Chess Program That Chunks. AAAAI 1983
Hans Berliner, Murray Campbell (1984). Using Chunking to Solve Chess Pawn Endgames. Artifical Intelligence, Vol. 23, No. 1
John E. Laird, Paul S. Rosenbloom, Allen Newell (1984). Towards Chunking as a General Learning Mechanism. AAAI 1984
Edward Feigenbaum, Herbert Simon (1984). EPAMlike models of recognition and learning. Cognitive Science, Vol. 8, 305-336, pdf
Ivan Bratko, Peter Tancig, Simona Tancig (1984). Detection of Positional Patterns in Chess. ICCA Journal, Vol. 7, No. 2 (abridged version)
Pertti Saariluoma (1984). Coding problem spaces in chess: A Psychological study. Societas Scientiarum Fennica. Commentationes Scientiarum Socialium 23/1984, amazon
Ivan Bratko, Peter Tancig, Simona Tancig (1984,1986). Detection of Positional Patterns in Chess. Advances in Computer Chess 4 (full paper)

1985 ...

Albrecht Heeffer, Marc Leman (1986). Chunking as a Method for Concept Acquisition. Proceedings of the 7th European Conference on Artificial Intelligence
Murray Campbell (1988). Chunking as an Abstraction Mechanism. Ph.D. thesis, Carnegie Mellon University

1990 ...

Pertti Saariluoma (1990). Chess players' search for task relevant cues: Are chunks relevant? In: David Brogan: Visual search. pp. 115-121
Michael George, Jonathan Schaeffer (1990). Chunking for Experience. ICCA Journal, Vol. 13, No. 3
Michael George, Jonathan Schaeffer (1991). Chunking for Experience. Advances in Computer Chess 6
Steven Walczak, Douglas D. Dankel II (1993). Acquiring Tactical and Strategic Knowledge with a Generalized Method for Chunking of Game Pieces. International Journal of Intelligent Systems, Vol. 8, No. 2
Fernand Gobet, Peter Jansen (1994). Towards a Chess Program Based on a Model of Human Memory. Advances in Computer Chess 7

1995 ...

Stephen Flinter, Mark Keane ( 1995). On the automatic generation of case libraries by chunking chess games. in Manuela Veloso, Agnar Aamodt (eds.) Case-Based Reasoning Research and Development. Lecture Notes in Computer Science, Vol. 1010, Springer
Pertti Saariluoma (1995). Chess players' thinking. Routledge. amazon
Fernand Gobet, Herbert Simon (1996). Recall of random and distorted positions: Implications for the theory of expertise. Memory & Cognition, 24, 493-503.
Fernand Gobet, Herbert Simon (1996). Recall of rapidly presented random chess positions is a function of skill. Psychonomic Bulletin & Review, 3, 159-163, word reprint.
Fernand Gobet, Herbert Simon (1998). Expert chess memory: Revisiting the chunking hypothesis. Memory, 6, 225-255, pdf
Fernand Gobet (1998). Memory for the Meaningless: How Chunks Help Proceedings of the 20th Meeting of the Cognitive Science Society

2000 ...

Fernand Gobet, Herbert Simon (2000). Five Seconds or Sixty? Presentation Time in Expert Memory. Cognitive Science, Vol. 24, No. 4
Pertti Saariluoma (2001). Chess and content-oriented psychology of thinking. Psicológica, 22, 143-164, pdf
Pertti Saariluoma, Tei Laine (2001). Novice construction of chess memory. Scandinavian Journal of Psychology, Vol. 42, No. 2
Tristan Caulfield (2004). Acquiring and Using Knowledge in Computer Chess. Undergraduate Dissertation, University of Bath, pdf

2005 ...

Fernand Gobet (2005). Chunking Models of Expertise: Implications for Education. Applied Cognitive Psychology, Vol. 19, No. 2
Tristan Caulfield, Joanna J. Bryson (2005). Chess by Imitation. Department of Computer Science, University of Bath, pdf
Han L.J. van der Maas, Eric-Jan Wagenmakers (2005). A psychometric analysis of chess expertise. University of Amsterdam, pdf
Takeshi Ito, Hitoshi Matsubara, Reijer Grimbergen (2005). Chunking in Shogi: New Findings. Advances in Computer Games 11
Richard L. Smith, Fernand Gobet, Peter Lane (2007). An Investigation into the Effect of Ageing on Expert Memory with CHREST. UKCI 2007
Guillermo Campitelli, Fernand Gobet, Kay Head, Mark Buckley, Amanda Parker (2007). Brain localisation of memory chunks in chessplayers. International Journal of Neuroscience, 117, 1641-1659.
Alexandre Linhares, Paulo Brum (2007). Understanding our understanding of strategic scenarios: What role do chunks play. Cognitive Science, 31, 989-1007. pdf
Merim Bilalić, Fernand Gobet (2007). They do what they are told to do: The influence of instruction on (chess) expert perception - Commentary on Linhares and Brum (2007). Cognitive Science. pdf
Fernand Gobet (2007). Chunk hierarchies and retrieval structures: Comments on Saariluoma and Laine. Scandinavian Journal of Psychology, 42. pdf
Peter Lane, Fernand Gobet, Richard L. Smith (2008). Attention mechanisms in the CHREST cognitive architecture. Proc. of the 5th International Workshop on Attention in Cognitive Systems
Roy W. Roring III (2008). Reviewing Expert Chess Performance: A Production-Based Theory of Chess Skill. Ph.D. thesis, advisor Neil Charness, Florida State University
Andrew Cook (2008). Chunk Learning and Move Prompting: Making Moves in Chess. Technical Report CSR-08-12, University of Birmingham
Jana Krivec, Matej Guid, Ivan Bratko (2009). Identification and Characteristic Descriptions of Procedural Chunks. ComputationWorld conference: Cognitive 2009. pdf
Richard L. Smith, Fernand Gobet, Peter Lane (2009). Checking chess checks with chunks: A model of simple check detection. ICCM 2009

External Links

References

What links here?

Page	Date Edited
Advances in Computer Chess 4	Jan 22, 2018
Alexandre Linhares	Nov 10, 2012
Blockage Detection	Oct 19, 2017
Check	Feb 1, 2018
Chessmaps Heuristic	Aug 27, 2015
CHREST	May 6, 2016
Chump	Jan 31, 2016
Chunker	Jul 12, 2016
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
Edward Feigenbaum	Jan 3, 2016
EPAM	Jul 15, 2017
Evaluation	Feb 1, 2018
Evaluation Patterns	Jun 24, 2013
Eyal Reingold	Nov 3, 2012
Fernand Gobet	May 11, 2017
Guillermo Campitelli	Jul 1, 2014
Hans Berliner	Jun 10, 2017
Judith Spencer Olson	Sep 24, 2014
Kevin J. Gilmartin	Jan 1, 2016
Knowledge	Jul 22, 2017
MAPP	Jan 30, 2016
Merim Bilalić	Oct 2, 2014
Michael Barenfeld	Oct 2, 2014
Michael George	Jan 3, 2016
Murray Campbell	Jun 2, 2017
Pattern Recognition	Sep 8, 2017
Paulo Brum	Nov 7, 2012
Perceiver	Nov 21, 2017
Pertti Saariluoma	Jun 13, 2017
Peter McLeod	Nov 4, 2012
Peter Tancig	Nov 7, 2012
Planning	Feb 12, 2018
Ruslan Hajiev	Oct 2, 2014
Simona Tancig	Nov 7, 2012
Tactics	Jan 12, 2018
Tei Laine	Jun 13, 2017
Tristan Caulfield	Dec 1, 2017
William Chase	Jan 21, 2016
Workshop Chess and Mathematics	Mar 5, 2015

Up one Level

Edwards' Tablebases

GerdIsenberg — Mon, 26 Sep 2016 14:53:49 GMT

Home * Knowledge * Endgame Tablebases * Edwards' Tablebases

Edwards' Tablebases,
are three-, four and some five-piece tablebases constructed by Steven Edwards in the early 90s, initially for his chess program Spector ^[1]. Edwards' Tablebases rely on Depth to Mate and the complete coverage for both sides, using one byte per position, with evaluations of the forms "mate in N", "lose (get mated) in N", "draw", and "illegal". Values for the number N (measured in fullmoves, not ply) for mates range from mate in 1 upto mate in 126 and for losses in 0 (lose in 0 means checkmated) to lose in 125 moves. Each file is for a given class (e.g., KBNK) and for a given side to move (e.g., White) ^[2]. After finishing the construction procedure in 1994, Steven Edwards made the whole data, documentation and a test program written in ANSI-C publicly available on the Internet. Until the advent of the compressed Nalimov Tablebases, Edwards' Tablebases were quite popular and used in several chess programs, such as Crafty, Gromit, and the commercial MChess Pro, to name a few.

Index Scheme

The index scheme for pawn-less endgames exploits the fourfold symmetry of the chessboard to restrict the last identified piece to the a1-d1-d4 triangle by horizontal, vertical, or diagonal reflections, and features vertical symmetry by confining one pawn to the queen-side flank for endgames with one pawn. Other schemes as applied for instance in Thompson's Databases, enumerating all legal positions of both kings as combined index and considering pawns can't reside on the first or eighth rank, feature denser index ranges than Edwards' ^[3].

Publications

Steven Edwards and the Editorial Board (1995). An Examination of the Endgame KBNKN. ICCA Journal, Vol. 18, No. 3, pdf
Steven Edwards (1996). An Examination of the Endgame KBBKN. ICCA Journal, Vol. 19, No. 1

Forum Posts

1990 ...

Announcing forced mates: a poll by Steven J. Edwards, rgc, July 21, 1994
KBBK tablebases: attempt #2 by Steven J. Edwards, rgc, August 13, 1994
Updated tablebase documentation by Steven J. Edwards, rgc, October 14, 1994
KPK tablebases now available via ftp by Steven J. Edwards, rgc, October 14, 1994

1995 ...

Re: FICS vs. ICS: No, really, which is better? by Steven J. Edwards, alt.chess.ics, June 01, 1995
MCP6 Endgame Tablebase. Thanks mr.Hirsch! by H.Pieters, rgcc, November 11, 1996
Steve Edward's Endgame Tablebase generator is now available for WIN95 by Mike Byrne, CCC, November 01, 1997
EGTB by Frank Phillips, CCC, February 10, 1998

2000 ...

Tablebases Edwards by RR, Winboard Forum, July 25, 2001

2010 ...

A different tablebase encoding format by Steven Edwards, CCC, August 10, 2014

Downloads

^[4]

tbgen.zip
- Details
- Download
- 44 KB
Spector.zip
- Details
- Download
- 370 KB

References

^ For chess program source collectors by Steven Edwards, Chess Circle, August 13, 2006
^ Steve Edward's Endgame Tablebase generator is now available for WIN95 by Mike Byrne, CCC, November 01, 1997
^ Ernst A. Heinz (1999). Endgame Databases and Efficient Index Schemes for Chess. ICCA Journal, Vol. 22, No. 1, ps
^ Courtesy Steven Edwards

What links here?

Page	Date Edited
CookieCat	Nov 15, 2016
Edwards' Tablebases	Sep 26, 2016
Endgame Tablebases	Mar 6, 2018
Ernst A. Heinz	Mar 6, 2017
Frank Phillips	Sep 26, 2016
Gaviota Tablebases	Apr 22, 2018
Lomonosov Tablebases	May 20, 2016
Michael Byrne	Jun 23, 2017
Nalimov Tablebases	Dec 23, 2016
Scorpio Bitbases	Mar 12, 2018
Spector	Nov 11, 2016
Steven Edwards	Aug 26, 2017
Syzygy Bases	Apr 19, 2018
Thompson's Databases	Dec 24, 2014

Up one level

Endgame Bitbases

GerdIsenberg — Wed, 05 Apr 2017 19:50:13 GMT

Bitbase Implementations

Home * Knowledge * Endgame Tablebases * Bitbases

Endgame Bitbases,
are compact endgame tablebases with game theoretical values of one or two bits per position stored. They are sufficient for various material configurations to reside inside RAM for short probing access time, intended to use deep inside the search. The boolean or four valued ranges are either {won, not_won} or {won, draw, loss, invalid}. While WDL information is sufficient to guide the search into won positions, it lacks any sense of progress in won positions. Therefor, programs either probe full tablebases at the root to reveal the number of moves until conversion or mate, or combine WDL-scores with heuristic evaluation scores, considering material, ply-distance to the root, pawn closeness to promotion, distance of pieces to opponent king, etc.. Endgame Bitbases were described in 1999 by Ernst A. Heinz in Knowledgeable Encoding and Querying of Endgame Databases, as applied with 4-men in DarkThought ^[1].

Bitbase Implementations

Publications

Ken Thompson (1996). 6-Piece Endgames. ICCA Journal, Vol. 19, No. 4
Ernst A. Heinz (1999). Knowledgeable Encoding and Querying of Endgame Databases. ICCA Journal, Vol. 22, No. 2, ps
Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3 ^[4]

Forum Posts

2000

EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001 ^[5]
Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001 ^[6]
Wu/Beal predates Koistinen by Guy Haworth, CCC, December 04, 2001
EGTB generation with 1 bit per position? by Martin Fierz, CCC, March 25, 2003
Any programs besides Yace and Patzer that can use bitbase files by Dann Corbit, CCC, June 17, 2004 » Patzer, Yace

2005

Bitbases - yace, scorpio, gambitfruit by Bernhard Bauer, CCC, December 06, 2005
Open Source bitbase program by Peter Fendrich, CCC, April 09, 2007
KQKB and KQKN heuristic for bitbases?! by Jesper Nielsen, CCC, May 01, 2007
bitbases and Linux by Charles Roberson, CCC, June 26, 2007
Question about bitbases by Thomas Gaksch, CCC, February 02, 2008
How to generate a "simple" bitbase? by Alessandro Scotti, CCC, February 12, 2008
How much are bitbases worth? by Tord Romstad, CCC, May 22, 2008
Bitbases by Frank Phillips, CCC, May 03, 2009
Endgame bitbase / tablebase compromise? by clgd, CCC, July 13, 2009
Bitbase indexing and en passant by Tord Romstad, CCC, August 14, 2009

2010

Gaviota TBs [0.1.6.1], bitbase-like interface by Miguel A. Ballicora, CCC, February 22, 2010
Gaviota TBs Probing Code (v0.2) UPDATE, Bitbases on the fly by Miguel A. Ballicora, CCC, March 20, 2010
hard-wired bitbases by Ben Stoker, CCC, April 13, 2010
Stockfish bitbase by kongsian, CCC, June 01, 2010
Search with bitbase by Pham Hong Nguyen, CCC, September 05, 2012
KPK bitbase by Maarten Bults, CCC, January 16, 2013 » KPK
What happens using egbb by Kai Laskos, CCC, October 12, 2013
Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014 » Scorpio Bitbases

2015 ...

Yet another KPK endgame table generator: pfkpk by Marcel van Kervinck, CCC, September 05, 2015 » KPK ^[7]

External Links

Endgame tablebase | Computer chess - Wikipedia
Computing endgames with few men by Urban Koistinen
dshawul/Scorpio · GitHub includes Six men egbb code » Scorpio Bitbases ^[8]
kervinck/pfkpk · GitHub » KPK Bitbase by Marcel van Kervinck ^[9]

References

^ Ernst A. Heinz (1999). Knowledgeable Encoding and Querying of Endgame Databases. ICCA Journal, Vol. 22, No. 2, ps
^ Gaviota TBs [0.1.6.1], bitbase-like interface by Miguel A. Ballicora, CCC, February 22, 2010
^ Shredderbases
^ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001, with reference to Computing endgames with few men by Urban Koistinen
^ Computing endgames with few men by Urban Koistinen
^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
^ kervinck/pfkpk · GitHub
^ Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014
^ Yet another KPK endgame table generator: pfkpk by Marcel van Kervinck, CCC, September 05, 2015

What links here?

Page	Date Edited
Arminius	Aug 5, 2017
Carballo	Oct 2, 2016
Chiron	Sep 24, 2017
CT800	Feb 21, 2018
DanaSah	Oct 9, 2017
Daniel Shawul	Jan 28, 2018
Data	Nov 26, 2017
Dictionary	Aug 24, 2017
Djinn	Feb 8, 2016
Donna	Aug 17, 2017
Edwards' Tablebases	Sep 26, 2016
Eiko Bleicher	Apr 24, 2014
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Eveann	Apr 3, 2017
Frank Phillips	Sep 26, 2016
Gambit Fruit	Mar 29, 2013
Gaviota Tablebases	Apr 22, 2018
Hash Table	Jan 1, 2018
Joshua Shriver	Nov 24, 2017
Kai Laskos	Jan 21, 2018
Knowledge	Jul 22, 2017
KPK	May 12, 2016
Lomonosov Tablebases	May 20, 2016
Marcel van Kervinck	Dec 6, 2017
Martin Fierz	Apr 26, 2018
Memory	Dec 8, 2017
Nalimov Tablebases	Dec 23, 2016
Patzer	Apr 5, 2017
Retrograde Analysis	Mar 21, 2017
Robocide	May 11, 2016
Scorpio	Mar 28, 2018
Scorpio Bitbases	Mar 12, 2018
Space-Time Tradeoff	Jun 17, 2015
Syzygy Bases	Apr 19, 2018
The Baron	Jan 8, 2018
Urban Koistinen	Apr 20, 2014
Yace	Dec 31, 2017

Up one level

Endgame Tablebases

GerdIsenberg — Tue, 06 Mar 2018 21:48:25 GMT

Home * Knowledge * Endgame Tablebases

		Endgame Tablebases, (EGTBs or EGTs) precalculated endgame tables generated by an exhaustive retrograde analysis. During its game play and/or search, recognizing a specific material composition, a chess program can probe, or in principle compute these tables to determine the outcome of positions definitively and act as an oracle providing the optimal moves. The tables are usually divided into separate files for each material configuration and side to move. What all different formats of tablebases have in common is that every possible piece placement has its own, unique index number which represents the position where the information about the position is located in the file. Positions with non-null castling rights could be represented in an EGT but typically are not. The term Tablebase opposed to endgame database was coined by Steven Edwards by means of a data vector and a single file access for both sides to move, when he introduced his Edwards' Tablebases, addressing several shortcomings of Ken Thompson's earlier database of positions with the weaker and hence potentially losing side to move only ^[1] .
Samuel Bak - Persistence ^[2]

Selected Publications

Metrics

DTM

Depth to Mate
'Mate' is the ultimate goal and ends the game. For each position that is represented, 'DTM' indicates the theoretical value, and the number of winner's moves to 'Mate' if won/lost - assuming that the winner is minimizing and the loser is maximizing DTM.

DTC

Depth to Conversion
'Conversion' is the changing of the force on the board, by capture and/or Pawn-conversion. For each position that is represented, 'DTC' indicates the theoretical value, and the number of winner's moves to the goal of 'Won Conversion' if won/lost - assuming that the winner is minimizing and the loser is maximizing DTC. DTC £ DTM.

DTZ

Depth to Zeroing (of the ply count)
The ply-count is zeroed if and only if a Pawn is pushed or a capture is made. For each position that is represented, 'DTZ' indicates the theoretical value, and the number of winner's moves to the goal of 'Win and ply-count zeroed' if won/lost - assuming that the winner is minimizing and the loser is maximizing DTZ. DTZ £ DTC £ DTM.

DTZ50

Depth to Zeroing (of the ply count) in the context of the 50-Move Rule
The DTC, DTM and DTZ metrics do not consider the current FIDE 50-move rule whereby a game in which no irreversible moves have been played for 100 plies can be claimed as a draw by the player 'on move'. In this metric, in addition to the DTC/DTM/DTZ draws, positions requiring more than 50 winner's moves to zero the ply-count are defined as draws. DTZ £ DTZ50 if DTZ50 ¹ draw. 'DTZ50' is one of a set of 'DTZk' rules: a k-move rule effectively applies if there are only k moves left before a draw-claim might be made. k1 £ k2 implies DTZk2 £ DTZk1 if DTZk1 ¹ draw.

Note that, because depth is measured in winner's moves rather than plies, this metric does not define as draw a position in which 50 winner's moves and 51 loser's moves are required to zero the ply-count, despite the fact that the loser would claim a draw after 100 plies had been played in that endgame.

DTR

Depth by the (k-move) Rule
'The Rule' referred to here is a notional set of k-move rules. For each position that is represented, 'DTR' indicates the theoretical value and, for won/lost positions, the least k for which DTZk is not draw - assuming that the winner is minimising and the loser is maximising DTR. DTZ £ DTR. No DTR EGTs have been created to date ^[3] .

DTZR

Depth to Zeroing move, give that DTR is being minimaxed
If DTR = draw, then DTZR = draw. Otherwise, Otherwise DTRZR indicates the theoretical value, and the number of winner's moves to the zeroing of the ply count, given that the two sides are minimaxing first DTR and then DTZR. DTZR would be used in conjunction with DTR to progress a deep win in the context of a k-move rule because DTR can remain unchanged over a sequence of moves. DTZR £ DTR but it is not always the case that DTZ £ DTZR as may seem intuitively obvious: the loser may zero the move-count to maximise DTR.

Summary

To summarize the different metrics of tablebases, each metric has its strengths and weaknesses. Nalimov's DTM EGTs are widely and commercially available, and used by many chess engines or chess GUIs. DTC EGTs are more easily computed and stored as they involve smaller depth-ranges and are more compressible. For endgames with less or equal than 5 pieces on the board, KNNKP comes closest to requiring more than one Byte per position to store DTM: maxDTM = 115 (1-0) and 73 (0-1) necessitating 190 values in the EGT. For KPPKP, maxDTM = 127 (1-0) but only 42 (0-1). But for certain 6 piece endgames, one Byte is not enough: maxDTM = 262 for a KRNKNN position. The DTC and DTZ metrics increasingly postpone the need for two Bytes per position in an uncompressed EGT, but KRBNKQN has maxDTC = maxDTZ = 517 (0-1), both wtm and btm.

In extremis, he unmoderated use of DTM, DTC or DTZ EGTs will let slip a winnable position in the context of the 50-move rule ... hence the marginal need for the DTR and DTZR metrics, coupled with the ability to recompute DTR/DTZR EGTs in the context of a limited move-budget.

Bitbases

see main article Endgame Bitbases

Inside the search much denser tables with value {won, draw, loss, invalid} or boolean {win, not_win} information are sufficient with respect to bounds. Denser tables are more efficiently used, given that memory and cache are limited resources. Boolean Win/Not_Win Bitbases require only one bit per position (and if necessary, further enquiry if draw is to be distinguished from loss with respect to bounds). Value Bitbases require two bits per position.

Indexing

Every position is assigned to an unique index to specify the location of the information stored about it. There are two main aims when generating the index number. The easier the algorithm to generate the index from any given position, the faster will be the probing of the tablebase as well as the generation of it. But the second aim is to get a relatively small range of index-numbers, to keep the size of the file as small as possible.

The most straight forward way would be to for every piece on the board use 6 bit (1-64 squares)

index = position_white_King + position_black_King * 64
 
for each piece {
    index = index * 64 + position
}

This can be optimized in several ways.
A chess board can be rotated and mirrored (if pawns are on the board only a vertical reflection is possible).

Pieces may not stand on the same square.
For pieces of the same type, different arrangements can be left away.
The side to move may not give check.
The distance between the two Kings must be greater than one.

Brief Info

of some popular Endgame tablebases:

Format	Metric	1st published	5 men	6 men	7 men
Thompson	DTC	1991	2.5 GiB (not completed)	-	-
Edwards	DTM	1994	56 GiB (estimated)	-	-
Nalimov	DTM	1998	7.1 GiB	1.2 TiB	-
Scorpio	WDL	2005	214 MiB	48.1 GiB	-
Gaviota	DTM	2008	6.5 GiB	-	-
Lomonosov	DTM	2012	-	-	140 TiB
Syzygy	WDL + DTZ50	2013	939 MiB	150.2 GiB	-

Formats

Generators

7-man EGTBs

2005

In 2005, Yakov Konoval started to collaborate with Marc Bourzutschky on constructing 7-man EGTBs. Yakov wrote the generator and Marc a verification program and some utilities for extracting the data. In October 2005, Yakov Konoval and Marc Bourzutschky announced that a position in the ending of a KRRNkrr requires 290 moves to convert to a simpler winning endgame ^[4] . The old record was 243 moves from a position in a rook and knight versus two knights endgame, discovered by Lewis Stiller in 1991 ^[5] .

2006

In March 2006, the wizards of 7-men endgames, Marc Bourzutschky and Yakov Konoval found a 330 moves win in KQBNkqb ^[6] and in May 2006 a 517 moves win in KQNkrbn ^[7] .

2012

In July 2012, Vladimir Makhnychev and Victor Zakharov from Moscow State University completed 4+3 DTM-tablebases (525 endings including KPPPKPP). The next set of 5+2 DTM-tablebases was completed during August 2012 ^[8] . The tablebases are named Lomonosov Tablebases, using the Lomonosov Supercomputer.

2013

Convekta Ltd. announced the release of Lomonosov Tablebases. Until December 31, 2013, the tablebases will be available online through ChessOk products ^[9] .

Selected Publications

1965 ...

Richard E. Bellman (1965). On the application of dynamic programming to the determination of optimal play in chess and checkers. Proceedings of the National Academy of Sciences of the United States of America. pdf

1970 ...

Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
Edward Komissarchik, Aaron L. Futer (1974). Ob Analize Ferzevogo Endshpilya pri Pomoshchi EVM. (Analysis of a queen endgame using an IBM computer) Problemy Kybernetiki, Vol. 29, pp. 211-220. English translation by C. Posthoff, revised in ICCA Journal, Vol. 9, No. 4 (1986)

1975 ...

A. G. Alexandrov, A. M. Baraev, Ya. Yu. Gol'fand, Edward Komissarchik, Aaron L. Futer (1977). Computer analysis of rook end game. Avtomatika i Telemekhanika, No. 8, 113–117
A. G. Alexandrov, Vladimir Arlazarov, A. M. Baraev, Ya. Yu. Gol'fand, V. N. Deza, T. P. Il’ina, Edward Komissarchik, Anatoly Uskov, I. A. Faradzhev, Aaron L. Futer (1977). Processing of large files of information on the example of the analysis of the rook’s end game. Programming and Computer Software, No. 3
Thomas Ströhlein, Ludwig Zagler (1977). Analyzing games by Boolean matrix iteration. Discrete Mathematics, Vol. 19, No. 2
Thomas Ströhlein, Ludwig Zagler (1978). Ergebnisse einer vollstandigen Analyse von Schachendspielen: König und Turm gegen König, König und Turm gegen König und Laufer. Report, Institut für Informatik, Technical University of Munich (German)
Max Bramer (1978). Computer-Generated Databases for the Endgame in Chess. Technical Report. Milton Keynes, Open University Faculty of Mathematics.
Aaron L. Futer (1978). Programming endgames with few pieces. Soviet Physics. Doklady, No. 23
Vladimir Arlazarov, Aaron L. Futer (1979). Computer Analysis of a Rook End-Game. Machine Intelligence 9 (eds. Jean Hayes Michie, Donald Michie and L.I. Mikulich), pp. 361-371. Ellis Horwood, Chichester. Reprinted in Computer Chess Compendium

1985 ...

Jaap van den Herik, Bob Herschberg (1985). The Construction of an Omniscient Endgame Data Base. ICCA Journal, Vol. 8, No. 2
John Roycroft (1985). Chess-Endgame Data-Base`Oracles': Necessary and Desirable Features. ICCA Journal, Vol. 8, No. 2
Harry Nefkens (1985). Constructing Data Bases to Fit a Microcomputer. ICCA Journal, Vol. 8, No. 4

1986

Jaap van den Herik, Bob Herschberg (1986). A Data Base on Data Bases. ICCA Journal, Vol. 9, No. 1
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. ICCA Journal, Vol. 9, No. 3
Ken Thompson (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3, pdf
Edward Komissarchik, Aaron L. Futer (1986). Computer Analysis of a Queen Endgame. ICCA Journal, Vol. 9, No. 4 ^[10]
Ken Thompson (1986). An Example of QPvQ. ICCA Journal, Vol. 9, No. 4
Hans Zellner (1986). Compressing Databases Down to Micro Size. ICCA Journal, Vol. 9, No. 4

1987

Hans Zellner (1987). KBBK Squeezed into a Micro. ICCA Journal, Vol. 10, No. 1
Jaap van den Herik, Bob Herschberg (1987). The KBBKN Statistics: New Data from Ken Thompson. ICCA Journal, Vol. 10, No. 1
Bob Herschberg, Jaap van den Herik (1987). More Truth on KBBK Database Results. ICCA Journal, Vol. 10, No. 2
Hans Zellner, Jaap van den Herik, Bob Herschberg (1987). Corrections and Substantiations to KBNK. ICCA Journal, Vol. 10, No. 3
Sito Dekker, Jaap van den Herik, Bob Herschberg (1987). Complexity Starts at Five. ICCA Journal, Vol. 10, No. 3
Lars Rasmussen (1987). Correcting grandmasters' Analyses in Elementary Endgames. ICCA Journal, Vol. 10, No. 4
Jaap van den Herik, Bob Herschberg, Najib Nakad (1987). A Six-Men-Endgame Database: KRP(a2)KbBP(a3). ICCA Journal, Vol. 10, No. 4, pdf
Sito Dekker, Jaap van den Herik, Bob Herschberg (1987). Perfect Knowledge and Beyond. Report 37-87, Delft University of Technology, Delft.
John Roycroft (1987). Expert Against Oracle. Machine Intelligence 11

1988

Jaap van den Herik, Bob Herschberg (1988). Computer Checks on Human Analyses of the KRKB Endgame. ICCA Journal, Vol. 11, No. 1
Lars Rasmussen (1988). Ultimates in KQKR and KRKN. ICCA Journal, Vol. 11, No. 1
Lewis Stiller (1988). Massively Parallel Retrograde Endgame Analysis. BUCS Tech. Report #88-014, Boston University, Computer Science Department.
Jaap van den Herik, Bob Herschberg, Najib Nakad (1988). A Reply to R. Sattler's Remarks on the KRP(a2)KbBP(a3) Database. ICCA Journal, Vol. 11, No. 2/3, pdf
Lars Rasmussen (1988). A Database for KRKP. ICCA Journal, Vol. 11, No. 4

1989

Christopher A. Marris (1989). Compressing a Chess-Endgame Database. ICCA Journal, Vol. 12, No. 1
David Forthoffer, Lars Rasmussen, Sito Dekker (1989). A Correction to some KRKB-Database Results. ICCA Journal, Vol. 12, No. 1
Edmar Mednis (1989). Rook and Bishop versus Rook: The Controversial Endgame. ICCA Journal, Vol. 12, No. 1
Lewis Stiller (1989). Parallel Analysis of Certain Endgames. ICCA Journal, Vol. 12, No. 2
Hans Zellner (1989). The KPK Database Revisited. ICCA Journal, Vol. 12, No. 2
Sito Dekker, Jaap van den Herik, Bob Herschberg (1989). Perfect Knowledge and Beyond. Advances in Computer Chess 5
Bob Herschberg, Jaap van den Herik, Patrick Schoo (1989). Verifying and Codifying Strategies in the KNNKP(h) Endgame. ICCA Journal, Vol. 12, No. 3, pdf
Hans Zellner (1989). KBBKN on a Micro. ICCA Journal, Vol. 12, No. 3
John Roycroft (1989). The Computer is at it again - Interfering with the Endgame! Britisch Chess Magazine, Vol. 109, No. 10

1990 ...

Bob Herschberg, Jaap van den Herik, Patrick Schoo (1990). Verifying and Codifying Strategies in a Chess Endgame. Computers, Chess, and Cognition, pp. 183-196
John Roycroft (1990). How to Treat Endgame Databases. ICCA Journal, Vol. 13, No. 2
Ken Thompson (1990). KQPKQ and KRPKR Endings. ICCA Journal, Vol. 13, No. 4
John Roycroft (1990). Identifying Three Types of Zugzwang. ICCA Journal, Vol. 13, No. 4 » Zugzwang

1991

Ken Thompson (1991). Chess Endgames Vol. 1. ICCA Journal, Vol. 14, No. 1
Ken Thompson (1991). New Results for KNPKB and KNPKN Endgames. ICCA Journal, Vol. 14, No. 1
Edmar Mednis (1991). Database Results for KQKRN and KQKRB annotated. ICCA Journal, Vol. 14, No. 2
John Roycroft (1991). A Postscript to the Computer's Involvement. Britisch Chess Magazine, Vol. 111, No. 2
Lewis Stiller (1991). Some Results from a Massively Parallel Retrograde Analysis. ICCA Journal, Vol. 14, No. 3
John Roycroft (1991). A Side-Effect of new Database Knowledge. ICCA Journal, Vol. 14, No. 3
John Roycroft (1991). A Use for Endgame Databases? ICCA Journal, Vol. 14, No. 4
John Roycroft, Don Beal (1991). To Make Dumb Endgame Databases Speak. Advances in Computer Chess 6

1992

Lewis Stiller (1992). KQNKRR. ICCA Journal, Vol. 15, No. 1
John Nunn (1992). Perfect Prose. ICCA Journal, Vol. 15, No. 2
Lars Rasmussen (1992). Queen versus Rook and Pawn. ICCA Journal, Vol. 15, No. 2

1993

Burton Wendroff, Tony Warnock, Lewis Stiller, Dean Mayer, Ralph Brickner (1993). Bits and pieces: constructing chess endgame databases on parallel and vector architectures. Appl. Num. Math. 12, pp. 285-295, zipped ps
Christian Posthoff, Michael Schlosser, Jens Zeidler (1993). Search vs. Knowledge? - Search and Knowledge! In: Proc. 3rd KADS Meeting, Munich, March 8-9 1993, Siemens AG, Corporate Research and Development, 305-326, 1993.
John Nunn (1993). Extracting Information from Endgame Databases. ICCA Journal, Vol. 16, No. 4

1994

Ingo Althöfer, Bernhard Walter (1994). Weak Zugzwang: Statistics on some Chess Endgames. ICCA Journal, Vol. 17, No. 2
John Nunn (1994). More, and More Perfect Prose. ICCA Journal, Vol. 17, No. 2
John Nunn (1994). Extracting Information from Endgame Databases. Advances in Computer Chess 7
Christian Posthoff, Michael Schlosser, Rainer Staudte, Jens Zeidler (1994). Transformations of Knowledge. Advances in Computer Chess 7
Grit Lachmann (1994). Verarbeitung von Wissen aus Endspieldatenbanken. Master's thesis, Chemnitz University of Technology (German)

1995 ...

Steven Edwards and the Editorial Board (1995). An Examination of the Endgame KBNKN. ICCA Journal, Vol. 18, No. 3
Henri Bal, Victor Allis (1995). Parallel Retrograde Analysis on a Distributed System. Supercomputing ’95, San Diego, CA.

1996

Dietmar Lippold (1996). Legality of Positions of Simple Chess Endgames. zipped pdf ^[11]
Ken Thompson (1996). 6-Piece Endgames. ICCA Journal, Vol. 19, No. 4
Lewis Stiller (1996). Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf

1997

Dietmar Lippold (1997). The Legitimacy of Positions in Endgame Databases. ICCA Journal, Vol. 20, No. 1
Ken Thompson (1997). 6-Piece Endgames. Advances in Computer Chess 8
Johannes Fürnkranz (1997). Knowledge Discovery in Chess Databases: A Research Proposal. Technical Report OEFAI-TR-97-33, Austrian Research Institute for Artificial Intelligence, zipped ps, pdf ^[12]

1999

Ernst A. Heinz (1999). Endgame Databases and Efficient Index Schemes for Chess. ICCA Journal, Vol. 22, No. 1, ps
Ernst A. Heinz (1999). Knowledgeable Encoding and Querying of Endgame Databases. ICCA Journal, Vol. 22, No. 2, ps
Christoph Wirth, Jürg Nievergelt (1999). Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame. ICCA Journal, Vol. 22, No. 2
Eugene Nalimov, Christoph Wirth, Guy Haworth (1999). KQQKQQ and the Kasparov-World Game. ICCA Journal, Vol. 22, No. 4
Ulrich Thiemonds (1999). Ein regelbasiertes Spielprogramm für Schachendspiele. University of Bonn, Diploma thesis, zipped ps (German)
Chrilly Donninger (1999). Der Fortschritt ist nicht aufzuhalten - Chrilly Donninger über Endspieldatenbanken. CSS 6/99, pdf (German)

2000 ...

Haw-ren Fang, Tsan-sheng Hsu, Shun-Chin Hsu (2000). Construction of Chinese Chess Endgame Databases by Retrograde Analysis. CG 2000
Ken Thompson (2000). The Longest: KRNKNN in 262. ICGA Journal, Vol. 23, No. 1
Peter Karrer (2000). KQQKQP and KQPKQP≈.ICGA Journal, Vol. 23, No. 2 ^[13]
Guy Haworth (2000). Chess Endgames: Currents and Futures. 5th Computer Olympiad Workshop
Thomas Lincke, Ambros Marzetta (2000). Large Endgame Databases with Limited Memory Space. 5th Computer Olympiad Workshop
Thomas Lincke, Ambros Marzetta (2000). Large Endgame Databases with Limited Memory Space. ICGA Journal, Vol. 23, No. 3
Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2000). Space-Efficient Indexing of Chess Endgame Tables. ICGA Journal, Vol. 23, No. 3, postscript

2001

John Tamplin, Guy Haworth (2001). Ken Thompson's 6-man Tables. ICGA Journal, Vol. 24, No. 2
Harold van der Heijden (2001). Endgame Tables and Endgame Study Composition. ICGA Journal, Vol. 24, No. 2
Noam Elkies (2001). Endgame Tables and Chess Composition. ICGA Journal, Vol. 24, No. 2
Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3 ^[14] ^[15]
Ren Wu, Don Beal (2001). Parallel Retrograde Analysis on Different Architectures. IEEE 10th Conference in High Performance Distributed Computing pp. 356-362, August 2001
Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2001). Space-efficient Indexing of Endgame Tables for Chess. Advances in Computer Games 9
Guy Haworth (2001). Four Notes on Chess Endgames. 6th Computer Olympiad Workshop, ppt
Guy Haworth (2001). Discarding Like Pieces. 6th Computer Olympiad Workshop
Guy Haworth (2001). Depth by The Rule. 6th Computer Olympiad Workshop
Guy Haworth (2001). 3-5-Man Chess Data. 6th Computer Olympiad Workshop
Guy Haworth (2001). 3-5-Man Mutual Zugzwangs in Chess. 6th Computer Olympiad Workshop
Guy Haworth (2001). Discarding Like Pieces. ICGA Journal, Vol. 24, No. 3
Guy Haworth (2001). Depth by The Rule. ICGA Journal, Vol. 24, No. 3
Guy Haworth, Peter Karrer, John Tamplin, Christoph Wirth (2001). 3-5-man chess: Maximals and mzugs. ICGA Journal, Vol. 24, No. 4

2002

Guy Haworth (2002). Secrets of Pawnless Endings. ICGA Journal, Vol. 25, No. 2
Eugène Nalimov (2002). Chess Endgame Tablebases. Invited Lecture, 7th Computer Olympiad Workshop
Guy Haworth (2002). Reference Fallible Endgame Play. 7th Computer Olympiad Workshop, pdf
Ren Wu, Don Beal (2002). A memory efficient retrograde algorithm and its application to solve Chinese Chess endgames. More Games of No Chance edited by Richard J. Nowakowski

2003

John Tamplin, Guy Haworth (2003). Chess Endgames: Data and Strategy. Advances in Computer Games 10
Guy Haworth, Rafael B. Andrist (2003). Model Endgame Analysis. Advances in Computer Games 10
Jonathan Schaeffer, Yngvi Björnsson, Neil Burch, Rob Lake, Paul Lu, Steve Sutphen (2003). Building the Checkers 10-Piece Endgame Databases. Advances in Computer Games 10. pdf » Checkers
Guy Haworth (2003). Reference Fallible Endgame Play. ICGA Journal, Vol. 26, No. 2
Ed Trice, Gil Dodgen (2003). The Perfect 7-Piece Checkers Database. ICGA Journal, Vol. 26, No. 4 » Checkers

2004

Haw-ren Fang (2004). Rule-Tolerant Verification Algorithms for Completeness of Chinese-Chess Endgame Databases. CG 2004
Eiko Bleicher (2004). Building Chess Endgame Databases for Positions with many Pieces using A-priori Information. Lehrstuhl Mathematische Optimierung, Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Jena, Germany, as pdf

2005 ...

Joe Hurd (2005). Formal Verification of Chess Endgame Databases. in Joe Hurd, Edward Smith, Ashish Darbari Theorem proving in higher order logics: Emerging trends proceedings. Technical Report PRG-RR-05-02, Oxford University Computing Laboratory, pdf
Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis, Supervisor Peter Bro Miltersen, Aarhus University, pdf ^[16]
Guy Haworth (2005). 6-Man Chess Solved. ICGA Journal, Vol. 28, No. 3
Marc Bourzutschky, John Tamplin, Guy Haworth (2005). Chess endgames: 6-man data and strategy. Theoretical Computer Science, Vol. 349, No. 2
Rafael B. Andrist, Guy Haworth (2005). Deeper model endgame analysis. Theoretical Computer Science, Vol. 349, No. 2
Guy Haworth (2005). Chess Endgame News. ICGA Journal, Vol. 28, No. 4
Yngvi Björnsson, Jonathan Schaeffer, Nathan Sturtevant (2005). Partial Information Endgame Databases. Advances in Computer Games 11, pdf, pdf

2006

Guy Haworth (2006). Chess Endgame News. ICGA Journal, Vol. 29, No. 1
Guy Haworth (2006). Chess Endgame News. ICGA Journal, Vol. 29, No. 2
Guy Haworth (2006). Chess Endgame News. ICGA Journal, Vol. 29, No. 3

2008

Bo-Nian Chen, Pangfeng Liu, Shun-Chin Hsu, Tsan-sheng Hsu (2008). Knowledge Inferencing on Chinese Chess Endgames. CG 2008

2009

Guy Haworth (2009). Chess Endgame Update. ICGA Journal, Vol. 32, No. 4

2010 ...

Bo-Nian Chen, Pangfeng Liu, Shun-Chin Hsu, Tsan-sheng Hsu (2010). Conflict Resolution of Chinese Chess Endgame Knowledge Base. Advances in Computer Games 12, pdf
Joe Hurd, Guy Haworth (2010). Data Assurance in Opaque Computations. Advances in Computer Games 12, pdf
Matej Guid, Martin Možina, Aleksander Sadikov, Ivan Bratko (2010). Deriving Concepts and Strategies from Chess Tablebases. Advances in Computer Games 12, pdf
Eiko Bleicher, Guy Haworth (2010). 6-Man Chess and Zugzwangs. Advances in Computer Games 12
Bo-Nian Chen, Pangfeng Liu, Shun-Chin Hsu, Tsan-sheng Hsu (2010). Knowledge Abstraction in Chinese Chess Endgame Databases. CG 2010
Ping-hsun Wu, Ping-yi Liu, Tsan-sheng Hsu (2010). An External-memory Retrograde Analysis Algorithm, slides as pdf
Eiko Bleicher, Guy Haworth, Harold van der Heijden (2010). Data-Mining Chess Databases. ICGA Journal, Vol. 33, No. 4

2011

Guy Haworth (2011). Chess Endgame News. ICGA Journal, Vol. 34, No. 2

2013

Guy Haworth (2013). Chess Endgame News. ICGA Journal, Vol. 36, No. 1
Guy Haworth (2013). Chess Endgame News. ICGA Journal, Vol. 36, No. 2
Abdallah Saffidine, Nicolas Jouandeau, Cédric Buron, Tristan Cazenave (2013). Material Symmetry to Partition Endgame Tables. CG 2013
John Nunn (2013). Discoveries in R+2P vs. R+P Endings. ICGA Journal, Vol. 36, No. 3
Guy Haworth (2013). Chess Endgame News. ICGA Journal, Vol. 36, No. 3
Karsten Müller, Guy Haworth (2013). Rook vs. Bishop. ICGA Journal, Vol. 36, No. 4
Bo-Nian Chen, Hung-Jui Chang, Shun-Chin Hsu, Jr-Chang Chen, Tsan-sheng Hsu (2013). Multilevel Inference in Chinese Chess Endgame Knowledge Bases. ICGA Journal, Vol. 36, No. 4 » Chinese Chess
Guy Haworth (2013). Chess Endgame News. ICGA Journal, Vol. 36, No. 4
Guy Haworth (2013). Haworth’s Law. ICGA Journal, Vol. 36, No. 4
Victor Zakharov, Vladimir Makhnychev (2013). Creating tables of chess 7-piece endgames on the Lomonosov supercomputer. Superkomp’yutery, No. 15

2014

Bo-Nian Chen, Hung-Jui Chang, Shun-Chin Hsu, Jr-Chang Chen, Tsan-sheng Hsu (2014). Advanced Meta-knowledge for Chinese Chess Endgame Knowledge Bases. ICGA Journal, Vol 37, No. 1 » Chinese Chess
Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 1 » Syzygy Bases
Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 2 » Syzygy Bases
Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 3 » Syzygy Bases

2015 ...

Nikolaos Papahristou, Ioannis Refanidis (2015). Constructing Pin Endgame Databases for the Backgammon Variant Plakoto. Advances in Computer Games 14 ^[17]
Guy Haworth (2015). Chess Endgame News. ICGA Journal, Vol. 38, No. 1 » Crafty, FinalGen
Galen Huntington, Guy Haworth (2015). Depth to Mate and the 50-Move Rule. ICGA Journal, Vol. 38, No. 2 » Fifty-Move Rule ^[18]
Michael Hartisch, Ingo Althöfer (2015). Optimal Robot Play in Certain Chess Endgame Situations. ICGA Journal, Vol. 38, No. 3

2016

Victor Zakharov, Michael G. Malkovsky, Vladislav Y. Shchukin (2016). Compression of underdetermined data in a 7-piece chess table. Moscow University Computational Mathematics and Cybernetics, Vol. 40, No. 1 ^[19]

2017

Karsten Müller (2017). Tablebases, Fermat, Knights and Knightmares. ICGA Journal, Vol. 39, No. 2
Guy Haworth (2017). Chess Endgame News. ICGA Journal, Vol. 39, No. 2

Forum Posts

1995 ...

endgame databases and Kasparov by Feng-Hsiung Hsu, rgc, April 25, 1995
Tablebases and castling? by Ronald de Man, rgcc, May 12, 1997
Steve Edward's Endgame Tablebase generator is now available for WIN95 by Mike Byrne, CCC, November 01, 1997
Questions about Endgame tablebases by Alexander Nitschke, rgcc, March 19, 1998
Tablebases by Eugene Nalimov, CCC, August 28, 1998 » Nalimov Tablebases
Ideas to reduce size of tablebases by Rémi Coulom, CCC, August 31, 1998
endgame databases by Robert Hyatt, rgcc, October 13, 1998
Interesting endgame database probe problem by Robert Hyatt, CCC, February 04, 1999
overlapping tablebase lookup by Jay Scott, CCC, February 09, 1999

2000 ...

Tablebase Access Code by Roberto Waldteufel, CCC, April 26, 2000 » Rabbit
EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001 ^[20]
Re: How endgame tablebases work by Bruce Moreland, rgcc, July 19, 2001
PONDER=ON and TableBases on 1 PC by Matthias Gemuh, CCC, July 27, 2001 » Pondering
Nalimov's EGTBs (long post with code) by Heiner Marxen, CCC, October 13, 2001
Incomplete egtbs can be harmful by Leen Ammeraal, CCC, November 06, 2001
Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001 ^[21] ^[22]
Wu/Beal predates Koistinen by Guy Haworth, CCC, December 04, 2001
3-3 tablebase (with pawns) suggestion by Shane Hudson, CCC, December 23, 2001
Interesting EGTB bug by Tom Likens, CCC, April 16, 2002
How to handle EGTB stalemates by Tom Likens, CCC, March 02, 2003 » Stalemate
EGTB generation with 1 bit per position? by Martin Fierz, CCC, March 25, 2003
Frank Phillips' KNNKP position revisited ... by Guy Haworth, CCC, September 18, 2003 ^[23]

2005 ...

EGTB question by Stef Luijten, Winboard Forum, January 09, 2006
EGTB compression by Stef Luijten, Winboard Forum, February 10, 2006
utility for testing tablebases integrity by Victor Zakharov, CCRL Discussion Board, October 24, 2007
EGTB compression (H. G. Muller tablebase...) by Dann Corbit, CCC, January 25, 2008
DTR is no good! by Harm Geert Muller, CCRL Discussion Board, September 24, 2008
Gaviota's Endgame Tablebases by Miguel A. Ballicora, CCC, December 07, 2008 » Gaviota Tablebases
Creating EGTBs by Carey, CCC, December 21, 2008
Other endgame tablebase generators by Denis P. Mendoza, CCC, January 23, 2009

2010 ...

Some tablebase formats by BB+, OpenChess Forum, November 25, 2010
Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010

2011

Gaviota tablebases, probing code v4 (UPDATE) by Miguel A. Ballicora, CCC, March 11, 2011
Large tablebases by BB+, OpenChess Forum, April 21, 2011
Mapping the 7-men computation by Astokes, CCRL Discussion Board, September 21, 2011
Poor Man Table Base by Ed Schroder, CCC, December 13, 2011
Number sequence puzzle by Steven Edwards, CCC, December 16, 2011 ^[24]
Tablebase class name list available by Steven Edwards, CCC, December 19, 2011 » CookieCat

2012

Compression of chess databases by Edmund Moshammer, CCC, July 09, 2012
pawn enumeration by Daniel Shawul, CCC, July 24, 2012

2013

New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013 » Syzygy Bases
Complete 7-piece tablebases are out! by Albert Silver, CCC, April 12, 2013 ^[25]
Multithreaded LRU by Alvaro Cardoso, CCC, October 06, 2013 » Memory
What happens using egbb by Kai Laskos, CCC, October 12, 2013 » Scorpio Bitbases
tablebase caching / mmap() / page cache by Ronald de Man, CCC, October 13, 2013 » Memory, Syzygy Bases
How to encode endgame tablebases by Mr. beo, Rybka Forum, October 18, 2013
Could EGTB make an Engine "weaker"? by Bill Henry, CCC, October 23, 2013
evaluating tablebases draws by Uri Blass, CCC, November 23, 2013 » Draw Evaluation
Table Base Cache Size question by Rob Nicholas, CCC, December 05, 2013 » Memory

2014

Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014 » Scorpio Bitbases
On-demand tablebase generation by Evert Glebbeek, CCC, January 19, 2014
Endgame tablebase generation for newbies by Alberto Sanjuan, CCC, April 04, 2014
A different tablebase encoding format by Steven Edwards, CCC, August 10, 2014
Tablebase access using a Solid State Disk by Steven Edwards, CCC, October 16, 2014 » Memory

2015 ...

how to probe egtb from console? by Marco Belli, CCC, May 15, 2015 » CLI
Yet another KPK endgame table generator: pfkpk by Marcel van Kervinck, CCC, September 05, 2015 » KPK Bitbase ^[26]
Is there tools to get the longest DTM/DTC for elementary EG? by Vincent Lejeune, CCC, September 07, 2015
7 men Rook endgames H4 vs SF in recent TCEC stage 1b by Nay Lin Tun, CCC, September 07, 2015 » Rook Endgame, TCEC Season 8

2016

Nalimov EGTB problem related to DTM? by Kai Laskos, CCC, February 14, 2016 » Nalimov Tablebases, DTM
Re: Nalimov EGTB problem related to DTM? by Ronald de Man, CCC, February 14, 2016
6-men tablebase wanted by Harm Geert Muller, CCC, March 03, 2016
Good testsets for tablebases testing by Sergei S. Markoff, CCC, May 15, 2016 » Test-Positions
EPD to test EGTB probe code by Sergei S. Markoff, CCC, May 24, 2016
11-men tablebases (XQ) by Harm Geert Muller, CCC, May 23, 2016 » Xiangqi
Natural TB by Marco Costalba, CCC, May 29, 2016 » Syzygy Bases, Stockfish
How texel probes endgame tablebases by Peter Österlund, CCC, July 16, 2016 » Gaviota Tablebases, Syzygy Bases, Texel
Getting engines to use TBs in Arena by Brendan J. Norman, CCC, July 19, 2016 » Arena
Syzygy and draw by repetition by Jon Dart, CCC, July 22, 2016 » Draw, Repetitions, Syzygy Bases
Verifiability of endgame tablebases by Joan Charmant, CCC, July 23, 2016

2017

Checkers Is Strongly-Solved for 8-pieces by Ed Trice, CCC, February 12, 2017 » Checkers
Search Halting Criteria When Probing Tablebases by Ed Trice, CCC, March 02, 2017
Probe EGT in quiescence? by Nguyen Pham, CCC, May 20, 2017 » Quiescence Search, Xiangqi
Incorporating Endgame tablebases by Pranav Deshpande, CCC, May 24, 2017
EGTB probe in search by Erin Dame, CCC, July 30, 2017
Natural TB (take 2) by Marco Costalba, CCC, August 22, 2017 » Syzygy Bases, Stockfish
understanding DTZ by Alexandru Mosoi, CCC, October 06, 2017 » DTZ, Syzygy Bases, Fathom

2018

A new design for Xianqgi (Chinese chess) Endgame Tablebase by Nguyen Pham, CCC, January 16, 2018 » Chinese Chess
Question about EGT formats by Harm Geert Muller, CCC, January 26, 2018
The history of Syzygy tablebases by Isaac Haïk Dunn, CCC, March 06, 2018 » Syzygy Bases

External Links

ICGA: Chess Endgames compiled by Guy Haworth and colleagues
Endgame tablebase from Wikipedia
Endgame Tablebases and Bitbases List from Computer-Chess Wiki by Ron Murawski
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
Gilith - Chess Endgames by Joe Leslie-Hurd
Endgame Tablebases - gaviota chess engine by Miguel A. Ballicora ^[27]
Compression Schemes for Gaviota Tablebases
Computing endgames with few men by Urban Koistinen ^[28] ^[29] ^[30]
Koistinen/Endgame · GitHub
End-Game Table Bases by Harm Geert Muller
The Leapfrog Tablebase Generator by Harm Geert Muller
Hoffman by Brent Baccala
Endgame databases by Emil Vlasák
CCRL Discussion Board - Endgame Tablebases
Guide to the use of Computer Chess Endgame Tablebases from FAQ on Winboard and Chess Engines by Aaron Tay
Can use of endgame tablebases weaken play? from FAQ on Winboard and Chess Engines by Aaron Tay
Can We Solve Chess One Day? | Gödel's Lost Letter and P=NP by Dick Lipton, May 12, 2010
7-man TB - Google+
syzygy1/tb · GitHub by Ronald de Man ^[31]
dshawul/Scorpio · GitHub includes Six men egbb code » Scorpio Bitbases ^[32]
kervinck/pfkpk · GitHub » KPK Bitbase by Marcel van Kervinck ^[33]

ChessBase

Engines and endgame tablebases by Albert Silver, ChessBase News, December 12, 2013
Perfect endgame play – with tablebases, ChessBase News, April 21, 2015
Just one of 17,823,400,766 positions by Frederic Friedel, ChessBase News, April 23, 2015

ChessOK

Lomonosov Endgame Tablebases

Online Lookup

Lomonosov - online 7-man tablebases
Endgame Nalimov Tablebases Online by ChessOK
Nalimov EGTB from GMchess.com
Nalimov Tablebase server (DTM) by Lokasoft
Web Query for Nalimov Endgame Tablebases (DTM) from Knowledge4IT by Eiko Bleicher
Chess Archives - Endgames (DTC, DTM, DTZ, DTZ-50) hosted by John Tamplin
Schach Endspiele (DTM) (German) by Joachim Rack

Download

Endgame Tablebases Online - 6-men endgame analysis free for everyone by Kirill Kryukov (3,4,5,6 pieces - via emule)
Index of /tablebases by kingliveson
tablebase.sesse.net by Sesse

Statistics

References

^ Ernst A. Heinz (1999). Endgame Databases and Efficient Index Schemes for Chess. ICCA Journal, Vol. 22, No. 1, ps
^ Persistence, Oil on Canvas, 200 x 160 cm, Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ DTR is no good! by Harm Geert Muller, CCRL Forum, September 24, 2008
^ Subject: KRRNKRR win in 290: a new record by Marc Bourzutschky from CCC, October 16, 2005
^ Chess endgame from Wikipedia
^ 311. 31 March 2006: White plays and wins in 330 moves by Tim Krabbé
^ OPEN CHESS DIARY 316. 26 May 2006: A 517-move win by Tim Krabbé
^ Endgame tablebase from Wikipedia - Background
^ Lomonosov Endgame Tablebases - ChessOK
^ Subject: brute-force vs. intuition in math & chess by Bill Dubuque, August 1996
^ Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis
^ Knowledge discovery from Wikipedia
^ Kasparov versus the World from Wikipedia
^ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001, with reference to Computing endgames with few men by Urban Koistinen
^ Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
^ OBDD - Ordered Binary Decision Diagram from Wikipedia
^ Plakoto from Wikipedia
^ Endgame tablebases with the fifty-move rule by Galen Huntington
^ tablebase compression / academic integrity by Ronald de Man, CCC, May 19, 2016
^ Computing endgames with few men by Urban Koistinen
^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
^ Computing endgames with few men by Urban Koistinen
^ Easy mate by Frank Phillips, CCC, September 13, 2003 » Checkmate
^ A018214 - OEIS | Alkane (or paraffin) numbers
^ Lomonosov Endgame Tablebases - ChessOK
^ kervinck/pfkpk · GitHub
^ Gaviota tablebases, probing code v4 (UPDATE) by Miguel A. Ballicora, CCC, March 11, 2011
^ EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001
^ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001
^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
^ New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013
^ Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014
^ Yet another KPK endgame table generator: pfkpk by Marcel van Kervinck, CCC, September 05, 2015

What links here?

Page	Date Edited
ACM 1978	Dec 23, 2017
Advances in Computer Chess 8	Jun 26, 2017
Albert Silver	Feb 25, 2018
Alberto Sanjuan	Nov 3, 2014
Albrecht Heeffer	Sep 6, 2016
Alexandru Mosoi	Jan 8, 2018
Alvaro Cardoso	Jan 12, 2018
Arena	Mar 16, 2018
Belle	Jan 18, 2018
Beowulf	May 5, 2017
Bernhard Walter	Dec 31, 2015
BMI2	Mar 6, 2018
Bo-Nian Chen	Jul 17, 2017
Brendan J. Norman	Jan 11, 2018
Brute-Force	Jul 27, 2017
Carey Bloodworth	Jul 19, 2016
Check Check	Jan 8, 2016
Checkers	Dec 23, 2017
Checkmate	Apr 13, 2018
Chenard	Sep 5, 2015
Chess for Android	Mar 1, 2018
Chess Game	Mar 28, 2017
Chess Problems, Compositions and Studies	Feb 19, 2018
ChessBase (Database)	Feb 26, 2018
ChessGUI	Jan 17, 2018
Chessmaster	Jan 21, 2018
ChessOK	Jul 30, 2013
Chinese Chess	Jan 16, 2018
Chiron	Sep 24, 2017
Christoph Wirth	Jan 8, 2017
CLI	Jan 20, 2018
Connection Machine	Oct 12, 2016
CookieCat	Nov 15, 2016
Corresponding Squares	Oct 9, 2017
Crafty	Jan 28, 2018
DarkThought	Jul 3, 2018
Data	Nov 26, 2017
Databases	Mar 18, 2018
David Forthoffer	Apr 25, 2016
Denis Onneweer	Oct 3, 2012
Diagonal Mirroring	Jun 29, 2013
Dictionary	Aug 24, 2017
Dietmar Lippold	Mar 22, 2014
Djinn	Feb 8, 2016
Draw	Apr 14, 2018
Draw Evaluation	Mar 12, 2018
Ed Trice	Feb 21, 2018
Edmund Moshammer	Sep 23, 2017
Edwards' Tablebases	Sep 26, 2016
Emil Vlasák	Sep 30, 2015
Endgame	Sep 18, 2017
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Engine Testing	Feb 1, 2018
Ernst A. Heinz	Mar 6, 2017
Evert Glebbeek	Sep 25, 2017
Ferret	Jan 7, 2016
Fifty-move Rule	Aug 9, 2017
FinalGen	Aug 14, 2016
Floyd	Sep 11, 2016
Frank Phillips	Sep 26, 2016
Frederic Friedel	Jan 6, 2018
Freezer	Aug 14, 2016
GAFS	Aug 14, 2016
Galahad	Jan 8, 2015
Galen Huntington	Dec 21, 2015
Galjoen	Mar 19, 2018
Gaviota Tablebases	Apr 22, 2018
Gerard Zielinski	Sep 25, 2014
Gijsbert Wiesenekker	Jan 17, 2018
Gil Dodgen	Mar 1, 2017
Grit Lachmann	Apr 26, 2014
GUI	Mar 16, 2018
Günter Rehburg	Nov 5, 2010
Guy Haworth	Nov 20, 2017
Hans Zellner	Jun 12, 2016
Harold van der Heijden	Jan 8, 2014
Hash Table	Jan 1, 2018
Hiarcs	Feb 25, 2018
Horizontal Mirroring	Jun 29, 2013
ICGA	Jul 8, 2017
ICGA Journal	Dec 21, 2017
Ikarus	Jul 5, 2016
Interior Node Recognizer	Mar 12, 2018
Ioannis Refanidis	Jan 19, 2016
Jesper Torp Kristensen	Oct 10, 2013
Joachim Rang	Mar 19, 2014
Joe Culberson	Dec 13, 2016
Joe Leslie-Hurd	Aug 15, 2013
John Nunn	Dec 9, 2017
John Roycroft	Apr 24, 2016
John Tamplin	Jan 9, 2017
Joshua Shriver	Nov 24, 2017
Kenneth Wingate Regan	Feb 19, 2018
Kirill Kryukov	Apr 16, 2014
Knowledge	Jul 22, 2017
KPK	May 12, 2016
KRK	Nov 26, 2016
Kuang-Che Wu	Dec 26, 2016
Lars Rasmussen	Apr 25, 2016
Leila	May 8, 2017
Lomonosov Supercomputer	May 19, 2016
Lomonosov Tablebases	May 20, 2016
Losing Chess	Sep 18, 2017
Ludwig Zagler	Sep 6, 2017
Marc Bourzutschky	Dec 16, 2013
Marco Belli	Jan 6, 2018
Mark Watkins	Dec 6, 2017
Martin Fierz	Apr 26, 2018
Match Statistics	Mar 31, 2018
Mate Search	Oct 22, 2016
Mathematician	Apr 9, 2018
Matthias Gemuh	Jan 21, 2018
Memory	Dec 8, 2017
Michael G. Malkovsky	May 20, 2016
Michael Hartisch	Aug 11, 2017
Miguel A. Ballicora	Jun 19, 2017
Much	Jun 7, 2016
Najib Nakad	Oct 22, 2014
Nalimov Tablebases	Dec 23, 2016
Nimzo	Dec 30, 2017
Nullmover	Jul 21, 2013
Oracle	Sep 4, 2016
Pandix	Feb 4, 2017
Patrick Schoo	May 25, 2016
Patzer	Apr 5, 2017
Paul Lu	Dec 13, 2016
Pepito	Nov 27, 2014
Peter Karrer	Jan 9, 2017
Peter van Diepen	Nov 5, 2015
Pharaon	Sep 2, 2017
Ping-hsun Wu	Jun 8, 2015
Pondering	Dec 9, 2017
Protector	Oct 12, 2017
python-chess	Nov 4, 2017
Quiescence Search	Aug 19, 2017
Rabbit	Oct 5, 2014
Rafael B. Andrist	May 30, 2017
Rémi Coulom	Feb 5, 2018
Ren Wu	Jul 23, 2017
Réti Endgame Study	Feb 25, 2014
RetroChess	Feb 2, 2014
Retrograde Analysis	Mar 21, 2017
Rob Lake	Dec 5, 2016
Roberto Waldteufel	Jun 5, 2013
Ronald de Man	Nov 20, 2017
Rook Endgame	Sep 18, 2017
Score	Apr 14, 2018
Scorpio Bitbases	Mar 12, 2018
Shess	Jan 7, 2016
Shun-Chin Hsu	Jul 22, 2017
Sidonia	May 19, 2016
Sito Dekker	Apr 25, 2016
SOS	Apr 5, 2017
Space-Time Tradeoff	Jun 17, 2015
Stalemate	Feb 21, 2018
Steven Edwards	Aug 26, 2017
Syzygy Bases	Apr 19, 2018
Test-Positions	Feb 25, 2018
Thomas Ströhlein	May 24, 2016
Thompson's Databases	Dec 24, 2014
Thread	Apr 22, 2018
Tom Likens	Mar 7, 2017
Tsan-sheng Hsu	Jul 17, 2017
UCI	Mar 4, 2018
Ulrich Thiemonds	Apr 26, 2014
User Interface	Feb 21, 2018
Vertical Flipping	Oct 10, 2013
Victor Zakharov	May 20, 2016
Vladimir Makhnychev	Nov 29, 2016
WCCC 2002	Nov 24, 2017
WChess	Jan 7, 2016
Wilhelm	Oct 6, 2015
Workshop Chess and Mathematics	Mar 5, 2015
XieXie	Jul 26, 2017
Yakov Konoval	Apr 28, 2009
YChess	Feb 25, 2018
Zeus	Jan 3, 2018

Up one level

EPAM

GerdIsenberg — Sat, 15 Jul 2017 11:52:44 GMT

Home * Knowledge * Cognition * EPAM

		EPAM, (Elementary Perceiver and Memorizer) an early computer model of rote learning by the method of paired associates, first conceived by Herbert Simon and Allen Newell during their early conception about computer simulation of cognitive processes in the 50s ^[1] , implemented as computer program by Edward Feigenbaum in the late 50s in IPL-V for the IBM 704 and IBM 7090, as topic of his Ph.D. thesis at Carnegie Mellon University. In terms of psychology and behaviorism EPAM associates responses with external stimuli, quite similar to classical conditioning. EPAM learns by growing a discrimination net kept in long-term memory, a tree-like structure whose nodes contain tests that may be applied to objects that have been described as bundles of perceptual features. In EPAM III, introduced in 1964 ^[2] , the test nodes were generalized as n-ary switch instead of binary of EPAM II. When a familiar object is perceived, it is recognized by being sorted through the EPAM net. At the terminal nodes of the EPAM net, partial "images" are stored, also in the form of feature bundles of the objects sorted to the respective terminals, together with other information about the objects ^[3] , such as cue information, used to feed back into the net recursively . Thus, EPAM has a recursive structure. Any object, once familiarized and incorporated into the net, can itself serve as a perceptual feature of a more complex object. For instance in the domain of chess, once the various types of chess pieces and their proximity become familiarized, these can become features of more complex configurations, i.e. a "fianchettoed castled Black King's position". Once familiarized, such a complex can, in turn, serve as a perceptual feature of a still more complex pattern, finally the entire chess position.
EPAM discrimination net ^[4]

The EPAM Simulation

Excerpt from Elementary Perceiver and Memorizer: Review of Experiments ^[5] :

The EPAM processes perform the following four principal functions:

Recognize an external stimulus as one about which some information has already been memorized
Add new stimulus items to the memory by building discriminations (tests) that allow the new item to be distinguished from stimuli previously learned
Associate (internally) two stored items, say x and y, by storing with x some cue information about y
Respond to an external stimulus X with a response, Y, by retrieving the cue to the response, and then retrieving the response using the cue

Thus, EPAM has two performance processes, enabling It to respond using material already learned: the discrimination process (1), which recognizes the stimulus, and the response process (4), which finds the appropriate response associated with the stimulus and produces it. EPAM also has two learning processes: the discrimination learning process (2), which elaborates the structure of discrimination tests it applies to stimuli, and the association learning process (3), which associates response cues with stimuli.

The central "memory structure, which the performance processes use and the learning processes construct, is the discrimination net. It is a tree-like nexus of associations at whose terminal nodes are stored Images of encodings of external stimuli. At the non-terminal nodes of the net are stored tests which examine particular bits of the encodings. The image of a stimulus is retrieved by sorting the encoding of the stimulus down through the tests of the net to the appropriate terminal. In learning a set of stimuli, the net is grown to a size that is Just large enough (roughly) to discriminate among the different stimuli that have been presented to the system.

Association of a response, y, to a stimulus, x, is accomplished by storing a small amount of the information about y (an incomplete cue image of y) along with the image of x. The system determines by trial and error how much information must be stored as a cue to retrieve the response from the net when the association is made.

MAPP

EPAM was influential in formalizing the concept of chunking. It was used in the MAPP (Memory-aided Pattern Perceiver) program by Simon and Gilmartin ^[6] to simulate the chess board reconstruction task. An EPAM net was stimulated by the piece fixation of the eye movement simulation program Perceiver, to recognize cluster of pieces surrounding the fixated piece as a familar chunk. In the perception phase up to seven symbols designating these chunks were stored in short-term memory. In the reconstruction phase, the EPAM net was used to decode the symbols held in short-term memory into locational information for each of the pieces in a chunk. In various experiments, MAPP was able to reconstruct positions with 73% accuracy ^[7] ^[8]

A schematic representation of the principle components of MAPP shows the learning and performance
processes used to reconstruct a chess position ^[9]

CHREST

The EPAM concept was further influential for Fernand Gobet's CHREST (Chunk Hierarchy and REtrieval STructures) architecture, applied in Gobet's and Jansen's pattern learning chess program CHUMP ^[10] .

Publicatons

1959

Edward Feigenbaum (1959). An Information Processing Theory of Verbal Learning. RAND Paper

1960 ...

Edward Feigenbaum (1960). Information Theories of Human Verbal Learning. Ph.D. thesis, Carnegie Mellon University, advisor Herbert Simon
Edward Feigenbaum (1961). The Simulation of Verbal Learning Behavior. Proceedings Western Joint Conference, Vol. 19
Edward Feigenbaum, Herbert Simon (1961). Performance of a Reading Task by an Elementary Perceiving and Memorizing Program. RAND Paper, pdf
Edward Feigenbaum, Herbert Simon (1961). Forgetting in an association memory. ACM '61, pdf
Edward Feigenbaum, Herbert Simon (1962). A Theory of the Serial Position Effect. British Journal of Psychology, Vol. 53, 307-32, pdf
Edward Feigenbaum, Herbert Simon (1963). Elementary Perceiver and Memorizer: Review of Experiments. in Symposium on Simulation Models
Herbert Simon, Edward Feigenbaum (1964). An Information-processing Theory of Some Effects of Similarity, Familiarization, and Meaningfulness in Verbal Learning. Journal of Verbal Learning and Verbal Behavior, Vol. 3, No. 5, pdf

1970 ...

Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5
Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, Reprinted (1988) in Computer Chess Compendium, pdf
Herbert Simon (1974). How big is a chunk? Science, Vol. 183, pdf

1980 ...

Lawrence W. Barsalou, Gordon H. Bower (1984). Discrimination Nets as Psychological Models. Cognitive Science, Vol. 8, No. 1 ^[11]
Edward Feigenbaum, Herbert Simon (1984). EPAMlike models of recognition and learning. Cognitive Science, Vol. 8, 305-336, pdf

1990 ...

Howard B. Richman, James J. Staszewski, Herbert Simon (1995). Simulation of Expert Memory with EPAM IV. Psychological Review, Vol. 102
Fernand Gobet, Howard B. Richman, James J. Staszewski, Herbert Simon (1997). Goals, Representations, and Strategies in a Concept Attainment Task: The EPAM model. The Psychology of Learning and Motivation, Vol. 37, pdf

2000 ...

Fernand Gobet, Herbert Simon (2000). Five Seconds or Sixty? Presentation Time in Expert Memory. Cognitive Science, Vol. 24, No. 4
Fernand Gobet, Peter Lane, Steve Croker, Peter C-H. Cheng, Gary Jones, Iain Oliver, Julian M. Pine (2001). Chunking mechanisms in human learning. Trends in Cognitive Sciences, Vol. 5, No. 6
Fernand Gobet (2005). Chunking Models of Expertise: Implications for Education. Applied Cognitive Psychology, Vol. 19, No. 2

External Links

EPAM from Wikipedia
Expertise in Memory - EPAM Model by Victor Long, Chandra Singh and David Snitkof, Brown University
Expertise in Memory - Evidence for Chunking Theory by Victor Long, Chandra Singh and David Snitkof, Brown University
Agnes Obel - Familiar, Alcaline, November 07, 2016, YouTube Video
featuring Kristina Koropecki, Charlotte Danhier, Catherine De Biasio

References

^ Edward Feigenbaum (1959). An Information Processing Theory of Verbal Learning. RAND Paper
^ Herbert Simon, Edward Feigenbaum (1964). An Information-processing Theory of Some Effects of Similarity, Familiarization, and Meaningfulness in Verbal Learning. Journal of Verbal Learning and Verbal Behavior, Vol. 3, No. 5, pdf
^ Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, Reprinted (1988) in Computer Chess Compendium, pdf
^ A typical EPAM discrimination net, Image from Edward Feigenbaum, Herbert Simon (1963). Elementary Perceiver and Memorizer: Review of Experiments. in Symposium on Simulation Models, pp. 103
^ Edward Feigenbaum, Herbert Simon (1963). Elementary Perceiver and Memorizer: Review of Experiments. in Symposium on Simulation Models
^ Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46, reprinted in Herbert Simon (1979). Models of Thought. Yale University Press
^ Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46
^ Michael George, Jonathan Schaeffer (1990). Chunking for Experience. ICCA Journal, Vol. 13, No. 3, pdf
^ Image from Expertise in Memory - Evidence for Chunking Theory by Victor Long, Chandra Singh and David Snitkof, Brown University, see also Figure 6 in Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, pp. 401, reprinted in David Levy (ed.) (1988) Computer Chess Compendium, pdf
^ Fernand Gobet, Peter Jansen (1994). Towards a Chess Program Based on a Model of Human Memory. Advances in Computer Chess 7
^ Pandemonium architecture from Wikipedia

What links here?

Page	Date Edited
CHREST	May 6, 2016
Chump	Jan 31, 2016
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
Dictionary	Aug 24, 2017
Edward Feigenbaum	Jan 3, 2016
EPAM	Jul 15, 2017
Eye Movements	Jul 22, 2015
Kevin J. Gilmartin	Jan 1, 2016
Learning	Feb 20, 2018
MAPP	Jan 30, 2016
Perceiver	Nov 21, 2017

Up one Level

Eye Movements

GerdIsenberg — Wed, 22 Jul 2015 18:56:03 GMT

Home * Knowledge * Cognition * Eye Movements

		Eye Movements, are voluntary or involuntary movements of the eyes helping in visual perception to fixate and track visual stimuli, to acquire information applied to memorization and learning in heuristic search and pattern recognition. Of special interest in chess and cognition are eye movements of chess players at the chess board, where cognitive experiments and computer chess simulations were conducted by various researchers to understand how chess masters grasp the important features of a chess position, giving hints to the search concerning move selectivity and ordering. In computer chess simulations, eye movement is related to attack and move generation, either one-many of one piece from its origin square to multiple target squares, or many-one, that is one particular target square attacked/defended by multiple pieces as in Square Attacked By with bitboards .
Eye movements of a chess champion ^[1]

Tichomirov and Poznyanskaya

Applications

Perceiver & MAPP

The experimental program Perceiver by Michael Barenfeld and Herbert Simon was able to duplicate the eye movements of a master by adhering to the simple relations of attack and defense ^[2], further extended by Kevin J. Gilmartin and Simon into a system called MAPP (Memory-aided Pattern Perceiver) which uses the learning mechanism of EPAM ^[3].

CHUMP

CHUMP, by Fernand Gobet and Peter Jansen ^[4], is an application of the Chunk Hierarchy and REtrieval STructures (CHREST), a pattern learning approach where an eye movement simulator is the only part of the system where the rules of the game, that is how pieces attack and move, influence the learning process.

Skill in Chess

Excerpt from Eye movements at the Chess Board in Skill in Chess, 1973 by Herbert Simon and William Chase ^[5]:

Serial or Parallel?

Explanations in terms of heuristic search postulate that problem solving, and cognition generally, is a serial, one-thing-at-a-time process. (We are oversimplifying matters to make the issue clear, but the oversimplification will suffice for the present.) Many psychologists have found this postulate implausible and have sought for evidence that the human organism engages in extensive parallel processing ^[6]. The intuitive feeling that much information can be "acquired at a glance" argues for a parallel processor. Of course, the correctness of the intuition depends both on the amount of information that can actually be acquired and upon what is meant by a "glance." If a glance means a single eye fixation (lasting anywhere from a fifth of a second to a half-second or longer), then we know that there are high-speed serial processes (e.g. short-term memory search, visual scanning) that operate within this time range ^[7]. Thus, it is certainly interesting and relevant to find out how the human eye extracts information from a complex visual display like a chess position and to see whether this extraction process is compatible with the assumptions of the heuristic search theories.

Tichomirov and Poznyanskaya

A pair of Russian psychologists, Tichomirov and Poznyanskaya, placed an expert before a chess position with instructions to find the best move, and they observed his eye movements during the first 5 seconds of the task ^[8]. The eye movements were inconsistent with the hypothesis that the subject, during these 5 seconds, was searching through a tree of possible moves and their replies. To describe further what Tichomirov and Poznyanskaya found, we must say a word about how the eye operates. The eye has a central region of high resolution, the fovea (about 1° in radius), surrounded by a periphery of decreasingly lower resolution. Most information about visual patterns is acquired while the fovea is fixated on them; and the eye moves abruptly, in so-called saccadic movements, from one point of fixation to the next. There are at most about four or five saccadic movements per second. In Tichomirov and Poznyanskaya's record of the first 5 seconds of their subject's eye movements, there were about 20 fixations. Most of these centered on squares of the board occupied by pieces that any chess player would consider to be of importance to the position. There were few fixations at the edges or corners of the board or on empty squares. Moreover, a large number of the saccades moved from one piece to another, where the former piece stood in a "chess" relation — that is, an attack or defense relation—to the latter. For example, the eye would move frequently from a pawn to a Knight that attacked it, or to a Knight that defended it, or from a Queen to a pawn it attacked. It is important to note that the saccadic movements were not random — therefore, that some information must have been acquired peripherally about the target square before the saccade began. From other evidenge, we know that a strong chess player can recognize a piece within a radius of 5° to 7° from his point of fixation; for eye-movement studies show that he can frequently replace such a piece correctly on a board when he has had no closer point of fixation to it ^[9].

Publicatons

1960 ...

Oleg K. Tichomirov, E. D. Poznyanskaya (1966). An Investigation of Visual Search as a Means of Analyzing Heuristics. Soviet Psychology, Winter 1966-67 (from Voprosy Psikhologii, 1966, 2, 4)
Herbert Simon, Michael Barenfeld (1968). Information Processing in the Perception of Chess Positions. Carnegie Mellon University, Paper #127
Herbert Simon, Michael Barenfeld (1969). Information Processing-Analysis of Perceptual Processes in Problem Solving. Psychological Review, Vol. 76, No. 5, reprinted in Herbert A. Simon (1979). Models of Thought. Yale University Press, pdf

1970 ...

Herbert Simon (1973). Lessons from Perception for Chess-Playing Programs (and Vice Versa). Computer Science Research Review 1972-73, pdf
Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, reprinted in David Levy (ed.) (1988) Computer Chess Compendium, pdf
Ruslan Hajiev (1975). Experimental Studies of Human Decision-Making and its Simulation by Situation Control Technique.. (on the basis of a chess endgame). IJCAI 1975, Tbilisi, Georgia, USSR, pdf

1980 ...

Ivan Bratko, Peter Tancig, Simona Tancig (1984). Detection of Positional Patterns in Chess. ICCA Journal, Vol. 7, No. 2

1990 ...

Fernand Gobet, Peter Jansen (1994). Towards a Chess Program Based on a Model of Human Memory. Advances in Computer Chess 7
Adriaan de Groot, Fernand Gobet (1996). Perception and memory in chess. Heuristics of the professional eye. Assen: Van Gorcum, The Netherlands. ISBN 90-232-2949-5. Chapter 9; A discussion: Two authors, two different views? word reprint.

2000 ...

Neil Charness, Eyal Reingold, et al. (2001). The perceptual aspect of skilled performance in chess: Evidence from eye movements. Memory & Cognition, Vol. 29, 1146-1152, pdf
Toma Roncevic, Vlasta Zanchi (2004). Following outlines by Robotic Retinal Eye Movements. 3rd DAAAM International Conference on Advanced Technologies for Developing Countries, Split, Croatia
Eyal Reingold, Neil Charness (2005). Perception in chess: Evidence from eye movements. Cognitive processes in eye guidance. Oxford University Press, pdf
Hans-Werner Hunziker (2006). Im Auge des Lesers: vom Buchstabieren zur Lesefreude. (In the eye of the reader: from letter recognition to the joy of reading) Transmedia Verlag, Zurich, ISBN 978-3-7266-0068-6 (German)
Merim Bilalić, Peter McLeod, Fernand Gobet (2008). Why Good Thoughts Block Better Ones: The Mechanism of the Pernicious Einstellung (set) Effect. Cognition, Vol. 108, No. 3, preprint pdf

External Links

Perception

Visual

Vision

Misc

McCoy Tyner Trio with Freddie Hubbard & Joe Henderson - Inner Glimpse, Jazz Ost-West, Nuremberg, 1986, YouTube Video
feat. Avery Sharpe and Louis Hayes

References

^ Hans-Werner Hunziker (2006). Im Auge des Lesers: vom Buchstabieren zur Lesefreude. (In the eye of the reader: from letter recognition to the joy of reading) Transmedia Verlag, Zurich, ISBN 978-3-7266-0068-6, Peripheral vision from Wikipedia
^ Herbert Simon, Michael Barenfeld (1969). Information-processing analysis of perceptual processes in problem solving. Psychological Review, Vol. 76, No. 5
^ Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46.
^ Fernand Gobet, Peter Jansen (1994). Towards a Chess Program Based on a Model of Human Memory. Advances in Computer Chess 7
^ Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4
^ Ulric Neisser (1963). The Imitation of Man by Machine. Science, Vol. 139
^ Saul Sternberg (1969). Memory-scanning: Mental Processes revealed by Reaction-time Experiments. American Scientist, Vol. 57, No. 4, pdf
^ Oleg K. Tichomirov, E. D. Poznyanskaya (1966). An Investigation of Visual Search as a Means of Analyzing Heuristics. Soviet Psychology, Winter 1966-67 (from Voprosy Psikhologii, 1966, 2, 4)
^ P. C. Noordzij (1966). Het registreren van oogbewegingen bij schakers. Psychology Laboratory of the University of Amsterdam

What links here?

Page	Date Edited
CHREST	May 6, 2016
Chump	Jan 31, 2016
Cognition	Dec 8, 2017
EPAM	Jul 15, 2017
Eye Movements	Jul 22, 2015
Kevin J. Gilmartin	Jan 1, 2016
MAPP	Jan 30, 2016
Merim Bilalić	Oct 2, 2014
Michael Barenfeld	Oct 2, 2014
Neil Charness	Oct 2, 2014
Oleg K. Tichomirov	Oct 2, 2014
Perceiver	Nov 21, 2017
Ruslan Hajiev	Oct 2, 2014

Up one Level

Gaviota Tablebases

GerdIsenberg — Mon, 23 Apr 2018 05:42:33 GMT

Home * Knowledge * Endgame Tablebases * Gaviota Tablebases

		Gaviota Tablebases, a depth to mate endgame tablebase by Miguel A. Ballicora, initially developed for his Gaviota engine ^[1] . The probing code, written in C, is open source, along with the tablebase files licensed under the MIT license. Gaviota Tablebases cache system works like bitbases on the fly, allowing to probe WDL information with fourfold increased cache efficiency. Further, the thread safe probing API allows soft probes to get information from the cache without reading the hard disk - intended to use everywhere inside the search, and the classical hard probe, suited to use with some distance to the horizon. The up to 5-men tablebase files can be generated ^[2] and checked ^[3] using the free command line program tbgen, performing several compression schemes using tbcp ^[4], yielding in 5-men sizes below 7 GB.
Gaviota base on Runde ^[5]

Forum Posts

2008

Gaviota's Endgame Tablebases by Miguel A. Ballicora, CCC, December 07, 2008

2009

Gaviota 0.74 released by Miguel A. Ballicora, CCC, October 21, 2009
Gaviota 0.74.6 (special for EGTB builders) by Miguel A. Ballicora, CCC, October 31, 2009
Gaviota's EGTBs are only 6.5 Gb now by Miguel A. Ballicora, CCC, December 01, 2009
Gaviota EGTBs, interface proposal for programmers by Miguel A. Ballicora, CCC, December 13, 2009
Gaviota Tablebases vs. Nalimov by Greg Simpson, CCC, December 24, 2009
Gaviota TBs, compression schemes by Miguel A. Ballicora, CCC, December 30, 2009

2010 ...

Gaviota TBs, compressor available (win32 for now) by Miguel A. Ballicora, CCC, January 04, 2010
Gaviota tablebases, probing code license by Miguel A. Ballicora, CCC, February 10, 2010
Gaviota tablebases, Probing Code Release (Finally) by Miguel A. Ballicora, CCC, February 10, 2010
Gaviota Tablebases Probing Code (v0.1.2) UPDATE by Miguel A. Ballicora, CCC, February 15, 2010
Gaviota TBs [0.1.6.1], bitbase-like interface by Miguel A. Ballicora, CCC, February 22, 2010
Gaviota TBs Probing Code (v0.2) UPDATE, Bitbases on the fly by Miguel A. Ballicora, CCC, March 20, 2010
Gaviota Tablebases and Delphi by Miguel A. Ballicora, CCC, March 28, 2010
libgaviota? by Michel Van den Bergh, CCC, April 11, 2010
Gaviota tablebases probing code (v0.2.2) small update by Miguel A. Ballicora, CCC, April 21, 2010
Gaviota tablebases probing code (v0.3) UPDATE by Miguel A. Ballicora, CCC, June 04, 2010
About Gaviota Tablebases License by Miguel A. Ballicora, CCC, June 26, 2010
Chessbase GUI & Critter + Gaviota tablebases by Richard Vida, CCC, December 01, 2010 » Critter
Gaviota EGTB in Houdini 1.5 + contacting Eugene Nalimov by Robert Houdart, CCC, December 01, 2010
Gaviota EGTBs: How long to generate 5-men TBs? by Joerg Oster, CCC, December 05, 2010
Gaviota tablebases, probing code v0.3.2 (UPDATE) by Miguel A. Ballicora, CCC, December 28, 2010

2011

For Miguel B: Gaviota tb_availability() sometimes incorrect by Robert Houdart, CCC, January 14, 2011 » Houdini
Houdini and Gaviota Tablebases by Edwin Meiners, CCC, January 16, 2011
Gaviota tablebases, probing code v4 (UPDATE) by Miguel A. Ballicora, CCC, March 11, 2011
Gaviota table bases in Scid? by Michel Van den Bergh, CCC, August 30, 2011 » Scid

2012

Gaviota access in Critter 1.4 by Jouni Uski, CCC, January 12, 2012 » Critter
Gaviota tablebases - how many files? - how big? by Marek Soszynski, CCC, June 27, 2012

2013

6-men Gaviota (Question to Miguel) by Harun Taner, CCC, December 27, 2013

2014

En passant problem in gaviota tablebases by Peter Österlund, CCC, July 02, 2014 » En passant

2015 ...

How texel probes endgame tablebases by Peter Österlund, CCC, July 16, 2016 » Syzygy Bases, Texel
Probing tablebases in python-chess by Robert Pope, CCC, March 20, 2017 » python-chess
Gaviota TB download link by Sven Schüle, CCC, April 21, 2018

External Links

References

What links here?

Page	Date Edited
Arena	Mar 16, 2018
Bagatur	Sep 10, 2016
Chess for Android	Mar 1, 2018
ChessGUI	Jan 17, 2018
Cinnamon	Sep 23, 2017
Coiled	Mar 12, 2017
Critter	Jan 25, 2014
DayDreamer	Aug 22, 2016
DroidFish	Jan 17, 2017
Edwards' Tablebases	Sep 26, 2016
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Gaviota	Jan 21, 2018
Gaviota Tablebases	Apr 22, 2018
JikChess	Nov 29, 2015
KnockOut	Sep 20, 2016
Lomonosov Tablebases	May 20, 2016
Miguel A. Ballicora	Jun 19, 2017
Nalimov Tablebases	Dec 23, 2016
Pawny	Jun 17, 2015
Peter Österlund	Aug 24, 2017
python-chess	Nov 4, 2017
Robert Pope	Jun 10, 2017
Scorpio Bitbases	Mar 12, 2018
Sidonia	May 19, 2016
Syzygy Bases	Apr 19, 2018
Texel	Oct 9, 2017

Up one level

Interior Node Recognizer

GerdIsenberg — Mon, 12 Mar 2018 19:17:07 GMT

Home * Knowledge * Interior Node Recognizer

		Interior Node recognizers are evaluation like functions called from within a node in order to avoid unnecessary searches if perfect knowledge is available, either to prune or narrow the bounds at interior nodes. Most of the time result replacing search is obtained from endgame tablebases, generated by retrograde analysis, but this may well be replaced by code detecting certain characteristics of the position. A trivial example of such a heuristic (restricted to detecting draws) may be found on a page devoted to KPK endings. Other examples are positions with known draws, such as lone K vs lone K, K+B vs K or K+N vs K. Implementation of this technique requires a legality check (even in the most basic example, claiming draw when there are only kings on the board, a buggy code may encourage going into this ending by the means of the illegal capture) or a legal move generator. In general, if a recognizer is based on a remaining material, special care must be taken to avoid the possibility of a stalemate and whether hanging pieces may be captured - for instance if the lonesome king in KBNK may capture either the bishop or knight. Score obtained from interior node recognizers may be treated as if it came from the probe of a transposition table, so they ought to be called near to it. In order to make recognizer results compatible with the results of probes from the transposition tables, they are composed from bound and score information.
M. C. Escher, Circle Limit IV, 1960 ^[1]

Score Type

Exact Score
Lower Bound
Upper Bound
Fail Bound for unsuccessful recognition

Publications

David Slate (1984). Interior-node Score Bounds in a Brute-force Chess Program. ICCA Journal, Vol. 7, No. 4
Ernst A. Heinz (1998). Efficient Interior-Node Recognition. ICCA Journal, Vol. 21, No. 3

Forum Posts

Help Finding X by Mark Lefler, CCC, June 08, 2007
Best was to Recognize Know Endgames? by Steve Maughan, CCC, August 03, 2013
Re: Best was to Recognize Know Endgames? by Harm Geert Muller, CCC, August 03, 2013 » KBNK Endgame

References

^ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website

What links here?

Page	Date Edited
Blockage Detection	Oct 19, 2017
Bobcat	Jun 27, 2017
Coiled	Mar 12, 2017
DarkThought	Jul 3, 2018
Djinn	Feb 8, 2016
Draw	Apr 14, 2018
Draw Evaluation	Mar 12, 2018
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Ernst A. Heinz	Mar 6, 2017
Fischerle	Aug 21, 2017
Fortress	Feb 1, 2018
Gibbon	Dec 23, 2014
Interior Node	Aug 6, 2012
Interior Node Recognizer	Mar 12, 2018
KBNK Endgame	Nov 26, 2016
Knowledge	Jul 22, 2017
KPK	May 12, 2016
KRK	Nov 26, 2016
Leon Piasetski	Nov 13, 2014
Mate Search	Oct 22, 2016
Material	Mar 31, 2018
Material Hash Table	Apr 3, 2014
Monsoon	Feb 8, 2015
Mop-up Evaluation	Nov 26, 2016
Nuchess	Apr 3, 2017
Oracle	Sep 4, 2016
Pattern Recognition	Sep 8, 2017
Robocide	May 11, 2016
Score	Apr 14, 2018
Space-Time Tradeoff	Jun 17, 2015
Stalemate	Feb 21, 2018
Terminal Node	Nov 17, 2012
Transposition Table	Apr 19, 2018
Typhoon	Apr 18, 2016
Witz	Nov 14, 2017

Up one Level

Knowledge

GerdIsenberg — Sat, 22 Jul 2017 18:04:38 GMT

Home * Knowledge

		Knowledge is the possession of information, its acquisition involves complex cognitive processes: perception, learning, communication, association and reasoning. Inside a chess program, knowledge is manifested either as procedural or as declarative knowledge. The declarative a priori knowledge about the rules of chess is immanent inside the move generator in conjunction with check detection. Further declarative knowledge is coded as rules of thumb of the evaluation function, as well as persistent perfect knowledge from retrograde analysis, or as empirical knowledge mostly from human experience, to retrieve moves from an hand crafted opening book. Procedural knowledge is applied by Learning, as well to backup declarative knowledge by Search. However, the Search versus Knowledge trade-off in computer chess and games refers heuristic or perfect knowledge.
Samuel Bak - Knowledgeable ^[1]

Search versus Knowledge

The trade-offs of search versus knowledge ^[2]

Curves A and B represent a fixed performance level, say 2000 for B and 2200 for A. The curves indicate that there are many ways to archive that level of performance, either by little knowledge and lot of search, or vice versa. If a program has archived point P on curve B, it may improve between search only (point S) or knowledge only (point K).

In Practice

Andreas Junghanns and Jonathan Schaeffer in Search versus knowledge in game-playing programs revisited ^[3]:

The difficulty lies in quantifying the knowledge axis. Perfect knowledge assumes an oracle, which for most games we do not have. However, we can approximate an oracle by using a high-quality, game playing program that performs deep searches. Although not perfect, it is the best approximation available. Using this, how can we measure the quality of knowledge in the program?

A heuristic evaluation function, as judged by an oracle, can be viewed as a combination of two things: oracle knowledge and noise. The oracle knowledge is beneficial and improves the program' s play. The noise, on the other hand, represents the inaccuracies in the program' s knowledge. It can be introduced by several things, including knowledge that is missing, over- or under-valued, and/or irrelevant. As the noise level increase, the beneficial contribution of the knowledge is overshadowed.

By definition, an oracle has no noise. We can measure the quality of the heuristic evaluation in a program by the amount of noise that is added into it. To measure this, we add a random number to each leaf node evaluation ...

HiTech versus LoTech

At the Advances in Computer Chess 5 conference 1987, Hans Berliner et al. introduced an interesting experiment. HiTech with a sophisticated evaluation competed versus LoTech, almost the same program but a rudimentary evaluation, at different search depths ^[4]. According to Peter Kouwenhoven ^[5], Berliner's conclusion was that more was to be won by increasing HiTech's knowledge at constant speed rather than further increasing its speed while keeping knowledge constant. The abstract from the extended 1990 paper ^[6]:

Chess programs can differ in depth of search or in the evaluation function applied to leaf nodes or both. Over the past 10 years, the notion that the principal way to strengthen a chess program is to improve its depth of search has held sway. Improving depth of search undoubtedly does improve a program's strength. However, projections of potential gain have time and again been found to overestimate the actual gain.

We examine the notion that it is possible to project the playing strength of chess programs by having different versions of the same program (differing only in depth of search) play each other. Our data indicates that once a depth of “tactical sufficiency” is reached, a knowledgeable program can beat a significantly less knowledgeable one almost all of the time when both are searching to the same depth. This suggests that once a certain knowledge gap has been opened up, it cannot be overcome by small increments in searching depth. The conclusion from this work is that extending the depth of search without increasing the present level of knowledge will not in any foreseeable time lead to World Championship level chess. The approach of increasing knowledge has been taken in the HiTech chess machine.

Ed Schröder's Conclusion

Ed Schröder concluded HiTech's extra knowledge was just worth one ply in the computer-computer area ^[7]^[8], and further elaborated on tactical evaluation knowledge helpful in early Rebel searching 5-7 plies versus Rebel searching 13-15 plies on 2001 hardware ^[9] ^[10]:

Some specific chess knowledge through the years become out-dated due to the speed of nowadays computers. An example: In the early days of computer chess, say the period 1985-1989 I as hardware had a 6502 running at 5 Mhz. Rebel at that time could only search 5-7 plies on tournament time control. Such a low depth guarantees you one thing: horizon effects all over, thus losing the game.

To escape from the horizon effect all kind of tricks were invented, chess knowledge about dangerous pins, knight forks, double attacks, overloading of pieces and reward those aspects in eval. Complicated and processor time consuming software it was (15-20% less performance) but it did the trick escaping from the horizon effect in a reasonable way.

Today we run chess program on 1500 Mhz machines and instead of the 5-7 plies Rebel now gets 13-15 plies in the middle game and the horizon effect which was a major problem at 5 Mhz slowly was fading away.

So I wondered, what if I throw that complicated "anti-horizon" code out of Rebel, is it still needed? So I tried and found out that Rebel played as good with the "anti-horizon" code as without the code. In other words, the net gain was a "free" speed gain of 15-20%, thus an improvement.

One aspect of chess programming is that your program is in a constant state of change due to the state of art of nowadays available hardware. I am sure a Rebel at 10 Ghz several parts of Rebel need a face-lift to get the maximum out of the new speed monster.

Search versus Evaluation

Mark Uniacke in a reply to Ed Schröder, on Search or Evaluation, mentioning the 1st Computer Olympiad, Null Move Pruning, Hiarcs, Woodpusher, E6P, Rebel, Fritz ... ^[11]:

I am not saying search is the only reason but that search is more significant in the Elo jump than other factors. Thanks for the interesting history which in general I agree with but I should add for clarification... In 1989 I was exposed to the null move in HIARCS' first official computer tournament at the Olympiad in London. John Hamlen had written his program Woodpusher as part of his M.Sc project investigating the null move exclamation and although Woodpusher did not do well in that tournament I had the good fortune to discuss null move with John and reading his project which interested me very much. John and I had many discussions on computer chess over the following months. That Olympiad probably had an impact on you too and not only because Rebel won Gold above Mephisto X and Fidelity X for the first time but because there was a program there running quite fast (at that time in history) called E6P (so named because it could reach 6 ply full width!) running on an Acorn ARM based machine. Jan was operating Rebel at the tournament as you know and I noticed Jan take a keen interest in this new machine. Frans was using null move in Fritz 2 in Madrid 1992 (I am not sure about Fritz 1). I am sure you remember that tournament fondly. I remember at Madrid having a discussion with a few programmers including Richard about what on earth was Fritz 2 doing to reach the depths it was attaining, this seed of interest made me investigate search enhancements carefully after Madrid and it was then that I began re-investigating the null move. It was not long before HIARCS began using null moves too and by Christmas 1992 I had a working implementation which gave a big jump over Hiarcs 1 which had only been released shortly before. I had much fun playing my Hiarcs 1.n against Mephisto Risc 1 in late 1992, early 1993 and that sort of closes the circle on the E6P story. Even so, the null move idea still evolved and my implementation today is much better than it was initially and so it can be for other ideas. We can all profit from these techniques but some gain more than others if they find new ways to exploit it. Rebel 7/8/9 and Hiarcs 5/6/7 battled hard in those years and my big jump to the top of the rating lists happened partly because of a search change to Hiarcs 5/6 which led at one stage to a 71 Elo lead on the SSDF. I recall Rebel and Hiarcs exchanging the lead on the SSDF list a number of times in those years. So we agree the impact search has made on computer chess progress is clear. Now we diverge on what might be the reason for new progress in the field. Clearly we have good search enhancements on cut nodes and all nodes, but that does not mean they cannot be improved and enhanced or in fact that another technique might prove to be superior or complementary. Meanwhile there can be no doubt that progress is made positionally irrespective of search but I do not believe it can be the reason for a breakthrough jump in chess strength but rather a steady climb. But wait! Maybe there is a middle way, a third avenue of improvement which sort of falls between the two pillars of search and evaluation and that is search intelligence. Something both of us have practiced in our programs for years but maybe not properly exploited. The ability of the eval to have a more significant impact on the search than traditionally has been the case. I think this area has been relatively unexplored and offers interesting potential.

Knowing

Declarative Knowledge

A Priori

Heuristic Knowledge

Empirical Knowledge

Perfect Knowledge

Perfect Knowledge usually incorporates analysis or stored results from exhaustive search, which requires no further search at interior nodes except the root. An oracle might be considered as "perfect" evaluation.

Interior Node Recognizer

Interior Node Recognizer

Endgame Databases

as probed inside a Recognizer framework, if a certain material constellation is detected.

Procedural Knowledge

Publications

1970 ...

Marvin Minsky (1974). Framework for Representing Knowledge 1974. MIT-AI Laboratory Memo 306
Coen Zuidema (1974). Chess: How to Program the Exceptions? Technical Report IW21/74, Mathematical Center Amdsterdam. pdf

1975 ...

Donald Michie (1976). An Advice-Taking System for Computer Chess. Computer Bulletin, Ser. 2, Vol. 10, pp. 12-14. ISSN 0010-4531.
Jack Good (1977). Dynamic Probability, Computer Chess, and the Measurement of Knowledge. Machine Intelligence, Vol. 8 (eds. E. Elcock and Donald Michie), pp. 139-150. Ellis Horwood, Chichester.
Ivan Bratko, Danny Kopec, Donald Michie (1978). Pattern-Based Representation of Chess Endgame Knowledge. The Computer Journal, Vol. 21, No. 2, pp. 149-153. pdf
Donald Michie, Ivan Bratko (1978). Advice Table Representations of Chess End-Game Knowledge. Proceedings 3rd AISB/GI Conference, pp. 194-200.
David Wilkins (1979). Using Patterns and Plans to Solve Problems and Control Search. Ph.D. thesis, Computer Science Dept, Stanford University, AI Lab Memo AIM-329
Max Bramer, Mike Clarke (1979). A Model for the Representation of Pattern-Knowledge for the Endgame in Chess. International Journal of Man-Machine Studies, Vol. 11, No.5

1980 ...

Ivan Bratko, Donald Michie (1980). A Representation of Pattern-Knowledge in Chess Endgames. Advances in Computer Chess 2
David Wilkins (1980). Using patterns and plans in chess. Artificial Intelligence, vol. 14, pp. 165-203. Reprinted (1988) in Computer Chess Compendium
David Wilkins (1982). Using Knowledge to Control Tree Searching. Artificial Intelligence, vol. 18, pp. 1-51.
Alen Shapiro, Tim Niblett (1982). Automatic Induction of Classification Rules for Chess End game. Advances in Computer Chess 3
Hans Berliner (1982). Search vs. knowledge: an analysis from the domain of games. Technical Report Department of Computer Science, Carnegie Mellon University
Allen Newell (1982). The Knowledge Level. Artificial Intelligence, Vol. 18, No. 1
Raymond Smullyan (1982). An Epistemological Nightmare. MIT
David Wilkins (1983). Using chess knowledge to reduce search. In Chess Skill in Man and Machine (Peter W. Frey, ed.), Ch. 10, 2nd Edition, Springer-Verlag.
Danny Kopec (1983). Human and Machine Representations of Knowledge. Ph.D. thesis, University of Edinburgh, supervisor: Donald Michie
Alen Shapiro (1983). The Role of Structured Induction in Expert Systems. University of Edinburgh, Machine Intelligence Research Unit (Ph.D. thesis) ^[12]
Jonathan Schaeffer (1984). The Relative Importance of Knowledge. ICCA Journal, Vol. 7, No. 3
Albrecht Heeffer (1984). Automated Acquisition on Concepts for the Description of Middle-game Positions in Chess. Turing Institute, Glasgow, Scotland, TIRM-84-005

1985 ...

Albrecht Heeffer (1985). Validating Concepts from Automated Acquisition Systems. IJCAI 85, pdf
Reiner Seidel (1985). Grammatical Description of Chess Positions, Data-Base versus Human Knowledge. ICCA Journal, Vol. 8, No. 3
Jonathan Schaeffer, Tony Marsland (1985). The Utility of Expert Knowledge. Proceedings IJCAI 85, pp. 585-587. Los Angeles.
Alen Shapiro, Donald Michie (1986). A Self-commenting Facility for Inductively Synthesised Endgame Expertise. Advances in Computer Chess 4
Bernd Owsnicki, Kai von Luck (1986). N.N.: A Case Study in Chess Knowledge Representation. Advances in Computer Chess 4
Jonathan Schaeffer (1986). Experiments in Search and Knowledge. Ph.D. Thesis, University of Waterloo. Reprinted as Technical Report TR 86-12, Department of Computing Science, University of Alberta, Edmonton, Alberta.
Peter W. Frey (1986). Fuzzy Production Rules in Chess. ICCA Journal, Vol. 9, No. 4
Peter W. Frey (1986). A Bit-Mapped Classifier. BYTE, Vol. 11, No. 12, pp. 161-172.
Subhash Kak (1987). Patanjali and Cognitive Science. Vitasta Publishing ^[13]
Alen Shapiro (1987). Structured Induction in Expert Systems. Turing Institute Press in association with Addison-Wesley Publishing Company, Workingham, UK. ISBN 0-201-178133. amazon^[14]
Stephen Muggleton (1988). Inductive Acquisition of Chess Strategies. Machine Intelligence 11 (eds. Jean Hayes Michie, Donald Michie, and J. Richards), pp. 375-389. Clarendon Press, Oxford, U.K. ISBN 0-19-853718-2.
Reiner Seidel(1989). A Model of Chess Knowledge - Planning Structures and Constituent Analysis. Advances in Computer Chess 5
Hans Berliner, Carl Ebeling (1989). Pattern Knowledge and Search: The SUPREM Architecture. Artificial Intelligence, Vol. 38, No. 2, pp. 161-198. ISSN 0004-3702.
Revised as Hans Berliner, Carl Ebeling (1990). Hitech. Computers, Chess, and Cognition
Hans Berliner, Gordon Goetsch, Murray Campbell, Carl Ebeling (1989). Measuring the Performance Potential of Chess Programs, Advances in Computer Chess 5
Hermann Kaindl (1989). Towards a Theory of Knowledge. Advances in Computer Chess 5

1990 ...

Hans Berliner, Gordon Goetsch, Murray Campbell, Carl Ebeling (1990). Measuring the Performance Potential of Chess Programs. Artificial Intelligence, Vol. 43, No. 1
Kiyoshi Shirayanagi (1990). Knowledge Representation and its Refinement in Go Programs. Computers, Chess, and Cognition
Robert Levinson, Feng-hsiung Hsu, Tony Marsland, Jonathan Schaeffer, David Wilkins (1991). The Role of Chess in Artificial Intelligence Research. IJCAI 1991, pdf, also in ICCA Journal, Vol. 14, No. 3, pdf
Christian Posthoff, Michael Schlosser, Jens Zeidler (1993). Search vs. Knowledge? - Search and Knowledge! In: Proc. 3rd KADS Meeting, Munich, March 8-9 1993, Siemens AG, Corporate Research and Development, 305-326, 1993.
Steven Walczak, Douglas D. Dankel II (1993). Acquiring Tactical and Strategic Knowledge with a Generalized Method for Chunking of Game Pieces. International Journal of Intelligent Systems 8 (2), 249-270.
Christian Posthoff, Michael Schlosser, Rainer Staudte, Jens Zeidler (1994). Transformations of Knowledge. Advances in Computer Chess 7
Robert Levinson, Gil Fuchs (1994). A Pattern-Weight Formulation of Search Knowledge. UCSC-CRL-94-10, CiteSeerX

1995 ...

Richard Fikes (1996). Ontologies: What Are They, and Where's The Research? KR 1996
Andreas Junghanns, Jonathan Schaeffer (1997). Search versus knowledge in game-playing programs revisited. IJCAI-97, Vol 1, pdf
Johannes Fürnkranz (1997). Knowledge Discovery in Chess Databases: A Research Proposal. Technical Report OEFAI-TR-97-33, Austrian Research Institute for Artificial Intelligence, zipped ps, pdf ^[15]
Krzysztof Krawiec, Roman Slowinski, Irmina Szczesniak (1998). Pedagogical Method for Extraction of Symbolic Knowledge from Neural Networks. Rough Sets and Current Trends in Computing 1998
Edward J. Quigley, Anthony Debons (1999). Interrogative Theory of Information and Knowledge. SIGCPR '99, pdf

2000 ...

Michael Thielscher (2000). Representing the Knowledge of a Robot. KR 2000, CiteSeerX
Krzysztof Krawiec (2002). Genetic Programming-based Construction of Features for Machine Learning and Knowledge Discovery Tasks. Genetic Programming and Evolvable Machines, Vol. 3, No. 4
Stuart Russell, Peter Norvig (2003). Artificial Intelligence: A Modern Approach, 2nd edition, 3rd edition 2009
Stuart Russell (2003). Rationality and Intelligence. In Renee Elio (Ed.), Common sense, reasoning, and rationality, Oxford University Press, pdf
Aleksander Sadikov, Ivan Bratko, Igor Kononenko (2003). Search versus Knowledge: An Empirical Study of Minimax on KRK. Advances in Computer Games 10, pdf
Tristan Caulfield (2004). Acquiring and Using Knowledge in Computer Chess. BSc Computer Science, University of Bath, pdf
Elias M. Awad, Hassan M. Ghaziri (2004,2010). Knowledge Management Systems. Pearson Education India, Knowledge Management Systems - Lecture Notes, LaTeX2HTML by Nikos Drakos, Ross Moore
Nick Pelling (2004). The Network Is The Knowledge: Ideology & Strategy in Mintzberg's Ten Schools. MBA dissertation, Kingston University Business School, Surrey, UK

2005 ...

Christian Posthoff, Michael Schlosser (2005). Optimal strategies — Learning from examples — Boolean equations. in Klaus P. Jantke, Steffen Lange (eds.) (2005). Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Computer Science 961, Springer
Aleksander Sadikov, Ivan Bratko (2006). Search Versus Knowledge Revisited Again. CG 2006
David J. Stracuzzi (2006). Scalable Knowledge Acquisition through Cumulative Learning and Memory Organization. Ph.D. thesis, University of Massachusetts Amherst, advisor Paul E. Utgoff, pdf
Guillaume Chaslot, Louis Chatriot, Christophe Fiter, Sylvain Gelly, Jean-Baptiste Hoock, Julien Pérez, Arpad Rimmel, Olivier Teytaud (2008). Combining expert, offline, transient and online knowledge in Monte-Carlo exploration. pdf
Guillaume Chaslot, Christophe Fiter, Jean-Baptiste Hoock, Arpad Rimmel, Olivier Teytaud (2009). Adding Expert Knowledge and Exploration in Monte-Carlo Tree Search. Advances in Computer Games 12, pdf, pdf

2010 ...

Matej Guid (2010). Search and Knowledge for Human and Machine Problem Solving, Ph.D. thesis, University of Ljubljana, pdf ^[16]
Shi-Jim Yen, Jung-Kuei Yang, Kuo-Yuan Kao, Tai-Ning Yang (2012). Bitboard Knowledge Base System and Elegant Search Architectures for Connect6. Knowledge-Based Systems, Vol. 34
Bo-Nian Chen, Hung-Jui Chang, Shun-Chin Hsu, Jr-Chang Chen, Tsan-sheng Hsu (2013). Multilevel Inference in Chinese Chess Endgame Knowledge Bases. ICGA Journal, Vol. 36, No. 4 » Chinese Chess, Endgame Tablebases
Bo-Nian Chen, Hung-Jui Chang, Shun-Chin Hsu, Jr-Chang Chen, Tsan-sheng Hsu (2014). Advanced Meta-knowledge for Chinese Chess Endgame Knowledge Bases. ICGA Journal, Vol 37, No. 1

2015 ...

Tamal T. Biswas, Kenneth W. Regan (2015). Quantifying Depth and Complexity of Thinking and Knowledge. ICAART 2015, pdf

Forum Posts

1996 ...

Incoporating chess knowledge in chess programs by Valavan Manohararajah, rgcc, June 26, 1996
computer chess "oracle" ideas... by Robert Hyatt, rgcc, April 1, 1997 » Oracle
Knowledge is not elegant by Don Dailey, CCC, June 14, 1998
The end of computer chess progress? by Ed Schröder, rgcc, March 06, 1999
The Limits of Positional Knowledge by Michael Neish from CCC, November 11, 1999

2000 ...

suggestions for (a new generation of) chess knowledge using engines by Ingo Lindam, CCC, October 23, 2002
likelihood instead of pawnunits? + chess knowledge by Ingo Lindam, CCC, October 25, 2002
Knowledge by Sergei S. Markoff, CCC, September 26, 2004

2005 ...

The superior Rybka chess knowledge by Chrilly Donninger, CCC, January 18, 2006 » Rybka
knowledge and blitz; search and long games by Joseph Ciarrochi, CCC, February 15, 2006
Search or Evaluation? by Ed Schröder, Hiarcs Forum, October 05, 2007 » Search, Evaluation
Re: Search or Evaluation? by Mark Uniacke, Hiarcs Forum, October 14, 2007

2010 ...

hardware advances - a different perspective by Robert Hyatt, CCC, September 09, 2010
old crafty vs new crafty on new hardware by Robert Hyatt, CCC, September 11, 2010 » Crafty
Crafty tests show that Software has advanced more by Don Dailey, CCC, September 12, 2010
Final results - Crafty - hardware vs software by Robert Hyatt, CCC, September 13, 2010 » Crafty
Deep Blue vs Rybka by Don Dailey, CCC, September 13, 2010 » Deep Blue, Rybka
hardware doubling number for Crafty by Robert Hyatt, CCC, September 15, 2010 » Crafty
Ahhh... the holy grail of computer chess by Marcel van Kervinck, CCC, August 23, 2011
Is search irrelevant when computing ahead of very big trees? by Fermin Serrano, CCC, July 24, 2013 » Search
Improve the search or the evaluation? by Jens Bæk Nielsen, CCC, August 31, 2013 » Search versus Evaluation
Slow Searchers? by Michael Neish, CCC, November 02, 2013
Chessprogams with the most chessknowing by Joe Boden, CCC, December 19, 2014

2015 ...

An attempt to measure the knowledge of engines by Kai Laskos, CCC, March 23, 2015
Re: Chessprogams with the most chessknowing by Vincent Lejeune, CCC, February 18, 2017
Re: Chessprogams with the most chessknowing by Alvaro Cardoso, CCC, February 18, 2017
Re: Chessprogams with the most chessknowing by Mark Lefler, CCC, February 18, 2017 » Komodo
Re: Chessprogams with the most chessknowing by Marco Costalba, CCC, February 19, 2017 » Stockfish

External Links

Knowledge

Types of Knowledge

Musicvideo

Mahavishnu Orchestra - You Know You Know, August 17, 1972, more recent 3Sat broadcast ^[17], YouTube Video
John McLaughlin, Billy Cobham, Rick Laird, Jan Hammer, Jerry Goodman

References

^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ Jonathan Schaeffer (1997). One Jump Ahead Challenging Human Supremacy in Checkers, Springer, ISBN 0-387-94930-5, Prelude to Disaster, pp. 255-256 or pp. 249-250 in the Second Edition, 2009
^ Andreas Junghanns, Jonathan Schaeffer (1997). Search versus knowledge in game-playing programs revisited. IJCAI-97, Vol 1, pdf, 3 Search Versus Knowledge: Practise
^ Hans Berliner, Gordon Goetsch, Murray Campbell, Carl Ebeling (1989). Measuring the Performance Potential of Chess Programs, Advances in Computer Chess 5
^ Peter Kouwenhoven (1987). Advances in Computer Chess, The 5th Triennial Conference. ICCA Journal, Vol. 10, No. 2 (report)
^ Hans Berliner, Gordon Goetsch, Murray Campbell, Carl Ebeling (1990). Measuring the Performance Potential of Chess Programs. Artificial Intelligence, Vol. 43, No. 1
^ Chess in 2010 by Ed Schröder, The Berliner Experiment
^ The end of computer chess progress? by Ed Schröder, rgcc, March 06, 1999
^ Re: Intelligent software, please by Ed Schröder, CCC, November 26, 2001
^ Schröder, Ed (German) from Schachcomputer.info - Wiki also refers the post by Ed Schröder
^ Re: Search or Evaluation? by Mark Uniacke, Hiarcs Forum, October 14, 2007
^ UCI Machine Learning Repository: Chess (King-Rook vs. King-Pawn) Data Set
^ Patanjali from Wikipedia
^ Dap Hartmann (1988). Alen D. Shapiro: Structured Induction in Expert Systems. ICCA Journal, Vol. 11, No. 4
^ Knowledge discovery from Wikipedia
^ Dap Hartmann (2010). How can Humans learn from Computers? Review on Matej Guid's Ph.D. thesis, ICGA Journal, Vol. 33, No. 4
^ Original ZDF broadcast "Sonntagskonzert", September 17, 1972, recorded at Kongresshalle Deutschen Museum, Munich, "Jazz Now", August 17, 1972, curator Joachim-Ernst Berendt, see The Mahavishnu Orchestra On Film, MUENCHEN-72_KPL.pdf, Diese Woche im Fernsehen, Der Spiegel 38/1972 (German), 1972 Summer Olympics

What links here?

Page	Date Edited
1st Computer Olympiad	Jul 25, 2017
ABK	Feb 1, 2017
Alexander Szabo	Nov 10, 2012
Applied Concepts	Dec 25, 2017
Artificial Intelligence	Apr 9, 2018
Automated Tuning	Feb 27, 2018
Awit	Dec 22, 2017
Bart Selman	Dec 26, 2017
Bernd Owsnicki-Klewe	Jan 20, 2018
Bo-Nian Chen	Jul 17, 2017
Bookbuilder	Feb 4, 2018
Bookup	Feb 4, 2018
Bs6676	Jul 21, 2016
CAPS	Dec 23, 2017
Chess	Jan 21, 2018
Chess Psychology Booklist	Apr 11, 2013
CHREST	May 6, 2016
Chunker	Jul 12, 2016
Chunking	Jun 12, 2017
Coen Zuidema	Mar 25, 2016
Cognition	Dec 8, 2017
Comet	Jan 8, 2016
Constellation	Oct 2, 2016
CTG	Aug 22, 2016
Cyrus	Jul 22, 2014
Data	Nov 26, 2017
David Wilkins	Mar 2, 2016
Depth	Feb 25, 2018
Diep	Jan 28, 2018
Dietmar Lippold	Mar 22, 2014
Distance	Sep 25, 2015
E6P	Dec 17, 2016
ECO	Nov 2, 2017
Edwards' Tablebases	Sep 26, 2016
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
EPAM	Jul 15, 2017
Eric Postma	May 26, 2015
Ernst A. Heinz	Mar 6, 2017
Eval Tuning in Deep Thought	Jun 7, 2016
Evaluation	Feb 1, 2018
Evaluation Patterns	Jun 24, 2013
Evaluation Philosophy	Sep 29, 2014
Eye Movements	Jul 22, 2015
Fermin Serrano	Nov 27, 2015
FinalGen	Aug 14, 2016
Floyd	Sep 11, 2016
Fortress	Feb 1, 2018
Francesca	Jan 7, 2016
Freezer	Aug 14, 2016
Fritz	Feb 26, 2018
GAFS	Aug 14, 2016
Gandalf	Jan 21, 2018
Gaviota Tablebases	Apr 22, 2018
Gian Piero Favini	Jan 4, 2017
Gil Fuchs	Sep 22, 2015
Goliath	Apr 5, 2017
Grit Lachmann	Apr 26, 2014
Guard Heuristic	Nov 18, 2015
Hannibal	Oct 4, 2017
Hardware	Jan 20, 2018
Hartmut Tanke	Sep 7, 2014
Hash Table	Jan 1, 2018
Hiarcs	Feb 25, 2018
HiTech	Mar 31, 2018
Home	Jul 2, 2018
Interior Node Recognizer	Mar 12, 2018
Ivan Bratko	Aug 16, 2017
J. Howard Johnson	May 23, 2016
Jens Bæk Nielsen	Mar 3, 2015
Johannes Fürnkranz	Feb 26, 2018
Kai von Luck	Jan 20, 2018
Knowledge	Jul 22, 2017
Komodo	Mar 6, 2018
KRK	Nov 26, 2016
LCZero	Apr 18, 2018
Learning	Feb 20, 2018
Lomonosov Tablebases	May 20, 2016
MAPP	Jan 30, 2016
Marco Costalba	Feb 28, 2018
Mark Uniacke	Dec 12, 2016
Marko Maliković	Aug 10, 2013
Martin Možina	Jun 11, 2016
Matjaž Gams	May 23, 2016
Max Bramer	May 20, 2014
Memory	Dec 8, 2017
Mephisto Roma	Sep 1, 2017
Michael Borgstädt	Jan 24, 2016
Michèle Sebag	May 23, 2016
Mobility	Jan 17, 2018
N.N.	Jan 20, 2018
Nalimov Tablebases	Dec 23, 2016
Neurologic	Jan 7, 2016
NIC-Key	Jul 16, 2017
Nick Pelling	Dec 11, 2016
Nimzo	Dec 30, 2017
Nodes per second	Feb 28, 2018
Now	Jan 7, 2016
Null Move Pruning	Dec 2, 2017
Opening Book	Feb 26, 2018
Opponent Model Search	Aug 14, 2017
Oracle	Sep 4, 2016
Paradise	Nov 19, 2014
Pattern Recognition	Sep 8, 2017
PawnKing	Sep 5, 2014
Perceiver	Nov 21, 2017
Pieter Spronck	Jan 5, 2017
Planner	Sep 24, 2012
Planning	Feb 12, 2018
Playing Strength	Mar 31, 2018
PolyGlot	Jan 17, 2018
Prodigy	Jan 19, 2018
Psion	Mar 20, 2017
Psychology	Sep 20, 2016
Rebel	Feb 25, 2018
RetroChess	Feb 2, 2014
Retrograde Analysis	Mar 21, 2017
Richard Lang	Jan 7, 2016
Richard Snyder	Sep 20, 2015
Robert Levinson	Aug 25, 2016
Ross Hayward	May 23, 2016
Santos Gerardo Lazzeri	Mar 19, 2016
Scorpio Bitbases	Mar 12, 2018
Search	Feb 1, 2018
Search with Random Leaf Values	Apr 23, 2018
SmarThink	Feb 2, 2018
Soei Tan	Oct 27, 2012
SOS	Apr 5, 2017
Space-Time Tradeoff	Jun 17, 2015
space.menu	Oct 9, 2015
Stavros Vassos	May 25, 2015
Stephan Schiffel	Jul 8, 2016
Stephen B. Streater	Dec 17, 2016
Steven Walczak	May 23, 2016
Stockfish	Apr 7, 2018
Strategy	Jan 18, 2018
Super Constellation	Oct 1, 2016
Syzygy Bases	Apr 19, 2018
Tactics	Jan 12, 2018
TechMate	Aug 23, 2014
Texel's Tuning Method	Dec 2, 2017
The Baron	Jan 8, 2018
Thompson's Databases	Dec 24, 2014
Tristan Caulfield	Dec 1, 2017
WCCC 1992	Feb 26, 2018
WChess	Jan 7, 2016
Woodpusher	Dec 12, 2016
Yace	Dec 31, 2017
Zeus	Jan 3, 2018

Up one Level

MAPP

GerdIsenberg — Sat, 30 Jan 2016 22:17:19 GMT

Schematic Representation

Home * Knowledge * Cognition * MAPP

MAPP, (Memory-aided Pattern Perceiver)
a program by Kevin J. Gilmartin and Herbert Simon to simulate the chess board reconstruction task examined by William Chase and Herbert Simon ^[1]. MAPP contains a learning component to acquire and store a large set of configurations of chess pieces and a performance component to carry out the the board reconstruction task. From Miller's chunking hypothesis ^[2], EPAM theory, and the limited capacity of short-term memory, one would predict that a chessboard can be reconstructed from information held in short-term memory if, and only if, it can be encoded in not more than about seven familiar perceptual chunks. If a single piece on a particular square constitutes a chunk for the subject, then it should be able to recall only about seven pieces. If it can recall the positions of more than twenty pieces, then it must be that each chunk consists, on average, of a configuration of about three pieces ^[3].

Schematic Representation

A schematic representation of the principle components of MAPP shows the learning and performance
processes used to reconstruct a chess position ^[4]

Perception

When a chess position is presented, a simplified version of the eye movement simulation program Perceiver is used to scan the board in order to notice the pieces and their relations. When a piece is fixated (salient piece), an EPAM-like discrimination process seeks to recognize cluster of pieces surrounding the fixated piece as a familar chunk. If it is successful, the symbol designating this chunk is stored in short-term memory. This process is repeated at successive points of fixation until no more pieces become salient or memory capacity is reached (no more than seven chunks).

Reconstruction

In the reconstruction phase, the EPAM net is used to decode the symbols held in short-term memory into locational information for each of the pieces in a chunk. In various experiments, MAPP was able to reconstruct positions with 73% accuracy ^[5] ^[6].

Publicatons

Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46, reprinted in Herbert Simon (1979). Models of Thought. Yale University Press
Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, reprinted in David Levy (ed.) (1988) Computer Chess Compendium, pdf
Neil Charness (1976). Memory for Chess Positions: Resistance to Interference. Journal of Experimental Psychology: Human Learning and Memory, Vol. 2, No. 6, pp. 641-653
Michael George, Jonathan Schaeffer (1990). Chunking for Experience. ICCA Journal, Vol. 13, No. 3, pdf
Fernand Gobet (2005). Chunking Models of Expertise: Implications for Education. Applied Cognitive Psychology, Vol. 19, No. 2

References

^ William Chase, Herbert Simon (1973). Perception in chess. Cognitive Psychology, Vol. 4, No. 1
^ George Armitage Miller (1956). The Magical Number Seven, Plus or Minus Two. Psychological Review, Vol. 101, No. 2, pdf
^ Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, pp. 401, reprinted in David Levy (ed.) (1988) Computer Chess Compendium, pdf
^ Expertise in Memory - Evidence for Chunking Theory by Victor Long, Chandra Singh and David Snitkof, Brown University, see also Figure 6 in Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, pp. 401, reprinted in David Levy (ed.) (1988) Computer Chess Compendium, pdf
^ Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46
^ Michael George, Jonathan Schaeffer (1990). Chunking for Experience. ICCA Journal, Vol. 13, No. 3, pdf

What links here?

Page	Date Edited
CHREST	May 6, 2016
Chump	Jan 31, 2016
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
Dictionary	Aug 24, 2017
EPAM	Jul 15, 2017
Eye Movements	Jul 22, 2015
Herbert Simon	Feb 11, 2016
Kevin J. Gilmartin	Jan 1, 2016
MAPP	Jan 30, 2016
Mater	Apr 26, 2016
Memory	Dec 8, 2017
Neil Charness	Oct 2, 2014
Perceiver	Nov 21, 2017

Up one Level

Nalimov Tablebases

GerdIsenberg — Fri, 23 Dec 2016 20:57:43 GMT

Home * Knowledge * Endgame Tablebases * Nalimov Tablebases

		Nalimov Tablebases, are 3-to-6-man endgame tablebases developed by Eugene Nalimov, providing depth to mate information. First published for up to 5-man in late 1998, 6-man files were released subsequently over the years and 6-man chess was finally solved in 2005 ^[1]. Nalimov Tablebases apply a more efficient indexing scheme than previous tablebases, and were further compressed into 8 KiB blocks exploiting common subsequences and Huffman coding as contributed by Andrew Kadatch, doing less file I/O which gets replaced by fast on-the-fly decompression ^[2]. This allows fast probing not only at the root, but during the search inside the tree ^[3], further utilized by an own LRU cache despite keeping TB files in the page cache by the operating system. For endgames with pawns of both sides, the TBs consider en passant with disjoint index ranges ^[4].
Huffman tree ^[5]

File Sizes

5-man Nalimov Tablebases are about two times smaller than Edwards' Tablebases when uncompressed, and about eight times smaller than Edwards' when compressed ^[6].

Men	Sum of File sizes
3	62	KiB
4	30	MiB
5	7.1	GiB
6	1.2	TiB

Savings

In CCC, Eugene Nalimov gave a brief summary, how to realize the space savings ^[7] :

For pawnless ending, one can restrict one piece to a1-d1-d4 triangle (that was done in SJE's generator). But if that piece happens to be on a1-d4 diagonal, one can restrict other piece to 'large' a1-h1-h8 triangle (exploit one more symmetry).
When one places a second piece on the board, one square is occupied already, so there are only 63 possible squares, for third - only 62, etc.
If there are two identical pieces (e.g. as in knnkp), one can order their locations - e.g. force second piece to occupy square with smaller number. Then one has not N*(N-1) total combinations, but N*(N-1)/2
Pawns occupy ranks 2-7. Even if one wants to handle en passant, there are better ways to do that than to reserve entire rank (or two) for possible en passant target
Kings never can be near each other, so there are only 3612 ways to place 2 kings on the empty board (not using symmetries), versus 4096 when using SJE's format
One cannot capture enemy's king, so, if one knows where it's located, there are some forbidden squares for the pieces of the side-to-move.

License

In the late 90s Nalimov Tablebases became defacto standard and were used in many commercial, private and free chess engines and GUI's. A reference implementation by Eugene Nalimov and Robert Hyatt was realized in Crafty, with Tablebases and probing code available from Bob Hyatt's site ^[8]. Probing could easily incorporated into own chess engines, however the license policy requires explicit permission by Eugene Nalimov.

Publications

Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2000). Space-Efficient Indexing of Chess Endgame Tables. ICGA Journal, Vol. 23, No. 3, postscript
Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2001). Space-efficient Indexing of Endgame Tables for Chess. Advances in Computer Games 9
Guy Haworth, Peter Karrer, John Tamplin, Christoph Wirth (2001). 3-5-man chess: Maximals and mzugs. ICGA Journal, Vol. 24, No. 4
Eugène Nalimov (2002). Chess Endgame Tablebases. Invited Lecture, 7th Computer Olympiad Workshop
Guy Haworth (2005). 6-Man Chess Solved. ICGA Journal, Vol. 28, No. 3

Forum Posts

1998 ...

Tablebases by Eugene Nalimov, CCC, August 28, 1998
Program for new TB by Dr. Eugene Nalimov ? by Michael Diosi, rgcc, November 6, 1998
Nalimov's TBs: one question by Jouni Uski, CCC, November 18, 1998
Re: Nalimov's TBs: one question by Eugene Nalimov, CCC, November 18, 1998
Q: Nalimov EGTB? by Dennis Breuker, CCC, August 05, 1999
Re: Q: Nalimov EGTB? by Eugene Nalimov, CCC, August 05, 1999
Nalimov TB caching ? by Ulrich Türke from CCC, August 06, 1999
EGTBs by Frank Phillips, CCC, September 03, 1999
difference betrween nalimov and thompson EGTB by Rajen Gupta, CCC, December 10, 1999
Re: difference betrween nalimov and thompson EGTB by Frederic Friedel, CCC, December 11, 1999

2000 ...

Nalimov-EGTBs in ANSI-C? by Heiner Marxen, CCC, January 21, 2000
Nalimov endgames by Jean-Christophe Weill, CCC, February 20, 2001
Nalimov's EGTBs (long post with code) by Heiner Marxen, CCC, October 13, 2001
Nalimov TB question by Bas Hamstra, CCC, November 11, 2001
Questions about the new Nalimov tablebase files... by Dann Corbit, CCC, December 12, 2002
Compressed Nalimov EGTBs by Leonardo Ljubicic, rgcc, November 18, 2003
Bug/glitch in Nalimov Code (and in Wilhelm)? by Dieter Bürssner, CCC, May 09, 2004
To Eugene Nalimov: Copyright of Tablebase files by Karl-Heinz Milaster, CCC, June 05, 2004
Are nalimov EGTB's a copyright from chessbase? by Vincent Diepeveen, CCC, June 07, 2004
Enpassant in Nalimov by Henry Hongdoyo, CCC, October 25, 2004

2005 ...

Subject: Problem (small bug?) with Nalimov TBs by Dieter Bürssner, CCC, January 23, 2005
For Eugene Nalimov: EGTB Request by Vasik Rajlich, CCC, December 16, 2005
smp and nalimov egtb, how to make it work? by Volker Böhm, CCC, February 23, 2006
Chessbase releases 9 dvds on Nalimov 6-piece database 43 gb by Daneil Johnson, CCC, February 23, 2006
Nalimov access with Vasik Rajlich, Rybka Forum, January 9, 2007
Nalimov Tablebases by Terry Giles, CCC, July 02, 2007
Nalimov EGTB by cyberfish, CCC, October 19, 2008
6-men (64 bit) Nalimov EGTB generator by Gian-Carlo Pascutto, CCC, September 13, 2009
Nalimov EGTB probes skeleton code by Joshua Shriver, CCC, December 17, 2009

2010 ...

Nalimov and memory for indexes (are you aware?) by Miguel A. Ballicora, CCC, March 01, 2010
Question for Nalimov experts by Mincho Georgiev, CCC, April 10, 2010
Gaviota EGTB in Houdini 1.5 + contacting Eugene Nalimov by Robert Houdart, CCC, December 01, 2010
Nalimov 6 men ... by Michael Diosi, CCC, January 12, 2013
Nalimov by Sune Larsson, CCC, May 22, 2013

2015 ...

Nalimov EGTB problem related to DTM? by Kai Laskos, CCC, February 14, 2016 » DTM
Re: Nalimov EGTB problem related to DTM? by Ronald de Man, CCC, February 14, 2016
Nalimov egtb probing code by Fabio Gobbato, CCC, May 16, 2016

External Links

General

Tablebases by Eugene Nalimov
Nalimov Tablebases from Arena Chess GUI
Eugene Nalimov: Winner of the ChessBase Award and Guest of Honor in Maastricht by Eric van Reem, ChessBase events, July 9, 2002 (archived)
Theoretical statistics for chess endgames with up to five pieces by Ulrich Thiel
Engines and endgame tablebases by Albert Silver, ChessBase News, December 12, 2013

Online Lookup

Download

Index of /hyatt/crafty/TB hosted by Robert Hyatt
Endgame Tablebases Online - 6-men endgame analysis free for everyone by Kirill Kryukov (3,4,5,6 pieces - via emule)
tablebase.sesse.net by Sesse

References

^ Guy Haworth (2005). 6-Man Chess Solved. ICGA Journal, Vol. 28, No. 3
^ Re: Compressed Nalimov EGTBs by Robert Hyatt, rgcc, November 18, 2003
^ Re: Q: Nalimov EGTB? by Eugene Nalimov, CCC, August 05, 1999
^ Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2001). Space-efficient Indexing of Endgame Tables for Chess. Advances in Computer Games 9, chapter 3. Nalimov’s Index Scheme
^ Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". The frequencies and codes of each character are below. Encoding the sentence with this code requires 135 bits, as opposed to 288 bits if 36 characters of 8 bits were used, Huffman coding from Wikipedia
^ Re: Q: Nalimov EGTB? by Eugene Nalimov, CCC, August 05, 1999
^ Re: Nalimov's TBs: one question by Eugene Nalimov, CCC, November 18, 1998
^ Index of /hyatt/crafty/TB hosted by Robert Hyatt

What links here?

Page	Date Edited
Alfil	Sep 3, 2015
Andrew Kadatch	Jun 3, 2017
Beowulf	May 5, 2017
BikJump	Aug 11, 2014
Chess Academy	Jan 15, 2014
Chess for Android	Mar 1, 2018
ChessBase (Database)	Feb 26, 2018
ChessBase Best-Publication Awards to Include	Jan 7, 2017
ChessOK	Jul 30, 2013
ChessPartner	Nov 13, 2017
Chest	Mar 3, 2015
Chispa	Feb 13, 2014
Crafty	Jan 28, 2018
DanChess	Jun 17, 2012
Delphil	Sep 17, 2016
Djinn	Feb 8, 2016
Dorky	Oct 10, 2016
Edwards' Tablebases	Sep 26, 2016
Eigenmann Endgame Test	Jun 1, 2017
Endgame Tablebases	Mar 6, 2018
Ernst A. Heinz	Mar 6, 2017
Eugene Nalimov	Dec 23, 2016
Firefly	Oct 23, 2017
Frank Phillips	Sep 26, 2016
Freezer	Aug 14, 2016
Frenzee	Feb 24, 2013
Fridolin	Jun 27, 2017
Fruit Reloaded	Dec 8, 2017
Gaviota Tablebases	Apr 22, 2018
Glass	May 24, 2017
Hagrid	Apr 12, 2016
Heiner Marxen	Apr 19, 2014
Houdini	Apr 14, 2018
InmiChess	Mar 6, 2014
John Kominek	Dec 30, 2016
Joker IT	Sep 16, 2017
Lomonosov Tablebases	May 20, 2016
Madeleine	May 18, 2017
Monsoon	Feb 8, 2015
Nalimov Tablebases	Dec 23, 2016
Nebula	Feb 7, 2015
Pepito	Nov 27, 2014
PostModernist	Jan 7, 2016
Scid	Apr 15, 2017
Scorpio Bitbases	Mar 12, 2018
Searcher	Sep 26, 2016
Snitch	Apr 7, 2016
Syzygy Bases	Apr 19, 2018
Terra	Feb 11, 2015
Thompson's Databases	Dec 24, 2014
Tornado	Dec 14, 2017
TRACE	Feb 14, 2013
Typhoon	Apr 18, 2016
Tytan	Nov 3, 2015
Ulrich Türke	Jan 8, 2016
WCCC 2002	Nov 24, 2017
WCCC 2017	Dec 31, 2017
Wilhelm	Oct 6, 2015
Workshop Chess and Mathematics	Mar 5, 2015

Up one level

Oracle

GerdIsenberg — Sun, 04 Sep 2016 12:54:27 GMT

Home * Knowledge * Oracle

		Oracle, an instance with the fame of perfect knowledge, that is evaluation without noise or errors, a form of divination, and a perfect supervisor in learning. For instance endgame tablebases act like an oracle, providing the optimal moves.
Consulting the Oracle by John William Waterhouse ^[1]

Pre-processing

A so called oracle approach is a knowledge instance applied at the root or the interior of the tree with some depth left to the horizon, which guides search and leaf evaluation for specific features or pattern, relevant in particular chess positions, and not in others. This applies to first order evaluation terms by initializing Piece-Square Tables, also dubbed Pre Scan Heuristics ^[2] as propagated by David Kittinger, as well as second order terms if related pattern match as described by Hans Berliner in Some Innovations Introduced by HiTech ^[3].

While Pre-processing seems somewhat outdated with todays search depths in conjunction with transposition table anomalies and resulting search instabilities, Oracle approaches may be used to control time management, to order moves, or, as proposed by Ronald de Man in scoring root moves by slightly shifting the alpha-beta windows ^[4].

Quotes

Bruce Wright

Bruce Wright on pre-processing in Duchess ^[5]

One thing that we used to do with our chess program, Duchess, was to have a special routine that ran before the main search that identified strong and weak points in each side's respective position - weak squares, passed pawns, weak king protection, etc, and tried to grow trees of moves to protect our own weak squares or attack the opponent's weak squares. These would be just sequences of moves by our own or our opponent's pieces and pawns to reach the targeted squares. A table was build for the value of reaching each of these goals for each type of piece and for reaching the middle points along the paths (the value diminishing the further they were from the goal). Then during the search the program would get bonus points for reaching some of the intermediate points in the plan. This seemed most useful in the endgame when actually reaching the culmination of a play might be beyond the search depth, and where tactics did not dominate as much as they do in the middle game; for example, Duchess was quite capable of finding long King maneuvers that might take the King far away from simpleminded heuristics such as "centralize the King in the endgame" and that were too deep to be found by a direct search. It wasn't perfect; it could not take into account the changes in strategy that might be dictated by a radically different structure encountered deep in the search, but it seemed to be better than nothing.

David Kittinger

David Kittinger and Scott McDonald in 1984 on Pre Scan Heuristics of the Super Constellation ^[6]

A second departure from other commercial programs has been the simplification of the evaluation function as applied to the end nodes of the tree search. The programs instead rely heavily on specific chess knowledge which is concentrated into a special preprocessor which interfaces to the tree search primarily through the scores associated with specific ply-one moves. This ides of a ply-one move preprocessor was originally implemented in the program Tech by James Gillogly in the late 1960s. Although Tech only achieved a high 1400 rating running on a large computer, the strategy has certain appeal. First, chess tree searching has become very efficient, and second, the interaction problems associated with putting ever increasing amounts of chess knowledge in the tree become formidable. It has become apparent to that this rather simple approach might contain the structure of a master level microcomputer program.

Peter Gillgasch

Peter Gillgasch on DarkThought's Oracle, February 1996 ^[7]

After toying with horrible slow code that did endpoint evaluations for the pieces I got the idea (as many did before, but I swear I didn't know that and hence I was quite proud of it) to analyze the root position and to modify the piece/square table relative to pawn structure and king locations. The piece/square table scores were also used for move ordering to cut down the tree size (this helped a lot since it is basically using the evaluation to order the moves at close to no cost). Of course the program played much better than before but it had serious trouble when the pawn structure was highly flexible and if there was a way to lock its bishops with own pawns it was guaranteed to like exactly this line ;) Later the three of us modified the oracle code (to use Berliner's term) and we where quite successful with it - DarkThought started to beat commercial PC programs. But it was quite hard to make further progress, so a lot of knowledge was moved to the endpoint evaluation up to the point that there was basically no oracle code left. This improved playing strength but it was always my impression that we suffered in the "tactical" aspect a bit since the search was no longer fast as hell and I was never convinced that going this way was the best decision.

Chrilly Donninger

Quote by Chrilly Donninger from CHE: A Graphical Language for Expressing Chess Knowledge, 1996 ^[8]

The main design criterion for successor Nimzo-3 was combining the positional play of Nimzo-2 with the tactical strength of a program like Fritz. Nimzo-2 was developed on an 486/50 MHz PC, which calculated about 3,000 nodes per second. Thereof 60 to 70 percent was spent/wasted in the leaf evaluation routines. Hence, a major improvement in speed and thus in tactical strength could only be obtained by performing most of the evaluation either in the root or the interior of the search tree. So, Nimzo-3 became a Genius/Fritz-like program with a complex root evaluation, called Oracle, similar to Berliner's Oracle, and with a very simple, mainly first order evaluation at the leaves ^[9]. Nimzo-3 spends about 10 to 20% on leaf evaluation, its node rate has increased by 400% up to 12,000 nodes/second on the same hardware.

Don Dailey

Don Dailey on Pre-processing, May 1998 ^[10] :

The term pre-processing is normally used in the context of an evaluation function. It's a process where you make most of your evaluation decisions BEFORE the search begins. Typically you determine where each piece should go and essentially build a 64 square table for each piece type of each color on the chess board. You might decide that the c file is open and so you give rooks a big bonus if they can get to the c file. Once you make this decision it doesn't change during the search. So if the c file suddenly gets blocked during the search, the rooks won't know this and still try to get on the c file. Pre-processing has many advantages and disadvantages. Here is a list of them: Pro's Very fast, evaluation almost free. Trivial to implement. Can put huge amounts of knowledge in chess program with essentially no slowdown. This is because all the real work is done in a fraction of a second before the search begins. Especially good with pawn patterns. (but not pawn structure) Con's The evaluation is very dependent on the starting position. Deeper searches suffer more than shallow one. Ironically, you can do deeper searches if you do lots of pre-processing. Very difficult to put in dynamic endings where relationships change quickly. Concepts like mobility are covered very inexactly. Pawn structure terms cannot be calculated with any reliability. Makes it problematic whether to use hash table aging because it affects the hash tables in strange ways. The problem is that 2 identical positions can have different scores if they are descendants of different starting positions. There are probably other pro's and con's I didn't think of. Many really good programs use this method, but almost always there is a mixture of pre-processing with more dynamic stuff like pawn structure which might be hashed, or calculated quickly with incremental updating schemes. There is quite a bit of diversity and opinion on this subject. Some swear by it and others shun it completely. I don't use it any more but my older programs did. My feeling is that with ever increasing depth, it becomes more and more troublesome. Imagine a program doing 60 ply searches. The end nodes of the tree will not bear very much resemblance to the initial position where the decisions were made. But since we don't usually look 60 ply deep pre-processing is still a workable method. But I believe you can still write very strong programs that do a substantial amount of pre-processing. Fritz is one example. Genius also does substantial pre-processing. I think probably more programs use this than not. My old program RexChess was almost all pre-process with a little dynamic pawn structure mixed in! Pre-processing does not necessarily have to be pure piece/sq tables. You can make other evaluation decisions in advance too and prepare them for fast execution during the search.

Ulrich Türke

Reply by Ulrich Türke ^[11] :

I too think that pre-processing is still done in most of the current chess programs, more or less. I am considering the possibility of a moderated pre-processing, i. e. apply the time-consuming pre-processing evaluation parts not at the root but to nodes at depth - say - the half of the aimed search depth. Thus, one would still have the main advantage, saving a lot of calculation time, because the number of pre-processed nodes would still be a microscopic fraction of the leaf nodes. But on the other hand, the pre-processed knowledge would be applied to nodes being far closer to the leaf nodes (in your examples "only" 30 ply instead of 60). Opinions?

Amir Ban

Note by Amir Ban ^[12] :

It's a fair but simplistic description of Junior.

Don Dailey

Don Dailey again ^[13] :

I've been considering this type of approach for a long time. I think it definitely has merit. It would suffer from hash table anomalies but there are ways to deal with this, the primary one to simply ignore them. There are a few issues to be dealt with but my feeling is that you might do well with this scheme. Scoring might be a little fuzzy at times but that might be ok. Probably the scheme would be to pre-process at every level up to MAX_DEPTH-n, where n might be at least 3 or 4 ply. Keep in mind that pre-processing is incredibly expensive even compared to fully dynamic processing, so I suspect you cannot get very close to the leaf nodes. Of course 3 or 4 ply away might be considered pretty close if you were doing 14 ply searches. The way I got this idea (which I'm not taking credit for) actually began when I was programming the ending Bishop and Knight vs King with a pre-processor program of mine a few years ago. This is a very good exercise for someone wanting to understand some of the difficulties of pre-processing. I tested with a 3 ply search, and tuned the thing up to do quite well. But it turned out to not work so well at other levels! It turns out that no matter what table you use, they will tend to be optimum for a specific depth only. It was almost funny because I kept figuring out which positions in the search were messing it up and changed the tables accordingly. These anticipations were wrong though at different levels! Finally though, I extracted the most general principles possible and created a table that was almost static (not based as much on the placing of the pieces) and it did ok, but not as good as the depth specific ones. Some pre-processors will suggest a move and for this ending that would work well. The idea is to give a bonus to the whole search tree under some root move. For example I might give a small bonus for playing any move that's a pin. This makes the program slightly in favor of playing a pin. I call these "ply 1 incentives" but there is probably better terminology in use. This is also another example of pre-processing. See note at end of my post. But your idea would solve this and a host of other problems. You could make very good guesses about configurations if you knew the possible changes to a position were limited. This would enable you to be more aggressive about the knowledge you included. Here is another idea I had which is more dynamic in nature. It occurred to me that you could do a fairly decent evaluation based on pawn position only, the idea being a separate set of tables for each pawn structure. These could be built by the pawn structure hash table mechanism most programs have. Most pieces can be judged well by the pawn structure around them. I did not pursue this idea because I fear it may still be too slow. If my hash table hit rate was say 95 percent, then 1/20 of the positions would require a pre-processing step. While this does not seem like much, you have to consider how expensive building the table is. It's pretty expensive, especially if you want sophistication. But on top of that you must recompute the positional score each time the pawn structure changes, EVEN if the table itself is ready to go. This should be fairly fast but not trivial in terms of execution speed. You have already killed some of the speed you were hoping to gain. Is the idea workable? Maybe, but I'm skeptical. Also, the pawn structure is not the only relevant factor so other evaluation would not doubt be needed. For instance you cannot look at the pawn structure and know for sure that you are in an endgame. You could make assumptions though based on the exact position you had when you built the tables. Anyway the idea is interesting and I sometimes toy with the idea of trying it out, but it seems like a lot of work for an experiment that may not pay off. It could well be that someone dedicated to making it work might find imaginative solutions to some of the problems. But your idea may be more sound. It may very well be that some are using it. I've never heard of a specific example of it though.

I think an old program called Tech used the method of "ply 1 move incentives." There was no evaluation at all (the way I remember it) except for material value and a list of moves was prepared in order of goodness from a pre-processor at the root. The program simply played the first move it came to in the move list that was at least as good tactical as any other. I'll bet Bob Hyatt knows about this one. I had a nice discussion once with the programmer when he was giving a talk on hash table collisions in chess programs.

Vincent Diepeveen

Vincent Diepeveen on Pre-processing, October 2000 ^[14]

It's pretending you know in advance what is the best move and just let the program figure out the tactics. It's fast and of course my first line is a rude outline of what it is, but it's definitely no compare to a leaf evaluation. So the 2 things against each other: Prescan heuristics/ piece square tables: fill a table BEFORE you search and apply there the knowledge, so for example for each piece at each square and in your makemove only add the score from the tables and do nothing in your leafs (don't see why one would need a qsearch in fact for such programs a 'guess' function should be plenty enough). No evaluation needed. Even passers you can easily do incremental, no problem. Leaf eval: you can sure use the makemove to build up data structures, but the evaluation is NOT dependent upon the moves made, but only upon the position and you go scan the board position in each leaf for chess knowledge. So the big difference is for example when exchanging queen: Chess Tiger used (don't know whether it's still a pre-processor) to be happy before queen exchange, then after queen exchange it's suddenly very unhappy. Old Fritz versions except the latest 6a, 6b etcetera were also pre-processors. Of course many programmers figured out that using a pre-processor only is very hard to play chess, so usually a few big scores they do in eval like passed pawns. Many old programs simply had no king safety at all. Nimzo is a classical case of pre-processing too. if you checkout its book you'll see it hardly plays openings with very tough pawn structures without having all tough lines in book, as otherwise the pre-processor makes big mistakes as it doesn't see the position change in the root of course. Now where is the big advantage of pre-processors apart that you can do it faster, why have they been so pretty successful in the past? I think very important reason is that it's also very easy to debug a pre-processor when comparing that with a leaf evaluation.

Publications

James Gillogly (1972). The Technology Chess Program. Artificial Intelligence, Vol. 3, pp. 145-163. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium
Peter W. Frey (1986). Fuzzy Production Rules in Chess. ICCA Journal, Vol. 9, No. 4
Hans Berliner (1987). Some Innovations Introduced by Hitech. ICCA Journal, Vol. 10, No. 3
Hans Berliner (1989). Some Innovations Introduced by Hitech. Advances in Computer Chess 5
Chrilly Donninger (1996). CHE: A Graphical Language for Expressing Chess Knowledge. ICCA Journal, Vol. 19, No. 4

Forum Posts

computer chess "oracle" ideas... by Robert Hyatt, rgcc, April 1, 1997
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 3, 1997
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997
What is "pre-processing" by Howard Exner, CCC, May 07, 1998
Re: What is "pre-processing" by Don Dailey, CCC, May 07, 1998
Preprocessing vs leaf evaluating - any preprocessors left? by Tom King, rgcc, July 05, 1998
Ply 1 scoring factors by Will Singleton, CCC, December 07, 1998
Re: What is Prescan Heuristics ?? by Vincent Diepeveen, CCC, October 13, 2000

External Links

References

^ "Consulting the Oracle" by John William Waterhouse, 1884, showing eight priestesses in a temple of prophecy, Oracle from Wikipedia
^ PSH from Schachcomputer.info Wiki (German)
^ Hans Berliner (1987). Some Innovations Introduced by Hitech. ICCA Journal, Vol. 10, No. 3
^ Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997
^ Bruce C. Wright (1996). Routines prior to Main Search. Computer Chess Reports, Vol. 5, Nos. 3+4, p. 102
^ David Kittinger and Scott McDonald (1984). Report from the U.S. Open. Computer Chess Digest Annual 1984 pp. 15-33
^ Drawn games (Was Re: Transposition table) by Peter Gillgasch, rgcc, February 06, 1996
^ Chrilly Donninger (1996). CHE: A Graphical Language for Expressing Chess Knowledge. ICCA Journal, Vol. 19, No. 4
^ This approach seems to have been invented by Kaare Danielsen for his program CXG Advanced Star Chess, Quote from Donninger's CHE paper
^ Re: What is "pre-processing" by Don Dailey, CCC, May 07, 1998
^ Re: What is "pre-processing" by Ulrich Türke, CCC, May 08, 1998
^ Re: What is "pre-processing" by Amir Ban, CCC, May 08, 1998
^ Re: What is "pre-processing" by Don Dailey, CCC, May 08, 1998
^ Re: What is Prescan Heuristics ?? by Vincent Diepeveen, CCC, October 13, 2000

What links here?

Page	Date Edited
More Links
Alpha-Beta	Jan 28, 2018
Andreas Mader	Dec 30, 2017
Andrew Tridgell	Aug 3, 2015
Bionic	May 27, 2013
Bionic Impakt	Sep 6, 2014
Bruce Wright	Jan 7, 2016
Cognition	Dec 8, 2017
CXG Star Chess	Jun 23, 2017
David Kittinger	Dec 27, 2017
Delfi	Jan 7, 2016
Dictionary	Aug 24, 2017
Duchess	Dec 22, 2017
Endgame Tablebases	Mar 6, 2018
Enterprise	Jun 23, 2017
Eval Tuning in Deep Thought	Jun 7, 2016
Evaluation	Feb 1, 2018
Evaluation Philosophy	Sep 29, 2014
Frenchess	Jan 7, 2016
Gazebo	May 21, 2017
Ghost	Feb 2, 2018
Hans Secelle	Nov 2, 2012
HiTech	Mar 31, 2018
KnightCap	Nov 6, 2016
Knowledge	Jul 22, 2017
KRK	Nov 26, 2016
Michael George	Jan 3, 2016
Move Ordering	Feb 27, 2018
Nimzo	Dec 30, 2017
Novag Expert	Aug 3, 2013
Novag Forte	Aug 3, 2013
Oracle	Sep 4, 2016
p4wn	Sep 23, 2017
Pattern Recognition	Sep 8, 2017
Piece-Square Tables	Mar 31, 2018
Planning	Feb 12, 2018
Retrograde Analysis	Mar 21, 2017
Robert Hyatt	Dec 25, 2017
RomiChess	Jan 2, 2018
Ronald de Man	Nov 20, 2017
Root	Sep 26, 2016

Up one Level

Pattern Recognition

GerdIsenberg — Fri, 08 Sep 2017 10:07:25 GMT

Home * Knowledge * Pattern Recognition

		Pattern Recognition, is used to assign a label to an input value ^[1] , for instance to apply classification in machine learning applications, i.e. to identify objects and images, as well as computer chess related pattern of chess positions in Cognitive Psychology and concerning evaluation and control of the search in computer chess. Pattern recognition algorithms generally aim to provide a reasonable answer for all possible inputs and to perform a "fuzzy" matching. In contrast, Pattern matching usually has to be exact.
Chess pattern ^[2]

Chess Pattern

Chess pattern range from simple properties of squares and pieces concerning occupancy and control, to a more complex interrelated sets of features. Recognizers are implemented with decision trees, neural networks, and fuzzy logics. In his ICCA Journal paper Fuzzy Production Rules in Chess, Peter W. Frey ^[3] proposed feature strings or sets of three types. Type-A features must match completely, type-B feature strings represent features which are usually but not always present, while type-C features are present occasionally but are highly diagnostic when available. Those features were intended to use at the root for an oracle approach.

Chess Programs

Publications

1950 ...

Woodrow W. Bledsoe, Iben Browning (1959). Pattern Recognition and Reading by Machine. In Proceedings of the Eastern Joint Computer Conference
Albert M. Uttley (1959). Imitation of Pattern Recognition and Trial-and-error Learning in a Conditional Probability Computer. Reviews of Modern Physics, Vol. 31, April 1959, pp. 546-548 ^[4] ^[5]

1960 ...

Mikhail Moiseevich Bongard ^[6] (1967). Проблема Узнавания. The Problem of Recognition, Nauka Press, Moscow, appeared as Pattern Recognition in its 1970 English translation
Chin-Liang Chang (1967). Fuzzy Sets and Pattern Recognition. Ph.D. Thesis, Advisor: Lotfi A. Zadeh, University of California, Berkeley

1970 ...

Mikhail Moiseevich Bongard (1970). Pattern Recognition. Rochelle Park, N.J., Hayden Book Co., Spartan Books
Albert Zobrist (1970). Feature Extraction and Representation for Pattern Recognition and the Game of Go. Ph.D. Thesis (152 pp.), University of Wisconsin. Also published as technical report #85
Albert Zobrist (1970). A Pattern Recognition Program which uses a Geometry-Preserving Representation of Features. Technical Report #85, pdf
James R. Slagle, Richard C. T. Lee (1971). Application of game tree searching techniques to sequential pattern recognition. Communications of the ACM, Vol. 14, No. 2
Albert Zobrist, Frederic Roy Carlson (1973). The USC chess program. Proceedings of the ACM annual conference, Atlanta, Georgia
Jacques Pitrat (1976). A Program to Learn to Play Chess. Pattern Recognition and Artificial Intelligence, pp. 399-419. Academic Press Ltd. London, UK. ISBN 0-12-170950-7.
Azriel Rosenfeld, Jerome A. Feldman, Laveen N. Kanal, Patrick H. Winston (1977). AI and Pattern Recognition. IJCAI 1977
Albert Zobrist, Frederic Roy Carlson (1977). Detection of Combined Occurrences. Communications of the ACM, Vol. 20, No. 1, pp. 31-35.
Walter R. Reitman, Bruce Wilcox (1977). Pattern Recognition and Pattern-Directed Inference in a Program for Playing Go. ACM SIGART Bulletin, No. 63
Rainer Kurz (1977). Musterverarbeitung bei der Schachprogrammierung. Ph.D. thesis, Universität Stuttgart (German)
Ivan Bratko, Danny Kopec, Donald Michie (1978). Pattern-Based Representation of Chess Endgame Knowledge. The Computer Journal, Vol. 21, No. 2, pp. 149-153. pdf
David Wilkins (1979). Using Patterns and Plans to Solve Problems and Control Search. Ph.D. thesis, Computer Science Dept, Stanford University, AI Lab Memo AIM-329
Max Bramer, Mike Clarke (1979). A Model for the Representation of Pattern-Knowledge for the Endgame in Chess. International Journal of Man-Machine Studies, Vol. 11, No.5

1980 ...

David Wilkins (1980). Using patterns and plans in chess. Artificial Intelligence, vol. 14, pp. 165-203. Reprinted (1988) in Computer Chess Compendium
Ivan Bratko, Donald Michie (1980). A Representation of Pattern-Knowledge in Chess Endgames. Advances in Computer Chess 2
Max Bramer (1980). An Optimal Algorithm for KPK using Pattern Knowledge. Advances in Computer Chess 2, pp. 82-96.
Zdenek Zdráhal, Ivan Bratko, Alen Shapiro (1981). Recognition of Complex Patterns Using Cellular Arrays. The Computer Journal, Vol. 24, No. 3, pp. 263-270
Max Bramer (1982). Pattern-Based Representations of Knowledge in the Game of Chess. International Journal of Man-Machine Studies, Vol. 16, pp. 439-448.
Alen Shapiro, Tim Niblett (1982). Automatic Induction of Classification Rules for Chess End game. Advances in Computer Chess 3
Ross Quinlan (1983). Learning efficient classification procedures and their application to chess end games. Machine Learning: An Artificial Intelligence Approach
Ivan Bratko, Peter Tancig, Simona Tancig (1984). Detection of Positional Patterns in Chess. ICCA Journal, Vol. 7, No. 2 (abridged version)
Ivan Bratko, Peter Tancig, Simona Tancig (1984,1986). Detection of Positional Patterns in Chess. Advances in Computer Chess 4 (full paper)
Ivan Bratko (1985). Symbolic Derivation of Chess Patterns. Progress in Artificial Intelligence (eds. L. Steels and J.A. Campbell), pp. 281-290. Ellis Horwood Ltd., Chichester, UK.
Peter W. Frey (1986). Fuzzy Production Rules in Chess. ICCA Journal, Vol. 9, No. 4
Kai-Fu Lee, Sanjoy Mahajan (1988). A Pattern Classification Approach to Evaluation Function Learning. Artificial Intelligence, Vol. 36, No. 1
Robert Levinson (1989). A Self-Learning, Pattern-Oriented Chess Program. ICCA Journal, Vol. 12, No. 4
Roger Hünen (1989). Efficient Pattern Recognition in Large Game Trees. Advances in Computer Chess 5
Hans Berliner, Carl Ebeling (1989). Pattern Knowledge and Search: The SUPREM Architecture. Artificial Intelligence, Vol. 38, No. 2, pp. 161-198. ISSN 0004-3702. Revised as Hans Berliner, Carl Ebeling (1990). Hitech. Computers, Chess, and Cognition

1990 ...

Eduardo F. Morales (1992). First-Order Induction of Patterns in Chess. Ph.D. Thesis, The Turing Institute, University of Strathclyde, Glasgow
Eduardo F. Morales (1992). Learning Chess Patterns. Inductive Logic Programming (ed. Stephen Muggleton), Academic Press, The Apic Series, London, UK
Steven Walczak (1992). Pattern-Based Tactical Planning. IJPRAI 6(5)
Steven Walczak, Douglas D. Dankel II (1993). Acquiring Tactical and Strategic Knowledge with a Generalized Method for Chunking of Game Pieces. International Journal of Intelligent Systems 8 (2), 249-270.
Laveen Kanal (1993). On Pattern, Categories and Alternate Realities. Pattern Recognition Letters, Vol. 14, No. 3, pdf
Eduardo F. Morales (1994). Learning Patterns for Playing Strategies. ICCA Journal, Vol. 17, No. 1
Robert Levinson, Gil Fuchs (1994). A Pattern-Weight Formulation of Search Knowledge. UCSC-CRL-94-10, CiteSeerX
Reijer Grimbergen (1996). Using Pattern Recognition and Selective Deepening to Solve Tsume Shogi. 3rd Game Programming Workshop, CiteSeerX ^[7]
Fernand Gobet, Herbert Simon (1998). Pattern recognition makes search possible: Comments on Holding (1992). Psychological Research, Vol. 61, pdf ^[8]
Hitoshi Matsubara, Steven Walczak, Reijer Grimbergen (1998). Analysis of important patterns in Shogi. The 15th Annual Meeting of the Japanese Cognitive Science Society, (Nagoya, Japan), 136-137. (in Japanese/Kanji)
Lev Finkelstein, Shaul Markovitch (1998). Learning to Play Chess Selectively by Acquiring Move Patterns. ICCA Journal, Vol. 21, No. 2, pdf
Erik van der Werf (1999). Non-linear target based feature extraction by diabolo networks. Masters thesis. Pattern Recognition Group, Department of Applied Physics, Faculty of Applied Sciences, Delft University of Technology, pdf
Kieran Greer, Piyush Ojha, David A. Bell (1999). A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic. ICCA Journal, Vol. 22, No. 1

2000 ...

Miroslav Kubat, Jan Žižka (2000). Learning Middle Game Patterns in Chess: A Case Study. Lecture Notes in Computer Science, Vol. 1821, Springer
Miroslav Kubat (2000). Designing neural network architectures for pattern recognition. The Knowledge Engineering Review, Vol. 15, No. 2
Ari Shapiro, Gil Fuchs, Robert Levinson (2002). Learning a Game Strategy Using Pattern-Weights and Self-play. CG 2002
R. Grekovs (2002). Methods of Fuzzy Pattern Recognition Riga Technical University, ps, covers Fuzzy Kora algorithm
Marcel van Kervinck (2002). A pattern-recognition strategy for chess position evaluation. Slides from The design and implementation of the Rookie 2.0 Chess Playing Program. ^[9]
Jan Žižka, Michal Mádr (2003). Learning Representative Patterns from Real Chess Positions: A Case Study. IICAI 2003
Christopher Chabris, Eliot Hearst (2003). Mentalizing, Pattern Recognition and Forward Search: Effects of Playing Speed and Sight of the Position on Grandmaster Chess Errors. Cognitive Science, Vol. 27
Bir Bhanu, Yingqiang Lin, Krzysztof Krawiec (2005). Evolutionary Synthesis of Pattern Recognition Systems. Springer, New York
Rajjan Shinghal (2006) Pattern Recognition, Techniques and Applications. Oxford University Press ISBN-13: 978-0195676853, available from amazon.ca
Chun-Bin Hsu (2006). Pattern Recognition in Chinese Chess. Master thesis, National Chiao Tung University, pdf (Chinese)
Antonio Fernández, Antonio Salmerón (2008). BayesChess: A computer chess program based on Bayesian networks. Pattern Recognition Letters, Vol. 29, No. 8

2010 ...

Merim Bilalić, Robert Langner, Michael Erb, Wolfgang Grodd (2010). Mechanisms and neural basis of object and pattern recognition: a study with chess experts. Journal of Experimental Psychology General, Vol. 139, No. 4
Abdallah Saffidine, Nicolas Jouandeau, Tristan Cazenave (2011). Solving breakthrough with Race Patterns and Job-Level Proof Number Search. Advances in Computer Games 13, pdf » Breakthrough (Game), Proof-Number Search

Forum Posts

Symbolic: On patterns by Steven Edwards, CCC, March 16, 2004 » Symbolic
Symbolic: First pattern instance generation by Steven Edwards, CCC, March 27, 2004
Symbolic: Demo: a few more bootstrap patterns by Steven Edwards, CCC, March 29, 2004

External Links

References

^ Pattern recognition from Wikipedia
^ Clipping from Chess pattern by ~Melmolly on deviantART, Graphics Software by Xara
^ Peter W. Frey (1986). Fuzzy Production Rules in Chess. ICCA Journal, Vol. 9, No. 4
^ Ratio Club from Wikipedia
^ Royal Radar Establishment from Wikipedia
^ Mikhail Moiseevich Bongard - Михаил Моисеевич Бонгард
^ Tsumeshogi from Wikipedia
^ Dennis H. Holding (1992). Theories of Chess Skill. Psychological Research, Vol. 54, No. 1
^ Marcel van Kervinck (2002). The design and implementation of the Rookie 2.0 Chess Playing Program. Masters Thesis, pdf
^ Bayesian spam filtering - Wikipedia

What links here?

Page	Date Edited
Advances in Computer Chess 6	Dec 17, 2016
AI Chess	Jan 7, 2016
Albert Zobrist	Jun 12, 2016
Alen Shapiro	May 3, 2015
Analog Evaluation	Oct 27, 2017
Ari Shapiro	Sep 22, 2015
Blockage Detection	Oct 19, 2017
Chessmaps Heuristic	Aug 27, 2015
Chimo	Jul 26, 2017
Chump	Jan 31, 2016
Chun-Bin Hsu	Jul 23, 2017
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
David Slate	Jul 19, 2016
EPAM	Jul 15, 2017
Evaluation Patterns	Jun 24, 2013
Eye Movements	Jul 22, 2015
Fortress	Feb 1, 2018
Gábor Lugosi	Apr 29, 2015
Gerhard Trippen	Jun 8, 2015
Gil Fuchs	Sep 22, 2015
Go	Jan 24, 2018
Guofeng Tong	May 23, 2016
HiTech	Mar 31, 2018
Hitoshi Matsubara	Feb 7, 2017
Huafu Chen	Aug 24, 2014
InmiChess	Mar 6, 2014
Ivan Bratko	Aug 16, 2017
Jan Žižka	Jun 17, 2016
Kai-Fu Lee	May 14, 2015
Kaissa	Apr 9, 2018
Killer (NL)	Dec 15, 2017
Knowledge	Jul 22, 2017
KRK	Nov 26, 2016
Krzysztof Krawiec	Dec 15, 2014
Laveen Kanal	Jun 2, 2015
Learning	Feb 20, 2018
Marco Wiering	Aug 4, 2015
Martin Riedmiller	Nov 29, 2016
MChess	Feb 26, 2018
Mirek Pawlak	May 23, 2016
Miroslav Kubat	Jun 16, 2016
Morph	Dec 7, 2017
Neural Networks	Mar 12, 2018
Paradise	Nov 19, 2014
Pattern Recognition	Sep 8, 2017
Paweł Liskowski	Jan 22, 2017
PawnKing	Sep 5, 2014
Peter W. Frey	Dec 25, 2017
Piece Recognition	Sep 8, 2017
Piyush Ojha	Jul 15, 2013
Planning	Feb 12, 2018
Quote Remembering Kronrod	Dec 2, 2013
Rajjan Shinghal	Nov 4, 2013
Richard C. T. Lee	May 13, 2015
Santos Gerardo Lazzeri	Mar 19, 2016
Shogi	Feb 19, 2018
Simon Liao	Apr 28, 2011
Stephen B. Streater	Dec 17, 2016
Symbolic	May 8, 2017
Tactics	Jan 12, 2018
The Sniper	Jun 3, 2016
USC CP	Aug 10, 2016
Werner Inmann	Mar 6, 2014
William Chase	Jan 21, 2016
Wojciech Jaśkowski	Dec 13, 2014
Woodrow W. Bledsoe	Oct 24, 2016
Xinbo Gao	May 28, 2015
Zdenek Zdrahal	Apr 4, 2013

Up one Level

Perceiver

GerdIsenberg — Tue, 21 Nov 2017 09:11:26 GMT

Home * Knowledge * Cognition * Perceiver

		Perceiver, an experimental chess program by Michael Barenfeld and Herbert Simon of the late 60s with focus on perceptual processes in problem solving. Perceiver was able to duplicate the eye movements of a chess expert by adhering to the simple relations of attack and defense, based on previously developed routines of the program Mater for detecting those basic chess relations ^[1].
Boldriaan - Het Oplettende Oog (2002) ^[2]

Fixated Squares

With the simulated fovea centralis fixated on a square of the board, information is acquired peripherally about pieces standing on nearby squares that attack or defend the fixated square, or that are attacked or defended by the piece on that square. Attention is then assumed to switch to one of these nearby squares, and, unless it immediately returns to the square already fixated, causes a saccadic movement to the new square. With the fovea fixated on the new square, the process simply repeats, causing a biased random walk of the fixation point around the board, returning most frequently to those regions of interest where relations among pieces are densest and spending little time on the edges of the board.

MAPP

Kevin J. Gilmartin and Herbert Simon further extended Perceiver into a system called MAPP (Memory-aided Pattern Perceiver) which uses the learning mechanism of EPAM, and reinforced the chunking hypothesis by subjecting MAPP to the same board reconstruction experiment that the human players faced ^[3] ^[4].

Publicatons

Herbert Simon, Michael Barenfeld (1968). Information Processing in the Perception of Chess Positions. Carnegie Mellon University, Paper #127
Herbert Simon, Michael Barenfeld (1969). Information Processing-Analysis of Perceptual Processes in Problem Solving. Psychological Review, Vol. 76, No. 5, reprinted in Herbert A. Simon (1979). Models of Thought. Yale University Press, pdf ^[5] ^[6]
Herbert Simon (1973). Lessons from Perception for Chess-Playing Programs (and Vice Versa). Computer Science Research Review 1972-73, pdf
Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46, reprinted in Herbert A. Simon (1979). Models of Thought. Yale University Press.pdf
Herbert Simon, William Chase (1973). Skill in Chess. American Scientist, Vol. 61, No. 4, reprinted in David Levy (ed.) (1988) Computer Chess Compendium, pdf

External Links

perceiver - Wiktionary
perceive - Wiktionary
perception - Wiktionary
Perception from Wikipedia
Visual perception from Wikipedia
Eye movement from Wikipedia
Agnes Obel - Stretch your Eyes, March 24, 2017, Soundcheck at Wonder Ballroom, Portland, YouTube Video ^[7]

References

^ George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted in Herbert A. Simon (1979). Models of Thought. Yale University Press, pp. 181-200, in David Levy (ed.) (1988). Computer Chess Compendium.
^ Het Oplettende Oog - The Watchful Eye (2002), Schaakkunst van Boldriaan
^ William Chase, Herbert Simon (1973). Perception in chess. Cognitive Psychology, Vol. 4, No. 1
^ Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46, reprinted in Herbert A. Simon (1979). Models of Thought. Yale University Press, pdf
^ Oleg K. Tichomirov, E. D. Poznyanskaya (1966). An Investigation of Visual Search as a Means of Analyzing Heuristics. Soviet Psychology, Winter 1966-67 (from Voprosy Psikhologii, 1966, 2, 4)
^ The Tichomirov-Poznyanskaya middlegame position analysis (1966) by John L. Jerz
^ Trautonium from Wikipedia

What links here?

Page	Date Edited
CHREST	May 6, 2016
Chump	Jan 31, 2016
Chunking	Jun 12, 2017
Cognition	Dec 8, 2017
EPAM	Jul 15, 2017
Eye Movements	Jul 22, 2015
Herbert Simon	Feb 11, 2016
Kevin J. Gilmartin	Jan 1, 2016
MAPP	Jan 30, 2016
Mater	Apr 26, 2016
Michael Barenfeld	Oct 2, 2014
Oleg K. Tichomirov	Oct 2, 2014
Perceiver	Nov 21, 2017

Up one Level

Planning

GerdIsenberg — Mon, 12 Feb 2018 11:58:25 GMT

Home * Knowledge * Planning

		Planning, the process of applying knowledge, thinking and prediction to create and maintain a plan, a temporal set of intended actions to achieve a certain goal, in chess, to finally win the game.
Plan is law, fulfillment is duty, over-fulfillment is honor! ^[1]

Terms of Planning

In 1997, Jan van Reek ^[2] categorized planning in chess to three main characteristics, tactics, positional play, and strategy, where positional play serves as guideline for planning of a strategy ^[3]:

	Terms of Planning	Aim	Dominating abstraction
Tactics	Short	To gain material or to mate	Matter
Positional play	Medium	To improve the position	Space
Strategy	Long	To swing the balance	Time

Long-range Planning

Long-range planning by human chess players is usually made on the basis of reasoning, experience, and intuition, as investigated by De Groot in 1946 ^[4].

Search and Evaluation

Conventional depth-first alpha-beta searchers have no real sense of planning other than minimaxing their score inside their search horizons. Inside chess programs, planning is often implicit due to look ahead and certain evaluation features and their associated weights. For instance, a bonus for a Rook on an open file, and another bonus to occupy the 7th rank is a typical example to mimic some kind of strategic planning. However, long-range planning and seeking for goals requires pattern recognition and associated advices if they match.

Oracle Approaches

Oracle approaches such as pre-processing and initializing piece-square tables based on features and pattern of the root may realize plans like minority attack and along with pawn structure and king placement, plans to attack the king. However, with todays typical search depths one has to consider path-dependencies, transposition table anomalies and resulting search instabilities. Instead, oracle approaches at or near the root, may be used to initialize dedicated piece-square tables for the sole purpose to control selectivity further down the tree, for instance to extend moves according to a certain plan.

Chess Quotes

^[5]

Frank Marshall: A bad plan is better than none at all.
Emanuel Lasker: To find the right plan is just as hard as looking for its sound justification.
Eugene Znosko-Borovsky: It is not a move, even the best move that you must seek, but a realizable plan.
Alexander Kotov: It is better to follow out a plan consistently even if it isn't the best one than to play without a plan at all. The worst thing is to wander about aimlessly.

Chess Programs

Publications

1946 ...

Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam, advisor Géza Révész; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions, (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6.

1950 ...

Max Euwe (1953). Judgment and Planning in Chess. McKay Company, New York, N.Y. ^[6]

1960 ...

Adriaan de Groot (1965, 1978). Thought and Choice in Chess. Mouton & Co Publishers, The Hague, The Netherlands. ISBN 90-279-7914-6
Jack Good (1968). A Five-Year Plan for Automatic Chess. Machine Intelligence Vol. 2 pp. 110-115, pdf from doczine

1970 ...

Mikhail Botvinnik (1970). Computers, Chess and Long-Range Planning. Springer-Verlag, New York.
Walter R. Reitman, James Kerwin, Robert Nado, Judith S. Reitman, Bruce Wilcox (1974). Goals and Plans in a Program for Playing Go. Proceedings of the 29th ACM Conference
Larry R. Harris (1975) The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play. 4. IJCAI 1975, reprinted (1988) in Computer Chess Compendium
Jacques Pitrat (1977). A Chess Combination Program Which Uses Plans. Artificial Intelligence, Vol 8, No. 3
Russell M. Church, Kenneth W. Church (1977). Plans, Goals, and Search Strategies for the Selection of a Move in Chess. Chess Skill in Man and Machine
David Wilkins (1979). Using Patterns and Plans to Solve Problems and Control Search. Ph.D. thesis, Computer Science Dept, Stanford University, Stanford, California, AI Lab Memo AIM-329
David Wilkins (1979). Using plans in chess. In Proceedings of the 1979 International Joint Conference on Artificial Intelligence, (Tokyo, Japan), pp. 960-967.
Jacques Pitrat (1979). A Program which Uses Plans for Finding Combinations in Chess. ICCA Newsletter, Vol. 2 No. 2

1980 ...

David Wilkins (1980). Using patterns and plans in chess. Artificial Intelligence, Vol. 14, pp. 165-203. Reprinted (1988) in Computer Chess Compendium
Jacques Pitrat (1980). The Behaviour of a Chess Combination Program using Plans. Advances in Computer Chess 2
Jonathan Schaeffer (1980). Long-Range Planning in Computer Chess. Master's thesis, Department of Computer Science, University of Waterloo
Sarah E. Goldin, Barbara Hayes-Roth (1980). Individual Differences in Planning Processes. RAND note N-1488
Jaime Carbonell (1981). Counterplanning: A Strategy-Based Model of Adversary Planning in Real-World Situations. Artificial Intelligence, Vol. 16
Kai von Luck, Bernd Owsnicki (1982). N.N.: A View of Planning in Chess. in Wahlster, GWAI-82
Helmut Horacek (1982). Construction of Planned Move Trees for Chess Pawn Endings. Sigart Newsletter 80, pp. 163-168.
E. D. Cherevik, Y. M. Shvyrkov (1982). An ABC of Planning : Fundamentals of the Theory and Methodology of Economic Planning. Progress Moscow
Hermann Kaindl (1982). Positional Long-Range Planning in Computer Chess. Advances in Computer Chess 3, also published as Hermann Kaindl (1983). Positional Long-Range Planning in Computer Chess. Vienna University of Technology, Austria.
Ivan Bratko (1984). Advice and Planning in Chess Endgames. Artificial and Human Thinking (eds. S. Amarel, A. Elithorn and R. Banerji). North-Holland.

1985 ...

Hans Berliner (1985). Goals, Plans, and Mechanisms: Non-symbolically in an Evaluation Surface. Presentation at Evolution, Games, and Learning, Center for Nonlinear Studies, Los Alamos National Laboratory, May 21.
Richard Korf (1987). Planning as Search: A Quantitative Approach. Artificial Intelligence, Vol. 33, pp. 65-88.
David Wilkins (1988). Practical Planning: Extending the Classical AI Planning Paradigm. (Morgan Kaufmann Series in Representation and Reasoning), amazon
Bruce Abramson (1989). Control Strategies for Two-Player Games. ACM Computing Surveys, Vol. 21, No. 2
Reiner Seidel (1989). A Model of Chess Knowledge - Planning Structures and Constituent Analysis. Advances in Computer Chess 5

1990 ...

David Wilkins (1991). Working notes on paradise chess patterns. Technical Note 509, AI Center, SRI International, 333 Ravenswood Ave., Menlo Park, CA 94025
Jens Christensen, Adam Grove (1991). A Formal Model Classical Planning. IJCAI-91, pdf
Jens Christensen (1991). Automatic Abstraction in Planning. Ph.D. thesis, Stanford University
Steven Walczak (1992). Pattern-Based Tactical Planning. IJPRAI, Vol. 6, No. 5
Stephen J.J. Smith, Dana S. Nau, Thomas A. Throop (1992). A hierarchical approach to strategic planning with non-cooperating agents under conditions of uncertainty. Proceedings of the First International Conference on AI Planning Systems
Stephen J.J. Smith, Dana S. Nau (1993). Strategic planning for imperfect-information games. Technical Report, University of Maryland, College Park
Mikhail Botvinnik, Evgeniĭ Dmitrievich Cherevik, Vasily Vladimirov, Vitaly Vygodsky (1994). Solving Shannon's Problem: Ways and Means. Advances in Computer Chess 7 » CC Sapiens
Andreas L. Opdahl, Bjornar Tessem (1994). Long-Term Planning in Computer Chess. Advances in Computer Chess 7

1995 ...

Stephen J.J. Smith, Dana S. Nau, Thomas A. Throop (1996). Total-Order Multi-Agent Task-Network Planning for Contract Bridge. AAAI 1996
Henry Kautz, Bart Selman (1996). Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. AAAI 1996, pdf
Chrilly Donninger (1996). CHE: A Graphical Language for Expressing Chess Knowledge. ICCA Journal, Vol. 19, No. 4
Jan van Reek (1997). Strategy in Chess. Schachfirma Fruth, Unterhaching, ISBN 3-9804896-9-8
Jan van Reek, Jos Uiterwijk, Jaap van den Herik (1998). Planning a Strategy in Chess. ICCA Journal, Vol. 21, No. 3
Stephen J.J. Smith, Dana S. Nau, Thomas A. Throop (1998). Computer Bridge: A Big Win for AI Planning. AI Magazine, Vol. 19, No. 2
Ian Frank (1998). Search and Planning Under Incomplete Information: A Study Using Bridge Card Play. Springer, Ph.D. thesis, University of Edinburgh

2000 ...

Mark Brockington (2000). Computer Chess Meets Planning. ICGA Journal, Vol. 23, No. 2
Alex B. Meijer, Henk Koppelaar (2001). Pursuing abstract goals in the game of Go. BNAIC 2001
Adi Botea (2002). Using Abstraction for Heuristic Search and Planning. Research Summary. In Proceedings of the 5th International Symposium on Abstraction, Reformulation, and Approximation SARA-02, volume 2371 of Lecture Notes in Artificial Intelligence, 326-327, Kananaskis, AB, Canada.
Ari Shapiro, Gil Fuchs, Robert Levinson (2002). Learning a Game Strategy Using Pattern-Weights and Self-play. CG 2002
Adi Botea, Martin Müller, Jonathan Schaeffer (2002). Using Abstraction for Planning in Sokoban. CG 2002
Joelle Pineau (2004). Tractable Planning Under Uncertainty: Exploiting Structure. Ph.D. thesis, Carnegie Mellon University, pdf

2005 ...

Adi Botea, Markus Enzenberger, Martin Müller, Jonathan Schaeffer (2005). Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators. Journal of Artificial Intelligence Research 24 (2005) 581-621, pdf
René Alquézar, A. Gonzalez Camargo, Alejandro González Romero (2006). Evolving Plans for the KRKa2 Chess Ending. Artificial Intelligence and Applications 2006
Adi Botea (2006). Improving AI Planning and Search with Automatic Abstraction. PhD Thesis, University of Alberta, pdf
Levente Kocsis, Csaba Szepesvári (2006). Bandit based Monte-Carlo Planning ECML-06, LNCS/LNAI 4212, pp. 282-293. introducing UCT, pdf
Frantisek Sailer, Michael Buro, Marc Lanctot (2007). Adversarial planning through strategy simulation. Computational Intelligence and Games, pdf
Zvi Retchkiman Königsberg (2007). A Combinatorial Game Mathematical Strategy Planning Procedure for a Class of Chess Endgames. International Mathematical Forum, Vol. 2, No. 68
Sylvain Gelly, Jean-Baptiste Hoock, Arpad Rimmel, Olivier Teytaud, Yann Kalemkarian (2008). The Parallelization of Monte-Carlo Planning - Parallelization of MC-Planning. ICINCO-ICSO 2008: 244-249, pdf, slides as pdf
Akihiro Kishimoto, Alex Fukunaga, Adi Botea (2009). Scalable, Parallel Best-First Search for Optimal Sequential Planning. In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS-2009) (Best Paper Award), pages 201-208, pdf
Gerhard Trippen (2009). Plans, Patterns and Move Categories Guiding a Highly Selective Search. Advances in Computer Games 12, pdf

2010 ...

Raghuram Ramanujan, Ashish Sabharwal, Bart Selman (2010). On Adversarial Search Spaces and Sampling-Based Planning. ICAPS 2010
Raghuram Ramanujan, Bart Selman (2011). Trade-Offs in Sampling-Based Adversarial Planning. ICAPS 2011, best paper, VideoLecture » UCT
Stefano Cianciulli, Stavros Vassos (2013). Planning for Interactive Storytelling Processes. ICAPS-2013, pdf
Arthur Guez, David Silver, Peter Dayan (2014). Better Optimism By Bayes: Adaptive Planning with Rich Models. arXiv:1402.1958v1
Arthur Guez, Nicolas Heess, David Silver, Peter Dayan (2014). Bayes-Adaptive Simulation-based Search with Value Function Approximation. NIPS 2014, pdf

2015 ...

Arthur Guez (2015). Sample-based Search Methods for Bayes-Adaptive Planning. Ph.D. Thesis, Gatsby Computational Neuroscience Unit, University College London, pdf

Forum Posts

Implementing Planning in an Engine by Tom Likens, CCC, February 04, 2004
Possible definition of planning by Charles Roberson, CCC, February 12, 2004

External Links

References

^ Лозунг «План — закон, выполнение — долг, перевыполнение — честь!» в здании Ольховско-Батьковского торфяного предприятия в Кубринске, Переславский район - «Plan is law, fulfillment is duty, over-fulfillment is honor!» Building Olkhovskaya Batkovsky - peat enterprise Kubrinsk, Pereslavskiy district, Photo by Н. Частов (N. Part), November 1997, Five-Year Plans for the National Economy of the Soviet Union - Wikipedia
^ Jan van Reek (1997). Strategy in Chess. Schachfirma Fruth, Unterhaching, ISBN 3-9804896-9-8
^ Jan van Reek, Jos Uiterwijk, Jaap van den Herik (1998). Planning a Strategy in Chess. ICCA Journal, Vol. 21, No. 3
^ Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions, (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6
^ Chess Quotes - Strategy
^ Judgment and Planning in Chess, games from Dr. Max Euwe's book Judgment and Planning in Chess. chessgames.com

What links here?

Page	Date Edited
Adi Botea	Jan 22, 2018
Alex B. Meijer	Aug 31, 2014
Andreas L. Opdahl	May 23, 2016
Anti-Computerchess	Jul 26, 2015
Arthur Guez	Dec 6, 2017
Artificial Intelligence	Apr 9, 2018
Bart Selman	Dec 26, 2017
Bernd Owsnicki-Klewe	Jan 20, 2018
Bjørnar Tessem	Apr 5, 2014
David McAllester	May 23, 2016
Dragon FR	Sep 9, 2016
Gerhard Trippen	Jun 8, 2015
Gil Fuchs	Sep 22, 2015
Giuseppe Maggiore	May 3, 2014
Goliath	Apr 5, 2017
Henk Koppelaar	Aug 31, 2014
Ian Frank	Feb 7, 2017
Ioannis Refanidis	Jan 19, 2016
Jacques Pitrat	Aug 7, 2015
James Kerwin	Sep 24, 2014
Jan van Reek	Aug 18, 2016
Jens Christensen	May 30, 2016
Joelle Pineau	Feb 12, 2018
Judith Spencer Olson	Sep 24, 2014
Knowledge	Jul 22, 2017
Learning	Feb 20, 2018
Manuela Veloso	Aug 5, 2015
Michael Borgstädt	Jan 24, 2016
N.N.	Jan 20, 2018
Nimzo	Dec 30, 2017
Olivier Teytaud	Jan 7, 2017
Opponent Model Search	Aug 14, 2017
Paradise	Nov 19, 2014
Pattern Recognition	Sep 8, 2017
Planner	Sep 24, 2012
Planning	Feb 12, 2018
Raghuram Ramanujan	Dec 26, 2017
Reinforcement Learning	Feb 12, 2018
Richard Korf	Dec 29, 2017
Robert Nado	Sep 24, 2014
Solomon Eyal Shimony	Sep 11, 2015
Stavros Vassos	May 25, 2015
Stephen J.J. Smith	Apr 7, 2014
Strategy	Jan 18, 2018
Symbolic	May 8, 2017
Tactics	Jan 12, 2018
Tom Likens	Mar 7, 2017
Wee Sun Lee	May 29, 2015
Yan Radovilsky	Sep 11, 2015
Zvi Retchkiman Königsberg	Feb 9, 2016

Up one Level

Retrograde Analysis

GerdIsenberg — Tue, 21 Mar 2017 20:26:58 GMT

Home * Knowledge * Retrograde Analysis

		Retrograde Analysis, a method in game theory to solve game positions for optimal play by backward induction from known outcomes. A sub-genre of solving certain chess problems uses retrograde analysis to determine which moves were played to reach a position, and for the proof game whether a position is legal in the sense that it could be reached by a series of legal moves from the initial position.
Retrograde analysis ^[1]

History

Algorithm

See also

Selected Publications

History

based on Lewis Stiller, Multilinear Algebra and Chess Endgames ^[2]

The mathematical justification for the retrograde analysis algorithm was already implicit in the 1912 paper of Ernst Zermelo ^[3]. Additional theoretical work was done by John von Neumann and Oskar Morgenstern ^[4].

The contemporary dynamic programming methodology, which defines the field of retrograde endgame analysis, was discovered by Richard E. Bellman in 1965 ^[5]. Bellman had considered game theory from a classical perspective as well ^[6] ^[7], but his work came to fruition in his 1965 paper, where he observed that the entire state-space could be stored and that dynamic programming techniques could then be used to compute whether either side could win any position.

Bellman also sketched how a combination of forward search, dynamic programming, and heuristic evaluation could be used to solve much larger state spaces than could be tackled by either technique alone. He predicted that Checkers could be solved by his techniques, and the utility of his algorithms for solving very large state spaces has been validated by Jonathan Schaeffer et al. in the domain of Checkers ^[8], Ralph Gasser in the domain of Nine Men’s Morris ^[9], and John Romein with Henri Bal in the domain of Awari ^[10]. The first retrograde analysis implementation was due to Thomas Ströhlein, whose important 1970 dissertation described the solution of several pawnless 4-piece endgames ^[11].

Algorithm

Retrograde analysis is the basic algorithm to construct Endgame Tablebases. A bijective function is used to map chess positions to Gödel numbers which index a database of bitmaps during construction and retrieval, in its simplest form based on a multi-dimensional array index. Following description is based on Ken Thompson's paper Retrograde Analysis of Certain Endgames with depth to mate (DTM) metric ^[12], and assumes White the winning side. Files of sets of chess positions, where a one-bit is associated with the Gödel number of a position, are successively manipulated during the iterative generation process:

Bi set of the latest newly found Black-to-move and lose in i moves positions
Wi set of the latest newly found White-to-move and win in i moves positions
B set of all currently known Black-to-move and lose positions, union of all Bi so far
W set of all currently known White-to-move and win positions, union of all Wi so far
Ji is temporary superset of Bi not necessarily lose positions

The algorithm starts in enumerating all Black-to-move checkmate positions B0 with the material configuration under consideration, an un-move generator is used to to build predecessor or parent positions. The un-move generation is similar to move generation, with the difference that it is illegal to start in check, but legal to un-move into check, and illegal to capture, but legal to un-capture by leaving an opponent piece behind.

for (i=0; Bi; i++)

Every parent of a Bi position is a White-to-move won position - newly-won positions Wi+1 are parents of a Bi not (yet) in W
Wi+1 becomes subset of W
Every parent of a Wi+1 position is a Black-to-move and lose position if Black wanted to mate himself, stored in Ji+1
Only if all successors (by generating and making legal moves ^[13]) of a Ji+1 position are member of W, the Ji+1 position becomes member of Bi+1 and B

The algorithm terminates, if no more newly predecessor positions were found, that is either Wi+1 or Bi+1 stay empty. Each one-bit in W or B correspondents to a White-to-move and won or Black-to-move and lose position. Remaining zero bits indicate either a draw, White-to-move and lose, Black-to-move and won, or illegal positions.

Selected Publications

1910 ...

Ernst Zermelo (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels Proc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge Univ. Press 1913, 501–504. Translation: On an Application of Set Theory to the Theory of the Game of Chess.

1920 ...

Dénes Kőnig (1927). Über eine Schlussweise aus dem Endlichen ins Unendliche. Acta Scientiarum Mathematicarum (University of Szeged)

1940 ...

John von Neumann, Oskar Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ

1960 ...

Richard E. Bellman (1965). On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers. PNAS
Vladimir E. Alekseev (1969). Compilation of Chess Problems on a Computer. Technical translation FSTC-HT-23-124-69, US Army, NTIS AD 689470 (Problemy Kibernetiki, 19, 1967)

1970 ...

Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
Edward Komissarchik, Aaron L. Futer (1974). Ob Analize Ferzevogo Endshpilya pri Pomoshchi EVM. (Analysis of a queen endgame using an IBM computer) Problemy Kybernetiki, Vol. 29, pp. 211-220. English translation by Christian Posthoff, revised in ICCA Journal, Vol. 9, No. 4 (1986)
A. G. Alexandrov, A. M. Baraev, Ya. Yu. Gol'fand, Edward Komissarchik, Aaron L. Futer (1977). Computer analysis of rook end game. Avtomatika i Telemekhanika, No. 8, 113–117
Thomas Ströhlein, Ludwig Zagler (1977). Analyzing games by Boolean matrix iteration. Discrete Mathematics, Vol. 19, No. 2
Thomas Ströhlein, Ludwig Zagler (1978). Ergebnisse einer vollstandigen Analyse von Schachendspielen: König und Turm gegen König, König und Turm gegen König und Läufer. Report, Institut für Informatik, Technical University of Munich (German)
Aaron L. Futer (1978). Programming endgames with few pieces. Soviet Physics. Doklady, No. 23
Vladimir Arlazarov, Aaron L. Futer (1979). Computer Analysis of a Rook End-Game. Machine Intelligence 9 (eds. Jean Hayes Michie, Donald Michie and L.I. Mikulich), pp. 361-371. Ellis Horwood, Chichester. Reprinted in Computer Chess Compendium
Raymond Smullyan (1979). The Chess Mysteries of Sherlock Holmes. Alfred A. Knopf, New York ^[14]

1980 ...

Raymond Smullyan (1981). The Chess Mysteries of the Arabian Knights . Alfred A. Knopf, New York ^[15]
Max Bramer, B. E. P. Alden (1982). A Program for Solving Retrograde Analysis Chess Problems. Advances in Computer Chess 3 ^[16]
Ken Thompson (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3, pdf
Edward Komissarchik, Aaron L. Futer (1986). Computer Analysis of a Queen Endgame. ICCA Journal, Vol. 9, No. 4
Lewis Stiller (1988). Massively Parallel Retrograde Endgame Analysis. BUCS Tech. Report #88-014, Boston University, Computer Science Department.
B. E. P. Alden, Max Bramer (1988). An Expert System for Solving Retrograde-Analysis Chess Problems. International Journal of Man-Machine Studies, Vol. 29, No. 2
Michael Schlosser (1988). Computers and Chess-Problem Composition. ICCA Journal, Vol. 11, No. 4
David Forthoffer, Lars Rasmussen, Sito Dekker (1989). A Correction to some KRKB-Database Results. ICCA Journal, Vol. 12, No. 1
Ingo Althöfer (1989). Retrograde Analysis and two Computerizable Definitions of the Quality of Chess Games. ICCA Journal, Vol. 12, No. 2

1990 ...

László Lindner, Michael Schlosser (1991). New Ideas in Problem Solving and Composing Programs. Advances in Computer Chess 6
Michael Schlosser (1991). Can a Computer Compose Chess Problems? Advances in Computer Chess 6
Lewis Stiller (1991). Some Results from a Massively Parallel Retrograde Analysis. ICCA Journal, Vol. 14, No. 3
Ralph Gasser (1991). Applying Retrograde Analysis to Nine Men’s Morris. Heuristic Programming in AI 2
Robert Lake, Jonathan Schaeffer, Paul Lu (1993). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Technical Report, TR93-13, ps
Robert Lake, Jonathan Schaeffer, Paul Lu (1994). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess 7
Henri Bal, Victor Allis (1995). Parallel Retrograde Analysis on a Distributed System. Supercomputing ’95, San Diego, CA.
Lewis Stiller (1996). Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf
Dietmar Lippold (1996). Legality of Positions of Simple Chess Endgames. zipped pdf ^[17]
Dietmar Lippold (1997). The Legitimacy of Positions in Endgame Databases. ICCA Journal, Vol. 20, No. 1
Hiroyuki Iida, Jin Yoshimura, Kazuro Morita, Jos Uiterwijk (1998). Retrograde Analysis of the KGK Endgame in Shogi: Its Implications for Ancient Heian Shogi. CG 1998
Christoph Wirth, Jürg Nievergelt (1999). Exhaustive and Heuristic Retrograde Analysis of the KPPKP Endgame. ICCA Journal, Vol. 22, No. 2

2000 ...

Roel van der Goot (2000). Awari Retrograde Analysis. CG 2000
Haw-ren Fang, Tsan-sheng Hsu, Shun-chin Hsu (2000). Construction of Chinese Chess Endgame Databases by Retrograde Analysis. CG 2000
Bruno Bouzy (2001). Go Patterns Generated by Retrograde Analysis. 6th Computer Olympiad Workshop, pdf
Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3 ^[18] ^[19]
Ren Wu, Don Beal (2001). Parallel Retrograde Analysis on Different Architectures. IEEE 10th Conference in High Performance Distributed Computing pp. 356-362, August 2001
Haw-ren Fang, Tsan-sheng Hsu, and Shun-Chin Hsu (2001). Construction of Chinese Chess Endgame Databases by Retrograde Analysis. Lecture Notes in Computer Science 2063: CG 2000
Ren Wu, Don Beal (2002). A memory efficient retrograde algorithm and its application to solve Chinese Chess endgames. More Games of No Chance edited by Richard J. Nowakowski
Thomas Lincke (2002). Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich, pdf
John Romein, Henri Bal (2003). Solving the Game of Awari using Parallel Retrograde Analysis. IEEE Computer, Vol. 36, No. 10, pp. 26–33
Ping-hsun Wu, Ping-Yi Liu, Tsan-sheng Hsu (2004). An External-Memory Retrograde Analysis Algorithm. CG 2004

2005 ...

Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis, Supervisor Peter Bro Miltersen, Aarhus University, pdf
James Glenn, Haw-ren Fang, Clyde Kruskal (2006). A Retrograde Approximation Algorithm for One-Player Can’t Stop. CG 2006
James Glenn, Haw-ren Fang, Clyde Kruskal (2007). A Retrograde Approximation Algorithm for Two-Player Can't Stop. CGW 2007, pdf
Haw-ren Fang, James Glenn, Clyde Kruskal (2008). Retrograde approximation algorithms for Jeopardy stochastic games. ICGA Journal, Vol. 31, No. 2, pdf
Noam D. Elkies, Richard P. Stanley (2008). Chess and Mathematics. excerpt, 6 Retrograde Analysis, pdf
Marko Maliković (2008). Developing Heuristics for Solving Retrograde Chess Problems. Seminar on Formal Methods and Applications, Varaždin, Croatia
Dan Heisman (2009). Steinitz, Zermelo, and Elkies. pdf from ChessCafe.com, on Wilhelm Steinitz, Ernst Zermelo and Noam Elkies

2010 ...

Victor Zakharov, Vladimir Makhnychev (2010). A Retroanalysis Algorithm for Supercomputer Systems on the Example of Playing Chess. Software Systems and Tools, Vol. 11 (Russian)
Ping-hsun Wu, Ping-yi Liu, Tsan-sheng Hsu (2010). An External-memory Retrograde Analysis Algorithm. slides as pdf
Paolo Ciancarini, Gian Piero Favini (2010). Retrograde analysis of Kriegspiel endgames. IEEE Conf. on Computational Intelligence and Games, Copenhagen.
Marko Maliković, Mirko Čubrilo (2010). What Were the Last Moves? International Review on Computers and Software
Marko Maliković, Mirko Čubrilo (2010). Solving Shortest Proof Games by Generating Trajectories using Coq Proof Management System. Proceedings of 21st Central European Conference on Information and Intelligent Systems, Varaždin, Croatia ^[20]
Marko Maliković (2011). Automated Reasoning about Retrograde Chess Problems using Coq. Fourth Workshop on Formal and Automated Theorem Proving and Applications, Belgrade, Serbia, slides as pdf
Jan van Rijn, Jonathan K. Vis (2013). Complexity and Retrograde Analysis of the Game Dou Shou Qi. BNAIC 2013 ^[21]
Jan van Rijn, Jonathan K. Vis (2014). Endgame Analysis of Dou Shou Qi. ICGA Journal, Vol. 37, No. 2, pdf

2015 ...

Michael Hartisch (2015). Impact of Rounding during Retrograde Analysis for a Game with Chance Nodes: Karl’s Race as a Test Case. ICGA Journal, Vol. 38, No. 2 » Games, EinStein würfelt nicht! ^[22]
Michael Hartisch, Ingo Althöfer (2015). Optimal Robot Play in Certain Chess Endgame Situations. ICGA Journal, Vol. 38, No. 3

Forum Posts

1995 ...

retrograde analysis by Stefan Schroedl, rgcc, August 15, 1995

2000 ...

reverse engineering by NoKetch, rgcc, June 16, 2000
EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001 ^[23]
Re: How endgame tablebases work by Bruce Moreland, rgcc, July 19, 2001
Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001 ^[24] ^[25]
Wu/Beal predates Koistinen by Guy Haworth, CCC, December 04, 2001
Question about retrograde analysis algorithm for endgame databases by mathpolymath, rec.games.abstract, April 24, 2002 ^[26]

2005 ...

Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
Could this program be written? by Steven Edwards, CCC, August 24, 2008
Retrograde analysis by Geolm, CCC, November 04, 2008

2010 ...

Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010
Reverse move generation by Kostas Oreopoulos, December 30, 2014 » Move Generation
Re: Reverse move generation by Harm Geert Muller, December 30, 2014

2015 ...

Position Legally Reachable? by Mark Lefler, CCC, March 21, 2017

External Links

Retrograde Analysis

Programs

Euclide 1.11 - Home by Étienne Dupuis » Euclide
Freezerchess.com - Endgame Analysis beyond Databases by Eiko Bleicher » Freezer
Natch - Checking proof games by Pascal Wassong » Natch
Retractor a program for Retrograde Analysis chess problems by Chad Whipkey and Theodore Hwa » Retractor

Induction

Retrograde

Retrograde (disambiguation) from Wikipedia
Retrograde motion from Wikipedia
Apparent retrograde motion from Wikipedia
Retrograde (music) from Wikipedia
Darryl Reeves - The Mercury Sessions - Retrograde, July 22, 2011 - Churchill Grounds - Atlanta, GA, YouTube Video
Darryl Reeves, Kenny Banks, Joel Powell, Kenton "Boom" Bostick

Analysis

References

^ Ретроградный анализ. / Retrograde analysis, Flickr: Fotostream by Segaboy
^ Lewis Stiller (1996). Multilinear Algebra and Chess Endgames. Games of No Chance edited by Richard J. Nowakowski, pdf
^ Ernst Zermelo (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels Proc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge Univ. Press 1913, 501–504. Translation: On an Application of Set Theory to the Theory of the Game of Chess
^ John von Neumann and Oskar Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ
^ Richard E. Bellman (1965). On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers. PNAS
^ Richard E. Bellman (1954). On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems. Technical Report P-473, RAND Corporation, Santa Monica, CA
^ Richard E. Bellman (1957). The Theory of Games. Technical Report P-1062, RAND Corporation, Santa Monica, CA
^ Robert Lake, Jonathan Schaeffer, Paul Lu (1994). Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess 7
^ Ralph Gasser (1991). Applying Retrograde Analysis to Nine Men’s Morris. Heuristic Programming in AI 2
^ John Romein, Henri Bal (2003). Solving the Game of Awari using Parallel Retrograde Analysis. IEEE Computer, Vol. 36, No. 10
^ Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
^ Ken Thompson (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3
^ dubbed "grandfather" method, Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010
^ Smullyan Problem in Sherlock Holmes book by Christopher Heckman, rgcc, January 18, 2013
^ Retrospektive (Retroanalyse) from German Wikipedia, Raymond Smullyan, Manchester Guardian, 1957
^ Jaap van den Herik (1981). Progress in Computer Chess. AISB Quarterly, reprinted in ICCA Newsletter, Vol. 4. No. 3, pdf
^ referred in Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis
^ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001, with reference to Computing endgames with few men by Urban Koistinen
^ Wu / Beal retrograde analisys algorithm by Alvaro Jose Povoa Cardoso, Winboard Forum, March 10, 2007
^ Coq from Wikipedia
^ Jungle (board game) from Wikipedia
^ Karl's Race A Game on Karl Scherer's Alternating Tiling by Ingo Althöfer, 2006
^ Computing endgames with few men by Urban Koistinen
^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
^ Computing endgames with few men by Urban Koistinen
^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3
^ EGTB: Better algorithm by Urban Koistinen, CCC, April 07, 2001
^ Generating egtbs ICGAJ by Tony Werten, CCC, December 04, 2001
^ Ren Wu, Don Beal (2001). Fast, Memory-efficient Retrograde Algorithms. ICGA Journal, Vol. 24, No. 3

What links here?

Page	Date Edited
Aaron L. Futer	Dec 23, 2014
Algorithms	May 5, 2017
Alvaro Cardoso	Jan 12, 2018
Awari	Feb 14, 2017
Chess	Jan 21, 2018
Chess Problem Solving Engines	Apr 21, 2017
Chess Problems, Compositions and Studies	Feb 19, 2018
Christoph Wirth	Jan 8, 2017
Connection Machine	Oct 12, 2016
Corresponding Squares	Oct 9, 2017
Don Beal	Jul 27, 2017
Dynamic Programming	Feb 11, 2018
Edward Komissarchik	May 20, 2016
EinStein würfelt nicht!	Aug 11, 2017
Endgame	Sep 18, 2017
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Ernst Zermelo	Sep 8, 2014
Games	Feb 20, 2018
Guy Haworth	Nov 20, 2017
Hash Table	Jan 1, 2018
Henri Bal	Aug 5, 2016
History	Jan 2, 2018
Holmes	Apr 24, 2014
ICGA Journal	Dec 21, 2017
Interior Node Recognizer	Mar 12, 2018
Iteration	May 5, 2017
Jan van Rijn	Dec 8, 2014
Joe Leslie-Hurd	Aug 15, 2013
Jonathan K. Vis	Dec 8, 2014
Kaissa	Apr 9, 2018
Knowledge	Jul 22, 2017
KPK	May 12, 2016
KRK	Nov 26, 2016
Lewis Stiller	Oct 11, 2016
Ludwig Zagler	Sep 6, 2017
Mark Lefler	Nov 23, 2017
Mark Watkins	Dec 6, 2017
Marko Maliković	Aug 10, 2013
Mathematician	Apr 9, 2018
Michael Hartisch	Aug 11, 2017
Mirko Čubrilo	Aug 10, 2013
Move Generation	Jan 29, 2018
Nine Men’s Morris	Dec 17, 2016
Patrick Schoo	May 25, 2016
Ping-hsun Wu	Jun 8, 2015
Proof-number search	Jan 22, 2018
Ralph Gasser	Jan 8, 2017
Raymond Smullyan	Nov 28, 2017
Ren Wu	Jul 23, 2017
Retrograde Analysis	Mar 21, 2017
Richard E. Bellman	Mar 15, 2017
Robots	Feb 20, 2018
Shun-Chin Hsu	Jul 22, 2017
Space-Time Tradeoff	Jun 17, 2015
Steven Edwards	Aug 26, 2017
Syzygy Bases	Apr 19, 2018
Thomas Lincke	Dec 22, 2016
Thomas Ströhlein	May 24, 2016
Thompson's Databases	Dec 24, 2014
Transposition	Jun 8, 2015
Yakov Konoval	Apr 28, 2009

Up one Level

Scorpio Bitbases

GerdIsenberg — Mon, 12 Mar 2018 18:38:47 GMT

Home * Knowledge * Endgame Tablebases * Scorpio Bitbases

		Scorpio Bitbases, are compact endgame bitbases created by Daniel Shawul with WDL information of up to 5-men, well suited to probe inside the search as applied in Daniel's engine Scorpio. The 5-men WDL holds in 200 MB. In order to make progress in won egtb-positions near the root, various evaluation heuristics are necessary to modify winning scores accordantly, considering material, ply-distance to the root, pawn closeness to promotion, distance of pieces to the opponent king, etc. ^[1] . Scorpio Bitbases are open source, since October 2013 distributed under the BSD license ^[2] . Under Windows, probing is encapsulated via a Dynamic-link library, which already provides a heuristic score instead of pure WDL information in order to make progress at the root without the need to probe huge DTC/DTM tablebases. As of January 2014, Daniel finished the 6-men Scorpio Bitbases, available from Joshua Shriver's torrent site ^[3] ^[4].
Scorpio constellation ^[5]

Forum Posts

2005 ...

Bitbases - yace, scorpio, gambitfruit by Bernhard Bauer, CCC, December 06, 2005
Re: Open Source bitbase program by Daniel Shawul, CCC, April 12, 2007
Scorpio BBs, licenses by Zach Wegner, CCC, January 28, 2008
Scorpio endgame bitbase specs? by Ilari Pihlajisto, CCC, December 02, 2008
New Scorpio bitbase files by Dann Corbit, CCC, March 09, 2009
Scorpio bitbases by Matthias Gemuh, CCC, April 06, 2009
Scorpio bitbases with linux. Any success? by Joona Kiiski, CCC, April 29, 2009
EGBB implementation by Michael Hoffmann, CCC, September 24, 2009

2010 ...

Some tablebase formats by BB+, OpenChess Forum, November 25, 2010
bitbase access by Scorpio versions... Dan Shawul? by Ernest Bonnem, CCC, May 28, 2012
pawn enumeration by Daniel Shawul, CCC, July 24, 2012
Re: Search with bitbase by Daniel Shawul, CCC, September 05, 2012
Houdini 3 with Scorpio Bitbases Question by Milton Zucker, CCC, October 16, 2012

2013

Re: syzygy question (for Ronald) by Daniel Shawul, CCC, October 04, 2013
Scorpio Egbb Thread by Joshua Shriver, CCC, October 07, 2013
What happens using egbb by Kai Laskos, CCC, October 12, 2013
Scorpio E.G.T.B. by AxeFever, Rybka Forum, October 22, 2013
Syzygy / egbb discussion by Daniel Shawul, CCC, October 23, 2013 » Syzygy Bases
Scorpio bitbases question by Harm Geert Muller, CCC, December 25, 2013

2014 ...

Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014
50 Gb 6-men scorpio bitbases available by stackOVERFLOW, OpenChess Forum, January 14, 2014
Stockfish goes EGBB by Daniel Shawul, CCC, January 29, 2014 » Stockfish
Scorpio & egbb issue (OSX) by Max May, CCC, February 01, 2014 » KBNK Endgame
Performance of Syzygy and Scorpio by Kai Laskos, CCC, February 04, 2014 » Syzygy Bases
Problem position using Scorpio Egbbs by Ross Boyd, CCC, March 11, 2018

External Links

Scorpio Chess and Nebiyu Alien
dshawul/egbbdll · GitHub
dshawul/Scorpio · GitHub includes Six men egbb code
OICS Chess and EGTB Tracker Statistics by Joshua Shriver ^[6]
Index of /tablebases/scorpio by kingliveson

References

^ Re: Search with bitbase by Daniel Shawul, CCC, September 05, 2012
^ Added liscense by Daniel Shawul, CCC, October 04, 2013
^ Scorpio 6men EGBB Now available by Joshua Shriver, CCC, January 14, 2014
^ dshawul/Scorpio · GitHub includes Six men egbb code
^ Scorpio constellation 1782, from Bode's revised and enlarged edition of Fortin's small star atlas of Flamsteed
^ BitTorrent from Wikipedia

What links here?

Page	Date Edited
Chess for Android	Mar 1, 2018
Chiron	Sep 24, 2017
Daniel Shawul	Jan 28, 2018
DayDreamer	Aug 22, 2016
Edwards' Tablebases	Sep 26, 2016
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Ernest Bonnem	Jan 26, 2014
Fridolin	Jun 27, 2017
Fruit Reloaded	Dec 8, 2017
Gambit Fruit	Mar 29, 2013
Gaviota Tablebases	Apr 22, 2018
Joshua Shriver	Nov 24, 2017
Kai Laskos	Jan 21, 2018
KBNK Endgame	Nov 26, 2016
Lomonosov Tablebases	May 20, 2016
Nalimov Tablebases	Dec 23, 2016
Ross Boyd	Mar 12, 2018
Scorpio	Mar 28, 2018
Scorpio Bitbases	Mar 12, 2018
Sinobyl	Jul 3, 2014
Sloppy	Sep 17, 2016
Stockfish	Apr 7, 2018
Syzygy Bases	Apr 19, 2018

Up one level

Syzygy Bases

GerdIsenberg — Thu, 19 Apr 2018 18:41:57 GMT

Home * Knowledge * Endgame Tablebases * Syzygy Bases

		Syzygy Bases, ^[1] a compact six piece endgame database developed by Ronald de Man, published April 01, 2013, but not as April Fool. Syzygy Bases consist of two sets of files, WDL files storing win/draw/loss information considering the fifty-move rule for access during search, and DTZ files with distance-to-zero information for access at the root. The generator is released under the GNU General Public License Version 2, the thread safe probing code is released without restrictions ^[2] . As of February 2015, all 3-5 and most important 6-men Syzygy Bases are commercially available on 4 DVDs by ChessBase as Endgame Turbo 4 for their products Deep Fritz 14, Komodo Chess 8, Houdini 4 or ChessBase 12/13 ^[3] ^[4] .
Syzygy - Three Planets Dance Over La Silla ^[5]

File Sizes

Men		WDL		DTZ
5		378 MiB		561 MiB
6		68.3 GiB		81.9 GiB

The additional use of Haswell's BMI2 Parallel Bits Deposit (PDEP) and Parallel Bits Extract (PEXT) instructions, or their slower serial implementations, allows further size reduction ^[6] .

Generation of 7-men tablebases would require about 1 TB of RAM. Generation time will be about 64 x per table, which means around 175 x time total ^[7] . Ronald de Man isn't interested in creation of 7-men Syzygy ^[8] .

During the Search

During the search, with the WDL tables stored on SSD ^[9] , it is possible to probe the tables at all depths without much slowdown. They have been tested in Ronald de Man's engine Sjaak (playing on FICS as TrojanKnight(C)) a couple of months quite successfully, don't probing in quiescence search.

At the Root

At the root, since pure DTZ50-optimal play (i.e. minimaxing the number of moves to the next capture or pawn move by either side) can be very unnatural, it might be desirable to let the engine search on the winning moves until it becomes clear that insufficient progress is being made and only then switch to DTZ-optimal play (e.g. by detecting repetitions and monitoring the halfmove clock) ^[10] .

Quotes

by Ronald de Man in a reply to Guy Haworth, April 06, 2013 ^[11] :

I create both WDL and DTZ in one go, so I don't use WDL in the creation of DTZ. The algorithm used is the grandfather algorithm with 2 plies per iteration (I think HGM calls this leapfrogging, but I might be wrong). I tried the outcounting method, but it didn't seem to be competitive (and it makes things more complicated). ^[12] ^[13]
A pure WDL/DTZ pair is not of much use for creating WDL50+/DTZ50+. I create tables in RAM that have all the information necessary for WDL50+ and DTZ50+, then permute them to different indexing schemes and compress. I do test runs on subsets of the data to find good permutations. (The idea to try permutations is from Jesper Torp Kristensen's master thesis.) ^[14] ^[15]

Endgame News

In his 2014 Chess Endgame News in ICGA Journal, Vol. 37, No. 2 ^[16] , Guy Haworth classified Syzygy Bases as new data in three ways:

5-valued scale for evaluating positions in the context of the FIDE 50-move rule (50mr) which constrains the length of phases of play
+2 ≡ unconditional win for the side to move
+1 ≡ ‘win’ which can be frustrated by best play and a 50mr draw-claim
_0 ≡ unconditional draw
-1 ≡ ‘loss’ saved by a 50mr draw-claim
-2 ≡ unconditional loss
depths for ‘50mr draw’ positions with value ±1
depths in symmetric, information-preserving ply ‘p’

and further gives some news about early software bugs and glitches concerning ChessBase products, and the importance of MD5 to check the EGT integrity.

Fathom

Fathom is a stand-alone Syzygy based probing tool and API by Basil Falcinelli, introduced in November 2015 along with his Gull 3 release ^[17] . Unlike the original tbprobe code, Fathom does not necessarily require the callee to provide move generation functionality. The new modifications and extensions to Ronald de Man's original code which can be "redistributed and/or modified without restrictions", are released under the permissive MIT License. The API consists of three functions ^[18] :

tb_init initializes the tablebase
tb_probe_wdl probes the Win-Draw-Loss (WDL) table for a given position
tb_probe_root probes the Distance-To-Zero (DTZ) table for the given position.

Jon Dart has a fork of Fathom with some bug fixes and enhancements ^[19].
.
See also

Publications

Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 1
Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 2
Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 3 » Fritz 14

Forum Posts

2013 ...

New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013 ^[20]
New 6-piece tablebase generator by syzygy, CCRL Discussion Board, April 01, 2013
Re: PEXT Bitboards by Ronald de Man, CCC, June 07, 2013 » BMI2 - PDEP, BMI2 - PEXT
Syzygy EGTB's via Torrent Thread by Joshua Shriver, CCC, September 11, 2013
Syzygy tablebases, work in Stockfish? by Jose Mº Velasco, CCC, September 23, 2013 » Stockfish
Building Syzygy bases by higgs, Rybka Forum, October 12, 2013
tablebase caching / mmap() / page cache by Ronald de Man, CCC, October 13, 2013 » Memory
Syzygy endgame tables: Generation and first impressions by Mike Scheidl, CCC, October 15, 2013
deMan TB Path and Cache by Matthias Gemuh, CCC, October 19, 2013
syzygy TB (3-4-5 men only) download link ? by MarshallArts, Rybka Forum, October 21, 2013
rkiss and other dependencies in syzygy by Don Dailey, CCC, October 23, 2013
Syzygy / egbb discussion by Daniel Shawul, CCC, October 23, 2013 » Scorpio Bitbases
Manual: How to use Syzygy (or any other) 6-men without SSD by Milos Stanisavljevic, CCC, November 16, 2013
potential deadlock in syzygy reference implementation by Richard Vida, CCC, November 23, 2013
Re: A note for C programmers by Marcel van Kervinck, CCC, November 27, 2013
Stockfish Syzygy: how to interpret mates? by Jouni Uski, CCC, December 01, 2013 » Stockfish, Mate Scores
Problem with 6-piece syzygy-bases using wine by Bernhard Bauer, CCC, December 05, 2013 ^[21]
ChessGUI 0.245f is available by Matthias Gemuh, CCC, December 14, 2013 » ChessGUI
Syzygybases suitable for win32-systems? by Norbert Raimund Leisner, CCC, December 17, 2013
Syzygy Tablebases list of importance by chri$, OpenChess Forum, December 21, 2013
Syzygy options by Harm Geert Muller, CCC, December 27, 2013

2014

Ideal Syzygy Probe Depth ? (using SSD) by Anil V Dharan, CCC, January 14, 2014
SYZYGY Base question by Ingo Bauer, CCC, January 19, 2014
problem with syzygy tablebases by Youri Matiounine, CCC, February 01, 2014
Performance of Syzygy and Scorpio by Kai Laskos, CCC, February 04, 2014 » Scorpio Bitbases
A question about syzygy by Enrico Tognoni, CCC, February 26, 2014
A question about syzygy 6 men and partial use by Enrico Tognoni, CCC, February 26, 2014
Syzygy on RAM Drive by Kai Laskos, CCC, May 23, 2014 » Stockfish, Komodo 7, Houdini 4
Re: Syzygy tb generator for windows by syzygy, CCRL Discussion Board, June 01, 2014
Question about syzygy bases by Gabor Szots, CCC, June 02, 2014
Re: 7-piece syzygy by syzygy, CCRL Discussion Board, July 03, 2014
Question on Stockfish and SyzygyCache UCI option by Erfuk Neuni, CCC, December 07, 2014
USB 3 Storage for Syzygy WDL files by Louis Zulli, CCC, December 13, 2014 » USB 3.0

2015 ...

Komodo 8 - 5-men Syzygy tablebases by Andreas Strangmüller, CCC, January 10, 2015 » Komodo 8
Problem with SF6 and Syzygy TB by Forrest Hoch, CCC, April 01, 2015 » Stockfish
SD Syzygy by Ted Summers, CCC, April 26, 2015
5 men Syzygy on USB 3.0 Flash Drive by Kai Laskos, CCC, May 09, 2015
Re: how to probe egtb from console? by Ronald de Man, CCC, May 15, 2015 » python-chess
Gull 3 Linux+Syzygy and Fathom released by Basil Falcinelli, CCC, November 20, 2015 » GullChess, Fathom
Syzygy probing code: DTZ in some cursed endgames off by one? by Niklas Fiekas, CCC, December 06, 2015

2016

Re: Squash anyone? by Ronald de Man, CCC, February 07, 2016 ^[22]
My troubles with MultiPV and Syzygy in Stockfish 7 by Árpád Rusz, CCC, February 16, 2016
Stockfish 7 and partial 6 piece syzygy problem? by Jouni Uski, CCC, March 01, 2016 » Stockfish
Re: Stockfish 7 and partial 6 piece syzygy problem? by Marco Costalba, CCC, September 01, 2016
Arasan Syzygy support (working with Windows, too) by Jon Dart, CCC, March 10, 2016 » Arasan
Question to syzygy author by Marco Costalba, CCC, April 24, 2016
syzygy question by Robert Hyatt, CCC, May 04, 2016
question about syzygy probing by Marco Belli, CCC, May 21, 2016
Natural TB by Marco Costalba, CCC, May 29, 2016 » Stockfish
syzygy questions by Robert Hyatt, CCC, July 06, 2016
How texel probes endgame tablebases by Peter Österlund, CCC, July 16, 2016 » Gaviota Tablebases, Texel
Syzygy and draw by repetition by Jon Dart, CCC, July 22, 2016 » Draw, Repetitions
Syzygy question by J. Wesley Cleveland, CCC, September 03, 2016
Suicide chess tablebases (stalemated player wins) by Niklas Fiekas, CCC, October 25, 2016 » Losing Chess
Syzygy tablebases by Andy Leese, CCC, December 01, 2016
Help for Syzygy probe? by Ted Wong, CCC, December 04, 2016 » Fathom

2017

6-men Syzygy from HDD and USB 3.0 by Kai Laskos, CCC, April 04, 2017 » Komodo, Playing Strength, USB 3.0
Fathom memory usage by Álvaro Begué, CCC, June 22, 2017» Fathom
RuyDos with support for syzygy tablebases by Álvaro Begué, CCC, June 23, 2017 » RuyDos
Natural TB (take 2) by Marco Costalba, CCC, August 22, 2017 » Stockfish
Probing tablebases through USB 3.0 by Jon Fredrik Åsvang, CCC, September 25, 2017 » USB 3.0
understanding DTZ by Alexandru Mosoi, CCC, October 06, 2017 » DTZ, Fathom
Is there now coming changes to syzygy databases? by Jouni Uski, CCC, November 13, 2017 » DTM, CFish
How to Download Syzygy Endgame Tablebase Files by Daniel Johnson, CCC, December 23, 2017

2018

The history of Syzygy tablebases by Isaac Haïk Dunn, CCC, March 06, 2018
7-men Syzygy attempt by Bojun Guo, CCC, March 10, 2018
Syzygy implementations of top engines by Kai Laskos, CCC, March 14, 2018
Probing the Syzygy tablebase - beginners question by Andreas Matthies, CCC, April 16, 2018

External Links

Tablebase

syzygy1/tb · GitHub by Ronald de Man
jromang · GitHub by Jean-Francois Romang has a fork from syzygy1/tb
python-chess/syzygy.py at master · niklasf/python-chess · GitHub by Niklas Fiekas, Python implementation of probing code » python-chess
niklasf/syzygy-tables.info · GitHub by Niklas Fiekas, GUI and public API for Syzygy probing
Syzygy endgame tablebases Web Interface - Syzygy online lookup
OICS Chess and EGTB Tracker Statistics by Joshua Shriver ^[23]
Endgame Tablebases Online by Kirill Kryukov
Index of /tablebases/syzygy (3,4,5) by kingliveson
tablebase.sesse.net by Sesse

Fathom

GitHub - basil00/Fathom: Syzygy TB probe tool by Basil Falcinelli
jdart1/Fathom · GitHub by Jon Dart (with some bug fixes and enhancements)

ChessBase

Syzygy Tablebases: newest, fastest, smallest by Albert Silver, ChessBase News, February 08, 2015
Syzygy tablebases: maximizing performance by Albert Silver, ChessBase News, February 10, 2015
Endgame Turbo 4 by ChessBase

Misc

References

^ Re: New 6-piece tablebases by Ronald de Man, CCC, April 10, 2013
^ New 6-piece tablebases by Ronald de Man, CCC, April 01, 2013
^ Endgame Turbo 4 by ChessBase
^ Syzygy Tablebases: newest, fastest, smallest by Albert Silver, ChessBase News, February 08, 2015
^ It’s a real treat for photographers and astronomers alike: our skies are currently witnessing a phenomenon known as a syzygy — when three celestial bodies (or more) nearly align themselves in the sky. When celestial bodies have similar ecliptic longitude, this event is also known as a triple near-conjunction. Of course, this is just a trick of perspective, but this doesn't make it any less spectacular. In this case, these bodies are three planets, and the only thing needed to enjoy the show is a clear view of the sky at sunset. Luckily, this is what happened for ESO photo ambassador Yuri Beletsky, who had the chance to spot this spectacular view from ESO's La Silla Observatory in northern Chile on Sunday May 26 , 2013. Above the round domes of the telescopes, three of the planets in our Solar System — Jupiter (top), Venus (lower left), and Mercury (lower right) — were revealed aftersunset, engaged in their cosmic dance. An alignment like this happens only once every several years. The last one took place in May 2011, and the next one will not be until October 2015. This celestial triangle was at its best over the last week of May, but you may still be able to catch a glimpse of the three planets as they form ever-changing arrangements during their journey across the sky - source Three Planets Dance Over La Silla | ESO, Syzygy (astronomy) from Wikipedia
^ Re: PEXT Bitboards by Ronald de Man, CCC, June 07, 2013
^ Re: Syzygy tb generator for windows by syzygy, CCRL Discussion Board, June 01, 2014
^ Re: 7-piece syzygy by syzygy, CCRL Discussion Board, July 03, 2014
^ Re: SSD and the use of Tablebases by Ronald de Man, CCC, May 08, 2013
^ Re: New 6-piece tablebases by Ronald de Man, CCC, April 05, 2013
^ Re: New 6-piece tablebase generator by syzygy, CCRL Discussion Board, April 06, 2013
^ Retrograde tablebase methods by BB+, OpenChess Forum, November 26, 2010
^ Leapfrog: Retrograde Analysis from Leapfrog tablebase generator by Harm Geert Muller
^ Jesper Torp Kristensen (2005). Generation and compression of endgame tables in chess with fast random access using OBDDs. Master thesis, Supervisor Peter Bro Miltersen, Aarhus University, pdf
^ OBDD - Ordered Binary Decision Diagram from Wikipedia
^ Guy Haworth (2014). Chess Endgame News. ICGA Journal, Vol. 37, No. 2
^ Gull 3 Linux+Syzygy and Fathom released by Basil Falcinelli, CCC, November 20, 2015
^ GitHub - basil00/Fathom: Syzygy TB probe tool by Basil Falcinelli
^ jdart1/Fathom · GitHub by Jon Dart
^ Found an interesting research by Kirill Kryukov, April, 12, 2013
^ Wine (software) from Wikipedia
^ N. Jesper Larsson, Alistair Moffat (1999). Offline Dictionary-Based Compression. DCC'99, pdf
^ BitTorrent from Wikipedia

What links here?

Page	Date Edited
Albert Silver	Feb 25, 2018
Alexandru Mosoi	Jan 8, 2018
Andreas Strangmüller	May 15, 2017
Arasan	Apr 8, 2018
Árpád Rusz	Oct 9, 2017
asmFish	Feb 14, 2018
Basil Falcinelli	Jun 23, 2017
BMI2	Mar 6, 2018
ChessBase (Database)	Feb 26, 2018
ChessGUI	Jan 17, 2018
Chiron	Sep 24, 2017
Crafty	Jan 28, 2018
DisasterArea	Mar 27, 2017
Draw	Apr 14, 2018
DroidFish	Jan 17, 2017
Edwards' Tablebases	Sep 26, 2016
Embla	Dec 3, 2017
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Fire	Oct 12, 2017
Fizbo	Dec 22, 2017
Gary Linscott	Jan 16, 2018
Gaviota Tablebases	Apr 22, 2018
Gogobello	Jul 30, 2017
GullChess	Jun 27, 2017
Guy Haworth	Nov 20, 2017
Hakkapeliitta	Apr 26, 2016
Houdini	Apr 14, 2018
ICGA Journal	Dec 21, 2017
Jean-Marc Alliot	Jun 28, 2017
Jeremy Bernstein	Nov 15, 2016
Jon Dart	Dec 17, 2017
Jose Maria Velasco	Feb 27, 2014
Joshua Shriver	Nov 24, 2017
Jouni Uski	Sep 28, 2017
Kai Laskos	Jan 21, 2018
Komodo	Mar 6, 2018
Laser	Dec 27, 2017
Lomonosov Tablebases	May 20, 2016
Losing Chess	Sep 18, 2017
Marco Costalba	Feb 28, 2018
Marvin	Feb 10, 2018
Match Statistics	Mar 31, 2018
Matthias Gemuh	Jan 21, 2018
Memory	Dec 8, 2017
Milos Stanisavljevic	May 23, 2016
Nalimov Tablebases	Dec 23, 2016
Nemorino	Dec 21, 2017
Niklas Fiekas	Sep 17, 2017
Norbert Raimund Leisner	Jul 28, 2016
Peter Österlund	Aug 24, 2017
Playing Strength	Mar 31, 2018
PT 50	May 3, 2017
python-chess	Nov 4, 2017
Repetitions	Jan 16, 2018
Ronald de Man	Nov 20, 2017
RuyDos	Feb 17, 2018
Score	Apr 14, 2018
Scorpio Bitbases	Mar 12, 2018
Sjaak	Dec 10, 2014
Stockfish	Apr 7, 2018
Syzygy Bases	Apr 19, 2018
TCEC Season 6	Dec 2, 2014
Teki	Mar 29, 2018
Texel	Oct 9, 2017
Thompson's Databases	Dec 24, 2014
WCCC 2017	Dec 31, 2017
WyldChess	Mar 10, 2018
Youri Matiounine	Jul 20, 2015

Up one level

Thompson's Databases

GerdIsenberg — Wed, 24 Dec 2014 09:39:03 GMT

Home * Knowledge * Endgame Tablebases * Thompson's Databases

		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 ^[1] , Thompson started in the mid 70s to apply retrograde analysis with Belle ^[2] . Advised by chess endgame expert John Roycroft, he finished the 5-men databases in the mid 80s. 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. 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 ^[3] .
Play Chess with God ^[4] ^[5]

Index Scheme

Usage

See also

Selected Publications

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.

Usage

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] .

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. ICCA Journal, Vol. 9, No. 3 (review)
Ken Thompson (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3, pdf
Ken Thompson (1986). An Example of QPvQ. ICCA Journal, Vol. 9, No. 4
Jaap van den Herik, Bob Herschberg (1987). The KBBKN Statistics: New Data from Ken Thompson. ICCA Journal, Vol. 10, No. 1

1990 ...

Ken Thompson (1990). KQPKQ and KRPKR Endings. ICCA Journal, Vol. 13, No. 4
Ken Thompson (1991). Chess Endgames Vol. 1. ICCA Journal, Vol. 14, No. 1
Ken Thompson (1991). New Results for KNPKB and KNPKN Endgames. ICCA Journal, Vol. 14, No. 1
John Roycroft (1991). A Postscript to the Computer's Involvement. Britisch Chess Magazine, Vol. 111, No. 2
Lewis Stiller (1991). Some Results from a Massively Parallel Retrograde Analysis. ICCA Journal, Vol. 14, No. 3
John Roycroft (1991). A Use for Endgame Databases? ICCA Journal, Vol. 14, No. 4
Ken Thompson (1996). 6-Piece Endgames. 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, Vol. 23, No. 1
John Tamplin, Guy Haworth (2001). Ken Thompson's 6-man Tables. ICGA Journal, Vol. 24, No. 2

Forum Posts

is there any program using ken thompson databases in the tree ? by Thorsten Czub, CCC, September 06, 1998
Re: End Game Tablebase Files (5-Man) For Crafty by Ernst A. Heinz, rgcc, Novemver 20, 1998
Ken Thompson's Endgame DBs....Still no copyright? by John Merlino, April 25, 2000
A question about Thompson endgame databases by Ruxy Sylwyka, CCC, September 08, 2011

External Links

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
Play Chess with God - 6-Piece Database by Ken Thompson, 2000
Can you play this endgame?, ChessBase News, December 07, 2001
Index of /chess/egtb/thompson hosted by Kirill Kryukov
Can We Solve Chess One Day? | Gödel's Lost Letter and P=NP by Dick Lipton, May 12, 2010

References

^ 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
^ Ernst A. Heinz (1999). Endgame Databases and Efficient Index Schemes for Chess. ICCA Journal, Vol. 22, No. 1, ps
^ 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
^ research!rsc: Play Chess with God by Russ Cox, January 18, 2008
^ Eugene Nalimov, Guy Haworth, Ernst A. Heinz (2000). Space-Efficient Indexing of Chess Endgame Tables. ICGA Journal, Vol. 23, No. 3
^ Re: is there any program using ken thompson databases in the tree ? by Ernst A. Heinz, CCC, September 06, 1998

What links here?

Page	Date Edited
ACM 1994	May 5, 2017
BBchess	Oct 30, 2011
Belle	Jan 18, 2018
Bernard Brioit	Jan 10, 2015
DarkThought	Jul 3, 2018
David Levy	Jan 3, 2017
Edwards' Tablebases	Sep 26, 2016
Endgame Tablebases	Mar 6, 2018
Ernst A. Heinz	Mar 6, 2017
Gaviota Tablebases	Apr 22, 2018
Ken Thompson	Sep 8, 2017
Lars Rasmussen	Apr 25, 2016
Lomonosov Tablebases	May 20, 2016
Nalimov Tablebases	Dec 23, 2016
Scorpio Bitbases	Mar 12, 2018
Syzygy Bases	Apr 19, 2018
TascBase	Dec 7, 2016
Thompson's Databases	Dec 24, 2014
Workshop Chess and Mathematics	Mar 5, 2015
Zugzwang (Program)	Dec 19, 2016

Up one level

Wikispaces : chessprogramming - items matching description

CHREST

Table of Contents

CHUMP

Architecture

See also

Publications

External Links

References

What links here?

Chunking

Table of Contents

Chunking in Chess

Chunking Hypothesis

Chess Patterns

See also

Publications

1920 ...

1940 ...

1950 ...

1960 ...

1970 ...

1975 ...

1980 ...

1985 ...

1990 ...

1995 ...

2000 ...

2005 ...

External Links

References

What links here?

Edwards' Tablebases

Table of Contents

Index Scheme

See also

Publications

Forum Posts

1990 ...

1995 ...

2000 ...

2010 ...

Downloads

References

What links here?

Endgame Bitbases

Table of Contents

Bitbase Implementations

See also

Publications

Forum Posts

2000

2005

2010

2015 ...

External Links

References

What links here?

Endgame Tablebases

Table of Contents

Metrics

DTM

DTC

DTZ

DTZ50

DTR

DTZR

Summary

Bitbases

Indexing

Brief Info

Formats

Generators

7-man EGTBs

2005

2006

2012

2013

See also

Selected Publications