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

			   by Jon Dart

Arasan is a chess program for 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 Visual C++
version 4.2, using the Microsoft Foundation Classes (MFC).  The source
will also compile under Visual C++ version 5.0, but I recommend that you
use 4.2 if possible as 5.0 appears to be buggier.  Note: this version of
Arasan requires Windows 95 or Windows NT.  It cannot be built or run
under Windows 3.1. 

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 32-bit console programs:

makebook - builds binary opening book files from text files
makeeco  - builds ecodata.h from from "eco" text file
testsrc  - test program for Arasan search engine
pgn2book - PGN to .bk file converter
arasanx  - version of Arasan that can use Winboard as a front end.

Following is a sketch of the Arasan source directory tree:

arasan
  4.0
    src     - source code
       res  - resource files, bitmaps, icons
    book    - text files for opening book and ECO recognizer
    help    - help file source
    doc     - documentation
    tests   - test files and documentation
    install - install script
    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 makefile "arasan32.mak" in the win32 subdirectory is used 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". 

Compiled versions of the tool programs are supplied in the
win32\ToolsRel directory (except for the Winboard client program
arasanx.exe, which is now packaged with the chess program itself). 


Opening book

Arasan stores the opening book in a binary file (BOOK.BIN). 

Since BOOK.BIN is supplied with the Arasan program distribution, you do
not need to build this file 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 BOOK.BIN.  Following is
information on how to do this. 

The book for Arasan is stored in a special ASCII format which is
converted to binary by the console program makebook.exe.  ASCII 
book files have the extension ".bk" and the ones used to construct
Arasan's default book are in the book directory.

In .bk files, 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.  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. 

If the same position occurs later in the book, any weight given for
it is ignored.  Only the first weight given is significant.

Comments are allowed in a .bk file and begin with a semicolon (;).
The comments are mostly used to identify the source of an opening
line, for example:

; Smejkal, Jan-Taimanov, Mark Prague (4) 1993 (0-1) [D16]

"makebook" recognizes lines of this form when it parses the file and
will store the game result (0-1, or won for Black in this case)
into the book file.  Moves that lead to a winning result are
favored over moves that lead to a loss or draw when Arasan
selects moves from the book at runtime.

The vast majority of the moves in the opening book are derived from
publically available games by strong players (most have an IM or GM
title, and nearly all are rated over 2400).  These games were converted
from PGN format to Arasan's .bk format by the program pgn2book. 

It would probably make sense to directly convert PGN files to the binary
opening book format, but since PGN files don't allow specifying move
weights, I have chosen to make it a two step process.  The supplied book
uses weights only in the misc.bk file, where they are used to steer the
computer away from possibly unsound gambits and other openings it doesn't
play well.

Arasan builds the opening book from two .bk files.  misc.bk contains
book lines for uncommon or unusual openings (mostly gambits) and has
weights in it.  standard.bk is derived from a large number of games, and
is a subset of the opening book I use when Arasan plays on FICS.
The batch file makebook.bat in the book directory will build the
opening book file (book.bin) from these three files.  There are over
100,000 total moves in book.bin.

See makebook.cpp for some documentation about the data layout within
the book.bin file.

A small separate book file (STYLES.BIN) is used for the "style" feature.
If an opening style other than "Balanced" is specified in the Openings
preferences page, then the styles.bin book will be searched before the
regular opening book.  Only those moves in styles.bin that match the
preferred style of opening will be selected.  If no such move is found,
the regular opening book is searched. 

The opening moves for the various styles are stored in STYLES.BK.  The
following command line is used to rebuild the style book:

makebook -h 101 -n 1 -p 8192 -o styles.bin styles.bk


ECO Recognizer

Arasan can produce 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

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 for debugging (with -D_DEBUG), 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 console program
that contains the Arasan search engine, but no user interface.  This
executable is called "TESTSRC" and can be built from the "tools32"
makefile. 

TESTSRC takes a command line that consists of one or more optional
switches followed by a filename.  The allowable switches are:

