25,161
edits
Changes
no edit summary
'''KnightCap''',<br/>
a [[XBoard]] compliant [[:Category:Open Source Engines|open source chess engine]] under the [[Free Software Foundation#GPL|GNU General Public License]] by [[Andrew Tridgell]] <ref>[[Andrew Tridgell]] ('''1997'''). ''KnightCap — a parallel chess program on the AP1000+''.</ref>, [[Jonathan Baxter]] and [[Lex Weaver]].
To [[Automated Tuning|tune]] it's [[Evaluation|evaluation]] in game play, it uses [[Temporal Difference Learning|temporal difference learning]] applied to [[Minimax|minimax]] search in chess, [[Temporal Difference Learning#TDLeaf|TDLeaf]] <ref>[[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</ref> <ref>[https://groups.google.com/group/rec.games.chess.computer/msg/4d6c328e8e8e0cd4 Re: Bit Board Bonkers?? - other alternatives] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], August 9, 1997</ref>. KnightCap features an own [[GUI]] with an optional [[3D Graphics Board]] <ref>[https://groups.google.com/group/rec.games.chess.computer/msg/ded7e4e4304d8d4e Re: Going commercial, maybe] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], March 9, 1997</ref>, and played multiple [[Australasian National Computer Chess Championship|Australasian National Computer Chess Championships]], and won two times, last one the [[NC3 2006]].
==[[Search]]==
The program performs a [[Iterative Deepening|iterative deepening]] [[Parallel Search|parallel]] [[MTD(f)]] search utilizing the [[Shared Hash Table|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|null move pruning]], [[Razoring|razoring]] and various [[Extensions|extensions]]. The [[Transposition Table|transposition table]] with 128 bit entries keeps separate [[Depth|depth]] and [[Score|scores]] for the [[Lower Bound|lower]] and [[Upper Bound|upper bound]]. The [[Move Ordering|move ordering]] system is a combination of the commonly used [[History Heuristic|history]], [[Killer Heuristic|killer]], [[Refutation Table|refutation]] and transposition table, along with [[Enhanced Transposition Cutoff|ETC]].
==[[Evaluation]]==
=Publications=
==1997 ...==
* [[Andrew Tridgell]] ('''1997'''). ''KnightCap — a parallel chess program on the AP1000+''. [http://ftp.riken.jp/pub/net/samba/tridge/knightcap_pcw97.ps.gz 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, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8263&rep=rep1&type=pdf pdf] via [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8263 citeseerX]* [[Jonathan Baxter]], [[Andrew Tridgell]], [[Lex Weaver]] ('''1998''') . ''Experiments in Parameter Learning Using Temporal Differences''. [[ICGA Journal#21_2|ICCA Journal, Vol. 21, No. 2]]
* [[Jonathan Baxter]], [[Andrew Tridgell]], [[Lex Weaver]] ('''1999'''). ''TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search''. [https://www.chatbots.org/journal/australian_journal_of_intelligent_information_processing_systems/ Australian Journal of Intelligent Information Processing Systems], Vol. 5 No. 1, [http://arxiv.org/abs/cs/9901001 arXiv:cs/9901001]
* [[Jonathan Baxter]], [[Andrew Tridgell]], [[Lex Weaver]] ('''1999'''). ''KnightCap: A chess program that learns by combining TD(lambda) with game-tree search''. [https://arxiv.org/abs/cs/9901002 arXiv:cs/9901002]
==2000 ...==
* [[Jonathan Baxter]], [[Andrew Tridgell]], [[Lex Weaver]] ('''2000'''). ''Learning to Play Chess Using Temporal Differences''. [http://www.dblp.org/db/journals/ml/ml40.html#BaxterTW00 Machine Learning, Vol 40, No. 3], [http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf pdf]
* [[Marco Block-Berlitz]] ('''2003'''). ''Reinforcement Learning in der Schachprogrammierung''. Studienarbeit, [[Free University of Berlin]], advisor: [[Raúl Rojas]], [http://page.mi.fu-berlin.de/block/Skripte/Reinforcement.pdf pdf] (German)
* [[Marco Block-Berlitz|Marco Block]], Maro Bader, [http://page.mi.fu-berlin.de/tapia/ Ernesto Tapia], Marte Ramírez, Ketill Gunnarsson, Erik Cuevas, Daniel Zaldivar, [[Raúl Rojas]] ('''2008'''). ''Using Reinforcement Learning in Chess Engines''. Concibe Science 2008, [http://www.micai.org/rcs/ Research in Computing Science]: Special Issue in Electronics and Biomedical Engineering, Computer Science and Informatics, Vol. 35, [http://page.mi.fu-berlin.de/block/concibe2008.pdf pdf]
=Forum Posts=
==1997 ...==
* [https://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/1f7ba9d3c31f071 KnightCap 1.0] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], February 27, 1997
* [https://groups.google.com/d/msg/rec.games.chess.computer/Wl7A-v-gWYQ/QLuvAp0l4_gJ Parallel searching] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], March 22, 1997 » [[Parallel Search]]
* [https://www.stmintz.com/ccc/index.php?id=28584 Parameter Tuning] by [[Jonathan Baxter]], [[CCC]], October 01, 1998 » [[Automated Tuning]]
* [https://www.stmintz.com/ccc/index.php?id=28647 KnightCap and Windows] by [[Torsten Schoop]], [[CCC]], October 02, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=100829 KnightCap installation question] by [[Sven Reichard]], [[CCC]], March 08, 2000
* [https://www.stmintz.com/ccc/index.php?id=306311 Question about the KnightCap find_pins function] by Matthew White, [[CCC]], July 14, 2003 » [[Pin]]
'''[[Engines|Up one level]]'''
[[Category:Open Source]][[Category:GPL]][[Category:XBoard]][[Category:Linux]][[Category:MTD(f)]]
