KnightCap is an open source

computer A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...

chess engine In computer chess, a chess engine is a computer program that analyzes chess or List of chess variants, chess variant positions, and generates a move or list of moves that it regards as strongest. A chess software engine, engine is usually a Front ...

. Its primary author is

Andrew Tridgell Andrew "Tridge" Tridgell (born 28 February 1967) is an Australian computer programmer. He is the author of and a contributor to the Samba (software), Samba file server, and co-inventor of the rsync algorithm. He has analysed complex proprieta ...

and it was created circa 1996. Major contributions have also been made by Jon Baxter and probably minor contributions by a few others. KnightCap is

free software Free software, libre software, libreware sometimes known as freedom-respecting software is computer software distributed open-source license, under terms that allow users to run the software for any purpose as well as to study, change, distribut ...

released under the

GNU General Public License The GNU General Public Licenses (GNU GPL or simply GPL) are a series of widely used free software licenses, or ''copyleft'' licenses, that guarantee end users the freedom to run, study, share, or modify the software. The GPL was the first ...

(GPL). In most ways, KnightCap is a fairly typical modern program. It uses

bitboard A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or d ...

data structures that are slightly different from those that were well known in 1996, but obvious enough and probably well known now. There is backward pruning using

MTD(f) MTD(f) is an alpha-beta game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory (usually a transposition table) to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for M ...

(a method approximately equivalent to

Alpha-beta pruning Alphabeta or Alpha Beta may also refer to: * Alphabeta, an Israeli musical group * Alpha Beta, a former chain of Californian supermarkets * The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters * Alpha and beta anome ...

but slightly more efficient in some settings). There is

Null-move heuristic In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha–beta pruning algorithm. Rationale Alpha–beta pruning speeds the minimax algorithm by identifying ''cutoffs'', points in the g ...

. There is a fairly complex end-node evaluation process that considers similar features to other programs. In addition, KnightCap has support for multi-processor computers, in particular the now obsolete Fujitsu CAP computer research machines. The most original feature of KnightCap, introduced in the late 1990s, was an experiment in

temporal difference learning Temporal difference (TD) learning refers to a class of model-free reinforcement learning methods which learn by bootstrapping from the current estimate of the value function. These methods sample from the environment, like Monte Carlo methods, a ...

as applied to chess. This technique allowed KnightCap to automatically tune the weights applied to the various features in its

evaluation function An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position (usually at a leaf or terminal node) in a g ...

based on the games it played. For a while in the 1990s, KnightCap was quite active on

chess servers Online chess is chess that is played over the Internet, allowing players to play against each other. This was first done asynchronously through PLATO and email in the 1970s. In 1992, the Internet Chess Server facilitated live online play via te ...

on the Internet, but it is now semi-retired and rarely seen. Its strength is below that of the strongest programs, but still quite good.{{Fact, date=February 2007

External links

KnightCap's home page

KnightCap: A Chess program that learns by combining TD(λ) with minimax search
Chess engines Free chess software