RDChess Technical Program Description

Part 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.

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. 

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

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.

Moves are stored in Move Lists, which are described below within the Move Generator.

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.  

Attack Tables

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).

The 8 attack bits are arranged in the attack byte from bit 0 - 7 as "k-q-rr-bb-pp", so an attack with a higher attack byte content is more threadening. 

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

Technical Description Part 3 (Evaluation,..)

Last modified 2002-08-22  Rudolf Posch