Bored losing day after day against chess computers?

Play the number puzzle Sudoku with Sudoku Rax!

RDChess Bedienungsanleitung in deutsch

RDChess   (c) 2010 Rudolf Posch, 2630 Ternitz, Österreich  Mail 

  Informationen, neue Features, Fehlerbehebungshinweise und die jeweils
 neueste Programmversion zum Download  finden Sie auf http://rdchess.com.

RDChess ist ein Freeware Schachprogramm für Personal Computer unter MS Windows.
RDChess kann auf 2 Arten benutzt werden

- im Winboard Modus
- im Windows (non-WinBoard) Modus

RDChess hat eine WinBoard-Schnittstelle (SS), welche RDChess das Spielen von Partien gegen eine große Zahl anderer Schachprogramme bzw. als Client auf Internet Schach Servern (ICS) ermöglicht. Aber RDChess besitzt im Gegensatz zu den meisten nur WinBoard-fähigen Schachprogrammen auch eine eigene grafische Windows-Benutzeroberfläche. Die RDCHESS Fenster werden im Winboard-Spiel zusätzlich zum Fenster des Programmes Winboard angezeigt.

Im Winboard-Modus wird RDChess durch das Programm WinBoard oder dazu kompatible Programme (z.B. Arena, WBTM,..) gestartet.
Wenn RDChess vom Betriebsystem gestartet wird und die Kommandozeile enthält "xboard" (ohne Anführungszeichen) bzw. /xb oder /wb, geht es in den WinBoard-Modus und tauscht Kommandos und Züge über die Winboard-SS aus. Die Züge des Gegners werden in das WinBoardfenster eingegeben bzw. über WinBoard von anderen Schachprogrammen empfangen. RDChess sendet seine berechneten Züge an WinBoard (aber aktualisiert auch das Brett und alle anderen Daten in den RDCHess-Fenstern).
Die RDChess Fenster dienen im WinBoard-Modus nur zur Information, nur einige wenige RDChess-Parameter und Funktionen bleiben verfügbar (Partie speichern, ...).

Im "non-WinBoard" Modus wird RDChess ausschließlich über seine grafische Benutzeroberfläche gesteuert.

Die RDChess-Benutzeroberfläche  besteht aus einem Hauptfenster mit Menü, dem Schachbrett zur Anzeige der Position und der Eingabe von Zügen. Weitere Fenster dienen zur Anzeige bzw. zum Editieren von Schachpartiedaten, der Zug-Historie, Konfigurationsparametern, Schachuhren, programmtechnischen Daten etc. Viele Fenster besitzen Kontext - Menüs,  die durch Drücken der rechten Maustaste auf einem sensitiven Objekt aufgeklappt werden können.

1. Hauptfenster

Das Hauptfenster besteht aus dem Schachbrett sowie
* Einem Hauptmenü oben,
* Einer Symbolleiste für häufig benötigte Befehle,
* Einer Statuszeile unten, die Hilfe u.a. nützliche Informationen über den aktuellen Status anzeigt..

Details zur Programm-Installation RDChess (Deutsch)

RDChess: Copyright (c) 2010 Rudolf Posch 2630 Ternitz, Österreich
Kommentare, Vorschläge, Fehlermeldungen willkommen als e-Mail

Zum Installieren unzippen sie die RDCHESSV3xx.zip Datei
in ein temporäres Verzeichnis und starten das Programm setup.exe.
Setup installiert alle RDChess-Programmdateien in ein
Standardverzeichnis (c:\RDChess), oder in ein anderes
Verzeichnis ihrer Wahl.
Das Programm besteht aus der RDChess.exe Programmdatei,
der vorliegenden readme.txt Datei mit Lizenzhinweisen,
einer Eröffnungsbibliotheksdatei (RDCH_op.lib),
einer englischen und deutschen Bedienungsanleitung
im .txt Format. sowie einigen .pgn - Beispielpartien.
Einige Konfigurationsparameter von RDChess (Farben, Bedien-
sprache, ... ) werden permanent in der Windows Registry
gespeichert und beim Programmstart gelesen.

