1. Architecture and Data structures
The following description is meant for computer programmers, who are already acquainted with the basic principles of chess programming like search algorithms, evaluation functions etc. The text describes the actual implementation in RDChess and highlights on specific features implemented in RDChess, probably not found (in this form) in other chess programs.
Architecture
Programming environment
RDChess runs under 32 bit MS Windows on Personal computers.
RDChess is written with the Borland Object Pascal language. Performance critical functions (e.g. the whole move generator, some evaluation functions like pawn evaluation etc.) are written in (Pentium II optimized / MMX) Intel assembler code.
The program uses the Borland’s DELPHI Visual Component Library for the Graphical User Interface (GUI) and to some extent (in not performance critical sections) self written classes.
Because of the use of some DELPHI 5 specific compiler extensions (e.g. 64-bit integers int64) the program compiles only with the DELPHI 5 or later compiler. RDChess consists of about 27 Delphi user interface forms (.frm) and 34 Delphi units ( .pas). The source code contains about 25.000 lines of code.
The following text describes the chess engine only. The User interface program parts are not included here, some information about it you find in the RDCHESS User manual. Information about the WinBoard interface built into RDCHESS you can read here. RDChess is written with the Borland Object Pascal language. Performance critical functions (e.g. the whole move generator, some evaluation functions like pawn evaluation etc.) are written in (Pentium II optimized / MMX) Intel assembler code.
The program uses the Borland’s DELPHI Visual Component Library for the Graphical User Interface (GUI) and to some extent (in not performance critical sections) self written classes.
Because of the use of some DELPHI 5 specific compiler extensions (e.g. 64-bit integers int64) the program compiles only with the DELPHI 5 or later compiler. RDChess consists of about 27 Delphi user interface forms (.frm) and 34 Delphi units ( .pas). The source code contains about 25.000 lines of code.
Architecture
RDChess is based on the broadly used template of "Shannon type A brute force searchers" , described in detail for the Northwestern University chess program CHESS 4.5 (/1/).
RDChess makes a "nominal" full width Alfa-Beta (NegaScout) search (/2/, /4/) until a predefined search depth, followed by a "quiescent search". The leaf positions in the search tree are scored with a static evaluation function, taking into account the material situation (number and type of black and white pieces) and -to a far less extent- the positional terms.
I have developed the program mainly with information contained in the following 5 books. I recommend /1/ and /2/ as classical standard books, reading these is a must for every serious chess programmer:
Peter Frey (editor)
/1/ Chess Skill in Man and Machine
Springer-Verlag, 1982 ISBN 0-387-90790-4, 3-540-90790-4
Tony Marsland, Jonathan Schaeffer (editors)
/2/ Computers, Chess, and Cognition
Springer-Verlag, 1990 ISBN 0-387-97415-6, 3-540-97415-6
Bartel, Kraas, Schrüfer
/3/ Das grosse Computerschachbuch
Data Becker 1985 ISBN 3-89011-117-3
Alexander Reinefeld
/4/ Spielbaumsuchverfahren (Informatik-Fachberichte 200)
Springerverlag, 1987 ISBN 3-540-50742-6
Ernst A.Heinz
/5/ Scalable Search in Computer Chess
Vieweg 2000 ISBN 3-528-05732-7
RDChess doesn’t use the today very popular “bit boards” (64 bit fields for diverse chess board representations, like e.g. a bit board with bits set for all pieces standing on the squares addressed by the bit number of the bit board).This has historical reasons, I started the program development with a board array and never changed to bit boards. Anyway, with the soon coming availability of Intel 64 bit micro proccesors I should revise my decision. Instead of, RDChess uses an older scheme, a 12 x 12 byte array as board, linearly addressed (Board: array[0..143] of TPieces). 2 rows and 2 files are added on both sides of the 8 x 8 chess board for easier move generation purposes.
Each field of the array contains a set value for the piece standing on the square (e.g. white king, black rook, etc.), or the value for a “free square” (only on the inner 8 x 8 chess board) or the value for an “outside square”.A second 144 byte (12 x 12) array contains for each square an index into the Piece List (to identify an actual piece standing on the square, discriminating e.g. between 2 rooks). Piece Lists (TPList)
RDChess keeps one list for all white and one list for all black pieces which are still on the board (max. 16 pieces per side), containing the set-value for the piece and the square index where it sits on the board (index into the 144 byte Board array).
The chess board and piece lists (and some more data in the following position context) are updated incrementally during a search, that means at deepening and restoring a chess position when executing/ taking back a move only the data items changed with the move are updated. This is faster than calculating e.g. the whole piece list every time from the scratch in a new position.
Move Structure (TMove)
The 32 bit TMove structure consists of four 1 bytes fields
Position context (TPosCtxt)
There is one large important data structure, which is used throughout the program. It contains all chunks of data which describe one chess position (additionally to the TBoard and TPL list).
RDChess calculates for each position (just before calling the move generator) two 12x12 byte attack table arrays for the black and white attacks to each square on the board. The RDChess attack table routines were implemented in assembler code with only one byte reserved for attacks to 1 square and have therefore severe shortcomings.
One square on a chess board may be attacked by
There are no extra X ray attack tables. But in the attack tables an X ray attack of a less valued piece through a more valued piece (like a rook behind a queen) is counted in the above described attack byte. X ray attacks of sliding pieces (queen, rooks, bishops) through the king are also counted on the squares behind the king.
Because of the above described shortcomings, the attack tables may not be used for a full fledged static exchange evaluator. But the attack tables suffice to support the "really plausible" move generator (see below) and for the purpose of better move ordering, where a wrong ordering because of missing attack data (e.g. not counting a second queen) may only result in a performance penalty and not in e.g. fully missing a good move.
An evaluation term for field control is calculated in the position evaluation routine, using the attack tables.
Pinned pieces array
The position context includes a "Pin" record array for a maximum of 8 pieces (from the side to move), which are pinned by opponent sliding pieces against the own king. A Pin record contains the direction of the pin, the pinned piece and the pinning piece, together with the squares where both pieces sit on.
This data is used during "really plausible" move generation and for an evaluation term, punishing pins which may be bad for the side on move.
Main Variation array
The principal variation array keeps for every searched depth the best move continuation (sequence of alternating best moves for both sides).
There are kept several main variation arrays, one for the search, one for the root position (permanent brain search) and others.
Killer move array
2. 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,
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.
RDChess makes a "nominal" full width Alfa-Beta (NegaScout) search (/2/, /4/) until a predefined search depth, followed by a "quiescent search". The leaf positions in the search tree are scored with a static evaluation function, taking into account the material situation (number and type of black and white pieces) and -to a far less extent- the positional terms.
I have developed the program mainly with information contained in the following 5 books. I recommend /1/ and /2/ as classical standard books, reading these is a must for every serious chess programmer:
Peter Frey (editor)
/1/ Chess Skill in Man and Machine
Springer-Verlag, 1982 ISBN 0-387-90790-4, 3-540-90790-4
Tony Marsland, Jonathan Schaeffer (editors)
/2/ Computers, Chess, and Cognition
Springer-Verlag, 1990 ISBN 0-387-97415-6, 3-540-97415-6
Bartel, Kraas, Schrüfer
/3/ Das grosse Computerschachbuch
Data Becker 1985 ISBN 3-89011-117-3
Alexander Reinefeld
/4/ Spielbaumsuchverfahren (Informatik-Fachberichte 200)
Springerverlag, 1987 ISBN 3-540-50742-6
Ernst A.Heinz
/5/ Scalable Search in Computer Chess
Vieweg 2000 ISBN 3-528-05732-7
Data Structures
The data items described in the following are used in the chess engine. Additional data structures used for the representations on the graphical user interface are not described here.Chess board representation (TBoard)RDChess doesn’t use the today very popular “bit boards” (64 bit fields for diverse chess board representations, like e.g. a bit board with bits set for all pieces standing on the squares addressed by the bit number of the bit board).This has historical reasons, I started the program development with a board array and never changed to bit boards. Anyway, with the soon coming availability of Intel 64 bit micro proccesors I should revise my decision. Instead of, RDChess uses an older scheme, a 12 x 12 byte array as board, linearly addressed (Board: array[0..143] of TPieces). 2 rows and 2 files are added on both sides of the 8 x 8 chess board for easier move generation purposes.
Each field of the array contains a set value for the piece standing on the square (e.g. white king, black rook, etc.), or the value for a “free square” (only on the inner 8 x 8 chess board) or the value for an “outside square”.A second 144 byte (12 x 12) array contains for each square an index into the Piece List (to identify an actual piece standing on the square, discriminating e.g. between 2 rooks). Piece Lists (TPList)
RDChess keeps one list for all white and one list for all black pieces which are still on the board (max. 16 pieces per side), containing the set-value for the piece and the square index where it sits on the board (index into the 144 byte Board array).
The chess board and piece lists (and some more data in the following position context) are updated incrementally during a search, that means at deepening and restoring a chess position when executing/ taking back a move only the data items changed with the move are updated. This is faster than calculating e.g. the whole piece list every time from the scratch in a new position.
Move Structure (TMove)
The 32 bit TMove structure consists of four 1 bytes fields
- the "from" and "to" squares (indices in the TBoard array),
- the move type (normal move, capturing move, castling move, en passant pawn capturing move, pawn promotion move),
- the set value of the piece which is moved (wKing, bRook etc.) or the promotion piece (white or black queen, rook, bishop, knight) in case of a pawn promotion move.
Position context (TPosCtxt)
There is one large important data structure, which is used throughout the program. It contains all chunks of data which describe one chess position (additionally to the TBoard and TPL list).
- TPosCtxt contains for a specific position
- the actual castling rights,
- the "Fifty move rule" count,
- the en passsant pawn status (to - square of an eventual double advance pawn move of the opponent, which resulted to the actual position),
- the previous move (which resulted to the actual position),
- the full width search depth of the current search
- the number of the white and black officers, white and black pawns (for null move and "pawn endgame" discrimination and other purposes)
- Material sums for the white and black pieces,
- 144 bytes (12x12) Attack Tables (TAttack, see below) for white and black,
- 64 bit hash value of the actual position for the position hash table (incrementally updated),
- 32 bit hash value of the actual King-Pawn formation for the King - pawn - hash table (incrementally updated),
- Game/ Opening library state information,
- a list of pinned pieces (for the "Pinned pieces evaluation term" and the "really legal" move generators),
- and more.
RDChess calculates for each position (just before calling the move generator) two 12x12 byte attack table arrays for the black and white attacks to each square on the board. The RDChess attack table routines were implemented in assembler code with only one byte reserved for attacks to 1 square and have therefore severe shortcomings.
One square on a chess board may be attacked by
- 0 - 1 king (1 k-bit),
- 0 - 8 (!) queens, implemented is only 1 q-bit ( 0-1 queens),
- 0 - 4 rooks, implemented are only 2 rr-bits (0-3),
- 0 - 4 bishops and
- 0 - 8 knights. Implemented are only 2 bb bits (0-3) for bishops and knights together!
- 0 -2 pawns ( 2pp-bits).
There are no extra X ray attack tables. But in the attack tables an X ray attack of a less valued piece through a more valued piece (like a rook behind a queen) is counted in the above described attack byte. X ray attacks of sliding pieces (queen, rooks, bishops) through the king are also counted on the squares behind the king.
Because of the above described shortcomings, the attack tables may not be used for a full fledged static exchange evaluator. But the attack tables suffice to support the "really plausible" move generator (see below) and for the purpose of better move ordering, where a wrong ordering because of missing attack data (e.g. not counting a second queen) may only result in a performance penalty and not in e.g. fully missing a good move.
An evaluation term for field control is calculated in the position evaluation routine, using the attack tables.
Pinned pieces array
The position context includes a "Pin" record array for a maximum of 8 pieces (from the side to move), which are pinned by opponent sliding pieces against the own king. A Pin record contains the direction of the pin, the pinned piece and the pinning piece, together with the squares where both pieces sit on.
This data is used during "really plausible" move generation and for an evaluation term, punishing pins which may be bad for the side on move.
Main Variation array
The principal variation array keeps for every searched depth the best move continuation (sequence of alternating best moves for both sides).
There are kept several main variation arrays, one for the search, one for the root position (permanent brain search) and others.
Killer move array
For each search depth 2 "killer" moves (best and "second best" move of all positions searched in this depth) are stored with attached killer move use counts.
New (different) killer moves overwrite the killer move with the less use count.
The killer move with the higher use count is searched first.
New (different) killer moves overwrite the killer move with the less use count.
The killer move with the higher use count is searched first.
2. 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.
- a Full Move Generator, which generates all possible moves (capture and non capture) and
- a Capture Move Generator, which generates only capture moves.
- 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).
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.
3. 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
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
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
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.
4. Evaluation Function
Positional scores for diverse positional advantages (e.g. a rook on a free file) are much less weighted as material advantage. They rarely exceed the value of one pawn (e.g. at bonuses for passed pawn near the 8th rank).
A chess mate position is valued -VMATT or +VMATT (generic value about +/- 18000 for loosing respectively winning), although such a position is detected in the search, and not in the evaluation function.
The RDChess evaluation is called in game states outside the opening library and discriminates between
RDChess keeps diverse global game state variables like the side to which (white and black) has castled, "White in the Endgame" etc.
Depending on that Game State variables, some position evaluation parameters are switched before searching at the root level.
E.g. the pawn advancement bonuses are increased at falling material sums or on the opposite side where we have castled, or the king changes his strategy from hiding in a corner in the early middle games to strive for the center, if the opponent material decreases.
For standard positions the evaluation function calculates the sum of
Pawn evaluation
The calculation of the pawn score term is the most elaborated part of the evaluation function and certainly one of the most important procedures.
Various positional characteristics like isolated pawns, doubled pawns, backward pawns, pawn advancement and passed pawns are scored.
For pawn advancement 12 x12 board advance tables are pre calculated at each root position, containing a value which is scored for a pawn standing on this square. The king castling status at the root position is taken into account. E.g. pawns on the opposite side of the board where the own king has castled get a higher advance bonus. Has the opponent king castled to this side, the advance bonus is even more raised.
Passed pawns are scored higher if they are supported by adjacent, connected own pawns. The attack status or blocks on squares before a passed pawn (in direction to the promotion square) is taken into account.
King evaluation
The king evaluation is strongly divided into a standard evaluation where king safety is of importance and an Endgame evaluation, where the king actively takes part in the game.
The standard evaluation punishes facts which hinder castling and rewards a king which has already castled. The punishment decreases for an not castled or "lone standing" king proportionally with a falling material strength of the opponent.
In the endgame there is a bonus for center tropism (small distance of king to the center of the board)..
The king evaluation is strongly interconnected with the positions of the pawns.
In standard evaluation the pawn shelter around the king is rewarded.
In the Endgame the distance of the king to pawns, especially to passed pawns and to "backward" pawns (pawns which cannot advance because of threads or hang behind) is of advantage and positively scored.
In a Pawn Endgame the distances of the kings to the promotion squares are considered ("square of king"- promotion rule) and in unmistakable favorable positions for queening very high bonuses are scored .
King-Pawn Hash Table
RDChess doesn't use like most other chess programs a pawn formation hash table and eventually a king hash table..
Instead of, because of the many evaluation terms both depending on the places of the kings and pawns, a single hash table, holding evaluation values for positions with identical king and pawn squares is kept.
This unique scheme proved to be quite advantageous, the read hit rate in the King-Pawn-Hash-Table is quite high, which I believe is because of seldom advantageously made king moves during a search.
Evaluation of Officers
All officers are punished for standing on the first rank in the early middle game, in order to favor early piece development (but queens are punished for moving too early over the third rank).
All officers get bonuses for controlling more centrally located squares and squares around near the opponents king.
Hung pieces (of the side on move) are punished. Against the king pinned own pieces are punished (see Pinned Pieces).
Rooks get a bonus for being on the seventh rank, for doubled rooks, for being on a file with passed or backward pawns. Standing behind a passed pawn in the Endgame is even more advantageously.
"Bishop pairs" (possession of more than one bishops of opposite colors) get a bonus.
In the endgame an proprietary RDChess bishop positional term is added. At endgames with different colored bishops or where the opponent has only a bishop of one color the own pawns get bonuses for standing on fields with the same color as the own bishop and punishments on fields with opposite color as the opponents (lone) bishop. For the opponents pawns there counts the opposite.
This term makes it easier to defend own pawns and attack the opponents pawns with bishops and should be advantageously in endgames, where is more room on the board. On the other side putting
There are some other scores not mentioned.
5. Performance
RDChess is a medium strength program, comparable with other free/ shareware chess programs like GNUCHESS or Waxman.
It is clearly inferior to commercial programs like Fritz etc. and other good academic programs like Crafty.
Anyway, it's strong enough to win nearly always against its creator (me) and 95% of all chess players on the world with a setting of 3 seconds/ move.
RDChess searches about 30.000 nodes/second in the opening, about 60.000 in the middle game and more than 90.000 nodes/s in end games (with few pieces left) on an Intel Pentium III 450 MHz processor.
On a newer PC with Intel Core 2 Q6600 Quad CPU with 2,4 GHz RDChess searches in the middle game around 500.000 nodes per seconds (which is quite few compared to other chess engines).
I observed a strong dependence of the search velocity on the alignment of critical data structures and (supposedly) the distribution of dynamical data in memory (L2 cache). Inserting a few bytes of code and rebuilding the program causes an unpredictable variation in the search velocity of up to 20 %, supposedly depending on the alignment (byte, word, .. paragraph/32 byte boundary) of often used data structures !
I have no data about the quality of code (relating to speed) generated by the Delphi 5 compiler (with compiler option “optimization” checked) compared to C++ Builder V4 or MS Visual C++ V6 generated code.
I assume that C++ code with compiler optimization is faster than Object Pascal code, but that is only a guess of mine.
I tried compiling the Delphi 5 code with C++ Builder V4, in order to port later the code to C++. This failed because of some incompatibilities between both compilers relating to register use in inline assembler code.
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/).
- First a 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 capture pieces, which have captured an own piece 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.
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
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).
- 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.
4. Evaluation Function
Position Evaluation
RDChess's position evaluation is like in most other chess programs dominated by material. The possession of a pawn is worth 100 units. Stronger pieces are valued similar to figures documented in the chess literature (a queen with about 900 units, a rook with about 510 units, bishops and knights with about 325 units).Positional scores for diverse positional advantages (e.g. a rook on a free file) are much less weighted as material advantage. They rarely exceed the value of one pawn (e.g. at bonuses for passed pawn near the 8th rank).
A chess mate position is valued -VMATT or +VMATT (generic value about +/- 18000 for loosing respectively winning), although such a position is detected in the search, and not in the evaluation function.
The RDChess evaluation is called in game states outside the opening library and discriminates between
- standard positions in the early and middle game,
- standard positions in (early) endgames states,
- Pawn end games (with only both kings and some pawns on the board),
- Near mating positions (the opponent being more than one rook value behind and having no pawns left). In such positions an abbreviated evaluation function is applied, driving the opponents king into a corner to mate;
- drawn positions because lack of material, positions with 50 Move Rule counts > 100 etc. A value for "Drawn position" is returned;
- Game theoretical special positions like KBB against K or KBN against K end games. A specifically adapted evaluation function is called for these positions.
RDChess keeps diverse global game state variables like the side to which (white and black) has castled, "White in the Endgame" etc.
Depending on that Game State variables, some position evaluation parameters are switched before searching at the root level.
E.g. the pawn advancement bonuses are increased at falling material sums or on the opposite side where we have castled, or the king changes his strategy from hiding in a corner in the early middle games to strive for the center, if the opponent material decreases.
For standard positions the evaluation function calculates the sum of
- the material balance (material difference between the sum of the material values of the white and black pieces),
- an additional material function value with a trade down bonus, raising the score for the side in advantage, if there are less pieces and less pawns on the board (this term is described in articles about the Northwestern university chess program CHESS 4.5),
- a field control term (difference between the number of from black and white attacked squares, weighted with quality factors),
- and positional score terms for pawns, the king and all the other pieces.
Pawn evaluation
The calculation of the pawn score term is the most elaborated part of the evaluation function and certainly one of the most important procedures.
Various positional characteristics like isolated pawns, doubled pawns, backward pawns, pawn advancement and passed pawns are scored.
For pawn advancement 12 x12 board advance tables are pre calculated at each root position, containing a value which is scored for a pawn standing on this square. The king castling status at the root position is taken into account. E.g. pawns on the opposite side of the board where the own king has castled get a higher advance bonus. Has the opponent king castled to this side, the advance bonus is even more raised.
Passed pawns are scored higher if they are supported by adjacent, connected own pawns. The attack status or blocks on squares before a passed pawn (in direction to the promotion square) is taken into account.
King evaluation
The king evaluation is strongly divided into a standard evaluation where king safety is of importance and an Endgame evaluation, where the king actively takes part in the game.
The standard evaluation punishes facts which hinder castling and rewards a king which has already castled. The punishment decreases for an not castled or "lone standing" king proportionally with a falling material strength of the opponent.
In the endgame there is a bonus for center tropism (small distance of king to the center of the board)..
The king evaluation is strongly interconnected with the positions of the pawns.
In standard evaluation the pawn shelter around the king is rewarded.
In the Endgame the distance of the king to pawns, especially to passed pawns and to "backward" pawns (pawns which cannot advance because of threads or hang behind) is of advantage and positively scored.
In a Pawn Endgame the distances of the kings to the promotion squares are considered ("square of king"- promotion rule) and in unmistakable favorable positions for queening very high bonuses are scored .
King-Pawn Hash Table
RDChess doesn't use like most other chess programs a pawn formation hash table and eventually a king hash table..
Instead of, because of the many evaluation terms both depending on the places of the kings and pawns, a single hash table, holding evaluation values for positions with identical king and pawn squares is kept.
This unique scheme proved to be quite advantageous, the read hit rate in the King-Pawn-Hash-Table is quite high, which I believe is because of seldom advantageously made king moves during a search.
Evaluation of Officers
All officers are punished for standing on the first rank in the early middle game, in order to favor early piece development (but queens are punished for moving too early over the third rank).
All officers get bonuses for controlling more centrally located squares and squares around near the opponents king.
Hung pieces (of the side on move) are punished. Against the king pinned own pieces are punished (see Pinned Pieces).
Rooks get a bonus for being on the seventh rank, for doubled rooks, for being on a file with passed or backward pawns. Standing behind a passed pawn in the Endgame is even more advantageously.
"Bishop pairs" (possession of more than one bishops of opposite colors) get a bonus.
In the endgame an proprietary RDChess bishop positional term is added. At endgames with different colored bishops or where the opponent has only a bishop of one color the own pawns get bonuses for standing on fields with the same color as the own bishop and punishments on fields with opposite color as the opponents (lone) bishop. For the opponents pawns there counts the opposite.
This term makes it easier to defend own pawns and attack the opponents pawns with bishops and should be advantageously in endgames, where is more room on the board. On the other side putting
There are some other scores not mentioned.
5. Performance
RDChess is a medium strength program, comparable with other free/ shareware chess programs like GNUCHESS or Waxman.
It is clearly inferior to commercial programs like Fritz etc. and other good academic programs like Crafty.
Anyway, it's strong enough to win nearly always against its creator (me) and 95% of all chess players on the world with a setting of 3 seconds/ move.
RDChess searches about 30.000 nodes/second in the opening, about 60.000 in the middle game and more than 90.000 nodes/s in end games (with few pieces left) on an Intel Pentium III 450 MHz processor.
On a newer PC with Intel Core 2 Q6600 Quad CPU with 2,4 GHz RDChess searches in the middle game around 500.000 nodes per seconds (which is quite few compared to other chess engines).
I observed a strong dependence of the search velocity on the alignment of critical data structures and (supposedly) the distribution of dynamical data in memory (L2 cache). Inserting a few bytes of code and rebuilding the program causes an unpredictable variation in the search velocity of up to 20 %, supposedly depending on the alignment (byte, word, .. paragraph/32 byte boundary) of often used data structures !
I have no data about the quality of code (relating to speed) generated by the Delphi 5 compiler (with compiler option “optimization” checked) compared to C++ Builder V4 or MS Visual C++ V6 generated code.
I assume that C++ code with compiler optimization is faster than Object Pascal code, but that is only a guess of mine.
I tried compiling the Delphi 5 code with C++ Builder V4, in order to port later the code to C++. This failed because of some incompatibilities between both compilers relating to register use in inline assembler code.
