Evaluation

[Dieter Hemmers]

Hello,
I have written a small chess engine with 0x88-Board-Representation and alpha-Beta search-algorithm. What is the best way to implement an evaluation function? Is it better to examine the position at the root much more than the others or should I examine all positions the same way. How do most programs work?
Dieter

[H.G.Muller]

I am not sure what you mean by 'more often'. Surely it is always meaningless to evaluate the same position more than once?

Usually one evaluates at the end-leaves, but if you iteratively deepen the search positions at any level will be end-leaves in some stage of the search process. Initially the ones close to the root, and then progressively further away.

If a certain position is an internal node for a certain search depth, where all moves radiating out from that position are searched, an evaluation will not be used at all: the score for that position is purely derived as the value of the best move, through minimax. Only in nodes where not all moves are tried (e.g. quiescence search) you need evaluation to determine the score, in case all moves that are tried turn out to be worse than the current position is evaluated statically, under the assumption that among the moves that you did not consider there will be at least one that preserves the current balance.

[Dieter Hemmers]

I am not sure what you mean by 'more often'. Surely it is always meaningless to evaluate the same position more than once?

Usually one evaluates at the end-leaves, but if you iteratively deepen the search positions at any level will be end-leaves in some stage of the search process. Initially the ones close to the root, and then progressively further away.

If a certain position is an internal node for a certain search depth, where all moves radiating out from that position are searched, an evaluation will not be used at all: the score for that position is purely derived as the value of the best move, through minimax. Only in nodes where not all moves are tried (e.g. quiescence search) you need evaluation to determine the score, in case all moves that are tried turn out to be worse than the current position is evaluated statically, under the assumption that among the moves that you did not consider there will be at least one that preserves the current balance.

My question is, if it is possible to find a "plan" in the root position. When you play chess, you look at a position and you find out, that there is only one good positional move. This evaluation could be very expensive. Then every position with this good positional move should give a plus in evaluation? The other side is to evaluate every position the same way by static parameters.

[Leen Ammeraal]

Chess engines evaluate the position, or 'plan' as you put it,
not only at the root but on the leaves of the search tree.
The fact that such static evaluation is often done rather
clumsily by computers (compared with good human players)
is compensated for by the enormous number of positions,
for which it is done.
I can understand your question very well, since
when I started chess programming I also tried to do this
static evaluation at a less deep level than the tactical
search for material gain and mate. But I soon abandoned this
idea, and I now do everything at the leaves, as everyone else does.
Leen Ammeraal

[mathmoi]

Chess engines evaluate the position, or 'plan' as you put it,
not only at the root but on the leaves of the search tree.
The fact that such static evaluation is often done rather
clumsily by computers (compared with good human players)
is compensated for by the enormous number of positions,
for which it is done.
I can understand your question very well, since
when I started chess programming I also tried to do this
static evaluation at a less deep level than the tactical
search for material gain and mate. But I soon abandoned this
idea, and I now do everything at the leaves, as everyone else does.
Leen Ammeraal

Hi Leen and Dieter,

REBEL call it's evaluation function at each nodes (http://members.home.nl/matador/chess840.htm) If I remember well it improves the move ordering (There is also oder benifit, refer to the REBEL page for more infos).

I also read about a technique that analyzed the root position to create piece/square tables based on the actual position at root. Thoses piece/sqares tables were used during the search to follow a plan choosen during the analyze of the root position. For example, if the b-file is open, the piece-squares values for a rook on a square of the b-file receive a bonus, so during the search the position wich have a rook on the b-file are prefered and this is virtually free to evaluate since any good chess engine already have a piece/sqare table evaluation. The analyze at the root is also virtually free since it's only run once.

This allow the search to follow a plan choosen in function of the root position. Program using them seem (and actually have) to have a long time plan. However with engine / hardware that reach depth of 14-16 ply like we do today the piece square table often end completly out of date, hurting performances.

This last technique is explained in "Programme d'?checs de championnat : architechture logicielle, synth?se de fonctions d'evaluations, parall?lisme de recherche" Phd Thesis from University Of Paris 8, January 1995. This document is avaible on the web in french version.

Mathieu Pag

[Tord Romstad]

If a certain position is an internal node for a certain search depth, where all moves radiating out from that position are searched, an evaluation will not be used at all: the score for that position is purely derived as the value of the best move, through minimax. Only in nodes where not all moves are tried (e.g. quiescence search) you need evaluation to determine the score, in case all moves that are tried turn out to be worse than the current position is evaluated statically, under the assumption that among the moves that you did not consider there will be at least one that preserves the current balance.

I don't quite agree. You are right that the static evaluation scores of internal nodes will never propagate back to the root, but in my experience it is very hard to write an efficient search without evaluating internal nodes. The nodes/second count drops a bit, but the vastly reduced tree size more than compensates for this.

It would be interesting to read the opinions and experiences of other programmers concerning this. Do you evaluate internal nodes or not?

Tord

[H.G.Muller]

With iterative deepening it might be difficult to really make the distinction, because every node that is touched starts out as a leave node, and thus needs evaluation. My own code does even internal iterative deepening, so each time you revisit a certain position in the tree, even if it is comparatively near the root for the current requested over-all depth, it starts with a zero-ply search (= evaluation), then one, etc. At least in theory, in practice of course all the shallower searches are already in the hash table and taken from there.

But I now understand the initial question better. It is important, however, to clearly distinguish evaluation of a move from evaluation of a position. For minimax you need evaluation of positions in the end leaves. You can try to build these from adding up evaluation of moves leading from the root to that position (differential update of the evaluation). In that case you have to start evaluating from the very beginning, of course, even without iterative deepening. Depending on how sensitive evaluation components are to subsequent moves this might either pay or not pay at all.

[smcracraft]

Hello,
I have written a small chess engine with 0x88-Board-Representation and alpha-Beta search-algorithm. What is the best way to implement an evaluation function? Is it better to examine the position at the root much more than the others or should I examine all positions the same way. How do most programs work?
Dieter

Dieter - congratulations on your program.

You will get many opinions.

Three choices appear:

1) pcsq with just material+pcsq at terminal nodes
This is very old - good for your first month. Test it and keep your testsuite
results.

2) terminal node evaluation with material+mobility+pawn_structure+
kingsafety
Compare this with #1

3) node evaluation at every node in the tree (Rebel method)
I experimented with this for a short while.

I now use #2 and am expanding my evaluation function. Although
it is bitboard-based, it is still a lot of programming to get all the
support bitboard tables, for example for passed pawn and square
of pawn setup - I still need to do those, plus a lot more pawn structure
logic -- which is fine since pawn structure is free - as I get 96% of
pawn structures pre-existing in hash table.

So enjoy your new program and I recommend #2.

Stuart