-p <number> - performs a fixed-ply search to the indicated depth.
-t <number> - searches for the given number of seconds.
-H <number> - hash table size (kilobytes)
-v          - "verbose", print extra information, not just the result.
-n<0|1|2>   - depth reduction for null moves (default: 2)
-k<0|1|2>   - number of killer moves per ply (default: 2)
-c<+|->     - check extensions on or off (default: on)
-f<+|->     - forced move extensions on or off (default: on)
-pp<+|->    - pawn push extensions on or off (default: on)
-h<+|->     - history heuristic on or off (default: on)
-e          - evaluate a positon
-x <number> - consider move correct if held for this number of plies

Note: the -p and -t switches are mutually exclusive, i.e. they may
not be specified together.  Switches like -c have two settings.
Specifying -c- will turn off check extensions, -c+ will turn them
on.  Extensions, killers, etc. are explained in more detail later on.

If you use the -e switch, testsrc expects to receive a file containing
a single position in FEN (Forsythe-Edwards notation).  It will evaluate
the position and print out details of how it is scored.  No search is
done, i.e. this is a static evaluation.

If you don't use the -e switch, testsrc expects a file containing one or
more commands.  The allowable commands are:

"svfe" - which indicates a position follows (in FEN notation)
"srch" followed by one or more moves - correct or recommended moves
"avoid" followed by one or more moves - moves that are bad
"noop" - a comment line
"echo" - a line to echo to stdout.

The TESTSRC program will read each position from the file, perform a
search, and report at the end the number of correct answers, the total
number of nodes searched, and the total time elapased.  If the "avoid"
keyword is used, the problem is scored as correct if the computer does
*not* make any of the indicated moves. 

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.

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. WAC.CI contains the 300 problems from Reinfeld's "Win At Chess"
book.  These are mostly easy tactical problems (a few are hard).

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

3. The file BK.CI contain the Bratko-Kopec series of tests, which
include both tactical and positional tests.  It is standard procedure to
allow the program 2 minutes for each test.  Some of these problems are
quite difficult. 

4. The file ECE3100.CI contains the first 100 problems from
Encyclopedia of Chess Endgames, volume 3.  These are rook endgames.
The solutions have been checked and corrected by Steven Edwards.

5. Another endgame test suite is FINE.CI, containing 48 king and pawn
endgame problems from Reuben Fine's Basic Chess Endings.  I am not sure
that all the solutions given are in fact correct. 

6. MES400.CI contains the first 400 problems from the book Modern
Endgame Studies. These cover a wide variety of different endgames.
I only use the first 400 problems because the whole set takes too
long to run.

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

8. FRANZ.CI is a group of 9 difficult endgame tests.

9. BT2630.CI is a set of 30 rather difficult problems.  This is
used to determine an approximate rating for the program.  Standard
procedure is to allow 15 minutes for each problem.  Add the time
needed to find the correct answer (900 for problems that are not
solved), divide by 30, and subtract from 2630.

10. LAPUCE2.CI is a set of 35 tests from the French chess magazine
La Puce Echiqueenne.  This is another test that purports to estimate
a program's rating.  Standard procedure is to allow 10 minutes for
each problem.  See LAPUCE2.DOC for the scoring procedure. 

The RESULTS file in the TESTS subdirectory summarizes Arasan's
performance on these test suites.  Note: these results were obtained
from the TESTSRC program.


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,
laid out so that square a8 has the value 0 and square h1 has the
value 63.

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.   A special value (127) is
used to represent a square that is uninitialized or invalid. 

The Board class also maintains several "bit boards" or quantities that
that hold 64 bits.  The Bitmap class in the source encapsulates a
bit board.  For example, the occupied bit board has one bit set
for every piece that is on the board (there are actually two such
bit boards, one for Black and one for White).

Rotated bitboards are used for computation of attack information.
The occupiedR90 bitboards are arranged so that pieces on the same
file occupied adjacent bits.  Similarly the occupiedDa1 bitboard
has pieces on the a1-h8 diagonal (and other diagonals going the
same direction) together, while the occupiedDa8 bitboard places
pieces on the h1-a8 diagonal (and others going the same direction)
together.

