Author: Steven J. Edwards
Date: 07:58:06 05/29/98
ReadMe.txt: brief documentation for the OCD (Object Chess Demonstrator)
Revised: 1998.05.28
Author: S. J. Edwards (sje@mv.mv.com)
WARNING: This is a work in progress. Use at your own risk. No
guarantees.
Abstract
--------
The OCD (Object Chess Demonstrator) is an ANSI C++ chess programming
toolkit. Its purpose is to help support standards for chess data
representation and interchange. The source is made publicly available
without charge for both research and commercial purposes.
Environments
------------
The OCD work originated on an Apple Macintosh PowerPC (604e PPC; OS 8;
MetroWerks CodeWarrior 6) and has been compiled and run on an Apple
Macintosh Performa (M68030; OS 7.5; MetroWerks CodeWarrior 6), a PC
Clone (P100; Linux 2.0.x; GNU g++), and also a different PC Clone (P233;
Microsoft Windows 95; Microsoft Visual C++ 4.0). The core application
requires about one Mbyte of RAM, but can use much more along with disk
space depending on deployment.
The program is controlled from a simple interactive console text
interface. If the routines in the program are embedded in another
program, the console interface can be removed.
All of the text output is channeled through a few routines in the source
file "TD.c" and these can be modified for a more sophisticated windowing
environment.
No special libraries or preprocessor files are required. The Macintosh
version does include some special window output, but this code is not
necessary for the main tasks of the program.
The source file names have ".h" and ".c" suffixes. These may have to be
changed for some compilation environments; i.e., MSVC seems to require
".cpp" instead of ".c" to activate C++ compilation.
Program Layout
--------------
All the global definitions are in the header file "GlobalDefs.h".
Global constants are declared in the file "GlobalCons.h" and are defined
in the file "GlobalCons.c". Global variables are declared in the file
"GlobalVars.h" and are defined in the file "GlobalVars.c".
Each named class has a name ending in the upper case letter "C". Each
named class has two corresponding source files: a ".h" header file and a
".c" body file. (E.g., the move class is named "MoveC" and has files
"MoveC.h" and "MoveC.c".) The header file contains the class
declaration and all inline methods for the class. The body file
contains all of the non-inline methods. Static methods are usually in
the body file. In some cases, larger methods appear in separate files
(e.g., move generation).
There are a few files not associated with a specific class. The file
"main.c" is the program entry point and main driver. The file "Init.c"
contains various one-time initialization routines (declared in "Init.h")
and the file "Term.c" contains various one-time termination routines
(declared in "Term.h"). The file "Misc.c" (declarations in "Misc.h")
has miscellaneous routines. Text file control is in "TF.c"/"TF.h" and
binary (coded) file control is in "BF.c"/"BF.h". Text display (console
output) is in "TD.c"/"TD.h". System dependent code is in
"SysDep.c"/"SysDep.h". Miscellaneous inline functions are in "Quick.h".
System utilities are in "Util.c"/"Util.h" ASCII representation coding
routines are in "Coder.c"/"Coder.h". There are also a few chess
specific non-class files.
Program Control
---------------
The program is controlled by a command verb processor. Command verbs
are instances of the "CommandC" class and static methods of the class
are used for interpretation and dispatch. The command processor reads
from standard input with prompting appearing on the standard output;
errors appear on the standard error. Program execution is further
controlled by a set of boolean options which are members of the
"OptionC" class. These options can be set (command verb "sopt") and
cleared (command verb "copt").
The command verb processor supports nested batch file input (command
verbs "call" and "retr"). It also supports output redirection to a
dribble file (command verbs "stof" and "ctof").
There is currently no processing for exceptions or signals.
Multithreaded execution is not yet implemented, but remains a topic for
future consideration.
Internal sanity checking
------------------------
Internal sanity checking code appears in a number of places. Its
selection is controlled at compilation time by the value of the
"SanityCheck" constant in the "GlobalDefs.h" file. When this is set to
zero, a decent compiler will remove the sanity checking code and its
entrance tests. Assigning a nonzero value to the symbol will activate
the code and will also greatly slow program operation.
Allocation issues
-----------------
Most everything in the program is dynamically allocated as needed with
the new and delete operators. Special allocation is performed for move
nodes and move lists (see below) for efficiency purposes; the
corresponding classes have overrides for their new and delete operators.
Scalar types
------------
Most simple scalar chess types are implemented as typedefs instead of
classes. These include color ("cT"), piece ("pT"), colorpiece ("cpT"),
rank ("rankT"), file ("fileT), square ("sqT"), and centipawn evaluation
("evalT"). Note that all typedef names end with the upper case letter
"T". Enumeration constants are used wherever possible; each such
constant has the typedef prefix name as its prefix name. See the
"GlobalDefs.h" file for details.
Hash codes
----------
The OCD has a hash code mechanism used for position indexing. Hash
codes are available for both the entire position and for position pawn
structure. The class "HashC" provides for the generation and
manipulation eight byte hash codes. Codes are used for position
transposition access, pawn structure transposition access, and position
library file access (the opening book).
Material balance
----------------
The class "MatBalC" holds the centipawn evaluations for both white and
black. These are material scores only and do not reflect positional
evaluation factors.
The position environment
------------------------
The position environment is represented by the class "EnvC". It
includes the position hash code, the pawn structure hash code, and the
material balance. It also includes the active color (side to move), the
castling availability (four bits for WQ, WK, BQ, and BK castling), the
en passant target square (the square passed over by a pawn that has just
made a double advance), the halfmove clock (the number of ply since the
last pawn advance or capturing move; used for the 50 move draw rule),
and the fullmove number (origin one, incremented after each black move).
The position environment also holds a vector of two squares, indexed by
color, that give the location of the kings.
Moves, move nodes, and move lists
---------------------------------
The class "MoveC" holds a single chess move. It contains the moving
piece, the origination square, the captured piece (if any), the
destination square, a special case indicator, and a few flags. (Note:
the captured piece component is vacant for an en passant capture is
vacant.) There are eight special case indicators (typedef "scmvT"):
scmvReg (regular move), scmvEPC (en passant capture), scmvCQS (castles
queenside), scmvCKS (castles kingside), and scmvPP[NBRQ] (pawn promotes
to knignt|bishop|rook|queen).
Moves are organized in move nodes (class "MoveNodeC") which form two way
linked lists. These lists are represented by the class "MoveListC". A
move node may have a descendent move list and a move list may have an
ascendent move node. Usually, all the moves in a move list are siblings
(generated form the same position).
A move node has a pointer to an axillary information block (class
"AuxMNodeC", used for future expansion). Likewise, a move list has a
pointer to an axillary information block (class "AuxMListC", also used
for future expansion).
There are some other move classes: "CompMoveC" for compressed moves and
"LongMoveC" for a move representation without move flags.
Ply indexed items
-----------------
Unlike most other chess programs, there is no master structure with ply
indexed items. There is likewise no global ply index. Instead,
developers have the flexibility to have multiple simultaneous search
trees and move stacks by organizing move lists according to specialized
design.
Boards and bitboards
--------------------
The class "BoardC" is a simple vector of 64 elements, each of which is
type "cpT" and is used to represent the piece placement of a chess
position. The class "BitBoardC" is a 64 bit structure with each bit
corresponding to a square and the entire structure representing some
boolean attribute for the board. For example, there is a constant
bitboard with square to be tested for vacancy for white queenside
castling. Bitboards are very useful for certain parallel set
operations.
The bitboard database
---------------------
The class "BdbC" represents a bitboard database. This is a large
collection of bitboards along with a regular board. It is a fairly
comprehensive set of objects that describe a position. The included
bitboards are: the all pieces merged occupancy bitboard, the color
occupancy bitboard vector (indexed by color), the colorpiece bitboard
occupancy vector (indexed by colorpiece), the attack by color bitboard
vector (indexed by color), the attack from square bitboard vector
(indexed by square), and the attack to square bitboard vector (indexed
by square). A bitboard environment is incrementally updated by the move
execution routines.
Move generation
---------------
There are two move generation schemes. Both are member functions of the
"MoveListC" class. The first uses the offset technique and requires an
"EnvC" object and a "BoardC" object. The second uses the bitboard
technique and requires an "EnvC" object and a "BdbC" object. Either
scheme may be used, but only one is required.
Move execution and retraction
-----------------------------
There are two sets of executors and retractors. Both sets are methods
of the "MoveC" class. The first used the offset technique and the
second uses the bitboard technique. Either set may be used, but only
one is required.
Move execution/retraction changes the passed environment and
board/bitboard database. For efficiency reasons, the bitboard database
retraction method is sometimes omitted and a local copy of the
pre-execution bitboard database is saved and then restored. In both
cases, there is no way to retract the environment object; the prior
environment must be saved and later restored. The non-class routines
named "Execute" in the file "Misc.c" are handy ways of executing moves.
Move legality
-------------
Move legality (i.e., not having the passive color king in check) is
handled during move execution by the method "DoFlags". A "broken" flag
in a move object records the legality status. Unlike some chess
programs, a king may never be captured.
SAN (Standard Algebraic Notation)
---------------------------------
The OCD fully supports SAN (Standard Algebraic Notation) for ASCII move
representation. The corresponding class is "SanC". Routines are also
included to map non-standard flavors of algebraic notation to SAN.
FEN (Forsyth-Edwards Notation)
------------------------------
The OCD fully supports FEN (Forsyth-Edwards Notation) for ASCII position
representation. The corresponding class is "FenC".
EPD (Extended Position Description)
-----------------------------------
The OCD fully supports EPD (Extended Position Description) for ASCII
position representation with extended attributes. The corresponding
class is "EpdC". Each EPD records has a list of operations (class
"EpdOpC"), and each operation has a list of EPD operands (class
"EpdOperandC").
There are a number of EPD file operations (mate finders, position
enumeration, etc.) in the file "EpdFileOps.c". Each operation has a
corresponding command with a name starting with "efo".
PGN (Portable Game Notation)
----------------------------
The OCD partially supports PGN (Portable Game Notation) for ASCII game
representation. The corresponding class is "PgnC". While only input of
simple PGN games is currently included, full support is planned in the
near future.
Mate finding
------------
A simple mate finder routine appears in the file "MateSearch.c" (command
"mate"). It is not a particularly fast routine, but it is included for
testing and as an example of using the chess manipulation routines.
Trajectory enumeration
----------------------
The file "Enumerate.c" contains trajectory enumerators that count the
number of distinct N ply trajectories for a given position. There is an
offset enumerator (command "etos") and a bitboard enumerator (command
"etbb"). There are included for testing and as an example of using the
chess manipulation routines. There are also useful for benchmark result
generation.
Position libraries
------------------
The class "PosLibC" is used for representing a position library. These
are employed for opening book files. An opening book is generated from
a file containing PGN games and appears as a binary (coded) file. Each
record in the coded file contains a position hash code, a move made from
that position, and a count of the number of times that move from that
position occurred in the input PGN file. Only moves for a winning side
are recorded, and only up to and including the 24th full move. An
opening book is probed by a binary search keyed on hash code and
implemented via a series of fseek() calls.
Response heuristics
-------------------
The class "ResMoveC" is used for assistance in implementing the response
move heuristic. The class "ResCountC" is used for assistance in
implementing the response count heuristic.
Transposition tables
--------------------
The class "TranTableC" represents a transposition table keyed by
position hash code. It contains elements of the class "TranC" which
hold a position hash code and a move. Further expansion is planned to
here including evaluation and analysis draft components.
The class "PawnTTC" represents a transposition table keyed by pawn
structure hash code. It contains elements of the class "PawnTC" which
hold a pawn structure hash code and a centipawn evaluation. Further
expansion is planned here as well.
Quantity counter
----------------
The "QwordC" class is used to represent unsigned integers larger than 32
bits in size. It is used for counting positions in enumeration and
searches.
Future plans
------------
Lots of stuff, as time permits. Suggestions welcome.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.