From Simple Features to
Sophisticated Evaluation Functions
Michael Buro
NEC Research Institute4 Independence Way
Princeton NJ 08540, USA

Abstract. This paper discusses a practical framework for the semi{
automatic construction of evaluation functions for games. Based on a
structured evaluation function representation, a procedure for exploring the feature space is presented that is able to discover new featuresin a computational feasible way. Besides the theoretical aspects, related
practical issues such as the generation of training positions, feature selection, and weight tting in large linear systems are discussed. Finally,
we present experimental results for Othello, which demonstrate the potential of the described approach.
Keywords: automatic feature construction, GLEM, Othello

1 Introduction
Many AI systems use evaluation functions for guiding search tasks. In the context of strategy games they usually map game positions into the real numbers for
estimating the winning chance for the player to move. Decades of research has
shown how hard a problem evaluation function construction is, even when focusing on particular games. In order to simplify the construction task, the notionof evaluation features was introduced. The underlying assumption is that there
exist reasonable approximations of the perfect evaluation function in the formof combinations of a few distinct numerical properties of the position | calledfeatures. Given this, evaluation functions can be constructed in two phases by1) selecting features and 2) combining them.
Selecting features is one of the most important and dicult sub{tasks inthe construction of a game playing program. It requires both domain speci cknowledge and programming skills because of the well known tradeo between
speed and knowledge in game{tree search. A couple of years ago, the authorsof the best game playing programs still picked not only features but also theirweights in course of a tedious optimization process. This is somewhat surprising,since already in [7] Samuel proposed ways for automatically tuning weights.
While selecting features is dicult for a machine, tting even a large number ofweights given a set of training positions is not. Research focused on the latter
topic produced TD{Gammon, a world{class backgammon{program [8, 9], andcontributed to Deep Blue's victory over Kasparov in 1997 [4].

In this article we go a step further towards the ultimate goal of automatic
evaluation function construction. First, a generalized linear evaluation modelis presented. It restricts evaluation features to boolean combinations of given
atomic functions. The model parameters can be tailored such that an automaticfeature space exploration becomes feasible. The following sections cover all aspects of evaluation function construction | from generating training positions
over feature selection to weight estimation | with respect to the new modeland emphasis on ecient implementation. Finally, we show how the presented
techniques can be applied to the game of Othello and discuss the new approachwith regard to related work.

2 Evaluation ModelWe rst give a de nition of the evaluation model we are proposing and discuss
its properties. In what follows, P denotes the set of all legal game positions1 ,and IR the set of real numbers. Let A be a nite set of integer valued | socalled atomic | features and RA := f (f () = k) j f 2 A; k is an integerg
the set of relations over A that compare feature values with integer constants.
Con gurations are conjunctions of relations in RA . For a position p 2 P and a
con guration c = r1 ^ : : : ^ rl we de neif r1 (p) ^ : : : ^ rl (p) = true :val(c(p)) := 01;; otherwise
A con guration c is called active in a position p, i c(p) = true.
With this notation we can now de ne the Generalized Linear Evaluation
Model | GLEM(P ; A; g) for short. Evaluation functions in this model have thefollowing form:e(p) = gnXwi  val(ci (p)) ;

i=1

(1)

where c1 ; :::; cn are con gurations over RA , w1 ; :::; wn 2 IR are weights, andg : IR ! IR is an increasing and di erentiable link function.
The weights are subject to the usual least{squares optimization. That is,given a set of con gurations c1 ; : : : ; cn , a link
 function g , and a sequence ofscored training positions (pi ; ri ) j i = 1 : : : N , the weights are chosen such thatthe total squared error

E (w) :=

NX
i=1

(ri ew (pi ))2 :is minimized. This model has several desirable properties:
1
W.l.o.g. it is assumed that game positions in P are normalized in such a way that axed player is to move.

{ Atomic features are the building blocks of more sophisticated ones. This,in principle, allows the automated discovery of new important features bysystematic combination.
{ If necessary, complex features can be added to A. Thus, \atomic" is notnecessarily a synonym for \simple".
{ When evaluating a position, features are combined linearly. This keeps thetime overhead low. Actually, not even a multiplication with the weight isnecessary since val(ci (p)) is either 0 or 1.
{ Non{linear e ects can be approximated by using con gurations that consistof several relations.
{ In order to deal with saturation an increasing non{linear link function, suchas g(x) = 1=(1 + exp( x)), can be used without increasing the run time
during minimax search. There is no need to compute g, because g(x1 ) >g(x2 ) () x1 > x2 .
{ The simple linear core of the evaluation function allows an ecient approximation of optimal weights, even for large systems. In the application reported
later, more than a million weights were tted to a training set consisting of
eleven million scored positions in a reasonable period of time.
At this point GLEM should be moved into the right perspective: in the statedform it is neither a new revolutionary evaluation approach, nor does it ease thetask of automatic evaluation function exploration. This is because the model isbuilt upon well known linear evaluation functions and does not impose a severe
restriction on the structure of functions it includes. E.g., for any atomic feature
set A, which is capable of distinguishing any two di erent positions (including
game history if the game result depends on it) via conjunctions over RA , GLEM
covers all evaluation functions over P . A trivial example for such a complete
atomic feature set for board games without position repetition is

contents of square s in position p; ;A = fs j sfsis(p)a =square
where the contents of a square is considered to be an integer value.
However, GLEM allows one to de ne a hierarchy of submodels in a naturalway, which re ects di erent levels of computational complexity and the expressive power of the covered evaluation functions. By restricting the size of A, thenumber of con gurations, or their structure, an automated search for new features becomes feasible. In the application discussed later, evaluation functions
based on GLEM outperformed the best known functions so far. In this respect,
GLEM breaks new ground.
Good evaluation functions accurately estimate the winning chances in positions visited during game{tree search and are optimized for speed. Therefore, thefollowing topics have to be borne in mind when using scored training positions
for tuning con guration weights:{ The training positions have to be representative of the positions that will be
evaluated later in actual game{tree search.

{ Training positions must be scored accurately.
{ The selected con gurations and their combination must have the expressive

power to explain the data reasonably well while avoiding over{ tting. Given
the at evaluation function representation in GLEM, meeting this condition
may require a large number of con gurations. Their automatic constructionis therefore of great interest.
{ Evaluation speed is important.
{ While computing weights is an o {line process, its memory and time consumption should still be subject to optimization. The reason is that in thefeature selection phase usually many evaluation function versions have to becompared. Moreover, without optimization the current solver might not beable to handle the number of features one would like to use.
In the following sections these topics are discussed in detail in the context of
GLEM.

3 Training Positions
A theory of how to generate good training sets in the context of evaluation
function tuning has not been developed yet. In this section practical ideas are
discussed which may become the seed for further investigations.
Training positions can be generated and scored in several ways. If the considered game has a long tradition and is quite popular, many games may beavailable in electronic format. The simplest scoring procedure assigns the nal
game result (depending on the side to move) to all positions occurring in agame. Obviously, this ad hoc procedure has limitations, since it does not ensure
accurate scoring. Selecting games between good players alleviates this problem.
But this approach leads to high{quality games, in which hardly any catastrophe takes place, such as losing material in chess or a corner in Othello withoutcompensation. The reason for this is obvious: good players know the importantevaluation features and keep them mostly balanced in their games. What we(and machines) can learn from such games are the ner points of play, whichmake the di erence between good and the best players. However, an evaluation
function must also be aware of the most important features. Thus, our training
set should also contain games in which at one point a player makes a serious
mistake that is rigorously exploited by the opponent. In summary, a reasonable strategy for generating training positions from a game database is to selectgames played by at least one good player and to score game positions according
to the nal game result. This procedure is ecient and its output can serve as
the basis for tuning the rst evaluation function version.
Besides the still present potential mis{scoring problem, the question arises,
whether the so generated training set is representative to positions encounteredin game{tree search. This question is of importance, since the weight t for alinear evaluation function is in uenced by the correlation among features in the
training set. The answer obviously depends on the type of game{tree search
we are conducting: in a highly selective search evaluated positions are in thevicinity of principal variations, whereas in brute{force searches many ridiculous
positions are evaluated, which one would never encounter in actual games. It
seems natural to let the search algorithm generate the training positions by itself. For instance, starting searches with positions from played games, a random
subset of evaluated positions can be saved in a le and serve as the training
set after scoring. In this way, the generated positions are surely a representative
sample of the positions encountered in game{tree searches. It remains to assign
accurate scores to the positions. This task can be accomplished again by game{tree searches, which normally return more reliable results than the evaluation
function itself. In particular, in many games endgame positions can be evaluatedperfectly | or at least more accurately than middle{game or opening positions| in a reasonable amount of time. In this case, a game{stage dependent evaluation function can be improved iteratively by rst tuning the endgame weights.
Thereafter, training positions from the previous game stage are evaluated by agame{tree search, which utilizes the just tuned evaluation function, and so on.
The next step would be to generate even positions and those with a narrowadvantage for one side. Similar to considering games between good players mentioned above, these positions are useful for tuning weights of minor features orrevealing possible tradeo s between major features (e.g. material vs. king safetyin chess or corner possession vs. mobility in Othello).
If training positions are selected randomly during minimax{based searches,
one soon discovers that the winning chance in such positions is biased towards
the player to move. This phenomenon is easy to explain, given the fact thatin typical positions the majority of searched moves lose. Its undesirable e ect
on tted weights is an arti cial bonus for the player to move. This, in turn,leads to unstable evaluations, which compromise comparing evaluations backed{
up from depths of odd di erence during selective search. Because the proposed
generation procedure labels positions with search results, a simple cure for thisproblem is to add the principal variation successor positions to the training set
after labelling them with the negated search result.

4 Selecting Con gurations
GLEM proposes a new perspective on how to look at evaluation features. In theclassical approach a couple of complex features are combined linearly. Weights
were mostly hand{tuned. Later, the study of neural networks opened up a practical way of combining features non{linearly. Application of the well known gradient descent procedure (in this context called \back{propagation") makes it
possible to automatically tune a large number of network parameters. A prominent and very successful example is Tesauro's backgammon network which, in
its strongest version, makes use of hand{crafted features in addition to a raw
board representation. GLEM uses a di erent approach. Instead of modellingnon{linear e ects by applying parameterized analytical functions to features,
GLEM handles non{linearities directly by assigning values to boolean feature
combinations, called con gurations. In this way, distinct cases can be handlednaturally, without the detour over non{linear analytical functions. The design ofneural networks corresponds to con guration selection in GLEM, which is the
topic of this section. After stating basic requirements for the atomic features,
we will present an algorithm for generating con gurations by analyzing training
positions, and discuss several optimizations.

4.1 Atomic Features
Atomic features are the building blocks for con gurations. As the scope of automatic con guration selection is limited by its time and space complexity, choosing the right abstraction level for atomic features is crucial. In Othello, con gurations based upon the raw board representation are sucient for building goodevaluation functions | as we shall see later. The reason is that many relevant
features in this game can be expressed by local board con gurations of small
cardinality. Other games may require a greater abstraction level. For instance,
the relation \piece A attacks piece B" in chess has a long description length
when using raw board representation languages. Since many important features,such as forks and pins, are based on those attack features, they certainly should
be included in the atomic feature set. In general, candidates for atomic features
are common parts of relevant features, that | combined in novel ways | maylead to new important features. Obviously, this selection task is beyond current
program abilities.
Not all atomic features have to be useful for building other features. Limitations of the con guration generator may suggest the inclusion of complex featuresthat can not be expressed or well approximated by restricted combinations ofother members of the atomic feature set.
Moreover, GLEM generalizes the classical use of features | w  f (p) | because (w  k) inXw  f (p) = (w  k)  val(f (p) = k):kspecializes the weight of val(f (p) = k). This generalization is only meaningful if
f has a small range. In case one likes to incorporate a feature f having a large
range, GLEM can be easily extended by allowing summation terms of the formw  f (p).

4.2 Generating Con gurations
In a balanced evaluation function design the number of features can be increased
up to a point where either 1) adding additional knowledge is compensated for by
a decreased evaluation speed or 2) over{ tting becomes a problem. Since con gurations can be computed quickly, once the atomic features have been evaluated,
GLEM encourages to use many con gurations rather than a few complex features. Our chief concern is therefore over{ tting.
We will rst present an algorithm for generating a con guration set that
does not su er from over{ tting. Thereafter, we will discuss how to deal with apossibly unacceptably long run time for the con guration generator, for weighttting, or for the con guration value look{up during game{tree search.
Con gurations have to cover positions that occur in game{tree search while
avoiding over{ tting when optimizing weights. Both requirements can be met byusing a large set of training positions | generated as described in the previous
section | and selecting con gurations that match a suciently large number ofthese positions. Fig. 1 shows a straight forward algorithm for this task. Given a
set of atomic features A, training positions E , and a minimal match count n, it
computes all valid con gurations over A that occur in at least n positions in E .
Beginning with all valid con gurations of length one, the algorithm iteratively
builds larger con gurations by specializing previously generated con gurations,
until the matches count drops below n. The algorithm certainly halts, since theset of valid con gurations is nite. Its correctness can be shown by induction
using the fact, that for k > 1, valid con gurations of length k have valid subcon gurations of length k 1.
The run time of the algorithm is O(jC j  jRA j2  jE j), where C is the computed set of valid con gurations and E the set of training examples. The mosttime{consuming part is computing the match counts in the inner loop. Since
in the beginning the number of checked con gurations grows exponentially in

Function GenConf
Input: atomic feature set A, training position set E , minimal match count n
Output: con gurations over A that are active in at least n positions of E

R := fff () = kg j f 2 A; k 2 range(f ); #match(ff () = kg; E )  ng
C := R ; collects all valid con gurations
N := R ; set of con gurations created in previous iteration

while N 6= ; doM := ;; set of valid con gurations in current iteration(*) foreach c 2 N; d 2 R doe := c [ fdg; specialize con guration c
if #match(e;E)  n thenM := M [ feg; append if valid
endif
endfor
N := M
C := C [ N

endwhile
return C; next con gurations to specialize; add valid con gurations

Fig. 1. Pseudo code for generating the set of con gurations that occur in at least n

training positions. The function iteratively specializes con gurations, which are implemented as sets of relations, until the number of matching positions (#match(e;E ))drops below n.

each iteration, it is crucial to optimize the match computations, especially if
the number of positions is large. The following optimizations speed up a naive
implementation considerably:{ Due to the commutativity of ^, valid con gurations of length k may haveseveral valid subcon gurations of length k 1. This observation suggeststhat we should check whether a given specialization has been tested before
in the current iteration, in order to avoid repeated match computations. Aneven better solution is to generate specializations in an ordered fashion byde ning a total order over R and replacing line (*) byforeach c 2 N; d 2 R with d > max
d do
d c
0

02

It is not hard to show that after applying this time{saving modi cation thealgorithm still generates all valid con gurations.
{ A naive algorithm for deciding #match(e; E )  n evaluates the relationsin e for every member of E . The computation time of this algorithm canbe reduced by preprocessing and parallelizing computations. The idea is tocompute, for each r 2 R, a sequence of bits (bi )#i=1E de ned by bi := val(r(pi )),where pi 2 E is the i{th training position. After this preprocessing step,
the actual features and positions are no longer needed. The match countcomputation reduces to and{combining the bit sequences of the involved
relations and counting set bits in the result sequence. Modern CPUs allow

Function MatchHeuristic
Input:
Output:con guration e, chunk size s, random partition E1 ; :::; Em of
position set E as described in the text, con dence level t > 0
true, if #match(e; E )  n is likely; false, otherwise

q := n=#E; match count fraction aimed for
d := 0; number of elements checked
u := 0; current match countfor i := 1 to m 1 dou := u+#match(e; Ei ); update counts
d := d + s p
if u  dq + t dq(1 q) thenreturn true; #match(e; E )  n is likely

endifp
if u < dq t dq(1 q) thenreturn false; #match(e; E ) < n is likely
endif
endforreturn u+#match(e;Em)  n

Fig. 2. A fast procedure for testing the hypothesis #match(e; E)  n

a very ecient implementation of the and{part by handling 32 or even 64
bits in parallel. Iterating x := x ^ (x 1), which clears the rightmost one
in the binary representation of x, allows us to count set bits quickly. In thisapplication table{based techniques for counting bits are inferior because thenumber of set bits is decreasing rapidly due to specialization.
{ Replacing the condition #match(e; E )  n by a sequential statistical test
procedure speeds up the computation further. This optimization can be motivated by an intuitive example: if among the rst 100 randomly selected
bits of 1000 there is only a single one, it is very unlikely that the total number of ones exceeds 500. More formally, we propose the following heuristic
function, which quickly checks whether #match(e; E )  n holds with a prescribed likelihood. In a preprocessing step, E is randomly partitioned into
chunks E1 ; :::; Em of size s (Em might have less elements). For a given conguration e, the function then iteratively computes the match counts forincreasing subsets beginning with E1 . If the match count fraction at one
point signi cantly di ers from the one we aim for, the function returns thelikely truth value of #match(e; E )  n early. The pseudo code implementation shown in Fig. 2 makes use of the fact that the expected number ofones in a sequence of d randomly
generated bits is dq, if Probf1g = q, whilep
its standard deviation is dq(1 q). The behaviour of this function is controlled by con dence level t. For large values of t, hardly any break condition
will be met | the function will be slow, and almost always return the correct
result. If t is small, the function is quick, but it also returns unreliable results.
Experiments can tell how to choose t depending on the speed/reliability one
likes to achieve.

4.3 Finding Active Con gurations
During weight tting and position evaluation the set of active con gurations
has to be computed quickly for a large number of positions. For this purpose,
we represent the set of all con gurations over RA by a DAG G. Nodes in G
correspond to con gurations, and arcs mark direct specializations. A detailed
example is shown in Fig. 3a. The just described selection algorithm computes all
con gurations that occur at least n{times in a set of training positions. This setof valid con gurations induces a sub{DAG G of G. Given a position, all active
con gurations can be found by a depth{ rst search in G starting at its root.
During search, all visited con gurations are marked and their active status isdetermined. The search stops in nodes that have been visited before or have beenfound inactive. This algorithm quickly nds all active con gurations. However,
the only relevant active con gurations for evaluation purposes are those without
active specializations, because generalizations are redundant. It is easy to extend
the described algorithm accordingly by restricting its output to leaves of theactive con guration sub{DAG. Fig. 4 illustrates the entire procedure.
0

0

a)

b)

r1,0 ^ r2,0r1,0r1,0 ^ r2,1

r1,1
true

pattern[ f1 ]

r1,0

0

r1,1

1

r2,0

0

r2,1

1

r2,2

2

r1,0 ^ r2,2

r2,0pattern[ f2 ]r1,1 ^ r2,0

r2,1

r1,1 ^ r2,1

r2,2

pattern[ f1, f2 ]r1,1 ^ r2,2

r1,0 ^ r2,00

r1,0 ^ r2,1

1

r1,0 ^ r2,22

r1,1 ^ r2,03

r1,1 ^ r2,1

4

r1,1 ^ r2,25table indicesFig. 3. a) Con guration DAG for two features f ; f with range(f ) = f0; 1g and12

1

range(f2 ) = f0; 1; 2g. ri;k denotes the relation fi () = k. b) Con gurations belonging
to patterns over f1 and f2 .
1

2

3

4

6

5

8

9

a) configuration sub-DAG G’

11

12

7

13

10

14

17

16

15

b) active configurations andleft-to-right DFS numbersc) most specific active
configurations

Fig. 4. Finding the most speci c active con gurations by depth{ rst search in the
con guration DAG

4.4 Reducing Complexity: Patterns
So far, our focus has been on ecient ways for generating con gurations andcomputing active con gurations. Despite the optimization e orts, GenConf may
still not be able to generate all valid con gurations due to time or space limitations. Furthermore, a large number of generated con gurations might preventan ecient position evaluation, because too many con gurations are active, orthe con guration data needs too much memory.
One solution to these problems is to increase the minimal match count n,until the number of generated con gurations is manageable. This approach, however, narrows the evaluation function's view by focusing it on the most common
phenomena. A compromise is to generate all valid con gurations choosing n highenough to avoid over{ tting, and to reduce their number afterwards by looking

at their statistical signi cance with regard to winning chance prediction.2 Another option for reducing the number of con gurations is to limit their size or tochoose subsets of the atomic feature set as the base for generating con gurations.
Finally, considering sets of mutual exclusive con gurations helps to reduce
the number of active con gurations in order to speed up the evaluation considerably. Let G be the complete con guration DAG for ff1 ; :::; fmg  A (Fig. 3a),and let rmin and rmax denote the minimum/maximum range cardinality of
the features. Then the number of nodes in G is bounded by (1 + rmin)m and(1 + rmax)m , and for any position the number of active con gurations is 2m. 3
Thus, in case of complete con guration DAGs the DFS algorithm presented in
the last subsection seems to waste time by searching a large number of nodes
before it eventually returns the single active con guration we are interested
in. This observation motivates looking for a more ecient data structure. For
ff1; :::; fm g  A we collect all possible most speci c con gurations in a set called
pattern[f1 ; :::; fm], i.e.
pattern[f1 ; :::; fm ] := fr1;l1 ^ ::: ^ rm;lm j ri;li = (fi () = li ); li 2 range(fi )g
Con gurations in pattern[f1 ; :::; fm ] correspond to leaves of the complete conguration DAG (Fig. 3b). Data related to these con gurations can therefore be
stored in a table addressed by feature values. For instance, in Fig. 3b the tableindex for pattern[f1 ; f2 ] with regard to position p is simply 3  f1 (p) + f2 (p).
Checking whether a pattern con guration is valid only requires incrementing amatch counter stored in a table whenever a con guration is active, and comparing the result with the minimal match count. Detecting whether a pattern
con guration is active during weight tting or positional evaluation is a matterof a fast index computation and one table access. Incremental updates of only
those indices which are in uenced by moves speeds up game{tree search further.
In summary, the at table is the data structure of choice for storing information
regarding small and medium sized complete con guration sets. The fast accessencourages to restrict con guration sets to patterns.
Large patterns require a more memory ecient representation. In order toavoid over{ tting, we are still only interested in con gurations that match several
training positions. Consequently, large patterns are sparse. Fig. 5 outlines a very
fast and | to our knowledge | novel technique for accessing sparse data which
trades memory for speed. It is based on representing valid con gurations as
index tuples (i1 ; i2 ). For a given position and pattern, i1 and i2 are computedby splitting the pattern's feature set into two parts and performing the index
calculations described above separately for each subset. Both indices are thenused for accessing a hash{table, in which data regarding con guration (i1 ; i2 )The general problem of deciding the relevance of variables in a multivariate regression
model in advance is hard. Nevertheless, simple statistics like the feature's correlation
with the training position scores can serve as a reasonable rst approximation.
3
These numbers can be derived by adding lower/upper bounds for the of
P numbernodes/active con gurations for each depth and applying the identity mi=0 mi xi =(1 + x)m .

2

i2
i1

offset(i1)i1data(i1,i2)

offset tablehash-table

Fig. 5. Fast sparse data access. Data regarding a con guration represented by two
indices i1 and i2 can be accessed quickly in two steps.

is stored. First, an o set is looked{up in a table using index i1 . Then, thiso set, incremented by i2 , is used to access the hash{table. For the algorithm
to be correct, 1) unique hash{table entries have to be assigned to valid index
tuples, and 2) invalid index tuples must be detected. The rst condition can be
met by choosing suitable o sets and a suciently large hash{table. In practice,
the following greedy algorithm for constructing collision{free hash{tables has
produced reasonable results: beginning with the most frequent i1{values, o sets
are assigned to them in rst{ t manner. That is, whenever a collision occurs
when attempting to occupy the hash{table entry o set(i1 ) + i2 , all i1 entries
claimed so far are erased and o set(i1 ) is incremented before restarting. The
hash{table size must be greater than the sum of the maximal o set and maximal
possible value of i2 , in order to avoid accesses beyond table end. A simple way
for meeting condition 2) is to add the lock i1 to hash entries for all valid tuples(i1 ; i2 ) and to reject tuples (i1 ; i2 ), for which the lock stored in the accessed hashentry does not match i1. Locks of unused hash entries must be initialized witha value di erent from any possible i1 (e.g. 1). Finally, o sets for all i1 , which
are not the rst component of any valid index tuple, can be safely set to 0, since
all locks in the hash{table are di erent from those i1 values.
Patterns may outperform con guration sets constructed by GenConf due toa much faster generation and evaluation of con gurations. However, patterns
su er from their limited scope because patterns may miss essential generalizations. This observation suggests building a hierarchy of patterns in order toquickly cover both general and speci c position aspects. Since this approachalso increases the evaluation time, experiments have to tell, which is the better
strategy for a given application.

5 Weight Fitting
The previous sections discussed the generation of scored training positions andthe selection of con gurations. In order to conclude the evaluation function construction, we must show how to assign weights to con gurations.
If the number of weights is large or non{linear models are used, direct weightcomputation is no longer feasible. Instead, iterative methods have to be used
for weight tting, which are usually based on variations of the gradient decent
procedure. In each step, this procedure updates the current weight vector in
direction of the negated gradient of the error function. If features are highly
correlated, this simple algorithm is known to converge slowly. Faster conjugate
gradient algorithms have been developed [6], that do not su er from this problem.
However, because the basic algorithm works suciently well in practice andis easier to implement, its application will be discussed in more detail in theremainder of this section.

5.1 Basic Considerations
In games, the purpose of evaluation functions is to estimate the winning chancefor the player to move. This goal can be accomplished literally by constructing
functions that map positions into [0; 1]. Alternatively, the game may provide
a numerical scoring of terminal positions re ecting the win size. In this case,a reasonable evaluation objective is to estimate the nal game score. In either
case, experiments should be conducted to nd a suitable link function g. The
most commonly used candidates are the identity function and sigmoid functionsof the form g(x) = 2C=(1+ exp( x)) C . For instance, for modeling the winningchance an S{shaped link function g : IR ! [0; 1] can be used in order to deal
with saturation. In this regard, g(x) = 1=(1 + exp( x)) is of special interest,
because the weight tting process bene ts from a quickly computable derivativeof g, which in this case is g(x)(1 g(x)). A straight forward scoring scheme forterminal positions in this model assigns 0.9 to won positions, 0.5 to draws, and
0.1 to lost positions for the player to move. It is important to realize that an
optimal weight vector may not exist if the extreme values 1.0 and 0.0 are chosen.
Given a sequence of scored training positions ((pi ; ri ))Ni=1 the objective is tond a weight vector w0 which minimizes the error function

where

E (w) = N1

N
X

n
X



k (w) := rk g

i=1

k=1

k (w)2 ;wi hi;k and hi;k := val(ci (pk )):Starting with an initial guess w(0) , in each step the basic gradient descent procedure updates the weight vector according to (t) =
 (gradw E )(w(t) ) 4
w(t+1) = w (t) +  (t) :> 0 is the step size and gradw E is the vector consisting of E 's partial deriva@E . This update scheme changes the weights in direction of the error
tives @w
ifunction's steepest descent and is widely used for training arti cial neural networks.
In this application, the partial derivatives have a simple form due to GLEM's
at evaluation structure:N Xn@E (w) = 2 X
k (w)hi;k :
w
h
g
i
i;k
@wi
N k=1 i=1
0

(2)

If g is the identity function, this expression reduces toN@E (w) = 2 X@wi
N k=1 k (w)hi;k :Thus, steepest descent updates for all weights can be computed eciently in asingle pass through the training data. It is worth noting, that the computationof (2) can be arranged in such a way that its run time depends on the numberof hi;k di erent from 0, rather than on N . Especially when using patterns, thesavings thus achieved are signi cant.
Since the con guration match count may vary by large factors, the described
update step changes weights at very di erent speeds. This is undesirable, because
at one point the iteration process has to be stopped, and by then, weights ofrare but important con gurations might not have reached a proper level yet. A
simple way to deal with this problem is to normalize the updates by dividing
the sum by the number of hi;k 6= 0 instead of N .

5.2 Position Type Dependent Weights
The evaluation of con gurations may depend on the game stage or, more generally, on the particular type of the position. For instance, centralizing the kingin chess openings is considered suicide, whereas his activation is crucial in many
endgames. It may therefore be worthwhile to partition the training set according to position type, and to select con gurations and t weights separately foreach set. In order to avoid big evaluation jumps when crossing type boundaries,
which can cause undesired artifacts in game{tree search, it is helpful to de ne ne
grained position types and to smooth evaluations across adjacent types. Fitting
4
adding  (t 1) | known as \momentum" | can improve the convergence in caseof correlated features.

weights for many position types, however, requires a large number of training
positions, provided the minimal match count is maintained in order to eliminate over{ tting. Globally lowering the match count is therefore not an option.
Instead, a more local view can help to reduce the number of needed positions.
One suggestion when tting weights for a particular position type, is to consider the training positions from adjacent types as well. This method increases
the number of positions for any single position type and weights are smoothed
automatically. The second option is to t position type dependent weights ina more exible manner. For this purpose, valid con gurations are generated byconsidering all training positions. The weight tting process then decides, how
to compute the con guration weights separately for each type of position. For
any type, for which the particular con guration match count is suciently high(say  20), it is safe to t the according weight as described in the previous
subsection. If the count is small (say  4), over{ tting is likely and the con guration should be treated as if there is no information available, i.e. the weight is
set to 0. Cases in between can be handled by merging adjacent position types,
until the total match number allows a robust weight t. Here, the alternatives
are to have only a single weight for all involved types or, if there are enoughpositions available, to t a parameterized weight model. An example for such amodel is w(k) = a  k + b; k0  k  k1 , which states a linear relationship between the weight and the position type k | coded as an integer | in [k0 ; :::; k1 ].
Of course, this kind of model is only meaningful for position types that can betotally ordered, such as opening, middle{game, and endgame. Incorporating the
update of parameters a and b in the gradient descent procedure is not hard.
This technique allows a exible and robust tting of position type dependent
weights. After generating training positions and selecting con gurations, thisconcludes the evaluation function construction.

6 Application: Othello
The presented general framework for the construction of evaluation functions
has been inspired by the work on our Othello program Logistello. Besides the
progress in selective search and automated opening book construction, the application of the techniques discussed has contributed to the considerable playing
strength of this program. Logistello is able to beat the best human Othello
players handily, even when running only on ordinary hardware [2]. The details
of Logistello's evaluation function already have been discussed in [1]. We will
therefore only give a short overview and concentrate on its recent improvement,
which is based on the sparse pattern approach presented above.
Othello is a popular Japanese board game, played by two players on an 8x8{
board using 64 two{colored discs. Moves consist of placing one disc on an empty
square and turning all bracketed opponent's discs over. Fig. 5 shows an example.
The game ends when neither player has a legal move, in which case the player
with the most discs on the board has won.

1
2
3
4
5
6
7
8

abc de f gh
 fv vfStarting position(Black to move)

1
2
3
4
5
6
7
8

abc de f gh


 vv fv ff f v
 v f v f v v
 vvvvfv
 ffvfvv
 fff vf f fWhite to move

abc de f gh
1
v f f2 
3  v f f f v
4  ffvfvv
5  ffffffv
6  ffvfvv
7  fff  v
8 fff
Position after move b5

Fig. 6. Example positions. Legal moves are marked with a dot.
The most important concepts in Othello are disc stability, mobility, and parity. In particular:{ Stable discs can not be ipped by the opponent. Therefore, they directly
contribute to the nal score. The most prominent stable discs are occupied
corners, which can be used as anchors for creating more stable discs.
{ Having fewer move options than the opponent is dangerous, because it increases the chance of losing a corner in the near future.
{ Making the last move in an Othello game is advantageous, since it increases
one's own disc count while decreasing the number of opponent's discs. Parity
generalizes this observation by considering last move opportunities for every
empty board region.
In [1] it has been shown, that all of these features can be quickly approximatedby pattern con gurations built upon a raw board representation. The chosenpatterns are shown in Fig. 7. Horizontal, vertical, and diagonal lines of length 4 are included for covering mobility. The remaining patterns deal with the important corner regions and edges. The evaluation function distinguishes 13 gamestages, depending on the number of discs on the board. Applying the techniques
described in the previous sections, about eleven million scored training positions
were generated to t approximately 1:5 million weights. This gure takes weightsharing among symmetrical con gurations into account. Starting with w(0) = 0,
the weight tting procedure took a Pentium II/333 CPU about 30 hours toreach an acceptable accuracy level after 250 iterations. Equipped with an evaluation function very similar to that we have just described, Logistello beat
the human Othello World{champion 6{0 in August 1997 [2]. After four years ofsuccessful tournament play, Logistello ended its career in October 1997 witha straight 22{win victory in its last computer Othello tournament.
Recently, the incorporation of larger patterns has improved the evaluation
performance. In the current implementation, con guration weights are represented as 16 bit integers. Storing weights for 10{square patterns in 13 at tables
thus requires 310  2  13  1:5 million bytes. Using the same approach for storing
weights for much larger patterns is therefore out of the question. The rst experiments with several sparse data access schemes based on binary search were


































 
 


 






Fig. 7. Logistello's previous pattern set. Patterns that can be obtained by rotating

and mirroring the board have been omitted. Each diamond represents an atomic feature
f with range f0; 1; 2g. f (p) is de ned by the particular square contents (e.g. white disc
7! 0, empty 7! 1, black disc 7! 2).
A B C

  

Fig. 8. Large patterns tested. For each of these patterns the simpli ed pattern versionof GenConf generated about 88,000 valid con gurations (#E  11 million, n = 75).
All con guration sets t in hash{tables with about 310 thousand entries.

disappointing. Increasing the program's knowledge by adding the patterns shownin Fig. 8 could not compensate for a slowdown of about 45%. Only after utilizing
the fast hash{table access scheme and adding just one of the three features, theprogram achieved its best performance so far. Table 1 summarizes the results ofall tournaments that have been played to evaluate each version. All games wereplayed by brute{force versions of Logistello running on Pentium II/333 PCs.
On this hardware Logistello achieves a middle{game speed of approximately
270K nodes/sec when the patterns shown in Fig. 7 are used. This speed enables
the program to look 12{14 ply ahead in the opening and middle part of ten
minutes games.
The patterns presented in Fig. 8 were chosen based on both game and evaluation speed considerations. Human players frequently make use of their abilities
to evaluate large disc formations which are not covered by the basic patterns.
Of special interest are edge interactions and 2  8{corner con gurations. On theother hand, it is preferable to add patterns for which the index computation canmake use of already determined indices. The chosen 16{square patterns meet thispreference. Nevertheless, the results show, that the combined knowledge codedTable 1. Tournament results. Logistello using the basic patterns played 434{gametournaments against several versions that | in addition | employed the large patterns shown in Fig. 8. The results indicate that speed matters. The strongest versions
are those that only use either pattern A or B . They beat the previous version signi cantly, although they are 11% slower. When playing at equal strength the best version
only needs to search about 2/3 of the nodes | as the results of the time{handicap
tournaments indicate.
opponent results
winning
opponent time/game #nodes(minutes) (fraction) wins draws losses percentage
A
10-10
0:89
213 58
163
55.8
B
10-10
0:89
211 60
163
55.5
10-10
0:83
203 60
171
53.7
AB
ABC
10-10
0:8
211 49
174
54.3
A
6-10
0:51
172 59
203
46.4
A
7-10
0:62
183 55
196
48.5
A
8-10
0:71
195 63176
52.2
in the new patterns does not compensate for the speed drop. This nding indicates that a signi cant improvement of a sequential program may not be possibleby adding further patterns based on the raw board representation. However, amore e ective atomic features might exist which in combination outperform thecurrent evaluation function.

7 Summary and Discussion
In this paper a practical framework for the semi{automatic construction of evaluation functions has been presented. Based on a generalized linear evaluation
model | called GLEM | ecient procedures have been developed for generating training positions, exploring the feature space, and tting feature weights.
Rather than combining a few features by using complicated non{linear functions,
we propose to construct evaluation functions by combining many | possibly
more than hundred thousand | features, which are boolean combinations ofatomic relations. This approach allows us to model non{linear e ects directly,
without the detour over analytic functions, and opens up practical ways for generating features automatically. GLEM allows the program author to concentrateon the part of evaluation function construction, where humans excel: the discovery of fundamental positional features by reasoning about the game. GLEM
simpli es this task because the exact feature formulation is no longer needed.
The system is able to approximate complex features by combining atomic fragments. In this way, it is now possible for the programmer to speculate about
feature building blocks and to leave the creation of actually used features as wellas assigning weights to them to the system. One example for this strategy has
been presented in this paper: the observation that con gurations can approximate important Othello concepts combined with the \mechanical" analysis of

millions of training positions has produced an expert program capable of beating
any human player. An interesting fact is that the game knowledge encoded by
the set of over a million con guration weights goes far beyond the features weintended the system to approximate in the rst place [1]. This result encourages
the application of GLEM to other games or even to search or decision problems
in other domains. Attractive candidates are chess and Go since both games arevery popular and well analyzed. And yet, for chess, hardware roughly equivalent
to four thousand ordinary PCs is currently needed5 to compete with the humanWorld{champion. For Go the status is even worse because brute{force search is
not feasible due to the large branching factor. Since a good evaluation function
is not known either amateurs are still able to beat the best Go programs. It is
our opinion that the key to better chess and Go programs lies in improved evaluation functions. A starting point is the analysis of known features with regard
to their approximation by weighted con gurations as proposed by GLEM.
The automatic construction of features has been studied by several authors.
Utgo [10] proposes a general evaluation function learner, called ELF, which
combines the processes of constructing boolean feature combinations and weighttting. This approach has been shown to be e ective in small arti cial problems,
but could not convince in its application to checkers. The main problem of
ELF is its low speed. Taking into account the large number of features needed
for an adequate evaluation in complex domains, and the resulting considerable
e ort for optimizing weights, it seems hopeless to combine feature construction
and weight tting. Other approaches for constructing features or adapting the
combination function while tting weights (e.g. Morph [5], meiosis networks [3],node splitting [11]), face similar complexity problems. Our solution is to separate
these tasks in order to speed{up the process and to give many opportunities for
optimization.

References
1. M. Buro. Experiments with Multi{Probcut and a new high{quality evaluation
function for Othello. Workshop on Game{Tree Search, NEC Research Institute,
1997.
2. M. Buro. The Othello match of the year: Takeshi Murakami vs. Logistello. ICCA
Journal, 20(3):189{193, 1997.
3. S.J. Hanson. Meiosis networks. Advances in Neural Information Processing Systems, pages 553{541, 1990.
4. F. Hsu, S. Anantharaman, M.S. Campbell, and A. Nowatzyk. Deep Thought. In
T.A. Marsland and J. Schae er, editors, Computer, Chess, and Cognition, pages
55{78. Springer Verlag, 1990.
5. R.A. Levinson and R. Snyder. Adaptive pattern{oriented chess. In L. Birnbaumand G. Collins, editors, Proceedings of the 8th International Workshop on Machine
Learning, pages 85{89, 1991.
5
Deep Blue searched around 200 million nodes per second in the 1997 match with
Kasparov. Assuming a speed{up of four gained by using special purpose evaluation
hardware and a speed of 200K nodes/sec of a state{of{the{art PC chess program
leads to the given speed factor estimate.

6. W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery. Numerical
Recipes, 2nd edition. Cambridge University Press, 1992.
7. A.L. Samuel. Some studies in machine learning using the game of checkers. IBM
Journal of Research and Development, 3(3):211{229, 1959.
8. G. Tesauro. TD{Gammon, a self{teaching backgammon program, reaches master{level play. Neural Computation, 6(2):215{219, 1994.
9. G. Tesauro. Temporal di erence learning and TD{Gammon. Communications of
the ACM, 38(3):58{68, 1995.
10. P.E. Utgo . Constructive function approximation. Technical Report 97{4, Univ. ofMass., 1997.
11. M. Wynne-Jones. Node splitting: A constructive algorithm for feed{forward neuralnetworks. Neural Computing and Applications, 1(1):17{22, 1993.