		Arasan - Chess for Windows - version 2.1
			Programmer's Guide

			   by Jon Dart

Arasan is a chess program for Windows 3.1, Windows 95 and Windows NT.
It is copyrighted but under terms that allow free distribution for
non-commercial purposes. 

This archive contains the source code for Arasan. It does not contain
executables for the chess program - they are in a separate archive.

I am providing the source code for the use of programmers who may
wish to understand how the program works or to modify it for their
own use.  However, you may not distribute a modified version of this
program without the consent of the original author.

Arasan is written in C++ and was compiled with Microsoft C++ version
2.1 (for the 32-bit version) and version 1.52 (for the 16-bit
version).  Earlier versions were built with Borland C++ and used
the Windows++ library by Paul DiLascia.  Since version 2.0, Arasan
has used Microsoft Foundation Classes (MFC) instead of Windows++.

The remainder of this file contains information for use by programmers
reading or working on Arasan source code.  I assume that you have a 
working familiarity with C++, Windows programming, and the Microsoft
compiler and tools.


Building Arasan

The source distribution for Arasan includes sources and makefiles
for building the chess program for both 16- and 32-bit Windows, and
also source and executables for the following three 32-bit
console programs:

makebook - builds binary opening book files from book.txt
makeeco  - builds ecodata.h from from "eco" text file
testsrc  - test program for Arasan search engine

Following is a sketch of the Arasan source directory tree:

arasan
  2.1
    src     - source code
       res  - resource files, bitmaps, icons
    misc    - text files for opening book and ECO recognizer
    data    - binary files used by arasan opening book, help file
    doc     - documentation
    win16   - makefiles, objects, and executables for win16
    win32   - makefiles, objects, and executables for win32
       WinRel - release objects and binaries
       WinDebug - debug objects and binaries
       ToolsRel - release objects and binaries for tools
       ToolsDbg - debug object and binaries for tools

The 16- and 32-bit build environments are a little different, mostly
because Visual C++ 1.5 (the 16-bit compiler) does not support
multiple targets within a single makefile.  Use Visual C++ 2.0 if you
can, you'll like it a lot better :-).

If you are working with Visual C++ 2.0 in the 32-bit environment,
then you will use the makefile "arasan32.mak" in the win32 subdirectory
to build the chess program itself.  The release version object and
binaries are placed in the "WinRel" directory under win32, while the
debug objects and binaries are put into "WinDebug".  There is also a
"tools32.mak" makefile for building the support tools.  Release objects
and binaries for these tools go into the "ToolsRel" directory, while
debug objects and binaries go into "ToolsDbg".

In addition, there is a "book32.mak" makefile for building the opening
book.  This is an "external makefile", which means that Visual C++ 
didn't write it and can't interpret it.  You can run it from the command
line with the command:

nmake -f book32.mak

The 16-bit environment has a Visual C++ makefile for Arasan, called
arasan16.mak, and a separate makefile for the opening book DLL,
book16.mak.  book16.mak is an external makefile.  Note: Visual C++
1.5 stores absolute paths in its makefiles, so you may get some
warning messages when loading arasan16.mak if you have installed the
Arasan files in a directory different from the one I use.  Visual C++
can convert the files to use a different directory location.  Or you
can edit the makefiles (carefully) to change the path information.

Unfortunately, Visual C++ 1.5 stores object files whereever the
makefile is located, so you can't segregate objects into separate
directories.  At least, I haven't found a way.  This is a real pain
if you switch often between release and debug builds.  Be careful
when you do a different kind of build than the one you have
previously done: in this case, you should select "Rebuild all" to
force a complete recompilation.  Visual C++ 2.0 doesn't have this
problem.

Compiled versions of the tool programs are supplied in the
win32\ToolsRel directory.  You could build 16-bit versions of these
programs, but I don't recommend it, because 16-bit console (i.e.,
MSDOS) applications are limited to 640K of memory, which is not
really enough to run these programs.

Opening book

