by Jon Dart
Arasan is a chess program.
Usage of the source code is governed by the MIT license: see the LICENSE file for details.
Arasan includes a console-based chess engine that be used with Winboard, a separately available interface for chess programs, or with UCI-compatible interface programs such as Arena and Shredder. In addition, a custom Windows-only user interface program for Arasan is available; it communicates with the chess engine using a pipe.
Arasan is written in C++. Versions before 6.0 ran only on Windows. In version 6.0 and higher, the Arasan chess engine supports both Windows (32- or 64-bit versions) and other platforms such as Linux, but the Arasan GUI is still Windows-only.
Arasan has mostly been tested on Intel & AMD processors, but the code is designed to be portable to other processors (there is some assembly code in bitboard.h, but that is not used unless you compile with -DUSE_ASM).
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++. Also, if you have no background in computer chess, you should probably start by reading some of the reference material mentioned at the end of this document.
See the BUILD.md file in the github doc directory for current build instructions.
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, and for this you will need to build the "makebook" program that is part of the source distribution. Following is further information on creating a book file.
The book for Arasan is converted from text files to the binary book by the console program makebook.exe.
The input files used to generate the opening book are in Portable Game Notation (PGN) format. More than one PGN file can be specified as input.
When multiple files are used, makebook treats the first one specially. The first file is a "steering" book used for manual tuning of the opening book weights. This file can be annotated using standard PGN comments and Numeric Annotation Glyphs (NAGs). A file with such annotations is supplied with the Arasan source and is named "basic.pgn".
In the annotated PGN file, an explict weight can be specified by putting a comment with the string "weight: " followed by a numeric value after a move. Weights are between 0 and 100. 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. By default, if no weight is specified, moves are selected at runtime based on win/loss/draw statistics and the move frequency.
PGN files can also have numeric annotation glyphs (best to use an editing program such as ChessBase to insert these). If present these have the following meaning in the context of "makebook:"
!! - a very good move, give it the maximum possible weight. ! - a good move, weight it 50% higher than normal. !? - a worthwhile move, weight it 25% higher than normal ? - a dubious move, do not play it ?? - a blunder, do not play it.
Glyphs can also be used to assign an evaluation to the end of an opening line and if so this evaluation modifies the weighting of moves along that line.
Formerly relative book weights were stored in the book file. Now generally they are not: except for special first PGN file, move records only store the win/loss/draw statistics for the move. Some selection logic is applied at runtime (see bookread.cpp), as follows (based partly on Thompson sampling - see references):
There are four options (settable in arasan.rc) that control the move selection:
Arasan comes with a book that was built from a combination of a fairly small hand-tuned book file (basic.pgn) and a fairly large collection of high-quality human and computer games. There are over 750,000 moves in the book.
You can make your own book file using the makebook utility. Typical usage would be like this:
makebook -n 100 -m 4 -o book.bin basic.pgn big.pgn
The -n parameter to makebook specifies how many "index pages" are in the binary book file. You may have to experiment with this parameter. Too small a value will cause an error building the book. Too large a value will waste space by creating a bigger book.bin than is required.
You can also specific the "-m" parameter to makebook with a number, to set a minimum number of times that a move must be played in a game collection to be included in the book (does not apply to the first PGN file). The default book shipped with Arasan was built with "-m 4". Other options include:
See bookdefs.h for some documentation about the data layout within the book.bin file.
Arasan has positional learning (a.k.a "permanent brain"). This feature is off by default, but can be enabled via CECP or UCI options. It is basically a persisent hashtable. If a search returns an unexpectedly high or low score, the position and its score are stored in a text file. The text file name and location are configurable, but by default:
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 C++ file that is then compiled into Arasan. The generated file is called "ecodata.cpp" 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.
makeeco takes a single argument: the location of the eco file. It writes the generated ecodata.cpp file to stdout.
Note: the ECO recognizer is pretty crude right now, because Arasan does not contain all the possible ECO lines and sublines in its data file. Therefore transpositions that wind up in an ECO subline like C18/3 but skip the position that is stored for C18 may not be recognized correctly. Transpositions across opening systems may also be missed. 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.
If compiled with TUNE=1 passed to the Makefile, or with -DTUNE in the compiler flags, Arasan enables parameter tuning by an external program, by presenting the internal tunable parameters as UCI options. Currently only integer-valued parameters are supported. One program that can use such options for tuning is Lakas.
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.
At runtime, adding the "-t" (trace) flag to the arasanx executable will cause it to output trace messages detailing its nternal operations. Trace messages are formatted approprately depending on the protocol (UCI or winboard). For Winboard, these messages will show up in the debug log if Winboard is started with the "-debugMode true" flag. For UCI engines, the debug output will appear as "info" output and will for example be recorded by cutechess-cli if the -debug option is specified.
The chess engine supports a couple of commands to aid with testing. The "eval" command followed by a filename will read the file (assumed to be in FEN format) and output the static evaluation of the position. If the EVAL_DEBUG and/or PAWN_DEBUG defines are uncommented in scoring.cpp, then you can see detailed output of the scoring components.
The "test" command followed by the name of a test suite file in EPD format will do a search on each position in the file and output the results to stdout. Additional switches can be added after the filename:
Either -d or -t must be included as one of the options.
If the search module is compiled with -D_TRACE, arasanx will print out copious information about the search process when it is run (if running multi-threaded, only the main thread is traced). See search.cpp to see what information is output and where it comes from.
The following test suites are provided with the source code (see the "tests" directory):
The results file in the tests subdirectory summarizes Arasan's performance on these test suites. There is a Perl script (tests.pl) in the tests directory that generates a summary of test results given a log file produced by the Arasan "test" command.
A built-in command in the engine can be used to run the "perft" command for testing. The command "perft" should be followed by a number indicating the ply depth for the computation.
If compiled with -DUNIT_TESTS, Arasan will run a set of tests on program startup (this flag is off by default). These tests verify that a set of critical functions operate correctly, verify that evaluation results are symmetrical between White and Black sides, and also run and verify the perft test over a set of positions.
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 a1 has the value 0 and square h8 has the value 63 (Note: versions before 11.0 had a different layout with a8=0).
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 Bitboard 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).
Each type of piece has its own bit board that has one bit set for each piece of that type (for example, there is a rook_bits Bitboard to hold rook locations). Since there is only one king location, though, this is kept in an integer variable.
Besides the bit boards, there is some other information in the Board structure. The enPassantSq variable holds the square position at which an en passant capture is possible (if none is possible, it has the value IllegalSquare). 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. (This hashing mechanism for chess was invented by Zobrist - see references). 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 also folded into the hash code, because positions with the same piece layout but different castling rights or possible en-passant captures must be kept distinct.
Arasan uses a 64-bit word to store move information. Each move contains a start square, destination square, promotion value, the type of piece being moved, the type of piece being captured (if any), and the type of move (normal, castling, en passant, etc).
Earlier versions of Arasan used rotated bitboards for computation of attack information. The rotated bitboards allow computing which pieces attack a square without using any loops in the code, just shift and mask operations. Starting with version 11.0, a different approach is used: it produces much the same benefits but is faster. This approach uses a technique called "magic bitboards", which basically computes a hash code that looks up attack information, in a way that ensures there are no invalid hash collisions.
There are several ways to do this, but the algorithms and data structures used in Arasan follow an approach initially published by Pradyumna Kannan. The constants for the 64-bit version were constructed by generation code posted by Tord Romstad. The 32-bit version follows an approach first taken by H. G. Mueller, as discussed in the Winboard Forum. Starting in version 20.3, Arasan alternatively supports computing sliding attacks using the x86_64 PEXT AND PDEP instructions, as first suggested by Michael Sherwin and later by Zech Wegner (see references).
The magic bitboard code is primarily in file attacks.cpp. There are two versions of the code: one uses 64-bit multiplication (or PEXT/PDEP if enabled) and is designed for a 64-bit architecture. The other uses only 32-bit multiplications. One or the other is automatically selected at compile time based on the target processor architecture.
The move generation logic is mostly contained in the MoveGenerator class and uses the magic bitboard attack functions.
The MoveGenerator class has separate routines to find all moves and to find just capture moves - the latter is all that is required in the quiescence search. Move generation is done incrementally, because if a move is found that causes cutoff, there is then no need to generate the rest of the moves for that position. Specifically, Arasan uses the "Fancy Magic Bitboards" technique described in the Chess Programming Wiki (see References), which was invented by Pradu Kannan.
Move generation occurs in this order (this is for positions where the side to move is not in check, and in the regular search, not the quiescence search):
Normally, the move generation process includes moves that are illegal because they place the side to move into check - these are weeded out in the search routine.
If the side to move is in check, a special function (generateEvasions) 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). Currently evasions are generated in two phases: first the hash move is tried, if there is one, and then only if that fails to produce cutoff is the full set of evasion moves generated.
Move ordering at the root node is done somewhat differently. The first time moves are generated at ply 0, a rough sorting by score is done. The next few plies are searched with a wide window, partly to facilitate "easy move" detection (a move that appears to be much better than alternatives may be selected after a shorter than usual search, so for example the program does not waste time on an obvious recapture). But another side-effect of the wide window is that we obtain scores for all moves and Arasan will sort the moves for the next iteration based on these scores.
After the "wide window" part of the search is over, the next iteration is searched putting the best move from the last iteration first. If another move then becomes best, it replaces the previous best move and all other moves are shifted down, so that their ordering from the previous iteration is retained in the next iteration.
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 findBestMove. This function does some initialization, and then calls ply0_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 "iterationDepth" 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.
In the first few iterations of the ply0 search, Arasan now uses wider than usual search bounds, so that each move gets a preliminary score. The scores are used to order the moves for deeper searching, and for "easy move" detection: if one move is found to have a significantly higher score than all others, and if subsequent searching still selects this move, then the search may be terminated early.
ply0_search does some other special processing and bookkeeping because it is at the top of the search tree. This function then calls search() to recursively process lower-depth nodes.
The first step in search() is to check if the current board position is drawn, due to insufficient material, a 3-fold repetition of moves, or the 50-move rule.
If the position is drawn, move_search calls the function drawScore. Usually a draw is given a score of 0, but when playing on a chess server, the relative rating of the opponent is also factored in, so that draws against a lower-rated opponent are penalized.
Arasan will also terminate the search immediately if the absolute maximum ply depth 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 may also try the endgame tablebases, if they are installed and enabled, and if material is reduced enough that they can give an exact score.
In non-PV nodes where the side to move is not in check, Arasan first tries a couple of techniques to decide if the entire node can be pruned away, before doing any searching. The first of these is "static null pruning", which cuts off search for nodes that have very high scores.
If still no cutoff has occured, we then 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.
A null move is searched to a depth less than that used for regular moves. Arasan uses at least a so-called R=3 depth reduction for the null move search: in other words, a search is done with the regular 1-ply reduction in depth plus three extra plies. (At high depths, a depth-dependent amount is added to the reduction factor.)
After a null move produces a beta cutoff, Arasan does an extra reduced-depth verification search to ensure that the null move cutoff is actually valid. The verification search uses reduced depth, but doesn't insert the null move first.
After null move search, but before the regular search, Arasan now applies a pruning mechanism called ProbCut (see Buro).
If neither the null move search nor ProbCut cause cutoff, then we must actually do some searching from the current node.
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. 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.
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).
Normally each move searched reduces the "depth" variable by a constant (DEPTH_INCREMENT). When depth reaches zero, the quiescence search will be entered (see below).
However, some moves are searched to a greater depth than normal. There are several cases in which this occurs:
Note that since Arasan 5.0, most extensions can be a fraction of a full ply. Search "depth" is normally decremented by the constant DEPTH_INCREMENT every time a new ply is begun; however, extensions can decrement it faster, typically an additional amount between 1/2 of a full ply and a full ply.
Individual extensions can be combined, but at any given ply, the total depth reduction from extensions cannot exceed DEPTH_INCREMENT, the equivalent of one extra ply.
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 the search function 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 root move 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.
Arasan now optimizes things further by only generating part of the moves at a time. That way, if cutoff occurs, the remainder of the move generation can be skipped.
Arasan also performs several types of pruning and depth reduction. These are the opposite of extensions: instead of searching deeper, Arasan either cuts off the search prematurely (pruning) or reduces the search depth.
Arasan uses "late move reductions." After the first few moves have been searched, including any killer moves, if the move is not extended, and if it is not considered potentially dangerous or advantageous, then the search depth is reduced. This can occur even at high depths in the search tree. If the reduced depth move returns a score above alpha, it is re-searched with normal depth. This technique became popular due to its use in Fabien Letouzey's program "Fruit".
Arasan also does several different kinds of pruning. Several tests are made on each move and if the move was extended for any reason, or if it is a capture, special move (like castling) or advance of a passed pawn, then it is not pruned.
Note that it is necessary to search at least one legal move before any pruning is done, because we need to distinguish nodes at which no moves are searched due to stalemate from those at which all nodes would cause pruning. Also no pruning is done at the root node.
Futility pruning in Arasan is similar to that described by Ernst Heinz for the program Dark Thought. It allows some moves to not be searched, if it determined that the side to move is behind in material and the move to be made is not likely to gain enough material to be worth considering. But moves with good history scores are not pruned.
Futility pruning is applied at relatively low search depths before the quiescence search and during the quiescence search. First the program computes an optimistic score for the move and adds a margin that varies based on search depth; the sum is then compared against alpha and the move is pruned if the optimistic score + margin is still below alpha.
Late move reduction is done before futility pruning and the futility margin is based on the reduced depth (if a reduction was done).
Arasan also does "late move pruning." In non-PV nodes, quiet moves that are in the history phase of move generation (after the pv move, winning captures, and killer moves) and are relatively late in the move order can be pruned away. The theory is that if we have not already achieved a cutoff searching more moves is not likely to produce one.
Another pruning method recently implemented is based on countermove and follow-up history scores. Quiet moves with bad history scores are pruned at low depths.
In addition at depths just before the quiescence search, moves that appear to lose material based on a static exchange analysis are pruned. This is done with more liberal pruning conditions than other types of pruning.
The final part of search() checks to see if checkmate or stalemate occurred, updates the hash table, and maintains the best variation. It also updates history scores, but only if the best move is not a promotion or capture. The best move from the search gets a history bonus. The remaining moves are given a penalty. Scores are maintained in a table (per thread) that is indexed by side, source square and destination square. In addition, Arasan now maintains a countermove history table and a "follow up" history" a.k.a. continuation history table (ideas from Stockfish). All history tables are used in move ordering and history values are a factor in computing the amount of late move reduction.
When the search terminates at ply 0, it updates the "Statistics" structure with the time and other information about the search (key parts of this structure are also updated during the search when the p.v. changes, so the UI and test suite code can monitor it).
As noted above, each recursive call to move_search decrements the "depth" parameter by a constant (DEPTH_INCREMENT). When "depth" drops below zero, Arasan enters the quiescence search by calling function quiesce(). Like search(), this is also a recursive search routine.
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. Generally, "quiesce" will only generate and search capture moves that appear to gain material, promotions of pawns, and moves that escape from a check.
If in check, all evasion moves are generated although some "quiet" evasions may be pruned and not searched.
The quiescence search for positions not in check also does forward pruning on moves, dropping any that appear to lose material based on the static exchange evaluator and those that fail a futility test.
Generally, forward pruning costs time (especially if the static exchange evaluator, "see", needs to be called), and involves some risk of dropping valuable capture moves. But, on the plus side, it significantly trims the size of the search tree.
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.
In version 10.0 and later, for nodes where it is not in check, if no cutoff has occurred so far, the quiescence search will generate and search moves that give check, at least in the first couple of quiescence search plies. But checks that appear to lose material are pruned.
The search routine uses a hash table for storing the results of evaluating previously visited positions. This table is implemented in several static functions defined in hash.cpp. 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 full 64-bit 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.
The hash table is limited in size and may fill up during a long search. In this case, we have a choice: when a new position is encountered, we can overwite an existing entry in the hashtable with the new position, or we can discard the information for the new position and not put it into the hashtable.
Arasan will generally only replace entries that have greater depth than existing entries, or entries that came from an earlier search (i.e. whose "age" field does not match the current search).
The hash table is not cleared after each search: instead, it is kept full, but old entries (from the previous search) are considered candidates for replacement.
The size of the main hashtable defaults to 64 Megabytes, but can be overridden with -H switch, followed by a size (such as '256M'), or by modifying the arasan.rc parameter file. Standard Winboard or UCI option commands can also be used to alter the hash table size at runtime.
Because multiple threads can be reading and writing the hash table, a "lockless hashing" technique is used to prevent conflicts (as done in Crafty). When a hash key is stored it is xored with the data value. When retrieving, the current data contents for a hash table entry are xored again with the stored hash key and this is used to match the hash key for the position. If another thread has overwritten or is overwriting the data field, then the comparison will fail and a match will not be returned.
Besides the main hash table, some smaller hash tables are used by the Scoring module to store the results of pawn structure scoring and king cover calculation. These are relatively small in size and are allocated on a per-thread basis (each thread has its own tables).
The following text describes the classical evaluation function.
There are roughly five main components to the positional score used by Arasan:
The positional score is typically within the range of plus or minus the value of a pawn (128), but can be greater in some circumstances.
Pawn structure scoring is done in two stages. First, the pawn hash table is probed to get the score for the position. If the position is not found in the hash table, then the pawn_structure_score routine is called. This routine only computes scoring parameters that depend only on the position of pawns. It also calculates several items that are useful in the rest of the evaluation.
The second-stage pawn scoring takes into account the relation between pawns and pieces.
The pawn structure score penalizes isolated, backward, weak, 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. A bonus is given for a rook behind a passed pawn. Blocked passed pawns and passed pawns on the rook file are given a penalty.
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.
Arasan 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. There are separate tables for the white and black sides. Entries in the pawn tables 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.
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, Knights, and Queens. 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.
The castling score penalizes the program for having its Rook blocked by the King (i.e. not being castled), or being unable to castle.
Arasan calculates king safety using a "cover" score that measures how protected a king is by pawns, combined with a "proximity" score that measures the closeness of enemy pieces to the king. The "cover" score is calculated and hashed for fast lookup.
King "cover" is considered worse if pawns are missing near the king or if the king is near an open or half-open file.
"Proximity" includes several measures based on the proximity of enemy pieces, advancing pawns (indicating a "pawn storm"), Rooks on open files near the king, and Queens or Bishops bearing on diagonals near the king.
If both proximity and cover scores are high (indicating that the king is both exposed and attacked) an additional "bonus" penalty is given.
The king safety score is scaled according to the amount of material the opponent has. The more material the opponent has, the more dangerous an uncovered and/or attacked king position is.
In the endgame, passed pawns are evaluated to see if they can safely queen without being intercepted by the opposing king. Arasan versions 5.0 and higher also have code that gives a bonus for an "outside" passed pawn, and that helps to evaluate pawn "races," where both sides are likely to promote.
In the endgame, the king is encouraged to move towards the center or opposite side of the board, and to stay near pawns. This code is not very effective in producing good play, but it is better than nothing.
Prior to version 6.0, endgame and king safety scoring were never applied together, but now they can be: if the position is in the process of transition to an endgame, it will be evaluated for both king safety and endgame positional factors.
A lookup table is used to speed up endgame calculations by storing information based on the position of king and pawns (for both sides). Once computed, this information is put into a hash table for later retrieval and use by any position that shares the same king + pawn configuration.
Arasan is aided in the endgame by the use of "bitbases" for the KPK endgame. Bitbases record for each position of the two kings and pawn whether the position is won for the stronger side, or only a draw. Unlike tablebases, bitbases do not record the number of moves to mate. Bitbases can be employed throughout the search tree since they are in memory. Arasan uses the KPK bitbases not only when there are only kings and one pawn left, but also as an aid to computing endgame scoring for more complex endgames.
Arasan also has some special-case code for other endgames including KNBK, KRK and KQK, which enables the program to play these fairly well, even without tablebases.
Arasan 23.0 introduces support for a Efficiently Updatable Neural Network (NNUE) that performs evaluation of chess positions. Arasan's implementation of this is largely in a submodule, the source of which is at https://github.com/jdart1/nnue. NNUE evaluation for chess was first introduced in Stockfish, whose implementation of it was contributed to the Stockfish project by Hisayori Noda aka Nodchip. Arasan 24.0's current implementation is compatible with the SFNNv4 network architecture used in Stockfish 15. Version 25.0 introduces a new, similar architecture, consisting of a horizionally mirrored feature transformer with 9 King buckets, followed by a hidden layer with 8 buckets based on material level.
Tuning was performed using the Bullet tuner using a combination of positions from Arasan selfplay games (generated from the "selfplay" utility program) and Lc0 training data.
The actual network data is loaded at runtime from a file. Unlike Stockfish and some other programs, Arasan does not embed the network data in the program executable. The default file name is part of the executable.
Arasan version 9 and above have support for using more than one thread during searching, enabling it to make use of multi-processor machines and multi-core CPUs. Version 10.0 was the first version to have this fully implemented.
A pre-requisite for implementing multi-threading is that global data structures that are accessed for read & write be made safe for parallel access, usually using locking.
However, locking has a performance overhead and is generally infeasible to do on a per-node basis. Arasan now does not lock the main hash table, to avoid this penalty, but uses a lockless hashing mechanism as described earlier.
My first attempt at implementing multi-threading used the ABDADA algorithm (see Weill's article). This is simple to implement since it uses the hash table as a single point of synchronization and control, but it did not perform well, because this usage of the hash table interferes with its normal usage as storage for scores and best moves from previously visited nodes. Consequently, the hash hit rate was reduced and multi processors did not achieve much of a speedup.
Arasan then implemented what is called the Young Brothers Wait concept (YBWC). This algorithm was described in Feldmann's Ph.D. thesis (see References) and several related publications in the early 1990s.
Arasan's current implementation uses what is called LazySMP. This has been implemented in several strong engines including Stockfish. It is somewhat similar to ABDADA conceptually. It entails letting each thread search from the root position using a standard alpha-beta aspiration search. No synchronization across the threads is done. Practically the only shared data structure is the global hash table. Threads in each iteration are started at somewhat different search depths, which helps avoid having them visit exactly the same nodes. The first thread is treated somewhat differently from the others: only it is allowed to output search progress updates, and its fail high/fail low history is used when making time control decisions. Each thread maintains its own Statistics structure, which holds interim search results. When a search termination condition (such as time up) is reached, all threads will be set back to idle and returned to the wait loop in the thread pool. The individual search results from each thread are then examined. The best result from all threads is the one that is returned as the overall search result, with the caveat that the result chosen must also have a final search depth not less than other threads.
The Windows user interface was re-written for version 6.0, although some code from earlier versions is still in use. The main difference from earlier versions is that the chess engine is now run as a separate process that communicates with the user interface through a socket, exactly like Winboard does. This is done to eliminate some problems that occured when using threads to manage the engine/UI communication in earlier versions.
Compared to Winboard, the Arasan UI lacks some features: for example, it cannot be used to communicate with a chess server, and has no facility for editing positions.
The Arasan user interface is a pretty standard MFC program. It uses the single document interface (SDI) model, so there is only one document class instance and one view instance active.
Earlier versions of the Arasan UI used bitmaps for display. The new version uses TrueType fonts. Several chess fonts are included in the program distribution. The original font archives, which include copyright and usage information, can be found in the fonts subdirectory of the Arasan source distribution.
While no formal support is offered for this software, if you do find bugs in it, or discover a way to improve it, I would like to hear from you.
Contact information and additional information about Arasan can be found at arasanchess.org
Buro, M. (1995) ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm. ICCA Journal Vol. 18, No. 2, pp. 71-76.
Chess Programming Wiki, topic Magic Bitboards.
Donninger, Ch. (1993). "Null Move and Deep Search" ICCA Journal, v. 16 no. 3.
Duchi, John, Hazan, Elad and Singer, Yoram. "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization" Journal of Machine Learning Research, Volume 12, 2/1/2011, pp. 2121-2159.
Ebeling, Carl. (1987). All The Right Moves: A VLSI Architecture for Chess. MIT Press.
Feldmann, Rainer. Game Tree Search on Massively Parallel Systems (1993). Ph.D. Thesis, University of Paderborn. (see also related publications.)
Frey, Peter W. (ed.) (1983). Chess Skill in Man and Machine. New York: Springer-Verlag.
Heinz, Ernst A. (1999). Scaleable Search in Computer Chess. Vieweg.
Hoki, Kunihuto and Kaneko, Tomoyuki (2014) "Large-Scale Optimization for Evaluation Functions with Minimax Search," Journal of Artificial Intelligence Research 49, pp. 527-568.
Kannan, Pradyumna (2007) Magic Move-Bitboard Generation in Computer Chess.
Kingman, Diederik P. and Ba, Jimmy Lei (2015) ADAM: A Method For Stochastic Optimization. Published as a conference paper at ICLR 2015.
Lai, Matthew (2015) Giraffe: Using Deep Reinforcement Learning to Play Chess. MSc Dissertation, Imperial College, London.
Marsand, T. Anthony and Schaeffer, Jonathan (1990). Computers, Chess and Cognition. New York: Springer-Verlag.
Sherwin, Michael (2006) New instruction that intel/amd should add (Winboard forum).
Stockfish blog (2020-08-07) Introducing NNUE Evaluation
Thompson, William R. (1933) "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples". Biometrika, 25(3–4):285–294
Wegner, Zach (2011) Haswell New Instructions.
Weill, Jean-Christophe (1996). "The ABDADA Distributed Search Algorithm" Proceedings of the 1996 ACM 24th annual conference on Computer science, pp. 131-138.
Winboard forum, discussion "A Faster Magic Move Bitboard Generator?"
Zobrist, A. L. (1970). "A new hashing method with applications for game playing," Technical report 88, Computer Science Department, University of Wisconsin.