KnightCap: A chess program that learns by combining TD(lambda) with minimax search

In this paper we present TDLeaf(), a variation on the TD() algorithm that enables it to be used in conjunction with minimax search. We present some experiments in which our chess program, "KnightCap," used TDLeaf() to learn its evaluation function while playing on the Free Ineternet Chess Server (FICS, fics.onenet.net). It improved from a 1650 rating to a 2100 rating in just 308 games and 3 days of play. We discuss some of the reasons for this success and also the relationship between our results and Tesauro's results in backgammon. 1 Introduction Temporal Difference learning or TD(), first introduced by Sutton [9], is an elegant algorithm for approximating the expected long term future cost (or cost-to-go) of a stochastic dynamical system as a function of the current state. The mapping from states to future cost is implemented by a parameterized function approximator such as a neural network. The parameters are updated online after each state transistion, or possibly in batch update..