Arasan 2.0 stores the opening book in a dynamic link library (DLL).
There are different DLLs for the 16- and 32-bit versions.  The 16
bit one is called BOOK16.DLL, while the 32-bit one is BOOK32.DLL.
They contain the same data; however, it is not possible to use
a 16-bit DLL with a 32-bit program, or vice versa, so we need two
DLLs.

Each dynamic link library contains a small amount of initialization
code and two user-defined resources.  At build time, the resource
compiler reads the resources from two data files and binds them into
the DLL.

The data files are called "BOOKW" (containing the White opening
moves) and "BOOKB" (containing the Black opening moves).  These files
are constructed by the "makebook" program.  Since "makebook" is
supported only for 32-bit environments, you need to run this program
under Windows 95 or Windows NT.

Since BOOKB and BOOKW are supplied with the source, you don't need to
create these files in order to build Arasan.  However, if you want to
modify the contents of the opening book, you will need to edit the
ASCII source for the openings and rebuild BOOKB and BOOKW.  Following
is information on how to do this.

The ASCII source for the opening book is contained in the file
BOOK.TXT, which is in the misc directory.  Moves are listed one or
more per line.  Most are in standard algebraic notation, but in some
cases "Informant-style" notation is used (e.g. knight takes bishop
might be written Nb2, not Nxb2).  The parser recognizes both forms.

A move may optionally be followed by a number from 0 to 9.  The
number, if given, is the "weight" assigned to the move.  A weight of
0 means that the computer will never play the move, but will respond
to it if it is played by its opponent.  However, if a weight of 0 is
specified after a non-zero weight for the same move in the same
position has already been specified, the original weight is
unchanged.

The higher the weight, the more often the computer will choose the
move compared to the other alternatives in the book.  By default, if
no weight is specified, a weight of 5 is assigned.  The supplied book
uses weights rather sparingly.  In general, the computer has been
steered away from gambits, and away from openings it doesn't play
well.  It is also biased towards playing the main line of an opening
as opposed to less common variants.  Note: I am not a strong player,
and so the opening book is probably far from optimal.  It is also not
very large: currently it contains aroud 15,000 half-moves, mostly
from recent grandmaster games.  Suggestions for expansion and/or
improvement of the opening book are quite welcome.

Some special symbols are allowed in the opening book.  Any line
beginning with ";" is treated as a comment and ignored.  An "m" in
the first column means that the present position should be
remembered.  An "r" in the first column restores the position to
where it was when the last "m" was encountered.  This allows easy
entry of variant lines from the same starting position.  Only one
remembered position can be stored and retrieved, however: e.g. if you
specify "m" twice, the first position stored is discarded.

After changing the book file, just type "nmake -f book16.mak" from
the command line to rebuild the data files (BOOKB and BOOKW) and then
rebuild the DLL.  Use book32.mak for the 32-bit platform.

Note: the current book format imposes a capacity limit of a little 
over 10,000 half-moves for BOOKB and BOOKW.  The current opening book
is quite close to this limit.  If a larger book is desired, the book
format will have to change.  See makebook.cpp for a description of
the current format.


ECO Recognizer

Arasan 2.0 has new code that will obtain an ECO (Encylopedia of Chess
Openings) code for a given game.  As with the opening book, the
mapping of chess positions to ECO codes is contained in a text file.
The file is called "eco" and is in the "misc" directory.  It contains
a series of lines, each starting with an ECO code, followed by a
series of chess moves, and ending with a quoted string that contains
the English name of the opening.

The "makeeco" program reads the "eco" data file and outputs to stdout
a header file that is then compiled into Arasan.  The header file is
called "ecodata.h" and contains a single large C data structure.  

Because Visual C++ makefiles don't handle generated source files like
this one, you need to run "makeeco" manually whenever you change the
"eco" data file.  To do this, CD to the src directory, and type:

..\win32\makeeco ..\data\eco >ecodata.h

Since makeeco is a 32-bit program, you need to do this under Windows
95 or Windows NT.

