Generation and compression of endgame tables
in chess with fast random access using OBDDs
The thesis can be downloaded here (minor corrections added since version handed in):
Chapter 8 was written in quite a hurry. This chapter is currently
being rewritten as an article that will be available here soon (09/05/2005).
The program and endgames can be downloaded
here.
References
-
Deep Blue vs Kasparov
-
Specification of PGN and FEN formats
-
Wikipedia: Chess
-
Wikipedia: Chess rules
-
FIDE rules
- Dietmar Lippold:
Legality of Positions of Simple Chess Endgames
-
ChessliB
-
ECO openings list
-
Nalimov tablebase server
-
GnuChess evaluation function
-
Search Versus Knowledge in Game-Playing Programs Revisited
-
XBoard and WinBoard
- Claude E. Shannon:
Programming a computer for playing chess
- Aske Plaat:
Thesis on game trees
- Robert Lake, Jonathan Schaeffer, Paul Lu:
Solving Large Retrograde Analysis Problems Using a Network of
Workstations
- Ernst A. Heinz:
Scalable Search in Computer Chess
- E. V. Nalimov, G.M C. Haworth and E. A. Heinz:
Space-efficient indexing of chess endgame tables
- Lewis Stiller:
Johan Melin: EgmProbe 2.0
- Henrik Reif Andersen:
An Introduction to Binary Decision Diagrams
- Martin Sauerhoff and Ingo Wegener:
On the complexity of minimizing the OBDD size for incompletely
specified functions
- Kouichi Hirata, Shinichi Shimozono and Ayumi Shinohara:
On the Hardness of Approximating the Minimum Consistent OBDD
Problem
- Shih-Chieh Chang, Malgorzata Marek-Sadowska and TingTing Hwang:
Technology Mapping for TLU FPGA's Based on Decomposition of
Binary Decision Diagrams
- Youpyo Hong, Peter A. Beerel, Jerry R. Burch and Kenneth L. McMillan:
Sibling-Substitution-Based BDD Minimization Using Don't Cares
- Youpyo Hong, Peter A. Beerel, Luciano Lavagno and Ellen M. Sentovich:
Don't care-based BDD Minimization for Embedded Software
- Richard Rudell:
Dynamic Variable Ordering for Ordered Binary Decision
Diagrams
- Ingo Wegener and Beate Bollig:
Improving the variable ordering of OBDDs is
NP-complete
- Pierluigi Crescenzi, Viggo Kann:
A compendium of NP optimization problems
-
Computational Complexity of Games and Puzzles
- Bernhard Balkenhol:
An Approach to Data Compression in Coding Chess Positions
- Michael Burrows, David Wheeler:
A Block-Sorting Lossless Data Compression Algorithm
- Hopcroft, J. and Karp, R:
An n^(5/2) Algorithm for Maximum Matching in Bipartite
Graphs
- Bellare, M., Goldreich, O., and Sudan, M. (1998):
Free bits, PCPs and non-approximability - towards tight results
- Uriel Feige, Joe Kilian:
Zero Knowledge and the Chromatic Number
- Dempster, A. P., Laird. N. M. and Rubin, D. B.:
Maximum Likelihood from Incomplete Data via the EM algorithm