Auf der RDChess Internetseite befindet sich auch ein Link auf
eine Datei RDCHESSSrcVxxx.zip mit den RDChess-Quelldateien.
Durch Aufruf von Setup.exe werden die Quellprogramme
in ein Unterverzeichnis \Source des
Installationsverzeichnisses kopiert.

Setup WinBoard.exe für RDChess:
-------------------------------
RDChess muß mit dem Parameter "xboard" (oder /xb oder /wb)
in der Kommanozeile aufgerufen werden, um im WinBoard-Modus
zu starten.

D.h. Erzeugen sie eine Verknüpfung am Desktop zum Aufruf von
winboard.exe mit RDChess als "erstes Schachprogramm (fcp)"
mit folgendem Kommandozeileninhalt:

"C:\Program Files\WinBoard\winboard.exe"
/cp /fcp="d:\rdchess\rdchess.exe xboard" /fd="d:\rdchess"
(in einer Zeile ohne Zeilenumbruch; verwenden sie die Pfade
von winboard und rdchess, wie sie auf ihrem PC installiert sind!)

Detailled program installation RDChess (English)

Freeware program RDChess Copyright (c) 2010 by Rudolf Posch 2630 Ternitz, Austria Europe
Comments/ suggestions / error reports welcome!

To install the program unzip the RDChessV3xx.zip file
into a temporary directory and start the setup program setup.exe.
Setup installs all RDChess program files into a
default directory (c:\RDChess) or into a directory
that may be chosen at the installation process.
The program consists of the RDChess.exe program file,
the actual readme.txt file with licence agreement,
an opening library file (RDCH_op.lib),
an English and German help-file in .txt format
and a few example chess games in .pgn format.
A few configuration parameters of RDChess (colors, language
of User interface, ... ) are stored permanently by RDChess
in the registry and read at the program start.

A second Zip file RDChessSrcV3xx.zip is available free on the
RDChess download site with the source code.
The source files are installed into a subdirectory \Source
of the install directory.

Setup WinBoard.exe for RDChess:
-------------------------------
RDChess must be called with the parameter "xboard" (or /xb or /wb)
in the command line in order to run in Winboard mode.

E.g. create a shortcut on the desktop calling the program
winboard.exe with RDChess as the
"first computer program (fcp)" with the following content:

"C:\Program Files\WinBoard\winboard.exe" /cp
/fcp="d:\rdchess\rdchess.exe xboard" /fd="d:\rdchess"
(enter as a full line; use the path specifiers for winboard
and rdchess as installed on your machine!)

Features of RDChess

• Medium strength state of the art chess engine
• Graphical User Interface in English and German (Main window with chess board and other info and dialog windows)
• Play gainst the RDChess program, choose the strength of RDChess
• Watch playing  RDChess as it plays against itself
• Load and save chess games in the Portable Game Notation Format (.pgn)
• Setup board positions, get a hint move for a position
• Replay or navigate back and forward through the moves of a chess game
• Display and edit game and move annotations 
• Opening book with learning mode and navigation
• Display of technical data for computer chess experts (search statistics, hash table usage, evaluation data, move sort order, ...)
• RDChess runs also under WinBoard , allowing to play with RDChess against other WinBoard compatible chess engines or on ICS chess servers
• Delphi Source code available

Licence Agreement for RDChess

RDChess: Copyright (c) 2003 - 2010 by Rudolf Posch 2630 Ternitz, Austria Europe

• RDChess version V3.23 is freeware and may be copied unlimited for personal use.
• It must be copied as a full package (file RDCHESSV323.zip), containing all the files therein.
• The program must not be changed. The program must not be sold or a fee collected for its use.
• The program may be used on his/ her own risk.
• The author doesn't guarantee that the program functions properly and takes no responsibility for a possible damage caused by its use.

Copyright for source code parts included in RDChess

• Bitmaps for the chess pieces Copyright(c) by Free Software Foundation GNU GENERAL PUBLIC LICENSE
• RDChess Version 2.98 and greater uses a subset of the Winboard Chess Engine Communication Protocol Version 2 (c) Tim Mann
• RDChess Logo created by Wilhelm Hudetz