Note: the ECO recognizer is pretty crude right now, because only the
main ECO lines are stored in the data file, not sublines like "ECO
C18/3".  Therefore transpositions that wind up in an ECO subline like
C18/3 but skip the position that is stored for C18 will not be
recognized correctly.  There is no general solution for this problem,
since the ECO classification scheme is ambiguous in some cases, but
recognition could be improved by expanding the number of positions in
the eco file.  If the number becomes large enough, however, the
current method of building a data structure and compiling it into
Arasan might have to be changed.


Testing support

Arasan includes several features to aid debugging.  If you compile
the source with -DRANGE_CHECK, checks are inserted for accessing
arrays past their boundaries, as well as some other sanity checks.
If any of these checks fail, an error box will be displayed with the
assertion that failed.

For debugging purposes, it is also possible to build a DOS executable
that contains the Arasan search engine, but no user interface.  This
executable is called "TESTSRC" and can be built from the "tools"
makefile.

TESTSRC can be used in one of two ways.  Typing "TESTSRC -m" will
calculate and print out some timing statistics for various program
functions.

The other way to use TESTSRC involves feeding it a command line that
consists of one or more optional switches followed by an optional
filename.  The two allowable switches are:

-p <number> - performs a fixed-ply search to the indicated depth.
-t <number> - searches for the given number of seconds.
-v          - "verbose", print extra information, not just the result.

Note: the -p and -t switches are mutually exclusive, i.e. they may
not be specified together.

The filename, if specified, contains one or more board positions to
be analyzed.  The position info is in stored in FEN (Forsythe-Edwards
notation).  Each line in the file begins with one of the following
commands:

"svfe" - which indicates a position follows
"srch" followed by one or more moves - correct or recommended moves
"noop" - a comment line
"echo" - a line to echo to stdout.

Note: testsrc should really be converted to take EPD files as input.

If the search module is compiled with -D_TRACE, TESTSRC will print
out copious information about the search process when it is run.  See
search.cpp to see what information is output and where it comes from.
Another compile-time debugging option is -DDEBUG_ATTACKS, which will
insert test code to check that the attack information for the board
is updated correctly when a move is made.

Because TESTSRC is a console program, it can easily be run from a
batch file to execute a series of tests.  The following test suites
are provided with the source code (see the TESTS directory):

1. EASY.CI contains 24 fairly simple tactical problems.  Arasan
should solve all these problems with a nominal 3-ply search.

2. WAC.CI contains the 300 problems from Reinfeld's "Win At Chess"
book.  These are mostly easy tactical problems.  Arasan solves about
2/3 of them with a 60-second search limit on a Pentium 60.

3. WCSAC.CI contains problems from Reinfeld's 1001 Winning Chess
Sacrifices and Combinations.  These are tactical problems similar in
difficulty to the "Win At Chess" series.

4. The file BK.CI contain the Bratko-Kopec series of tests.  It is
standard procedure to allow the program 2 minutes for each test.
Some of these problems are quite difficult.

5. The file ECE3100.CI contains the first 100 problems from
Encyclopedia of Chess Endgames, volume 3.  These are rook endgames.

6. Another endgame test suite is FINE.CI, containing 48 king and
pawn endgame problems from Reuben Fine's Basic Chess Endings.

7. TYPP.CI contains tests from Bellin and Ponzetto's book Test
Your Positional Play.

8. ECM.CI contains test positions from the Encyclopedia of Chess
Middlegames.  These are difficult middlegame problems.

The RESULTS file in the TESTS subdirectory summarizes Arasan's
performance on these test suites.  Note: these results were obtained
with the 32-bit version of TESTSRC. 


Algorithms and data structures

1. The chess board

Following is some information about the algorithms and data
structures used by Arasan.  If you are new to computer chess
programming, I suggest first reading a general work on the
subject such as Frey (1983) or Marsland and Schaeffer (1990).

The chess board in Arasan is represented by an array of 64 squares.
Each square contains 0 if it is empty, or a piece identifier if it is
occupied.  Black pieces have identifier values between 1 and 6, while
White pieces have values between 9 and 15.  (Note: the program used
to use a variant of the "mailbox" representation described by Frey,
with 120 squares.  This allows easy detection of when a piece has
reached the board boundary.  However, because stack space is a
limited resource in Windows, the representation was changed to use
only 64 squares).  A special value (127) is used to represent a
square that is uninitialized or invalid.

