Evaluation (Jazz)

The purpose of the evaluation function

As mentioned in the section on search techniques, the search operates by selecting moves that lead to good positions. There has been a long debate in the chess programming community about whether search or static evaluation is the most important. It is known (from an experiment by Berliner) that a greater search depth of 1-2 ply can fully compensate for a lack of extensive chess knowledge.

From this consideration, it's clear what the task of the evaluation function is: the evaluation function must assist the search in finding the best move. In particular, the evaluation function should help improve move ordering for positional play.

This isn't a particularly revolutionary idea, but adopting this stance puts us in a slightly different mind-set on what the evaluation function should do.

Dynamic evaluation

Chess is a dynamic game: every move changes the position on the board. Therefore, applying a static evaluation function in any arbitrary position is wrong: the static evaluation should only be applied in positions where there is no direct dynamcial threat (say, hanging pieces).

This is of course the purpose of the quiescence search: resolve any dynamical threats until the position is stable enough that we can give it to the static evaluation function. In other words, there's not a great deal more to consider here.

Static exchange evaluation

The one exception is "static exchange evaluation" (SEE). The purpose of SEE is to decide, based on the attackers and defenders present, whether any particular capture will win material. There is a relatively simple algorithm for this called the "swap algorithm" (chess programming wiki).

The down side of SEE is that it is static: there is no detection of dynamical threats: a capture may lead to a discovered attack (or a discovered check) or leave two pieces in a position where they can be forked. So it is not fool-proof, and trying to make it foll-proof is likely going to be too complicated and slow to make it worth it.

However, the fact that SEE is somewhat crude and doesn't always give the "right" answer doesn't really matter: the purpose of the evaluation is to improve the efficiency of the search, and for that SEE works very well.

The static evaluation function

Preliminaries

Assesing the (relative) worth of a position as a whole is the job of the (normal) evaluation function. There are a number of points that the evaluation function needs to consider:

  1. The material balance: the side ahead is likely to be better off.
  2. Material imbalance: we need to be aware of "bad exchanges": two minors for a rook and a pawn, say, or two pawns for the exchange.
  3. Piece placement: rooks should be on open files, knights should be directed to outposts, there should be a pawn shield in front of teh king, free pawns should advance.

There are a number of additional considerations for the relative worth of pieces as well (see Kaufman's article on naterial imbalances for more information):

  1. It's usually better to have two bishops rather than one. If both bishops are present, we give a small bonus. The "bishop pair" is a well-known concept.
  2. Knights are stronger in closed positions than in open positions. This is again well-known. Kaufman's article relates this to scaling the value of a knight with the number of pawns on the board, which is a proxy for how closed a position is likely to be.
  3. Conversely, rooks are stronger in open positions after a few pawns have been exchanged. This is again well known. Kaufman again relates this to scaling the value of the rook by the number of pawns on the board.
  4. Doubled pawns are bad, free or passed pawns are good

Kaufman's article also discusses penalties for rook and knight pairs, citing a "principle of redundancy". I'm not a chess master, so maybe it's not my place to say that this sounds strange to me - especially since combined rooks across a file are very strong, and trading rooks in a rook end game is usually a bad idea (makes the position more draw-ish). So I don't buy that argument for the rook (in fact, I don't really buy the argument for scaling the worth of the rook with the number of pawns either, unless the rook happens to be on a semi-open or open file, in which case the increased value of the rook is just a reflection of it being well placed). However, I will buy that two knights work together less well than two rooks or two bishops. Therefore, I applied Kaufman's relative scaling of the value of the knight only to the first knight: this makes the second knight worth relatively less than the first one, so the program is more likely to exchange a knight. Without this, the program would happily enter end games with two knights against two bishops, which isn't good - but by tne time this becomes clear, it's too late.

The placement of pieces (rooks on open files, etc.) can be dealt with in several ways. What I chose to do, which may be quite expensive, is to put all that information in the piece square tables, rather than calculate it on the fly whenever it's needed. There is one caveat, of course: the piece square table still needs to be calculated. However, we can do this once and then store the result for later retrieval if the position is similar. We do the same for the pawn structure.

When are positions similar? Well, if their pawn structures are the same.

Material imbalance

Pawn structure evaluation

Mobility

Piece square tables: knights

As a rule-of-thumb, knights are poorly placed on the edge of the board and even worse in corners. In other words, knights belong in or near the centre of the board. This is generally true and taken care of by the static piece square tables already.

In the dynamic piece square tables, we take into account good squares for the knight taking into account the pawn structure.

Good squares for knights are:

  1. Outposts, especially on the opponent's side of the board or near the centre. An outpost is a square that is defended by a friendly pawn and cannot be attacked by an enemy pawn.
  2. Stop squares in front of enemy free pawns.

Because the purpose of the evaluation is to guide the search to finding a good move, it's important to score positions in which good moves are likely a bit higher. For this reason, we also give a (smaller) bonus to squares that are one knight-step away from either a strong square or a stop square.

Knights should avoid getting trapped. This is an element of the mobility evaluation. I give a penalty for any square where a knight's mobility is impaired either by friendly pawns or by enemy pawns. In fact, I think I double count squares near the rim here as well, but that doesn't seem to hurt...

Piece square tables: bishops

Piece square tables: rooks

King safety

Both Jazz and Sjaak use a modified version of Ed Schöder's king safety algorithm. In some chess variants, there can be more than one king. In those cases, Sjaak does not calculate king safety at all.

Evaluation (Sjaak)

Sjaak's evaluation is greatly simplified: it uses material balance, static piece-square tables derived from heuristics based on how pieces move, mobility and king safety.

Sjaak also uses a modified version of the SEE routine from Jazz to evaluate captures.