The rotated bitboards allow computing which pieces attack a square
without using any loops in the code, just shift and mask operations.
The primary use of the bitboards is in functions Board::any_attacks
(which computes whether any pieces attack a square) and the global
function attack_estimate (which estimates the gain from capturing a
piece, taking into account all attackers and defenders).  These
functions are complex and I won't try to explain the bit operations in
great detail.  The idea of using rotated bitboards comes from Bob
Hyatt's program Crafty.  Arasan's code is different in detail from
Crafty's because the board is layed out differently, and because it uses
the C++ Bitmap class instead of straight C code. 

Besides the bitboards, 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.  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 64 bits and is computed by fetching, for each piece and
square combination, a unique 64-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.

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, en passant, and move count 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 legality.
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.  The first time moves are generated 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.  Later
iterations resort the ply 0 moves so that the principal variation from
the last iteration is used first, followed by one or more "killer" moves
(moves that have previously caused beta cutoff at ply 0), followed by
the rest of the moves in their initial sort order. 

At higher plies, a somewhat different algorithm is used.  The principal
variation (best move from a previous search of this node) is always put
first.  Then capture moves that appear to gain material are tried, along
with pawn promotions.  Then the two "killer" moves (moves which have
recently caused beta cutoff) are tried.  Finally, the remaining moves
are sorted in the order of their "history" values. 

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.  Note:
the 16-bit version of Arasan has a significantly different search
engine.  This text describes the 32-bit version.

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 "iteration_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 check 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 calls the function draw_score,
which penalizes the program for allowing a draw when it is ahead in
material or has a superior position.  There is also a penalty for
making a draw early in the game.

Arasan will also terminate the search immediately if the absolute
maximum ply depth (currently 40) is reached.  This is quite unlikely.

If no draw is present and the maximum depth hasn't been reached, the
next step 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. 

If the hash table lookup didn't produce an exact value or narrow the
bounds enough to cause cutoff, then we try a further trick to get a fast
termination of the search.  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.

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. See
Donninger's article in ICCA for more information on this algorithm. 

If the null move doesn't cause cutoff, then we must actually do some
searching from the current node.  Before doing this, we check to see
if the current node should be searched to a greater depth than normal.
There are three cases in which this occurs:

a. If the side to move is in check, the search is extended an extra ply.
(There are some limits to how many check extensions can be done).
    
b. Forced moves (i.e. the side to move has only one legal move)
cause the search to be extended one ply.

c. Pushing a pawn to the 7th rank causes the search to be extended one
ply, on the theory that this pawn may soon promote.

Each type of extension can be turned on or off via the "Advanced"
preferences dialog.

The first move searched is called the "principal variation" move.  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. 

In cases where there is no hash move, we do a shallow search to obtain a
suitable move to try first.  This is called "internal iterative
deepening" and has been used in Hitech (see Ebeling's book) and also Bob
Hyatt's program Crafty.  This step is skipped if a flag is set in the
hash entry indicating that we have done "deepening" before for this
position and failed to get a move out of it.

Now (in most cases) we should have an initial move to try (if not we
generate all moves and take the first one).  We 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 (i.e., it is recursive). 

Each recursive call to move_search decrements the "depth" parameter by
one.  When it reaches zero, we enter the quiescence search.  The
difference between the regular and the quiescence search is that the
latter will call the function "quiesce" instead of move_search.
"quiesce" will only generate and search capture moves that appear to
gain material, promotions of pawns, and moves that escape from a
check.  

As the name implies, the goal of the quiescence search is to reach a
relatively "quiet" position that can be more or less accurately
evaluated.  The quiescence search terminates when no more moves of an
appropriate type are available.  The search may also terminate early
if the side to move is not in check, and the current evaluation of the
position is enough to cause cutoff.  The theory here is that the side
to move can choose to not capture any further.  If the current
evaluation is good enough to cause cutoff, there is no need to try
captures and promotions to get a better score. 