The Board class also maintains a parallel board representation called
"PiecePos" consisting of two arrays of 16 entries each.  These contain
lists of the squares occupied by pieces of each side.  Any array
entry unoccupied by a piece is set to 127.

Several other pieces of information are stored in the Board class and
are updated for each move.  The KingPos array holds the location of
each side's king.  The PFileCount array holds a count of the number
of pawns on each file, for each side, and the RFileCount array holds
a similar value for rooks.  The pawn_bits data member contains a 64-
bit bitmap with bits set for each square that contains a pawn of the
appropriate color.  This is used for detecting passed, isolated, and
backward pawns.

The EnPassantSq array holds the square position, for each side, on
which an en passant capture is possible (obviously, only the side to
move can have a possible en passant capture, but we maintain two
values for programming convenience).  The CastleStatus array holds an
enum for each side indicating whether castling has occurred.  Also,
if the king or a rook has been moved, making castling on one side or
another impossible, CastleStatus is set to an appropriate value.

Each board position also has a hash code associated with it.  The
hash code is 32 bits and is computed by fetching, for each piece and
square combination, a unique 32-bit code from a table of random
numbers, and computing the exclusive or of these codes.  The
low-order bit of the hash code is then set to identify whether White
or Black is to move.  Castling status and en passant status are not
folded into the hash code, but are stored in a separate field in a
hash table entry - they must match the current board in order
for a position to be retrieved from the table.

Finally, the board position includes an array, for each side, of type
Attacks.  This contains an integer for each square indicating which
pieces and of what kinds attack the square.  This information is
incrementally updated (by the Attacks class) when a move is made or
unmade.  Attacks does not store information about "stacked"
attackers, which may make some calculations involving this
information inaccurate.

An earlier chess program I wrote re-calculated complete attack
information for each position that was evaluated, but it wound up
spending a large fraction of its time in the attack calculation
procedure.  Incrementally updating the attack information is
relatively cheap and probably faster.

2. Moves

There are three move classes used in Arasan.  "Move" maintains only
the minimal information need to unambiguously specify a move: start
square, destination square, and promotion value.  "ExtendedMove"
contains also the piece being moved, the piece being captured (if
any), and the type of move (normal, castling, en passant, etc).
Finally, "ReversibleMove" contains in addition the castling and en
passant status of the board before the move was made.  Since this
information is needed for restoring the board position, only a
ReversibleMove can be "undone".

3. Move Generator

The move generation logic is mostly contained in the classes Bearing,
Move_Generator and Move_Ordering.  Bearing contains static functions
to compute squares to which a piece can move.  Except for pawn moves,
and for castling, move generation is done by table lookup.  Each
class of piece has an associated table.  Each table is indexed by
square number and side to move, and contains a list of squares to
which the piece could move (these tables are in beardata.h).
Additional checks are made to see that the destination square doesn't
contain a piece of the same color.  However, moves into check are
possibly included.

The Move_Generation class uses functions from Bearing to generate all
moves for a given side.  Moves into check are included, unless the
side to move is in check.  In that case, a special function
(Check_Evasions) is called that strictly checks moves for equality.
It is very important to know whether any legal moves are possible
when in check: if there are none, the side to move is checkmated.
Also, some search extensions depend on the existence of a forced move
(one single legal move).

Move_Generation also calls the Move_Ordering class to re-order the
moves.  At ply 0, some rather elaborate criteria are used for move
ordering: this includes a computation of each moves' positional
score, and also (for captures), a call to function attack_estimate,
which uses the attack information for the destination square to
estimate the gain from a capture.  At ply 0, all moves are scored and
sorted.  At higher plies, a less elaborate algorithm is used, which
moves the first few most promising moves to the start of the move
array, and then sorts only those.  Captures are given a high priority
in the search order - higher if the capture appears to gain material,
but fairly high even if the capture apparently loses.  Promotions are
also given special treatment.

