KnightCap
KnightCap’s 3D Board [1] KnightCap,
a XBoard compliant open source chess engine under the GNU General Public License by Andrew Tridgell [2], Jonathan Baxter and Lex Weaver. To tune it’s evaluation in game play, it uses temporal difference learning applied to minimax search in chess, TDLeaf [3] [4]. KnightCap features an own GUI with an optional [5], and played multiple Australasian National Computer Chess Championships, and won two times, last one the NC3 2006.
Board Representation
KnightCap maintains an incremental updated attack table of 64 piece-sets - for each square indicating all pieces attacking or defending that square. Despite move generation, this approach pays off in determining in-check, and square control evaluation.
Search
The program performs a iterative deepening parallel MTD(f) search utilizing the shared transposition table. The variation of MTD(f) that KnightCap uses includes some convergence acceleration heuristics that prevent the very slow convergence that can sometimes plague MTD(f) implementations. Selectivity is due to null move pruning, razoring and various extensions. The transposition table with 128 bit entries keeps separate depth and scores for the lower and upper bound. The move ordering system is a combination of the commonly used history, killer, refutation and transposition table, along with ETC.
Evaluation
Conventional
KnightCap uses a quite slow evaluation function that evaluates a number of computationally expensive features such as board control to reasonably accurately consider the presence of hung, trapped and immobile pieces, and further has some asymmetric evaluation as well as search terms with a leaning towards careful play.
TD Considerations
One major modification for TDLeaf was that all evaluation coefficients became part of a weight vector. Another significant modification that was required was an increase in the bit resolution of the evaluation type so that a numerical partial derivative of the evaluation function with respect to the evaluation coefficient vector could be obtained with reasonable accuracy. To ensure small fluctuations in the relative values of leaf nodes did not produce large temporal differences, the raw linear leaf evaluation score was squashed to a ±1 range of a hyperbolic tangent sigmoid function with 0.25 equivalent a material superiority of one pawn. The outcome of the game was set to 1 for a win, -1 for a loss and 0 for a draw. Negative values of temporal differences (dt) were left unchanged as any decrease in the evaluation from one position to the next can be viewed as mistake. However, positive values of dt can occur simply because the opponent has made a blunder. To avoid KnightCap trying to learn to predict its opponent’s blunders, all positive temporal differences were set to zero unless KnightCap predicted the opponent’s move [6].
Selected Games
NC3 2006, round 2, Bodo - KnightCap
See also
Publications
1997 …
- Andrew Tridgell (1997). KnightCap — a parallel chess program on the AP1000+. zipped ps
- Jonathan Baxter, Andrew Tridgell, Lex Weaver (1997). Knightcap: A chess program that learns by combining td(λ) with minimax search. 15th International Conference on Machine Learning, pdf via citeseerX
- Jonathan Baxter, Andrew Tridgell, Lex Weaver (1998). Experiments in Parameter Learning Using Temporal Differences. ICCA Journal, Vol. 21, No. 2
- Jonathan Baxter, Andrew Tridgell, Lex Weaver (1999). TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search. Australian Journal of Intelligent Information Processing Systems, Vol. 5 No. 1, arXiv:cs/9901001
- Jonathan Baxter, Andrew Tridgell, Lex Weaver (1999). KnightCap: A chess program that learns by combining TD(lambda) with game-tree search. arXiv:cs/9901002
2000 …
- Jonathan Baxter, Andrew Tridgell, Lex Weaver (2000). Learning to Play Chess Using Temporal Differences. Machine Learning, Vol 40, No. 3, pdf
- Marco Block-Berlitz (2003). Reinforcement Learning in der Schachprogrammierung. Studienarbeit, Free University of Berlin, advisor: Raúl Rojas, pdf (German)
- Marco Block, Maro Bader, Ernesto Tapia, Marte Ramírez, Ketill Gunnarsson, Erik Cuevas, Daniel Zaldivar, Raúl Rojas (2008). Using Reinforcement Learning in Chess Engines. Concibe Science 2008, Research in Computing Science: Special Issue in Electronics and Biomedical Engineering, Computer Science and Informatics, Vol. 35, pdf
Forum Posts
1997 …
- KnightCap 1.0 by Andrew Tridgell, rgcc, February 27, 1997
- Parallel searching by Andrew Tridgell, rgcc, March 22, 1997 » Parallel Search
- KnightCap v1.8 by Andrew Tridgell, rgcc, April 03, 1997
- Re: computer chess “oracle” ideas… by Andrew Tridgell, rgcc, April 03, 1997 » Oracle
- Re: cheaper search ? by Shaun Press, rgcc, April 26, 1997 » Copy-Make, Vanilla Chess
- Re: Bit Board Bonkers?? - other alternatives by Andrew Tridgell, rgcc, August 9, 1997 » Piece-Sets
- asymmetry by Andrew Tridgell, rgcc, August 12, 1997 » Asymmetric Evaluation, Parity Pruning
- Re: How to get chess program to solve KBN mate? by David John Blackman, rgcc, September 18, 1997 » KBNK Endgame
- KnightCap—A free chess program that learns by Jonathan Baxter, CCC, November 26, 1997
- Parameter Tuning by Jonathan Baxter, CCC, October 01, 1998 » Automated Tuning
- KnightCap and Windows by Torsten Schoop, CCC, October 02, 1998
2000 …
- KnightCap installation question by Sven Reichard, CCC, March 08, 2000
- Question about the KnightCap find_pins function by Matthew White, CCC, July 14, 2003 » Pin
- KnightCap source code by Robert Pope, CCC, February 19, 2016
External Links
- Welcome to the KnightCap home page
- Index of /pub/KnightCap [7]
- KnightCap from Wikipedia
- chessexpress: Tridge by Shaun Press, July 23, 2007
References
- ↑ Welcome to the KnightCap home page
- ↑ Andrew Tridgell (1997). KnightCap — a parallel chess program on the AP1000+.
- ↑ Jonathan Baxter, Andrew Tridgell, Lex Weaver (1997) Knightcap: A chess program that learns by combining td(λ) with minimax search. 15th International Conference on Machine Learning
- ↑ Re: Bit Board Bonkers?? - other alternatives by Andrew Tridgell, rgcc, August 9, 1997
- ↑ Re: Going commercial, maybe by Andrew Tridgell, rgcc, March 9, 1997
- ↑ Jonathan Baxter, Andrew Tridgell, Lex Weaver (1997) Knightcap: A chess program that learns by combining td(λ) with minimax search. 15th International Conference on Machine Learning
- ↑ Re: KnightCap source code by Jim Ablett, CCC, February 19, 2016