Rudolf Posch

RDChess Technical Program Description

Part 2 Move generation and search

Move Generation

RDChess implements a Move List Class (TMovLst), containing all legal moves out of a position and the member functions for move generation etc.
RDChess is outstanding in this respect, most of the move generators of other current chess programs generate "pseudo legal" moves, containing also moves which may leave the own king in check (e.g. moving a piece which is pinned to the own king). Generating only the "really legal" moves needs a high programming effort (much code), which I think is the main reason for its rare use.

The additional code consumes time at move generation, which is lost in cases where the move is not even searched later (because of Alfa-Beta pruning) .
But RDChess uses efficient Pentium inline assembler code nearly throughout the whole move generators and a very efficient 32 bit TMove structure (which fits into the 32 bit registers of the Intel processor architecture).
Overall the "really legal" move generation seems advantageously.

Moves ( 32 bit TMove items) are generated and stored in 2 different move lists,

one for capture (+ en passant, + pawn promotion ) moves,
one for normal (non capture, including castling) moves.

There exist 4 move generation routines. At positions, where the own king is not in check

a Full Move Generator, which generates all possible moves (capture and non capture) and
a Capture Move Generator, which generates only capture moves.

In positions, where the own king is in check, there are

a "Capture Checking Piece" Move Generator, which generates all possible captures of checking pieces and
an "Escape Check" Move Generator, which generates non capture moves, leading out of check (king moves to unchecked squares and moves from pieces to block the ray from the checking piece to the own king).

Besides the above mentioned 4 move generation routines there exist no "incremental" move generation routines, creating only few moves at a time, in the hope an early cutoff saves partly move generation effort.

For better Alf-Beta efficiency the moves are preordered at generation time to some extent. The move generators generate moves in direction "forward" and in direction to the opponents king before generating moves backward and away from the opponents king. For this purpose black and white"direction tables" with one of 8 entries per "from"- square (North, East, South, West, NW, NO, SW, SO) are precalculated. The opponents kings square from the root position is used for choosing the proper direction table at the root level of the search.
Capture moves from less valuable pieces are normally generated first as well as some other rules are followed (e.g. double rank advance pawn moves before single rank advance move are in the average presumably more valuable) .

During the search moves are selected from the preordered move lists applying special rules (see below), but the pre-order is coming into effect if no other rules override.
2 debug windows of RDChess show the moves in generation order and in the order, in which they are searched.

Search Engine

The Search is called for a computer move, returning a "main variation" (best move sequence) out of the current position and an evaluation value for this best move. The search is also called during the opponents time to think for his move ("permanent brain"). Assuming the opponents most favorable move done, a computer reply move for that position is searched . If the opponent doesn't choose the expected move, the search result move is discarded and the search for the computer answer move must be started again from the position reached by the unexpected move.

The search routine runs not in an extra MS Windows thread (I had no opportunity yet to implement this). Instead of the search suspends at regular intervals (with an "Application.ProcessMessages" call) to the Windows message loop, allowing the processing of user interaction (e.g. press of the Escape key) during the computer search.

The search engine uses an depth first Alfa- Beta search routine in NegaMax formulation and consists of 3 routines.

At the root level (depth 0) a search function with an aspiration window (preset Alfa and Beta value guesses) deepens the search iteratively until the allocated time has expired or the maximum assigned search depth is reached. If the search result is outside the Alfa-Beta aspiration window values, the search is repeated.
The root search returns a best move out from the Principal Variation, an evaluation value for the move and additional data (search statistic data, ...).

Until the maximum full width search depth, the search calls recursively a full width NegaMax search routine.

The full width search routine features

Use of Position hash tables
Null window search ("Nega Scout" search algorithm with an narrow window after the first ("best") move of each position has been searched ),
Null move heuristic,
Search extensions, increasing the full width depth for 1 ply under certain conditions (when the own king is in check and in a few other positions, e.g. after moving a pawn from the six to the seventh rank),
Recognize position repetitions (inside the search as well as in the move history of previous moves) and evaluate them to "near draw values",
Forward Pruning techniques like razoring at horizon depth -3, extended futility pruning at horizon depth - 2 and normal futility pruning at frontier nodes (horizon depth -1) (see /5/).