Arasan also uses the "killer" heuristic.  Moves that cause beta
cutoff in the search are stored in a killer array, and the move
ordering routine will give these moves a higher score than other
moves.  But captures are generally given a higher score than "killer"
moves, so the killer moves have a relatively small effect on the
overall move ordering.  The scoring algorithms in Move_Ordering have
been tuned to maximize search speed, but there is doubtless more
room for improvement.

4. Searching

Arasan uses an alpha-beta search algorithm with a variety of search
extensions.  The search class is the largest single module in the
program, and is necessarily rather complicated, but I have tried to
structure it and comment it so that it is understandable.  I will
assume that the reader knows the basics of the alpha-beta algorithm,
and will concentrate on describing this implementation of it. 

In general, the search routine tries to terminate a search tree, or
some portion of one, as soon as possible, and will defer as much work
as possible until it is certain that no earlier and quicker
termination can be done.  The techniques for doing this are mostly
well-known and there is nothing very original about the search
algorithms used by Arasan.  However, as with most chess programs,
there is a fine balance between terminating a search too soon and
extending it into unprofitable and very unlikely lines of play.  The
precise nature of this balance depends not only on the search
algorithms used, but also the relative efficiency of operations such
as move generation, position evaluation and move ordering.  Each
program therefore strikes this balance in a somewhat different way.

The entry point for a search is a routine called find_best_move.
This function does some initialization, and then calls move_search,
which implements the alpha-beta search algorithm.  The search
proceeds one ply (half move, i.e. move by one side) at a time.  That
is, first a one-ply search is done, then a two-ply search, then
three, etc. until either the maximum ply limit has been reached or
the time control has been exceeded.  Each search uses the results of
the preceeding search.  The variable "max_depth" holds the current
nominal ply depth for the search.  However, the presence of search
extensions means that some nodes may be searched to a greater depth
than this.

The first step in move_search is to look in the hash table (further
described in the next section), in order to see if an identical
position has been visited before.  This may happen due to a
transposition of moves that lead to the same position, or because a
previous search to a shallower depth visited the same node.  If a
hash table entry is found and if it contains a valid value (i.e. one
that did not cause cutoff), then that value is returned immediately
and no further searching from that node occurs.  In other cases, the
hash table may not contain an exact value, but may hold an upper or
lower bound that can be used to narrow the alpha-beta window.

After the hash table check, a further check is made to see if the
current board position is drawn, due to insufficient material or to a
3-fold repetition of moves.  Arasan does not currently check for
draws due to the 50-move rule or variants of it.

If the position is drawn, move_search returns the negative of the
evaluation function.  This penalizes the program for allowing a draw
when it is ahead in material or has a superior position.

If the search has reached the nominal search depth plus the maximum
possible search extension depth, or exceeded the maximum supported
ply depth, it also terminates immediately.

Normally the initial score for the position is set to -Constants::BIG
(BIG is a large integer used several places in the search process).
However, a different approach is taken when pursuing search
extensions, i.e. portions of the search tree beyond the nominal
search depth (max_depth).  Three different types of search extension
are used in Arasan:

a. If the side to move is not in check, and if the search exceeds the
maximum depth, searching continues but includes only promotions and
capture moves that appear to gain material.  There is a limit, set in
the Extensions structure, to how many additional plies may be
searched.

b. If the side to move is in check, the search is also extended, and
includes all legal replies, again up to the limit set in Extensions.

c. Finally, forced moves (moves with only one possible reply) cause
the search to be extended one ply and this ply is not counted towards
the computation of any other search limit.

In case a., which in the source code is called a "capture search,"
the current position is evaluated and searching may terminate if the
resulting value causes beta cutoff.  The reasoning is that there is
no point continuing the search if the side to move can "stand pat"
without making any furture captures, and still obtain a value high
enough for cutoff.  However, this early cutoff is inhibited if the
side to move has an apparently trapped piece, or appears to have
a "hung" piece (a piece subject to profitable capture).