Some chess programming/ chess playing URL's

The following table contains a small collection of links to chess papers, chess home pages, chess servers, companies etc., which I saved as bookmarks because they were seemingly more or less important for me;

Books and Literature: Bitboard Infrastructure (Heinz) Computer Chess Books Computer Chess programming (Verhelst) Chess GML (Andreas Saremba) Chess Programming Topics (Bruce Moreland) 14.3 Computer Chess DelphiMax chess program from Bauer &Schweitzer Game Programming Eppstein GameDev.net--Chess Programming Part I Getting Started GameDev.net--Chess Programming Part II Data StructuresGameDev.net--Chess Programming Part III Move Generation GameDev.net -- Chess Programming Part IV Basic Search GameDev.net -- Chess Programming Part V Advanced Search Guide to Endgames Table BasePGN XML Proposal Academics: Int. Comp. Games Association (ICGA) WWW Pages of DarkThought (Dr. E.Heinz)Home Page of Jonathan Schaeffer Ph.D.Thesis Dennis Breuker'sDownloads: FTP Directory _ftp.cis.uab.edu_pub_hyatt_ Chess servers for playing chess: PlayChess.com Free Internet Chess server (FICS) Internet Chess Club Kaiserslautern Chess Server MSN Gaming Zone Chess Diverse: ChessBase Computerschach u.Spiele(german periodical) FIDE Franks Chess Page Rebel (Schroeder BV NL) The Week in Chess (London Chess center) Tim Mann's Chess Pages Chess engines Tournaments Ridderkerk (Leo Dijksman) WinBoard Forum news:rec.games.chess.computer

RDChess User Manual

RDChess is a chess playing program for personal computers running under MS Windows. RDChess has a graphical user interface by its own, but interfaces also to Winboard, which allows RDChess to play by itself against a great number of other chess engines.
In Winboard mode RDChess is started from the program WinBoard or compatible programs (e.g. Arena,..).
When RDChess is started with the command line parameter "xboard" (without quotation marks), it assumes Winboard play and exchanges commands and moves over the Winboard interface. Opposite player moves are entered into the WinBoard window or received from other chess engines. The RDChess windows are for information only. Only a limited number of data may be entered or changed into the RDChess windows (Save, some config params, etc.). RDChess sends its calculated move to WinBoard (and updates the board and position in the RDChess windows).
In the standard (non-WinBoard) mode RDChess is controlled solely by its Graphical User interface (GUI).
The User Interface consists of a main window with menus and the chess board for entering and displaying moves.
Various other windows are for displaying and editing chess game data, move history, configuration parameters, chess watches, technical data etc.
Some windows have context menus, which pop up by clicking with the right mouse button on a sensitive object.

1. Main Window 

The main window displays the chess board  and controls the program with a menu bar at the top, a tool bar with shortcuts for often used commands, the names of the white and black player and arrows for scrolling backwards and forward through the positions of the actual chess game, a status bar at the bottom, displaying help and other useful information about the current game state. Game Menu With the “Game” menu items you start a new game from the initial position, load or save a game,  replay the current game,  set up a specific board position manually or  make test runs with pgn libraries like the Bratko-Kopec test suite and end the RDChess program.

Chess games are stored and loaded in the"portable game notation format" (.pgn). Piece symbols are in English  (K = king, Q = queen, R = Rook, B = Bishop, N = Knight, P = pawn). The start position of the chess game is stored in FEN-Format. A few "Extended position description" (EPD) tags are also stored (best move(s), principal variation, position id).  If a stored .pgn file contains more than one chess game, a dialog window opens and allows selecting a single game out from a list box for loading. Game related data like the event, site, date and result of the game, the white and black player names etc. are displayed and may be edited in an extra “Game Data” window (see below), but are stored together with the move journal in the .pgn file.

Playing a game
There are 3 playing modes

• Player against computer (standard mode),
• Player against player (player enters moves for both sides),
• Computer against computer (computer plays both sides in an automatic mode) 