The principal variation phase of the search is over when we have found
a legal move and searched its descendants (including quiesence nodes)
so that we have a value for it.  It is possible that this value will
be greater than beta, which means that we have set the initial search
window wrong and must repeat the search with a different window.

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 (i.e. beta is set
to alpha+1).  All such searches will cause a cutoff.  If the value
returned by the search is between alpha and the original beta, 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.

Currently the hash table is used only during the regular seach, not
in the quiescence search.  The hash table is not cleared after
each search: instead it is kept full, but old entries (from the
previous search) are allowed to be overwritten by entries from the
current search.

Arasan 4.0 also uses a pawn hash table, maintained in the Scoring class,
which holds information on pawn structure and a score that evaluates how
good or bad that structure is.  This table is accessed via a hash key
that depends only on the position of pawns (of both sides).  Entries in
the table are always allowed to be replaced.  This technique has been
used in Cray Blitz and Crafty.  It significantly speeds up the scoring
routine by avoiding computation of the pawn structure score in most
cases. 

Under Windows, the size of the hash table is configured at runtime based
on the amount of memory available.  The user can also override this
calculation and specify a different size.  The "testsrc" console program
uses a fixed-size hash table: the default size is 4 Megabytes, but
this can overridden with a command-line switch. The pawn hash table is 
currently fixed at 50,000 entries per side (about 800K of memory).

Memory allocation and deallocation for the main hash table can be quite
expensive, especially under Windows.  To minimize this, operators new
and delete are overloaded for the Position_Info class (and for several
other frequently allocated classes).  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 four main components to the positional score used by Arasan:

a. Pawn structure
b. Development
c. Castling
d. King safety

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.

The pawn structure score penalizes isolated, backward, and doubled
pawns.  An increased penalty is given if there are multiple such
defects in the pawn structure.

A bonus is given 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.

In the opening and middlegame, the pawn structure score includes a
center control component that gives bonuses for occupation or
control of the center by pawns.

In the endgame, passed pawns are also evaluated to see if they
can safely queen without being intercepted by the opposing king.
Special code handles the case where two (or more) passed pawns
exist which could be captured individually, but cannot
be both stopped.

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.

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", bonuses are given 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 until it has castled.

The king safety score evaluates the extent to which the king is
protected by pawns, and also the extent to which opposing pieces and
pawns are near the king.  Having the king open to attack or near enemy
pieces is given a penalty that varies with the amount of material that
the opponent has.  The king safety score is pretty inexact, but does at
least alert the side to move when the king is in serious trouble.  In
Arasan 4.0, the king safety scoring has been made slightly asymmetric.
That is, Arasan values its own king's safety more than that of its
opponent's king.

7. User Interface

Arasan is built with MFC.  It is an SDI (Single Document Interface)
application and uses the Document/View architecture.  Most of the
message handling is done in the CArasanView class (file arasavw.cpp).
Toolbars and help are handled in the CMainFrame class (file
mainfrm.cpp).  Application startup, command-line processing, and
termination are handled by the CArasanApp class (file arasan.cpp). 
The document class (CArasanDoc) exists but does very little: it
only overrides OnOpenDocument so that we use our own I/O routines
instead of MFC's.

One factor complicating the user interface is that Arasan can "think"
on its opponents time.  This means that it must appear to do two
things at once: perform a search for a move and wait for user input.
Arasan handles this by using threads.  When it begins a search,
either to find a move when it is the computer's turn, or look ahead
during its opponent's time, it calls Search::start_search, which
creates a new thread and performs the search in that thread.  The
main application thread also continues to run and will send mouse,
keyboard, and menu events to CArasanView, as usual.  When an event
occurs that must cause the search in progress to stop (for example,
the user enters a move), then CArasanView::OnCommand will call
stop_search(), wait for the search thread to complete, and then 
continue command processing.

The console version of Arasan (arasanx.exe) does not use threads:
instead, it polls for user input in the search routine.  Originally
the console version was multithreaded, too, but I have had major
problems getting it to work right and finally took out the thread
code.


Contacting the Author

I have been working on computer chess programming since about 1987, 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@best.com. 


References

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

Ebeling, Carl. (1987). All The Right Moves: A VLSI Architecture for Chess.
MIT Press.

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.