If early cutoff doesn't occur, the next step is to try the "null
move.".  The side to move is changed without altering the board
position and the opposing side is then allowed to move.  Of course,
this could not occur in a game - a player is not allowed to "pass,"
but must move.  However, the theory is that if the null move causes
cutoff, then the side to move must have a good position, since in
effect giving the opponent a free move still produces a high value
for the side to move.  In this case, beta cutoff is allowed to occur
and no more searching is done from this node.  This search
enhancement is enabled by compiling with -DNULL_MOVE.

Starting in Arasan 2.0, null move pruning is applied in subtrees that
are themselves part of a null move search, provided that two null
moves are not tried in a row.  This is known as the "deep null"
algorithm. It is enabled by the define -DDEEP_NULL.  See Donninger's
article in ICCA for more information on this algorithm.

If the null move does not cause cutoff, then the principal variation
move is searched.  In the case of an initial search (e.g. a one-ply
search), the principal variation move is just the first move returned
by the move generator.  Otherwise, at ply 0, it is the
highest-scoring move from the previous search iteration.  This is
obtained by sorting the 0-ply moves from the last iteration, all of
which were stored along with their scores.  At deeper plies, the hash
table is queried and if a best move has been stored for the position,
that move is tried first and is considered the principal variation.

The search first calls skip_move to see if the move should be
skipped.  skip_move enforces the search extension limits mentioned
above.  If the move is not to be skipped, skip_move returns "False",
and the search proceeds to call try_move.  try_move will first make
the move, then query the attack info for the board to see if the side
to move is in check (remember, the move generator typically does not
exclude moves into check).  If a move into check is found, the
special value Illegal is returned and the next move is tried.  If the
move passes the legality check, then move_search is called again (it
is thus indirectly recursive).

If the return value from move_search did not cause cutoff, then the
search must be peformed again with a wider search window.  try_move
takes care of this.  try_move also checks the timer (if a timed search
is being done) and determines when to terminate the search.  Usually
this occurs when 95% of the allotted time has been used, but in some
cases the computer will be allowed to search a slightly longer time.

Once try_move returns a value for the node, it is compared against
alpha and beta.  If the value exceeds alpha, then a new best move has
been found at this node and the move is stored.  If the value exceeds
beta, cutoff occurs and no more searching is done.  A special check
is also made to see if the value indicates that mate has occurred,
since there is no point searching any further after that.

Assuming the principal variation move does not cause cutoff or mate,
then move_search proceeds to search the remainder of the moves.  These
moves are searched with a zero-width alpha-beta window.  All such
searches will cause a cutoff.  Then the search is repeated with a 
wider search window to determine the correct score.  It is generally
faster to get a fast cutoff and then re-search with a wider (but not
infinite) window than to do a single search with unlimited bounds.

Note that since the principal variation move is usually obtained from
the hash table or the ply0moves array, it may be the case that the
move generator has never had to be called during the principal
variation search.  If so, we call it before doing the non-p.v. moves.
An earlier version of Arasan tried to optimize things further by only
generating part of the moves at a time.  That way, if cutoff
occurred, the remainder of the move generation could be skipped.
However, there was a cost to this in terms of complexity and it did
not seem to help search speed much.

The final part of move_search checks to see if checkmate or stalemate
occurred, and updates the hash table.

When the top-level invocation of move_search terminates, it returns
to find_best_move, which determines the time used, and updates the
"Statistics" structure with the time and other information about the
search.

5. The hash table

The search routine uses a hash table for storing the results of
evaluating previously visited positions.  This table is implemented
in the "Hash" class, which is based on the MFC class CPtrList.  The
hash table is basically an array of lists.  Each list contains a
series of nodes, each of which contains some data (in the case of the
search engine, a class of type Position_Info) and a pointer to the
next node.  Each list holds entries that hash, modulo the hash table
size, to the same value.  Each node contains the whole hash code, so
that finding a given node to match a given hash code consists of
indexing into the hash table, then following the list until the hash
codes match.