Search order of moves:

First an eventual stored move from the position hash table is tried,
Secondly a null move (only under certain conditions like "own king not in chess" and others ) is searched;
Moves which are capturing pieces, which have captured an own peace at the previous move,
Moves from the killer move list (there are two killer moves stored for each search depth),
Capture moves with an expected positive static exchange value, sorted falling with expected win value,
Normal moves (= non capture) from "strongly" attacked squares to "not attacked" or defended squares,
Remaining normal moves from any squares to "not attacked" or defended squares,
Remaining normal pawn moves (from any squares to any squares),
Capture moves with an expected negative static exchange (e.g. queen captures a pawn, which is defended by a pawn),
All remaining normal moves.

Move generation is postponed after a hash table respectively null move has been tried.

After the full width search a quiescent search tries eventual capturing moves in order to reach a "quiescent" position for static evaluation.

The quiescent search routine features

Use of position hash tables (reading hash values; but storing only at the nominal full width search depth),
Forward pruning of non-checking moves if the static position evaluation value plus an estimate of a capture gain value is below the current Alfa boundary (assuming that the capture move doesn't lead inside the Alfa-beta window),
estimation of a position value without calling the evaluation function , if the material score plus/ minus a reasonable maximum value for positional evaluation parts of the position are below/ above Alfa/ Beta,
estimation of a position value without calling the evaluation function for positions beyond the maximum full width search depth

The quiescent search terminates when a capture move leads to a Beta cutoff or after the best of the capture moves searched raised the static position evaluation value.
Is not such a capture move found, it will be assumed that at least one "non capture" move leads to an evaluation as good as the static position evaluation and the search is terminated also. This is only true if the own king is not in check. If the own king is in check, after the "Capture checking piece" moves there are generated all "Escape Chess" moves and tried one by one. If the score of one of these moves reaches the static position evaluation value, the quiescent search terminates, assuming that the remaining "non capturing" moves don't lead to scores greater than the static evaluation.

Position (Transposition) Hash Table

The current implementation of RDChess stores during a full width search for each position which increases the Alfa value a hash record in the transposition hash table.

The hash record contains

a 64 bit hash key (for collision detection),
the best move (32 bit TMove) for this position,
a set value for the type of the hash entry (value is exact, upper bound or lower bound),
the value of the position (exact value or value of upper bound or value of lower bound),
a "draft" (search depth which was used for acquiring the position value).

These stored values are used if the same position is reached again in the search later on,

because the same position was reached over another path (transposition),
or in a search repetition because of a null window fail high < Beta,
within iterative deepening
or in searching a follow up root position.

In full width search, only hash entries are used with a draft greater/ equal then the current remaining search depth. In quiescent search, a successfully read hash entry is used independently of the draft.
Depending on both the bounds in effect when the hash value was stored and the current Alfa-Beta values, the hash value may be used immediately (e.g. with an exact value), or leads to a cutoff (lower bound hash value greater/equal to current Beta value; higher bound hash value lower/ equal to current Alfa value) or raise the current Alfa value (lower bound value greater than current Alfa value) or lowers the current Beta value (upper bound lower the current Beta value).

For calculating the position hash key a constant table with 64 (square index) x 13 (piece set values) random 64 bit integers is used (Zobrist scheme).
The hash key is calculated by adding for each piece on the board a 64 bit integer out from the table, indexed by the piece value and the square the piece sits on. In order to discriminate fully a board position, additional random numbers are folded in, depending on the side to move (black or white), on the castling rights and the Enpas square.
The 50 move rule count is not counted for. Positions devaluated because of "position repetition" are therefore not stored in the hash table.

The hash table is not cleared after executing a move in the root position. Instead of, the hash table is used and expanded for several moves on the board. Entries from previous searches are flagged and will be earlier overwritten in case of low memory.
A "hash table use count" is incremented (at normal moves by one, capture and pawn moves by 2) until a preset "maximum hash table use count" is reached. The maximum use count is set higher in the endgame as in the early/ middle game.

Go to to RDChess Technical Description Part 3 (Evaluation, ...)

Back to RDChess Technical Description Part 1

Last modified 2002-08-22 Rudolf Posch