which may be selected with the “Mode” menu items. 
There are further a “continuous” and a “single step” mode. In the continuous mode the computer makes repeatedly a move if it is its turn or waits for the player to enter a move (thinking on “permanent brain”).
In single step mode the computer is idle after each move (of which side whatsoever).
Some functions (controls) of the chess program are available only in the program idle state!

Entering a move
A move is entered by drag and drop (clicking with the left mouse button into the "from" square and moving the mouse with still pressed left button to the move destination square and releasing it there), or by 2 clicks, clicking into the "from" square and afterwards into the "to"-square. A valid selected piece to move is highlighted with a hatched brush on the “from” square, indicating that the program is waiting for enter of the “to” square.
For information purposes the target square of the last made move has a blue rectangle around it.
A king in check has a red rectangle around the square he is sitting on (this feature may be deactivated with the board context menu). Interrupting the move entering or a computer move search
You may interrupt a move with the "Escape" key. Click on an invalid board square to abort move entering and return to the idle state.
By clicking the “Abort move” icon on the tool bar a running computer move (“computer is thinking”) is interrupted.
Undo / Redo a move (ply)
With the appropriate move commands moves may repeatedly be undone or replayed.
You may navigate through a whole chess game (going to the begin or to the end position, ...)  with help of the horizontal left and right arrow icons above of the board or with help of the Journal window.
Changing the side to play
In the idle state you can force the computer to play one ply with the menu command “Move->Computer 1 ply” (or shortcut Icon).
In the idle state you can start a players move by clicking into the board (on a square with a valid to move chess piece) or with the menu command “Move->Play 1 ply” (or shortcut).
Options Menu
The “Options” Menu items allow turning around the board, switch the user language (English <--> German) and choose the colour of the black and white board squares and pieces.
A tabbed control Configuration allows setting diverse parameters for the playing strength (level), kind of computer play (“Permanent brain”, “Mate search”, …) and debug data.
The Transposition Hash Table size may be set to 24 MByte (standard), 48 MByte or 96 MByte
The check box “Use hash table” may be switched off in case of to less available main memory.

The playing strength of the program may be set to different levels

• Tournament time control  (m minutes for the n moves; e.g. 120 minutes for 40 moves). If one player uses up his time, he looses by timeout. After n (e.g. 40) moves of both sides the time control is set new to m minutes for the next n (e.g. 40) moves
• Incremental mode (lie used on the ICS Server): Each player is allocated a base time (e.g. 2 minutes)   and an increment of n seconds after each move
• N seconds search time allocated for each computer move
• Computer searches independently of time until the maximum search depth n
• Time control giving the computer and player equal time spans
• Unlimited search time (e.g. for solving mate puzzles).

2. Additional windows and controls

Windows of RDChess  (User language German above, English below)

The 2 screen shots above show a Windows Vista desktop with most of the RDChess program windows open in German resp. Englsh user language. To the left above is the Main window, on top of it a search watchdog and below the chess watches and Opening Library. 
On the right above is the Journal (move history), below right the Info Windw and further below "Game Data" window.

The “Windows” Menu items allow to open 6 additional windows for standard chess playing users.
 Even 7 more windows are for technical background /debug purposes and show program data like e.g. the usage of the hash tables, search statistics and other data.
 Data in all (13) windows are shown in different detail, depending on the configuration checkboxes “Test level 1” and “Test level2” in the tabbed configuration dialog box.

 The Journal Window