Besides the hash code, each hash entry also contains the score for
the node, a set of flags indicating whether the value is exact, an
upper bound or a lower bound, the depth of search used to evaluate
the node, a word holding the castling status and en passant square,
and the best move for the position.

Under Windows, the number of lists in the hash table is configured
at runtime based on the amount of memory available.  Under DOS,
the number of lists is fixed in size.  In both cases, there is also
a limit on how many nodes can be entered into the table.  The hash
table is cleared after each search.

Memory allocation and deallocation for the hash table can be quite
expensive, especially under Windows.  To minimize this, operators new
and delete are overloaded for the Position_Info class.  These
operators use a simple memory allocation scheme that obtains memory
from the OS in large chunks and does suballocation out of the chunks
(class Pool implements this).  Memory freed via "delete" goes into a
free list and is immediately available for allocation again via
"new".  Memory is not actually freed until the "freeAll" method is
called, which occurs only when the hash table is cleared.  Then the
large memory chunks are returned to the OS.

6. Position Scoring

There are six main components to the positional score used by Arasan:

a. Center control
b. Development
c. Castling
d. Pawn structure
e. King safety
f. Threats

The positional score is typically within the range of plus or minus
the value of a pawn (64), but can be greater in some circumstances.

When in the endgame (determined by the amount of material on the
board) simplified and/or different scoring parameters are used.
Also, special scoring code is used for "mopping up" positions, in
which one side has a large material advantage.  Chess 4.5 from
Northwestern University used a similar scheme.

Center control is mostly calculated by table lookup.  For sliding
pieces, a check is made to be sure that the piece has an unobstructed
line of movement to the center of the board.  This component of the
score is not used in the endgame.

The development score encourages the program to move its pieces from
the back rank, but discourages premature development of the queen.  A
measure of piece mobility is also calculated for bishops and rooks.
Bonuses are awarded for a rook on the 7th rank, and also for a rook
on an open or half-open file, and for doubled rooks.

In the endgame, the development score encourages the king to move
towards the center or opposite side of the board, and to stay near
pawns.  A bonus is also awarded for having the opposition.  This code
is not very effective in producing good play, but it is better than
nothing.  Special-case code is included for KPK and KNBK endgames,
which enables the program to play these fairly well.

When "mopping up", the development score gives a bonus for
restricting the opposing king's mobility and for driving the opposing
king to an edge or corner of the board. 

The castling score penalizes the program for being unable to castle,
either temporarily (because a square traversed by castling is under
attack) or permanently (because the king or rook has made another
move).

The pawn structure score penalizes isolated, backward, and doubled
pawns, and gives a bonus for passed pawns.  If a passed pawn exists,
its value depends on its rank and also on whether squares ahead of it
are occupied or controlled by the opposing side.

The king safety score evaluates the extent to which the king is
protected by pawns, and also the extent to which opposing pieces
attack squares near the king.  It is pretty inexact, but does at
least alert the side to move when the king is in serious trouble.

The threat score penalizes the side to move for having pieces that
appear to be trapped or to be subject to profitable capture ("en
prise").  A pinned piece is given the same penalty as a trapped
piece.  Usually the search routine will extend the search when such
situations exist, but we have to do something when the terminal
search depth is reached.


Contacting the Author

I have been working on computer chess programming for around seven
years, and this is the second complete chess program I have written.
It is still very much imperfect - but I have decided to release it in
its present form, both so that others can enjoy playing with it and
so that programmers can study it, learn from it, and maybe improve
it.  I don't guarantee any support for this program.  However, if you
do find bugs in it, or discover a way to improve it, I would like to
hear from you.  I can be reached via email at jdart@netcom.com.


References

Donninger, Ch. 1993. "Null Move and Deep Search" ICCA Journal,
v. 16 no. 3.

Frey, Peter W. (ed.) (1983). Chess Skill in Man and Machine.
New York: Springer-Verlag.

Marsand, T. Anthony and Schaeffer, Jonathan (1990).  Computers,
Chess and Cognition. New York: Springer-Verlag.


