Subversion Repositories Games.Chess Giants

#include "chess.h"

#include "data.h"

#if defined(UNIX)

#  include <unistd.h>

#  include <pwd.h>

#  include <sys/types.h>

#endif

#include <signal.h>

#if defined(SYZYGY)

#  include "tbprobe.h"

#endif

/* last modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *  Crafty, copyright 1996-2016 by Robert M. Hyatt, Ph.D.                      *

 *                                                                             *

 *  Crafty is a team project consisting of the following members.  These are   *

 *  the people involved in the continuing development of this program, there   *

 *  are no particular members responsible for any specific aspect of Crafty,   *

 *  although R. Hyatt wrote 99%+ of the existing code, excepting the Magic .   *

 *  move stuff by Pradu Kaanan, syzygy code written by Ronald de Man, and the  *

 *  epd stuff written by S. Edwards.                                           *

 *                                                                             *

 *     Robert Hyatt, Pelham, AL.                                               *

 *     Mike Byrne, Pen Argyl, PA.                                              *

 *     Tracy Riegle, Hershey, PA.                                              *

 *     Peter Skinner, Edmonton, AB  Canada.                                    *

 *                                                                             *

 *  All rights reserved.  No part of this program may be reproduced in any     *

 *  form or by any means, for other than your personal use, without the        *

 *  express written permission of the authors.  This program may not be used   *

 *  in whole, nor in part, to enter any computer chess competition without     *

 *  written permission from the authors.  Such permission will include the     *

 *  requirement that the program be entered under the name "Crafty" so that    *

 *  the program's ancestry will be known.                                      *

 *                                                                             *

 *  Copies of the source must contain the original copyright notice intact.    *

 *                                                                             *

 *  Any changes made to this software must also be made public to comply with  *

 *  the original intent of this software distribution project.  These          *

 *  restrictions apply whether the distribution is being done for free or as   *

 *  part or all of a commercial product.  The authors retain sole ownership    *

 *  and copyright on this program except for 'personal use' explained below.   *

 *                                                                             *

 *  Personal use includes any use you make of the program yourself, either by  *

 *  playing games with it yourself, or allowing others to play it on your      *

 *  machine,  and requires that if others use the program, it must be clearly  *

 *  identified as "Crafty" to anyone playing it (on a chess server as one      *

 *  example).  Personal use does not allow anyone to enter this into a chess   *

 *  tournament where other program authors are invited to participate.  IE you *

 *  can do your own local tournament, with Crafty + other programs, since this *

 *  is for your personal enjoyment.  But you may not enter Crafty into an      *

 *  event where it will be in competition with other programs/programmers      *

 *  without permission as stated previously.                                   *

 *                                                                             *

 *  Crafty is the "son" (direct descendent) of Cray Blitz.  it is designed     *

 *  totally around the bit-board data structure for reasons of speed of ex-    *

 *  ecution, ease of adding new knowledge, and a *significantly* cleaner       *

 *  overall design.  it is written totally in ANSI C with some few UNIX system *

 *  calls required for I/O, etc.                                               *

 *                                                                             *

 *  main() is the driver for the chess program.  Its primary function is to    *

 *  cycle between asking the user for a move and calling for a tree search     *

 *  to produce a move for the program.  After accepting an input string from   *

 *  the user, this string is first passed to Option() which checks to see if   *

 *  it is a command to the program.  If Option() returns a non-zero result,    *

 *  the input was a command and was executed, otherwise the input should be    *

 *  passed to input() for conversion to the internal move format.              *

 *                                                                             *

 *  The following diagram shows how bit numbers / squares match up in Crafty's *

 *  bitboard arrays.  Note that bit zero (LSB) corresponds to square A, which  *

 *  makes this a mental challenge to take a 64 bit value and visualize it as   *

 *  chess board, since the files are reversed.  This was done for the          *

 *  following reasons:  (1) bit 0 needs to be the LSB, and bit 63 needs to be  *

 *  the MSB so that the Intel BSF/BSR instructions return the proper square    *

 *  number without any remapping.  (2) the lower 3 bits (file number) are now  *

 *  0 for A, 1 for B, ..., 7 for H.  The upper 3 bits (rank number) are then   *

 *  0 for rank 1, 1 for rank 2, ..., 7 for rank 8.                             *

 *                                                                             *

 *  A8 B8 C8 D8 E8 F8 G8 H8                                                    *

 *  A7 B7 C7 D7 E7 F7 G7 H7                                                    *

 *  A6 B6 C6 D6 E6 F6 G6 H6                                                    *

 *  A5 B5 C5 D5 E5 F5 G5 H5                                                    *

 *  A4 B4 C4 D4 E4 F4 G4 H4                                                    *

 *  A3 B3 C3 D3 E3 F3 G3 H3                                                    *

 *  A2 B2 C2 D2 E2 F2 G2 H2                                                    *

 *  A1 B1 C1 D1 E1 F1 G1 H1                                                    *

 *                                                                             *

 *  56 57 58 59 60 61 62 63                                                    *

 *  48 49 50 51 52 53 54 55                                                    *

 *  40 41 42 43 44 45 46 47                                                    *

 *  32 33 34 35 36 37 38 39                                                    *

 *  24 25 26 27 28 29 30 31                                                    *

 *  16 17 18 19 20 21 22 23                                                    *

 *   8  9 10 11 12 13 14 15                                                    *

 *   0  1  2  3  4  5  6  7                                                    *

 *                                                                             *

 *  version  description                                                       *

 *                                                                             *

 *    1.0    First version of the bit-board program to play a legitimate game  *

 *           even though significant features are missing:  transposition      *

 *           table, sophisticated scoring, etc.                                *

 *                                                                             *

 *    1.1    Added the minimal window search.  At each ply in the tree, the    *

 *           first branch is searched with the normal alpha/beta window, while *

 *           remaining nodes are searched with value/value+1 which was         *

 *           returned from searching the first branch.  If such a search       *

 *           returns the upper bound, this position is once again searched     *

 *           with the normal window.                                           *

 *                                                                             *

 *    1.2    Added the classic null-move search.  The program searches the     *

 *           sub-tree below the null move (typically) one play shallower than  *

 *           the normal search, saving a lot of time.                          *

 *                                                                             *

 *    1.3    Added the transposition table support.  This also includes the    *

 *           code in Iterate() necessary to propagate the principal variation  *

 *           from one iteration to the next to improve move ordering.          *

 *                                                                             *

 *    1.4    Modified the transposition table to use three tables, one for 64  *

 *           bits of white entry, one for 64 bits of black entry, and one with *

 *           the remaining 32 bits of white and black entry combined into one  *

 *           64 bit word.  Eliminated the "bit fields" since they seemed to be *

 *           erratic on most compilers and made portability nearly impossible. *

 *                                                                             *

 *    1.5    Pawn scoring added.  This required three additions to the code:   *

 *           (1) InitializePawnMasks() which produces the necessary masks to   *

 *           let us efficiently detect isolated, backward, passed, etc. pawns; *

 *           (2) a pawn hash table to store recently computed pawn scores so   *

 *           it won't be too expensive to do complex analysis;  (3) Evaluate() *

 *           now evaluates pawns if the current pawn position is not in the    *

 *           pawn hash table.                                                  *

 *                                                                             *

 *    1.6    Piece scoring added, although it is not yet complete.  Also, the  *

 *           search now uses the familiar zero-width window search for all but *

 *           the first move at the root, in order to reduce the size of the    *

 *           tree to a nearly optimal size.  This means that a move that is    *

 *           only one point better than the first move will "fail high" and    *

 *           have to be re-searched a second time to get the true value.  If   *

 *           the new best move is significantly better, it may have to be      *

 *           searched a third time to increase the window enough to return the *

 *           score.                                                            *

 *                                                                             *

 *    1.7    Replaced the old "killer" move ordering heuristic with the newer  *

 *           "history" ordering heuristic.   This version uses the 12-bit key  *

 *           formed by <from><to> to index into the history table.             *

 *                                                                             *

 *    1.8    Added pondering for both PC and UNIX-based machines.  Also other  *

 *           improvements include the old Cray Blitz algorithm that takes the  *

 *           P.V. returned by the tree search, and "extends" it by looking up  *

 *           positions in the transposition table, which improves move         *

 *           ordering significantly.  Repetitions are now handled correctly.   *

 *                                                                             *

 *    1.9    Added an opening book with flags to control which moves are       *

 *           selected for play.  The book maintenance code is stubbed directly *

 *           into the program, so that no additional executables are needed.   *

 *                                                                             *

 *    1.10   Added king safety + hashing (as done in the old Cray Blitz).      *

 *           Nothing novel other than the use of bit-masks to speed up some of *

 *           the tests.                                                        *

 *                                                                             *

 *    1.11   Additional evaluation knowledge plus log_file so that program     *

 *           saves a record of the game statistics for later analysis.  Added  *

 *           the "annotate" command to make the program analyze a game or part *

 *           of a game for testing/debugging.                                  *

 *                                                                             *

 *    1.12   Added ICS (Internet Chess Server) support for Xboard support so   *

 *           that Crafty can play on ICS in an automated manner.  Added new    *

 *           commands to be compatible with Xboard.  Crafty also has a new     *

 *           command-line interface that allows options to be entered on the   *

 *           command-line directly, ie:  "crafty alarm=off verbose=2" will     *

 *           start the program, set the move alarm off, and set verbose to     *

 *           2.  This allows an "alias" to easily customize the program.       *

 *                                                                             *

 *    1.13   Added time-control logic to the program.  It now monitors how     *

 *           much time both it and its opponent uses when thinking about a     *

 *           move to make.  When pondering, it only times itself from the      *

 *           point that a move is actually entered.                            *

 *                                                                             *

 *    1.14   Added the piece/square tables to the program to move static       *

 *           scoring to the root of the tree since it never changes (things    *

 *           like centralization of pieces, etc.)  also some minor tuning of   *

 *           numbers to bring positional score "swings" down some.             *

 *                                                                             *

 *    1.15   Added edit so that positions can be altered (and so ICS games     *

 *           can be resumed after they are adjourned).  Also added a "force"   *

 *           command to force the program to play a different move than the    *

 *           search selected.  Search timing allocation slightly altered to    *

 *           improve ICS performance.                                          *

 *                                                                             *

 *    1.16   Significant adjustments to evaluation weights to bring positional *

 *           scores down to below a pawn for "normal" positions.  Some small   *

 *           "tweaks" to king safety as well to keep the king safer.           *

 *                                                                             *

 *    1.17   Added "development" evaluation routine to encourage development   *

 *           and castling before starting on any tactical "sorties."  Also     *

 *           repaired many "bugs" in evaluation routines.                      *

 *                                                                             *

 *    1.18   Added the famous Cray Blitz "square of the king" passed pawn      *

 *           evaluation routine.  This will evaluate positions where one       *

 *           side has passed pawns and the other side has no pieces, to see    *

 *           if the pawn can outrun the defending king and promote.  Note that *

 *           this is ridiculously fast because it only requires one AND        *

 *           to declare that a pawn can't be caught!                           *

 *                                                                             *

 *    2.0    initial version preparing for search extension additions.  This   *

 *           version has a new "next_evasion()" routine that is called when    *

 *           the king is in check.  It generates sensible (nearly all are      *

 *           legal) moves which include capturing the checking piece (if there *

 *           is only one), moving the king (but not along the checking ray),   *

 *           and interpositions that block the checking ray (if there is only  *

 *           one checking piece.                                               *

 *                                                                             *

 *    2.1    Search is now broken down into three cleanly-defined phases:      *

 *           (1) basic full-width search [Search()]; (2) extended tactical     *

 *           search [extend()] which includes winning/even captures and then   *

 *           passed pawn pushes to the 6th or 7th rank (if the pawn pushes     *

 *           are safe);  (3) normal quiescence search [Quiesce()] which only   *

 *           includes captures that appear to gain material.                   *

 *                                                                             *

 *    2.2    King safety code re-written and cleaned up.  Crafty was giving    *

 *           multiple penalties which was causing the king safety score to be  *

 *           extremely large (and unstable.)  Now, if it finds something wrong *

 *           with king safety, it only penalizes a weakness once.              *

 *                                                                             *

 *    2.3    King safety code modified further, penalties were significant     *

 *           enough to cause search anomolies.  Modified rook scoring to avoid *

 *           having the rook trapped in the corner when the king is forced to  *

 *           move rather than castle, and to keep the rook in a position to be *

 *           able to reach open files in one move, which avoids getting them   *

 *           into awkward positions where they become almost worthless.        *

 *                                                                             *

 *    2.4    King safety code completely rewritten.  It now analyzes "defects" *

 *           in the king safety field and counts them as appropriate.  These   *

 *           defects are then summed up and used as an index into a vector of  *

 *           of values that turns them into a score in a non-linear fashion.   *

 *           Increasing defects quickly "ramp up" the score to about 1/3+ of   *

 *           a pawn, then additional faults slowly increase the penalty.       *

 *                                                                             *

 *    2.5    First check extensions added.  In the extension search (stage     *

 *           between full-width and captures-only, up to two checking moves    *

 *           can be included, if there are checks in the full-width part of    *

 *           the search.  If only one check occurs in the full-width, then     *

 *           only one check will be included in the extension phase of the     *

 *           selective search.                                                 *

 *                                                                             *

 *    2.6    Evaluation modifications attempting to cure Crafty's frantic      *

 *           effort to develop all its pieces without giving a lot of regard   *

 *           to the resulting position until after the pieces are out.         *

 *                                                                             *

 *    2.7    New evaluation code to handle the "outside passed pawn" concept.  *

 *           Crafty now understands that a passed pawn on the side away from   *

 *           the rest of the pawns is a winning advantage due to decoying the  *

 *           king away from the pawns to prevent the passer from promoting.    *

 *           The advantage increases as material is removed from the board.    *

 *                                                                             *

 *    3.0    The 3.* series of versions will primarily be performance en-      *

 *           hancements.  The first version (3.0) has a highly modified        *

 *           version of MakeMove() that tries to do no unnecessary work.  It   *

 *           is about 25% faster than old version of MakeMove() which makes    *

 *           Crafty roughly 10% faster.  Also calls to Mask() have been        *

 *           replaced by constants (which are replaced by calls to Mask() on   *

 *           the Crays for speed) to eliminate function calls.                 *

 *                                                                             *

 *    3.1    Significantly modified king safety again, to better detect and    *

 *           react to king-side attacks.  Crafty now uses the recursive null-  *

 *           move search to depth-2 instead of depth-1, which results in       *

 *           slightly improved speed.                                          *

 *                                                                             *

 *    3.2    Null-move restored to depth-1.  Depth-2 proved unsafe as Crafty   *

 *           was overlooking tactical moves, particularly against itself,      *

 *           which lost several "won" games.                                   *

 *                                                                             *

 *    3.3    Additional king-safety work.  Crafty now uses the king-safety     *

 *           evaluation routines to compare king safety for both sides.  If    *

 *           one side is "in distress" pieces are attracted to that king in    *

 *           "big hurry" to either attack or defend.                           *

 *                                                                             *

 *    3.4    "Threat extensions" added.  Simply, this is a null-move search    *

 *           used to determine if a move is good only because it is a horizon  *

 *           effect type move.  We do a null move search after a move fails    *

 *           high anywhere in the tree.  The window is normally lowered by 1.5 *

 *           pawns, the idea being that if the fail-high move happens in a     *

 *           position that fails "really low" with a null move, then this move *

 *           might be a horizon move.  To test this, re-search this move with  *

 *           the depth increased by one.                                       *

 *                                                                             *

 *    3.5    50-move rule implemented.  A count of moves since the last pawn   *

 *           move or capture is kept as part of the position[] structure.  It  *

 *           is updated by MakeMove().  When this number reaches 100 (which    *

 *           in plies is 50 moves) Repeat() will return the draw indication    *

 *           immediately, just as though the position was a repetition draw.   *

 *                                                                             *

 *    3.6    Search extensions cleaned up to avoid excessive extensions which  *

 *           produced some wild variations, but which was also slowing things  *

 *           down excessively.                                                 *

 *                                                                             *

 *    3.7    Endgame strategy added.  Two specifics: KBN vs K has a piece/sq   *

 *           table that will drive the losing king to the correct corner.  For *

 *           positions with no pawns, scoring is altered to drive the losing   *

 *           king to the edge and corner for mating purposes.                  *

 *                                                                             *

 *    3.8    Hashing strategy modified.  Crafty now stores search value or     *

 *           bound, *and* positional evaluation in the transposition table.    *

 *           This avoids about 10-15% of the "long" evaluations during the     *

 *           middlegame, and avoids >75% of them in endgames.                  *

 *                                                                             *

 *    4.0    Evaluation units changed to "millipawns" where a pawn is now      *

 *           1000 rather than the prior 100 units.  This provides more         *

 *           "resolution" in the evaluation and will let Crafty have large     *

 *           positional bonuses for significant things, without having the     *

 *           small positional advantages add up and cause problems.  V3.8      *

 *           exhibited a propensity to "sac the exchange" frequently because   *

 *           of this.  It is hoped that this is a thing of the past now.       *

 *           Also, the "one legal reply to check" algorithm is now being used. *

 *           In short, if one side has only one legal reply to a checking move *

 *           then the other side is free to check again on the next ply. this  *

 *           only applies in the "extension" search, and allows some checks    *

 *           that extend() would normally not follow.                          *

 *                                                                             *

 *    4.1    Extension search modified.  It now "tracks" the basic iteration   *

 *           search depth up to some user-set limit (default=6).  For shallow  *

 *           depths, this speeds things up, while at deeper depths it lets the *

 *           program analyze forcing moves somewhat deeper.                    *

 *                                                                             *

 *    4.2    Extension search modified.  Fixed a problem where successive      *

 *           passed-pawn pushes were not extended correctly by extend() code.  *

 *           Threat-extension margin was wrong after changing the value of a   *

 *           pawn to 1000, it is now back to 1.5 pawns.                        *

 *                                                                             *

 *    4.3    Hash scoring "repaired."  As the piece/square tables changed, the *

 *           transposition table (positional evaluation component) along with  *

 *           the pawn and king-safety hash tables prevented the changes from   *

 *           affecting the score, since the hashed scores were based on the    *

 *           old piece/square table values.  Now, when any piece/square table  *

 *           is modified, the affected hash tables are cleared of evaluation   *

 *           information.                                                      *

 *                                                                             *

 *    4.4    Piece/square tables simplified, king tropism scoring moved to     *

 *           Evaluate() where it is computed dynamically now as it should be.  *

 *                                                                             *

 *    4.5    Book move selection algorithm replaced.  Crafty now counts the    *

 *           number of times each book move was played as the book file is     *

 *           created.  Since these moves come (typically) from GM games, the   *

 *           more frequently a move appears, the more likely it is to lead to  *

 *           a sound position.  Crafty then enumerates all possible book moves *

 *           for the current position, computes a probability distribution for *

 *           each move so that Crafty will select a move proportional to the   *

 *           number of times it was played in GM games (for example, if e4 was *

 *           played 55% of the time, then Crafty will play e4 55% of the time) *

 *           although the special case of moves played too infrequently is     *

 *           handled by letting the operator set a minimum threshold (say 5)   *

 *           Crafty won't play moves that are not popular (or are outright     *

 *           blunders as the case may be.)  Pushing a passed pawn to the 7th   *

 *           rank in the basic search [Search() module] now extends the search *

 *           by two plies unless we have extended this ply already (usually a  *

 *           check evasion) or unless we have extended the whole line to more  *

 *           than twice the nominal iteration depth.                           *

 *                                                                             *

 *    5.0    Selective search extensions removed.  With the extensions now in  *

 *           the basic full-width search, these became more a waste of time    *

 *           than anything useful, and removing them simplifies things quite   *

 *           a bit.                                                            *

 *                                                                             *

 *    5.1    Pondering logic now has a "puzzling" feature that is used when    *

 *           the search has no move to ponder.  It does a short search to find *

 *           a move and then ponders that move, permanently eliminating the    *

 *           "idle" time when it has nothing to ponder.                        *

 *                                                                             *

 *    5.2    Evaluation terms scaled down to prevent positional scores from    *

 *           reaching the point that sacrificing material to avoid simple      *

 *           positional difficulties begins to look attractive.                *

 *                                                                             *

 *    5.3    Performance improvement produced by avoiding calls to MakeMove()  *

 *           when the attack information is not needed.  Since the first test  *

 *           done in Quiesce() is to see if the material score is so bad that  *

 *           a normal evaluation and/or further search is futile, this test    *

 *           has been moved to inside the loop *before* Quiesce() is           *

 *           recursively called, avoiding the MakeMove() work only to          *

 *           discover that the resulting position won't be searched further.   *

 *                                                                             *

 *    5.4    New SEE() function that now understands indirect attacks through  *

 *           the primary attacking piece(s).  This corrects a lot of sloppy    *

 *           move ordering as well as make the "futility" cutoffs added in     *

 *           in version 5.3 much more reliable.                                *

 *                                                                             *

 *    5.5    Checks are now back in the quiescence search.  Crafty now stores  *

 *           a negative "draft" in the transposition table rather than forcing *

 *           any depth < 0 to be zero.  The null-move search now searches the  *

 *           null-move to depth-1 (R=1) rather than depth-2 (R=2) which seemed *

 *           to cause some tactical oversights in the search.                  *

 *                                                                             *

 *    5.6    Improved move ordering by using the old "killer move" idea.  An   *

 *           additional advantage is that the killers can be tried before      *

 *           generating any moves (after the captures.)  Quiescence now only   *

 *           includes "safe" checks (using SEE() to determine if it is a safe  *

 *           checking move.                                                    *

 *                                                                             *

 *    5.7    King safety now "hates" a pawn at b3/g3 (white) or b6/g6 (black)  *

 *           to try and avoid the resulting mate threats.                      *

 *                                                                             *

 *    5.8    EvaluateOutsidePassedPawns() fixed to correctly evaluate those    *

 *           positions where both sides have outside passed pawns.  Before     *

 *           this fix, it only evaluated positions where one side had a passed *

 *           pawn, which overlooked those won/lost positions where both sides  *

 *           have passed pawns but one is "distant" or "outside" the other.    *

 *                                                                             *

 *    5.9    Removed "futility" forward pruning.  Exhaustive testing has       *

 *           proved that this causes significant tactical oversights.          *

 *                                                                             *

 *    5.10   Added code to handle king and pawn vs king, which understands     *

 *           the cases where the pawn can't outrun the king, but has to be     *

 *           assisted along by the king.                                       *

 *                                                                             *

 *    5.11   Two king-safety changes.  (1) The program's king safety score is  *

 *           now "doubled" to make it much less likely that it will try to win *

 *           a pawn but destroy it's king-side.  (2) The attack threshold has  *

 *           been lowered which is used to key the program that it is now      *

 *           necessary to move pieces to defend the king-side, in an effort to *

 *           protect a king-side that is deemed somewhat unsafe.               *

 *                                                                             *

 *    5.12   Improved null-move code by computing the Knuth/Moore node type    *

 *           and then only trying null-moves at type 2 nodes.  This has        *

 *           resulted in a 2x speedup in test positions.                       *

 *                                                                             *

 *    5.13   Optimization to avoid doing a call to MakeMove() if it can be     *

 *           avoided by noting that the move is not good enough to bring the   *

 *           score up to an acceptable level.                                  *

 *                                                                             *

 *    5.14   Artificially isolated pawns recognized now, so that Crafty won't  *

 *           push a pawn so far it can't be defended.  Also, the bonus for a   *

 *           outside passed pawn was nearly doubled.                           *

 *                                                                             *

 *    5.15   Passed pawns supported by a king, or connected passed pawns now   *

 *           get a large bonus as they advance.  Minor fix to the ICC resume   *

 *           feature to try to avoid losing games on time.                     *

 *                                                                             *

 *    6.0    Converted to rotated bitboards to make attack generation *much*   *

 *           faster.  MakeMove() now can look up the attack bit vectors        *

 *           rather than computing them which is significantly faster.         *

 *                                                                             *

 *    6.1    Added a "hung piece" term to Evaluate() which penalizes the side  *

 *           to move if a piece is attacked by a lesser piece, or a piece is   *

 *           attacked and not defended at all.  Additionally, a new scoring    *

 *           term was added to detect a weak back rank (where the king does    *

 *           not attack an empty square on the 2nd rank, and there are no      *

 *           horizontally sliding pieces [rook or queen] on the first rank to  *

 *           guard against back-rank mates.                                    *

 *                                                                             *

 *    6.2    Modified the "futility" cutoff to (a) emulate the way the program *

 *           normally searches, but avoiding MakeMove() calls when possible,   *

 *           and (2) not searching a move near the horizon if the material     *

 *           score is hopeless.                                                *

 *                                                                             *

 *    6.3    Null-move code moved from NextMove() directly into Search().      *

 *           this results is a "cleaner" implementation, as well as fixing an  *

 *           error in the node type, caused by Search() thinking that after    *

 *           the first move tried fails to cause a cutoff, that suddenly this  *

 *           node is a type=3 node (Knuth and Moore).  This bug would then     *

 *           introduce null-moves into later nodes that are a waste of time.   *

 *                                                                             *

 *    6.4    Pawn scoring modified.  Passed pawns were scored low enough that  *

 *           Crafty would let the opponent create one in the endgame (as long  *

 *           as it wasn't an "outside" passed pawn).  This required adjusting  *

 *           isolated pawns as well.  All "weak" pawns (pawns on open files    *

 *           that aren't defended by a pawn) are not penalized so much if      *

 *           there aren't any rooks/queens to attack on the file.              *

 *                                                                             *

 *    7.0    Removed the to.attack and from.attack bitboards.  These are now   *

 *           computed as needed, using the rotated bitboards.  Hung piece      *

 *           stuff removed due to lack of any verified benefit.                *

 *                                                                             *

 *    7.1    Modified next.c and nextc.c so that they check "mvv_lva_ordering" *

 *           to determine which capture ordering strategy to use.  Note that   *

 *           setting this to "1" (default at present) disables the forward     *

 *           pruning in quiescence search that wants to cull losing captures.  *

 *                                                                             *

 *    7.2    Major clean-up of MakeMove() using macros to make it easier to    *

 *           read and understand.  Ditto for other modules as well.  Fixed a   *

 *           bug in Evaluate() where bishop scoring failed in endgame          *

 *           situations, and discouraged king centralization.                  *

 *                                                                             *

 *    7.3    Evaluate() is no longer called if material is too far outside the *

 *           current alpha/beta window.  The time-consuming part of Evaluate() *

 *           is no longer done if the major scoring contributors in Evaluate() *

 *           haven't pulled the score within the alpha/beta window, and the    *

 *           remainder of Evaluate() can't possible accomplish this either.    *

 *           Gross error in EvaluatePawns() fixed, which would "forget" all    *

 *           of the pawn scoring done up to the point where doubled white      *

 *           pawns were found.  Error was xx=+ rather than xx+=, which had     *

 *           an extremely harmful effect on pawn structure evaluation.         *

 *                                                                             *

 *    7.4    Performance improvements produced by elimination of bit-fields.   *

 *           This was accomplished by hand-coding the necessary ANDs, ORs, and *

 *           SHIFTs necessary to accomplish the same thing, only faster.       *

 *                                                                             *

 *    7.5    Repetition code modified.  It could store at replist[-1] which    *

 *           clobbered the long long word just in front of this array.         *

 *                                                                             *

 *    7.6    Null move search now searches with R=2, unless within 3 plies     *

 *           of the quiescence search, then it searches nulls with R=1.        *

 *                                                                             *

 *    8.0    Re-vamp of evaluation, bringing scores back down so that Crafty   *

 *           will stop sacrificing the exchange, or a piece for two pawns just *

 *           it thinks it has lots of positional compensation.  The next few   *

 *           versions are going to be tuning or coding modifications to eval.  *

 *                                                                             *

 *    8.1    Futility() re-written to be more efficient, as well as to stop    *

 *           tossing moves out based on the +/- 2 pawn window, which was too   *

 *           speculative.  It still saves roughly 20% in speed over the same   *

 *           searches without futility, but seems to have *no* harmful effects *

 *           in tests run to date.                                             *

 *                                                                             *

 *    8.2    Futility() removed once and for all.  Since MakeMove() is so      *

 *           fast after the new attack generation algorithm, this was actually *

 *           slower than not using it.                                         *

 *                                                                             *

 *    8.3    EvaluatePawns() weak pawn analysis bug fixed.  Other minor        *

 *           performance enhancements and cleanup.                             *

 *                                                                             *

 *    8.4    Dynamic "king tropism" evaluation term now used, which varies     *

 *           based on how exposed the target king is.  The more exposed, the   *

 *           larger the bonus for placing pieces near the king.  New "analyze" *

 *           feature that complements the "annotate" feature that Crafty has   *

 *           had for a while.  Annotate is used to play over moves that are    *

 *           either in the current game history, or have been read in using    *

 *           the "read <filename>" command.  Analyze, on the other hand, will  *

 *           immediately begin searching the current position.  Each time the  *

 *           operator enters a move, it will make that move on the board, and  *

 *           then search the resulting position for the other side.  In effect *

 *           this gives a running commentary on a "game in progress".  These   *

 *           moves can be pumped into Crafty in many ways so that "on the fly" *

 *           analysis of a game-in-progress is possible.                       *

 *                                                                             *

 *    8.5    More cleanup.  Pawn promotions were searched twice, thanks to the *

 *           killer moves, although often they resulted in no search overhead  *

 *           due to transposition table hits the second time around.  Other    *

 *           minor fixes, including one serious "undefined variable" in        *

 *           Evaluate() that caused grief in endings.                          *

 *                                                                             *

 *    8.6    New book file structure.  It is no longer necessary to enter the  *

 *           "number of records" as Crafty now uses a new compressed hashing   *

 *           technique so that the book has no empty space in it, and the size *

 *           is computed "on the fly" producing a smaller book without the     *

 *           user having to compute the size.  Tweaks to Evaluate() to cure    *

 *           minor irritating habits.                                          *

 *                                                                             *

 *    8.7    Repaired optimization made in null-move search, that forgot to    *

 *           clear "EnPassant_Target".  A double pawn push, followed by a null *

 *           left the side on move "very confused" and would let it play an    *

 *           illegal enpassant capture in the tree. Sort.<n> files are now     *

 *           removed after book.bin is created.  Also, minor change to book    *

 *           format makes it incompatible with older book versions, but also   *

 *           allows book lines to be as long as desired, and the book size to  *

 *           reach any reasonable size.  Dynamic king tropism replaced by a    *

 *           dynamic computation, but with a static king tropism score, rather *

 *           than a score based on king exposure.  There was simply too much   *

 *           interaction, although this may prove workable later.              *

 *                                                                             *

 *    8.8    Tweaks to passed pawn scoring.  Scores were too low, making       *

 *           Crafty "ignore" them too much.                                    *

 *                                                                             *

 *    8.9    Internal iterative deepening is now used in those rare positions  *

 *           where a PV node has no hash move to search.  This does a shallow  *

 *           search to depth-2 to find a good move for ordering.               *

 *                                                                             *

 *    8.10   Internal interative deepening modified to handle cases where lots *

 *           of tactics make the deepening search fail high or low, and        *

 *           occasionally end up with no move to try.  This produced a "bad    *

 *           move from hash table" error.                                      *

 *                                                                             *

 *    8.11   Minor bug in internal iterative deepening fixed.  Also, macros    *

 *           for accessing the "position" data structure are now used to make  *

 *           things a little more readable.                                    *

 *                                                                             *

 *    8.12   Fixed minor bugs in quiescence checks, which let Crafty include   *

 *           more checks than intended (default quiescence_checks=2, but the   *

 *           comparison was <= before including a check, which made it include *

 *           three.  Additionally, a hashed check was *always* tried, even if  *

 *           quiescence_checks had already been satisfied.  Pawn scoring also  *

 *           had a bug, in that there was a "crack" between opening and middle *

 *           game, where Crafty would conclude that it was in an endgame, and  *

 *           adjust the pawn advance scores accordingly, sometimes causing an  *

 *           odd a4/a5/etc move "out of the blue."  Minor bug in next_capture  *

 *           was pruning even exchanges very early in quiescence search.  That *

 *           has now been removed, so only losing exchanges are pruned.        *

 *                                                                             *

 *    8.13   NextCapture() now *always* tries checking moves if the move at    *

 *           the previous ply was a null-move.  This avoids letting the null   *

 *           move hide some serious mating threats.  A minor bug where Crafty  *

 *           could draw by repetition after announcing a mate.  This was a     *

 *           result of finding a mate score in hash table, and, after the      *

 *           search iteration completed, the mate score would terminate the    *

 *           search completely.  Now, the search won't terminate until it      *

 *           finds a mate shorter than the previous search did.  Minor eval    *

 *           tweaks and bugfixes as well.                                      *

 *                                                                             *

 *    8.14   Checks after null moves discontinued.  Worked in some cases, but, *

 *           in general made the tree larger for nothing.  Eval tweaks to stop *

 *           sacs that resulted in connected passed pawns, often at the        *

 *           expense of a minor piece for a pawn or two, which usually lost.   *

 *           Mobility coeffecient increased for all pieces.  Asymmetric king   *

 *           safety discontinued.  King safety for both sides is now equally   *

 *           important.  King safety is now also proportional to the number of *

 *           pieces the other side has, so that a disrupted king-side will     *

 *           encourage trading pieces to reduce attacking chances.             *

 *                                                                             *

 *    8.15   Weak pawn scoring modified further.  The changes are designed to  *

 *           cause Crafty to keep pawns "mobile" where they can advance,       *

 *           rather than letting them become blocked or locked.                *

 *                                                                             *

 *    8.16   Still more weak pawn modifications.  In addition, there is no     *

 *           "rook on half-open file" any longer.  If there are only enemy     *

 *           pawns on the file, and the most advanced one is weak, then the    *

 *           file is treated as though it were open.  Technical error in the   *

 *           EvaluateDevelopment() code that caused screwey evaluations is     *

 *           fixed, making Crafty more likely to castle.  :)  Book() now       *

 *           verifies that the current position is in book, before trying any  *

 *           moves to see if the resulting positions are in book.  This avoids *

 *           something like e4 e5 Bb5 a6 Nf3 from causing Crafty to play Nc6   *

 *           which takes it back into book, rather than axb5 winning a piece.  *

 *           This will occasionally backfire and prevent Crafty from trans-    *

 *           posing back into book, but seems safer at present.                *

 *                                                                             *

 *    8.17   Piece values changed somewhat, to avoid Crafty's propensity to    *

 *           make unfavorable trades.  An example:  Crafty is faced with the   *

 *           loss of a pawn.  Instead, it trades the queen for a rook and      *

 *           bishop, which used to be the same as losing a pawn.  This is not  *

 *           so good, and often would result in a slow loss.  This version     *

 *           also implements several "user-supplied" patches to make Crafty    *

 *           compile cleanly on various machines.  In addition, you no longer  *

 *           have to continually modify types.h for different configurations.  *

 *           the Makefile now supplies a -D<target> to the compiler.  You need *

 *           to edit Makefile and set "target" to the appropriate value from   *

 *           the list provided.  Then, when getting a new version, save your   *

 *           Makefile, extract the new source, copy in your makefile and you   *

 *           will be ready, except for those rare occasions where I add a new  *

 *           source module.  Other changes are performance tweaks.  One is a   *

 *           simple trick to order captures while avoiding SEE() if possible.  *

 *           If the captured piece is more valuable than the capturing piece,  *

 *           we can simply use the difference (pessimistic value) rather than  *

 *           calling SEE() since this pessimistic value is still > 0.  Other   *

 *           tweaks to the various Next_*() routines to avoid a little un-     *

 *           necessary work.                                                   *

 *                                                                             *

 *    8.18   Book move selection algorithm changed.  Note that this is highly  *

 *           speculative, but when best book play is selected, Crafty will     *

 *           use the books.bin file as always.  If there is no move in books,  *

 *           Crafty reverts to book.bin, but now finds all known book moves    *

 *           and puts them into the root move list.  It then does a fairly     *

 *           short search, only considering these moves, and it will play the  *

 *           best one so long as the evaluation is acceptable.  If not, it     *

 *           simply returns as though there was no book move, and executes a   *

 *           search as it normally would.  The book hashing algorithm was also *

 *           modified so that the 64-bit hash key is slightly different from   *

 *           the real hash key.  In effect, the upper 16 bits are only set as  *

 *           a result of the side-not-to-move's pieces.  This means that for a *

 *           given position, all the book moves will be in the same "cluster"  *

 *           which makes the book dramatically faster, since one seek and read *

 *           produces all the possible book moves (plus some others too, since *

 *           the upper 16 bits are not unique enough.)  A significant speed    *

 *           improvement is noticable, particularly with a 60mb opening book.  *

 *           Crafty now understands (if that's the right word) that endings    *

 *           with bishops of opposite colors are to be avoided.  When such an  *

 *           ending is encountered, the total score is simply divided by two   *

 *           to make the ending look more drawish.                             *

 *                                                                             *

 *    8.19   Book selection algorithm further modified, so that the result of  *

 *           each game in the GM database is known.  Now Crafty will not play  *

 *           a move from book, if all games were lost by the side on move,     *

 *           hopefully avoiding many blunders.  Crafty now understands how to  *

 *           attack if both players castle on opposite sides, by encouraging   *

 *           pawn advances against the kings.  Other minor modifications to    *

 *           the eval values.                                                  *

 *                                                                             *

 *    8.20   PVS search finally implemented fully.  Problems several months    *

 *           ago prevented doing the PVS search along the PV itself.  This is  *

 *           therefore quite a bit faster, now that it's fully implemented and *

 *           working properly.  Elapsed time code modified so that Crafty now  *

 *           uses gettimeofday() to get fractions of a second elapsed time.    *

 *           Slight modification time allocation algorithm to avoid using too  *

 *           much time early in the game.                                      *

 *                                                                             *

 *    8.21   Courtesy of Mark Bromley, Crafty may run significantly faster on  *

 *           your machine.  There are some options in the Makefile that will   *

 *           eliminate many of the large attack computation long longs, which  *

 *           helps prevent cache thrashing.  On some machines this will be     *

 *           slower, on others 20% (or maybe more) faster.  You'll have to     *

 *           try -DCOMPACT_ATTACKS, and if that's faster, then it's time to    *

 *           try -DUSE_SPLIT_SHIFTS which may help even more.  Finally, if you *

 *           are running on a supersparc processor, you can use the fastattack *

 *           assembly module fastattack.s and get another big boost.  (Attack  *

 *           function is largest compute user in Crafty at present.) Serious   *

 *           search problem fixed.  It turns out that Crafty uses the hash     *

 *           table to pass PV moves from one iteration to the next, but for    *

 *           moves at the root of the tree the hash table has no effect, so a  *

 *           special case was added to RootMoveList to check the list of moves *

 *           and if one matches the PV move, move it to the front of the list. *

 *           This turned out to be critical because after completing a search, *

 *           (say to 9 plies) Crafty makes its move, then chops the first two  *

 *           moves off of the PV and then passes that to iterate to start a    *

 *           search.  This search starts at lastdepth-1 (8 in this case) since *

 *           the n-2 search was already done.  The "bug" showed up however, in *

 *           that RootMoveList() was not checking for the PV move correctly,   *

 *           which meant the root moves were ordered by static eval and static *

 *           exchange evaluation.  Normally not a serious problem, just that   *

 *           move ordering is not so good.  However, suppose that the opponent *

 *           takes a real long time to make a move (say 30 seconds) so that    *

 *           Crafty completes a 10 ply search.  It then starts the next search *

 *           at depth=9, but with the wrong move first.  If the target time is *

 *           not large enough to let it resolve this wrong move and get to the *

 *           other moves on the list, Crafty is "confused" into playing this   *

 *           move knowing absolutely nothing about it.  The result is that it  *

 *           can play a blunder easily.  The circumstances leading to this are *

 *           not common, but in a 60 move game, once is enough.  PV was pretty *

 *           well mis-handled in carrying moves from one search to another     *

 *           (not from one iteration to another, but from one complete search  *

 *           to another) and has been fixed.  A cute glitch concerning storing *

 *           PV from one iteration to another was also fixed, where the score  *

 *           stored was confusing the following search.                        *

 *                                                                             *

 *    8.22   EPD support (courtesy of Steven Edwards [thanks]) is now standard *

 *           in Crafty.  For porting, I'll provide a small test run which can  *

 *           be used to validate Crafty once it's been compiled.               *

 *                                                                             *

 *    8.23   Cleanup/speedup in hashing.  ProbeTransRef() and StoreTransRef()  *

 *           now carefully cast the boolean operations to the most efficient   *

 *           size to avoid 64bit operations when only the right 32 bits are    *

 *           significant. Repeat() code completely re-written to maintain two  *

 *           repetition lists, one for each side.  Quiesce() now handles the   *

 *           repetition check a little different, being careful to not call it *

 *           when it's unimportant, but calling it when repetitions are        *

 *           possible.                                                         *

 *                                                                             *

 *    8.24   Tweaks for king tropism to encourage pieces to collect near the   *

 *           king, or to encourage driving them away when being attacked.  A   *

 *           modification to Evaluate() to address the problem where Crafty    *

 *           is forced to play Kf1 or Kf8, blocking the rook in and getting    *

 *           into tactical difficulties as a result.  Book problem fixed where *

 *           Bookup was attempting to group moves with a common ancestor       *

 *           position together.  Unfortunately, captures were separated from   *

 *           this group, meaning capture moves in the book could never be      *

 *           played.  If a capture was the only move in book, it sort of       *

 *           worked because Crafty would drop out of book (not finding the     *

 *           capture) and then the search would "save" it.  However, if there  *

 *           was a non-capture alternative, it would be forced to play it,     *

 *           making it play gambits, and, often, bad ones.  Tablebase support  *

 *           is now in.  The tablebase files can be downloaded from the ftp    *

 *           machine at chess.onenet.net, pub/chess/TB.  Currently, Steven     *

 *           Edwards has all interesting 4 piece endings done.  To make this   *

 *           work, compile with -DTABLEBASES, and create a TB directory where  *

 *           Crafty is run, and locate the tablebase files in that directory.  *

 *           If you are running under UNIX, TB can be a symbolic or hard link  *

 *           to a directory anywhere you want.                                 *

 *                                                                             *

 *    8.25   Minor repair on draw by repetition.  Modified how books.bin was   *

 *           being used.  Now, a move in books.bin has its flags merged with   *

 *           the corresponding move from book.bin, but if the move does not    *

 *           exist in book.bin, it is still kept as a book move.  Repetitions  *

 *           are now counted as a draw if they occur two times, period.  The   *

 *           last approach was causing problems due to hashing, since the hash *

 *           approach used in Crafty is fairly efficient and frequently will   *

 *           carry scores across several searches.  This resulted in Crafty    *

 *           stumbling into a draw by repetition without knowing.  The con-    *

 *           figuration switch HAS-64BITS has been cleaned up and should be    *

 *           set for any 64bit architecture now, not just for Cray machines.   *

 *                                                                             *

 *    8.26   New search extension added, the well-known "one legal response to *

 *           check" idea.  If there's only one legal move when in check, we    *

 *           extend two plies rather than one, since this is a very forcing    *

 *           move.  Also, when one side has less than a rook, and the other    *

 *           has passed pawns, pushing these pawns to the 6th or 7th rank      *

 *           will extend the search one ply, where in normal positions, we     *

 *           only extend when a pawn reaches the 7th rank.                     *

 *                                                                             *

 *    9.0    Minor constraint added to most extensions:  we no longer extend   *

 *           if the side on move is either significantly ahead or behind,      *

 *           depending on the extension.  For example, getting out of check    *

 *           won't extend if the side on move is a rook behind, since it's     *

 *           already lost anyway.  We don't extend on passed pawn pushes if    *

 *           the side on move is ahead a rook, since he's already winning.     *

 *           minor adjustments for efficiency as well.  The next few versions  *

 *           in this series will have module names in these comments           *

 *           indicating which modules have been "cleaned" up.  This is an      *

 *           effort at optimizing, although it is currently directed at a line *

 *           by line analysis within modules, rather than major changes that   *

 *           effect more global ideas.  This type of optimization will come at *

 *           a later point in time.                                            *

 *                                                                             *

 *    9.1    NextMove(), NextCapture() and NextEvasion() were re-structured    *

 *           to eliminate unnecessary testing and speed them up significantly. *

 *           EvaluateTrades() was completely removed, since Crafty already has *

 *           positional scores that encourage/discourage trading based on the  *

 *           status of the game.  EvaluateTempo() was evaluated to be a        *

 *           failure and was removed completely.                               *

 *                                                                             *

 *    9.2    Quiesce()) and Search() were modified to be more efficient.  In   *

 *           addition, the null-move search was relaxed so that it always does *

 *           a search to depth-R, even if close to the end of the tree.        *

 *                                                                             *

 *    9.3    Check() is no longer used to make sure a position is legal after  *

 *           MakeMove() called, but before Search() is called recursively.  We *

 *           now use the same approach as Cray Blitz, we make a move and then  *

 *           capture the king at the next ply to prove the position is not a   *

 *           valid move.  If the side-on-move is already in check, we use      *

 *           NextEvasion() which only generates legal moves anyway, so this    *

 *           basically eliminates 1/2 of the calls to Check(), a big win.      *

 *           This resulted in modifications to Search(), Quiesce(), and        *

 *           QuiesceFull().  Connected passed pawns on 6th-7th no longer       *

 *           trigger search extensions.  Solved some problems like Win at      *

 *           Chess #2, but overall was a loser.                                *

 *                                                                             *

 *    9.4    Lookup now checks the transposition table entry and then informs  *

 *           Search() when it appears that a null move is useless.  This is    *

 *           found when the draft is too low to use the position, but it is at *

 *           least as deep as a null-move search would go, and the position    *

 *           did not cause a fail-high when it was stored.  King-safety was    *

 *           modified again.  The issue here is which king should attract the  *

 *           pieces, and for several months the answer has been the king that  *

 *           is most exposed attracts *all* pieces.  This has been changed to  *

 *           always attract one side's pieces to the other king.  Crafty's     *

 *           asymmetric king-safety was making it overly-defensive, even when  *

 *           the opponent's king was more exposed.  This should cure that and  *

 *           result in more aggressive play.                                   *

 *                                                                             *

 *    9.5    "Vestigial code" (left over from who-knows-when) removed from     *

 *           Evaluate().  This code used an undefined variable when there was  *

 *           no bishop or knight left on the board, and could add in a penalty *

 *           on random occasions.  Quiescence checks removed completely to see *

 *           how this works, since checks extend the normal search significant *

 *           amounts in any case.  QuiesceFull() removed and merged into       *

 *           Quiesce() which is faster and smaller.  First impression: faster, *

 *           simpler, better.  The benefit of no quiescence checks is that the *

 *           exhaustive search goes deeper to find positional gains, rather    *

 *           than following checks excessively.  No noticable loss in tactical *

 *           strength (so far).                                                *

 *                                                                             *

 *    9.6    legal move test re-inserted in Search() since null-moves could    *

 *           make it overlook the fact that a move was illegal.  New assembly  *

 *           code for X86 improves performance about 1/3, very similarly to    *

 *           the results obtained with the sparc-20 assembly code.  This was   *

 *           contributed by Eugene Nalimov and is a welcome addition.          *

 *                                                                             *

 *    9.7    Optimizations continuing.  Minor bug in pawn evaluation repaired. *

 *           Crafty looked at most advanced white pawn, but least-advanced     *

 *           black pawn on a file when doing its weak pawn evaluation.  The    *

 *           history heuristic was slightly broken, in that it was supposed to *

 *           be incrementing the history count by depth*depth, but this was    *

 *           somehow changed to 7*depth, which was not as good.  Assembly      *

 *           language interface fixed to cleanly make Crafty on all target     *

 *           architectures.                                                    *

 *                                                                             *

 *    9.8    The first change was to borrow a time-allocation idea from Cray   *

 *           Blitz.  Essentially, when Crafty notices it has used the normal   *

 *           time allotment, rather than exiting the search immediately, it    *

 *           will wait until it selects the next move at the root of the tree. *

 *           The intent of this is that if it has started searching a move     *

 *           that is going to be better than the best found so far, this will  *

 *           take more time, while a worse move will fail low quickly.  Crafty *

 *           simply spends more time to give this move a chance to fail high   *

 *           or else quickly fail low.  A fairly serious bug, that's been      *

 *           around for a long time, has finally been found/fixed.  In simple  *

 *           terms, if the "noise" level was set too high, it could make       *

 *           Crafty actually play a bad move.  The more likely effect was to   *

 *           see "bad move hashed" messages and the first few lines of output  *

 *           from the search often looked funny.  The bug was "noise" was used *

 *           as a limit, until that many nodes had been searched, no output    *

 *           would be produced.  Unfortunately, on a fail-high condition, the  *

 *           same code that produced the "++  Nh5" message also placed the     *

 *           fail-high move in the PV.  Failing to do this meant that the      *

 *           search could fail high, but not play the move it found.  Most     *

 *           often this happened in very fast games, or near the end of long   *

 *           zero-increment games.  It now always saves this move as it should *

 *           regardless of whether it prints the message or not.               *

 *                                                                             *

 *    9.9    Interface to Xboard changed from -ics to -xboard, so that -ics    *

 *           can be used with the custom interface.  Additional code to        *

 *           communicate with custom interface added.  Search() extensions are *

 *           restricted so that there can not be more than one extension at a  *

 *           node, rather than the two or (on occasion) more of the last       *

 *           version.                                                          *

 *                                                                             *

 *    9.10   Converted to Ken Thompson's "Belle" hash table algorithm.  Simply *

 *           put, each side has two tables, one that has entries replaced on a *

 *           depth-priority only, the other is an "always replace" table, but  *

 *           is twice as big.  This allows "deep" entries to be kept along     *

 *           with entries close to search point.  Basically, when the depth-   *

 *           priority table gets a position stored in it, the displaced        *

 *           position is moved to the always-replace table.  If the position   *

 *           can not replace the depth-priority entry, it always overwrites    *

 *           the other always-replace entry.  However, a position is never put *

 *           in both tables at the same time.                                  *

 *                                                                             *

 *    9.11   Bug in Search() that could result in the "draft" being recorded   *

 *           incorrectly in the hash table.  Caused by passing depth, which    *

 *           could be one or two plies more than it should be due to the last  *

 *           move extending the search.  Repeat() completely removed from      *

 *           Quiesce() since only capture moves are included, and it's         *

 *           impossible to repeat a position once a capture has been made.     *

 *                                                                             *

 *    9.12   optimizations: history.c, other minor modifications.              *

 *                                                                             *

 *    9.13   EvaluatePawns() modified significantly to simplify and be more    *

 *           accurate as well.  Pawns on open files are now not directly       *

 *           penalized if they are weak, rather the penalty is added when the  *

 *           rooks are evaluated.  Pawn hashing modified to add more info to   *

 *           the data that is hashed.  King safety scores toned down almost    *

 *           50% although it is still asymmetric.                              *

 *                                                                             *

 *    9.14   EvaluatePawns() modified further so that it now does the same     *

 *           computations for king safety as the old EvaluateKingSafety*()     *

 *           modules did, only it produces four values, two for each king,     *

 *           for each side of the board (king or queen-side).  This is now     *

 *           hashed with the rest of the pawn scoring, resulting in less       *

 *           hashing and computation, and more hits for king-safety too.  King *

 *           safety modified further.  Asymmetric scoring was accidentally     *

 *           disabled several versions ago, this is now enabled again.         *

 *                                                                             *

 *    9.15   Evaluate() now attempts to recognize the case where a knight is   *

 *           trapped on one of the four corner squares, much like a bishop     *

 *           trapped at a2/a7/h2/h7.  If a knight is on a corner square, and   *

 *           neither of the two potential flight squares are safe (checked by  *

 *           SEE()) then a large penalty is given.  This was done to avoid     *

 *           positions where Crafty would give up a piece to fork the king and *

 *           rook at (say) c7, and pick up the rook at a8 and think it was an  *

 *           exchange ahead, when often the knight was trapped and it was      *

 *           two pieces for a rook and pawn (or worse.)  Two timing bugs fixed *

 *           in this version:  (1) nodes_per_second was getting clobbered at   *

 *           the end of iterate, which would then corrupt the value stored in  *

 *           nodes_between_time_checks and occasionally make Crafty not check  *

 *           the time very often and use more time than intended; (2) the      *

 *           "don't stop searching after time is out, until the current move   *

 *           at the root of the tree has been searched" also would let Crafty  *

 *           use time unnecessarily.                                           *

 *                                                                             *

 *    9.16   Significant changes to the way MakeMove() operates.  Rather than  *

 *           copying the large position[ply] structure around, the piece       *

 *           location bitmaps and the array of which piece is on which square  *

 *           are now simple global variables.  This means that there is now an *

 *           UnmakeMove() function that must be used to restore these after a  *

 *           a move has been made.  The benefit is that we avoid copying 10    *

 *           bitmaps for piece locations when typically only one is changed,   *

 *           Ditto for the which piece is on which square array which is 64    *

 *           bytes long.  The result is much less memory traffic, with the     *

 *           probability that the bitmaps now stay in cache all the time. The  *

 *           EvaluatePawns() code now has an exponential-type penalty for      *

 *           isolated pawns, but it penalizes the difference between white and *

 *           black isolated pawns in this manner.  King evaluation now         *

 *           evaluates cases where the king moves toward one of the rooks and  *

 *           traps it in either corner.                                        *

 *                                                                             *

 *    9.17   Xboard compatibility version!  Now supports, so far as I know,    *

 *           the complete xboard interface, including hint, show thinking,     *

 *           taking back moves, "move now" and so forth.  Additionally, Crafty *

 *           now works with standard xboard.  Notice that this means that a    *

 *           ^C (interrupt) will no long terminate Crafty, because xboard uses *

 *           this to implement the "move now" facility.  This should also      *

 *           work with winboard and allow pondering, since there is now a      *

 *           special windows version of CheckInput() that knows how to check   *

 *           Win95 or WinNT pipes when talking with winboard.                  *

 *                                                                             *

 *    9.18   Xboard compatibility update.  "force" (gnu) mode was broken, so   *

 *           that reading in a PGN file (via xboard) would break.  Now, Crafty *

 *           can track the game perfectly as xboard reads the moves in.  King  *

 *           safety modified to discourage g3/g6 type moves without the bishop *

 *           to defend the weak squares.  Significant other changes to the     *

 *           Evaluate() procedure and its derivatives.  Very nasty trans/ref   *

 *           bug fixed.  Been there since transposition tables added.  When    *

 *           storing a mate score, it has to be adjusted since it's backed up  *

 *           as "mate in n plies from root" but when storing, it must be saved *

 *           as "mate in n plies from current position".  Trivial, really, but *

 *           I overlooked one important fact:  mate scores can also be upper   *

 *           or lower search bounds, and I was correcting them in the same way *

 *           which is an error.  The effect was that Crafty would often find a *

 *           mate in 2, fail high on a move that should not fail high, and end *

 *           up making a move that would mate in 3.  In particularly bad cases *

 *           this would make the search oscillate back and forth and draw a    *

 *           won position.  The fix was to only adjust the score if it's a     *

 *           score, not if it's a bound.  The "age" field of the trans/ref     *

 *           table was expanded to 3 bits.  Iterate now increments a counter   *

 *           modulo 8, and this counter is stored in the 3 ID bits of the      *

 *           trans/ref table.  If they are == the transposition_id counter,    *

 *           we know that this is a position stored during the current search. *

 *           If not, it's an "old" position.  This avoids the necessity of     *

 *           stepping through each entry in the trans/ref table (at the begin- *