Displays the game history (moves with system or user entered annotations).You may scroll through the chess game positions in the move list with the cursor movement keys (up, down, page up/down, Pos1, End, ..) or by clicking to the line where you want to go in the journal. For each move is displayed the move number, move notation e.g. Bg1f3 (Bishop from square g1 to f3) in pgn format (there exists a configuration switch for long or short notation) and system or user move annotations inside the { } brackets.  Move annotation: Depending on the “Test level 1" and "Test level 2” configuration switches in the Configuration menu a move annotation looks like {C 1.48/ 218.888/MxViT:14/NSWh:15/NM#:6667/NM-ßCut:5732/HTU:6/Ha-ßCut:6550} and means C = computer move ( P = player move , B = book move from opening library , 1 = One move flag, D = Direct move from permanent brain) 1.48 evaluation of current position (pawn value = 1.00, + is good for white; minus is good for black. Mxx means mate in xx. 218.888 Number of nodes searched for the calculation of this ply MxViT: 14 maximal visited search depth = 14 ... and further program technical data (NegaScout repetitions NSWH, Null move count NM#, Null move beta cut-offs NM-ßCut, Hash table use count (HTU), Beta cut-offs through hash table use, etc. By clicking with the right mouse button into a line with a move a popup menu appears and offers a move annotation, which may be edited in an edit control

The Status Information Window

Displays (read only) information about the actual current position like game state, position value, castling rights, 50-move repetition count, position repition count, computer search level of play, last move, opening type etc

The Game Data Window

The game data window displays and allows editing data related with the actual loaded chess game. The window has 3 parts standard pgn data fields (event, site, date, name of white and black player, ...) , EPD data fields (best move, ..) and a large edit field for a comment to the chess game.

 The Opening Library Window

Displays the status and information about the current opening library in use.  The RDChess opening library (RDCH_op.lib) has a proprietary format and has to reside in the default RDChess directory. If there is no opening library file found in the current chess directory, a new (empty) opening library is inserted.The program is usually “inside” the library when starting a new chess game from the initial base position and progresses the opening library state as long as the opponent makes moves which are stored for the actual position in the opening library. An entry in the opening library may contain 0 - 6 moves out of the actual chess position.  The computer chooses arbitrarily an opening move out of these 1-6 when it is to move.  A move may be marked “active”/ or “passive”.” Passive moves will be used from the computer only if there are no active moves in the current opening library entry for the position. One of the 1-6 stored opening book moves may be selected from the move list by double clicking the line with the wished move in the opening library window.The opening library may be extended by a user through going to a stored position in the opening library and then starting the “learning mode”. Playing a move on the board enters it automatically in the opening library. The program asks for an annotation for each newly entered position. Clicking the “Stop learning” button stops extending the opening library.

The Chess Watches Window

Displays 2 digital watches for the times used so far by the black and white player. In the Tournament and the "ICS" mode the watches display the remaining time until the next time control/ end of game. The watches may be reset to zero with the "Reset" push button. When playing in WinBoard mode with use of the "tim/ otim WinBoard protocol commands" the time difference between the remaining times of RDChess and the opponent is displayed additionally.

The Search Watchdog Window 

Is a small window, usually sitting just above the main window. During a computer search it displays the number of visited nodes, the currently favored “best move” (mean continuation, “principal variation”), the evaluation (in centi pawn units) of this variation and some other data (current search depth, progress bar, ..).

Debug windows

There are currently 7 “debug” windows, which are not important for a user just playing chess with the program.
The data may be interesting for users programming chess computers, although I am too lazy to describe here the meaning of all the displayed data.
The “position hash table” window (see below) and the “king + pawn hash table” info window (not shown here) display information about the actual status of the hash tables and its usage within the last search.

The iterative search overview window shows in detail the iterative search deepening process of the computer search with search depth, evaluation values measured in centi pawn units (Alfa, Best, Beta), search time, node counts and principal variation for every searched depth.  

The Evaluation data debug window (not shown here) displays various data about the evaluation function values of the current position and the pawn structure.
A Winboard connection debug window shows online all moves and data traffic sent and received over the Winboard interface pipes and logs the data into a Winboard log text file.

Help

The  Help menu offers 2 entries

• Clicking "General help" opens a short user manual in English or German language (depending on the language setting in the Options Dialog box),
• Clicking "About" shows a Dialog box with the current RDChess program version and the Copyright notice of the author.

3. System requirements

• Windows 95, 98, ME, NT, 2000, XP, Vista 
• Windows desktop resolution at least 800 x 600. 1024 x756 or more are recommended.
• Intel x86 or compatible AMD PC with MMX instruction set.
• When using the hash tables at least 128 MBytes main system memory recommended 

4. Program Installation and execution
The program downloads freely from http://rdchess.com
To install the program unzip the RDCHESSVx.zip file into a temporary directory and start the set up program setup.exe. Setup installs all RDChess program files into a default directory (c:\RDCHESS) or into a directory, which may be chosen at the installation process.
The program consists of the rdchess.exe program file, a readme.txt file with a licence agreement, an opening library file (RDCH_op.lib), an English and German help-file in .txt format and a few example chess games in .pgn format.
RDChess is executed with the command line ... path\rdchess.exe  [xxxxx.pgn] [xboard]
The optional parameter "xxxxx.pgn" loads the chess game xxxxx at startup. When RDChess is known to MS Windows as program for executing .pgn files, a double click on a .pgn file loads automatically RDChess.
The optional parameter "xboard" starts RDChess in WinBoard mode (see next paragraph). This parameter makes no sense when RDChess is called stand alone with its own GUI.

The RDChess Delphi source code can be downloaded separately and freely from http://www.rdchess.com  and installed with Installshield to a subdirectory ...\Source.

Installing RDChess for use by WinBoard
To install a chess engine to be called from Winboard see the WinBoard Homepage of Tim Mann .

RDCHESS.EXE must be called with the parameter "xboard" (or /xb or /wb) in the "DOS" command line in order to run in Winboard mode.
E.g. create a shortcut on the desktop calling the program winboard.exe with RDChess as the "first computer program (fcp)" with the following content:
"C:\Program Files\WinBoard\winboard.exe" /cp /fcp="d:\rdchess\rdchess.exe xboard" /fd="d:\rdchess"
c:\Program Files\WinBoard .... is the directory where winboard.exe resides,
d:\rdchess .... is the directory where rdchess.exe resides
Another example for playing Gromit Chess V3.82 as first engine against RDChess as second computer chess engine a match of 10 games :
"C:\Program Files\WinBoard\winboard.exe" /cp /matchGames 5
/fcp "c:\Program Files\gromit382\gromit382.exe xboard" /fd "c:\Program Files\Gromit382"
/scp="d:\rdchess\rdchess.exe xboard" /sd="d:\rdchess" (input as a single line !)


5. Known problems and hints

E1) The RDChess windows positions on the desktop are optimally arranged for a screen resolution of 1152 x 864 or higher. On screens with smaller resolutions you may have to move the windows to a better position manually. (Sorry, I have not yet implemented a “Save/ restore RDChess desktop to disk”).
E2) If your PC has less than 64 Mbytes main memory, there may be problems with using the hash tables (full standard hash tables use approximately 26 Mbytes).
If your computer accesses at a computer move (search) frequently the hard disk and the program runs slowly, uncheck the “Use hash table” check box in the configuration control (Menu Option/->Configuration… ->Computer Search).
E3) Not all user interface items are properly displayed in English or German language.
The File Dialog Menu as well as buttons in dialog boxes use the language of the installed windows (.dll) and are not switched with the RDChess language configuration check box.
The debug windows are mainly in English only.
E4) RDChess (all versions) has a bug, playing sporadically a blunder move (e.g. giving away material for nothing). Despite eager long search I was not able to find this bug.

RDChess Technical Program Description

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

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.

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.

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.

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

• 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:

1. First a stored move from the position hash table is tried,
2. Secondly  a null move (only under certain conditions like "own king not in chess" and others ) is searched;
3. Moves which capture pieces, which have captured an own piece at the previous move,
4. Moves from the killer move list (there are two killer moves stored for each search depth),
5. Capture moves with an expected positive static exchange value, sorted falling with expected win value,
6. Normal moves (= non capture) from "strongly" attacked squares to "not attacked" or defended squares,
7. Remaining normal moves  from any squares to "not attacked" or defended squares,
8. Remaining normal pawn moves  (from any squares to any squares),
9. Capture moves with an expected negative static exchange (e.g. queen captures a pawn, which is defended by a pawn),
10. 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.

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 doesn't  use Endgame databases.

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.

The detailed evaluation features and exact  values of the many evaluation parameters  are not described here because of lacking space. Interested may look at the source code, freely available.
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.