. . . . . . . . .

Crafty 9.x Version History

9.31

minor changes by Lloyd for performance enhancements on the code he modified for the Macintosh port. Bug in evaluate() fixed that would produce bogus results for certain cases of a king that might move to f8 (for example) trapping the rook at h8.

9.30

minor change to InputMove() for autoplay promotion bug. this version has some c++ extensions so that it will now compile and run, even on machines without long long (64bit) integers. this includes the macintosh, with the changes provided by Lloyd Lim.

9.29

InCheck() is never called in Quiesce() now. as a result, Crafty won't recognize mates in the q-search. this has speeded the code up with no visible penalty, other than it will occasionally find a win of material rather than a mate score, but this has not affected the problem suite results in a measurable way (it has improved somewhat), other than crafty is now about 10% faster in average positions, and much faster in others. the latest epd code from Steven Edwards is a part of this version, which includes updated tablebase access code. other minor tuning changes are included. This is probably the last version to be released for a while as I'm fixing to begin preparations for the WMCCC tournament in Jakarta, and plan on spending as much time as possible getting ready for this event. The Jakarta version will be released as soon as the tournament ends, however a few "top secret" ideas won't "hurt." :) 9.29 will certainly be updated if any problems show up, however.

9.28

piece/square table added for rooks. primary purpose is to discourage rooks moving to the edge of the board but in front of pawns, where it is easy to trap it. Crafty now understands the concept of blockading a passed pawn to prevent it from advancing. it always understood that advancing one was good, which would tend to encourage blockading, but it would also often ignore the pawn and let it advance a little here, a little there, until it suddenly realized that it was a real problem. the command to set the size of the hash table has been modified. this command is now "hash n", "hash nK" or "hash nM" to set the hash table to one of bytes, Kbytes, or Mbytes. Note that if the size is not an exact multiple of what crafty needs, it silently reduces the size to an optimum value as close to the suggested size as possible. trade bonus/penalty is now back in, after having been removed when the new UnMake() code was added. crafty now tries to trade pawns but not pieces when behind, and tries to trade pieces but not pawns when ahead. EvaluateDraws() now understands that rook pawns + the wrong bishop is a draw. minor adjustment to the quiescence-search pruning introduced in 9.27, to avoid excluding captures that didn't lose material, but looked bad because the positional score was low. slightly increased the values of the pieces relative to that of a pawn to discourage the tendency to trade a piece for two or three pawns plus some positional plusses that often would slowly vanish. null-move search modified to try null-moves, even after captures. this seems to hurt some problem positions, but speeds up others significantly. seems better but needs close watching. EvaluateDraws() call moved to the top of Evaluate() to check for absolute draws first. Quiesce() now always calls Evaluate() which checks for draws before trying the early exit tests to make sure that draws are picked up first. EvaluateDraws() substantially re-written to get rid of lots of unnecessary instructions, and to also detect RP+B of wrong color even if the losing side has a pawn of its own. Crafty would often refuse to capture that last pawn to avoid reaching an endgame it knew was drawn.

9.27

this version has an interesting modification to NextCapture(). Quiesce() now passes alpha to NextCapture() and if a capture appears to win material, but doesn't bring the score up to the value of alpha, the capture is ignored. in effect, if we are so far behind that a capture still leaves us below alpha, then there is nothing to gain by searching the capture because our opponent can simply stand pat at the next ply leaving the score very bad. one exception is if the previous ply was in check, we simply look for any safe-looking capture just in case it leads to mate. bad book bug with book random=1 or 2 fixed (this is set when playing a computer). this bug would cause crafty to play an illegal move and bust wide open with illegal move errors, bad move hashed, and other things. book randomness also quite a bit better now.

9.26

minor bug fixes in time allocation. this mainly affects Crafty as it plays on a chess server. the problem is, simply, that the current internal timing resolution is 1/10 of a second, kept in an integer variable. .5 seconds is stored as 5, for example. this became a problem when the target time for a search dropped below .3 seconds, because the "easy move" code would terminate the search after 1/3 of the target time elapsed if there were no fail lows or PV changes. unfortunately, 2 divided by 3 (.2 secs /3) is "zero" which would let the search quickly exit, possibly without producing a PV with a move for Crafty to play. Crafty would play the first PV move anyway, which was likely the PV move from the last search. this would corrupt the board information, often produce the error "illegal move" when the opponent tried to move, or, on occasion, blow crafty up. on a chess server, Crafty would simply flag and lose. after this fix, I played several hundred games with a time control of 100 moves in 1 second and there were no failures. before the fix, this time control could not result in a single completed game. if you don't run Crafty on a chess server, this version is not important, probably. a minor fix for move input, so that moves like e2e4 will always be accepted, where before they would sometimes be flagged as errors.

9.25

minor bug in Book() fixed where it was possible for crafty to play a book move that was hardly ever played. minor change to time utilization to use a little more time "up front". tuned piece/square tables to improve development some. saw Crafty lose an occasional game because (for example) the bishop at c1 or c8 had not moved, but the king had already castled, which turned the EvaluateDevelopment() module "off". first[ply] removed, since it was redundant with last[ply-1]. the original intent was to save a subscript math operation, but the compilers are quite good with the "strength-reduction" optimization, making referencing a value by first[ply] or last[ply-1] exactly the same number of cycles. passed pawn scores increased. the reduction done to reduce all scores seemed to make Crafty less attentive to passed pawns and the threats they incur. Minor bug in Book() fixed, the variable min_percent_played was inoperative due to incorrect test on the book_status[n] value. pawn rams now scored a little differently, so that pawn rams on Crafty's side of the board are much worse than rams elsewhere. This avoids positional binds where, for example Crafty would like black with pawns at e6 d5 c6, white with pawns at e5 and c5. black has a protected passed pawn at d5 for sure, but the cramp makes it easy for white to attack black, and makes it difficult for black to defend because the black pawns block the position badly. king safety tweaked up about 30%, due to using nearly symmetrical scoring, the values had gotten too small and were not overriding minor positional things.

9.24

minor bug in Quiesce() repaired. when several mate-in-1 moves were available at the root, Crafty always took the last one, which was often an under-promotion to a rook rather than to a queen. It looked silly and has been fixed so that it will play the first mate-in-1, not the last. RootMoveList() went to great pains to make sure that promotion to queen occurs before rook. bug in EvaluateOutsidePassedPawns() would fail to recognize that one side had an outside passer, unless both sides had at least one passer, which failed on most cases seen in real games. minor "tweak" to move ordering. GenerateMoves() now uses the LastOne() function to enumerate white moves, while still using FirstOne() for black moves. this has the effect of moving pieces toward your opponent before moving them away. a severe oversight regarding the use of "!" (as in wtm=!wtm) was found and corrected to speed things up some. !wtm was replaced by wtm^1 (actually, a macro ChangeSide(wtm) is used to make it more readable) which resulted in significant speedup on the sparc, but a more modest improvement on the pentium.

9.23

more evaluation tuning, including the complete removal of the mobility term for rooks/queens. since rooks already have lots of scoring terms like open files, connected, etc, mobility is redundant at times and often misleading. The queen's mobility is so variable it is nearly like introducing a few random points at various places in the search. minor xboard compatibility bug fixed where you could not load a game file, then have crafty play by clicking the "machine white" or "machine black" options.

9.22

more castling evaluation changes, to tune how/when Crafty chooses to castle. bugs in Option() where certain commands could be executed while a search was in progress. if these commands did anything to the board position, it would break Crafty badly. all that was needed was to check for an active search before some commands were attempted, and if a search was in progress, return to abort the search then re-try the command. when playing games with computers (primarily a chess-server consideration) Crafty is now defaulting to "book random 0" to use a short search to help avoid some ugly book lines on occasion. in this version, *all* positional scores were divided by 2 to reduce the liklihood that crafty would sacrifice material and make up the loss with some sort of positional gain that was often only temporary. note that king safety scores were not reduced while doing this. new book random options: 0=search, 1=most popular move, 2=move that produces best positional value, 3=choose from most frequently played moves, 4=emulate GM frequency of move selection, 5=use sqrt() on frequencies to give more randomness, 6=random. for now, computers get book_random=1, while GM's now get 4 (same as before), everyone else gets 5. up until this point, there has penalty for doubled/tripled pawns. it now exists. also, if the king stands on E1/E8, then the king-side king safety term is used to discourage disrupting the king-side pawns before castling. Crafty now has a start-up initialization file (as most Unix programs do). this file is named ".craftyrc" if the macro UNIX is defined, otherwise a "dossy" filename "crafty.rc" is used. Crafty opens this file and executes every command in it as though they were typed by the operator. the last command *must* be "exit" to revert input back to STDIN.

9.21

castling evaluation has been significantly modified to handle the following three cases better: (a) one side can castle at the root of the tree, but can not castle at a tip position. if the move that gave up the right to castle was *not* a castle move, penalize the score. (b) one side can castle short or long at the root, but has already castled by the time the search reaches a tip position. here the goal is to make sure the player castled to the "better" side by comparing king safety where the king really is, to king safety had the king castled to the other side. if the latter is "safer" then penalize the current position by the "difference" in king safety to encourage that side to delay castling. this is a problem when Crafty can castle kingside *now*, but the kingside has been disrupted somehow. if the search is not deep enough to see clearing out the queenside and castling long, then it will often castle short rather than not castle at all. this fix will make it delay, develop the queenside, and castle to a safer king shelter, unless tactics force it to castle short. (c) one side can castle short or long at the root, but can only castle one way at a tip position, because a rook has been moved. if the remaining castle option is worse than castling to the side where the rook was moved, then we penalize the rook move to keep castling to that side open as an option.

9.20

bug in SetBoard() fixed. validity checks for castling status and en passant status was broken for castle status. it was checking the wrong rook to match castling status, and would therefore not accept some valid positions, including #8 in Win At Chess suite. minor repetition bug fixed, where Crafty would recognize that a three-fold repetition had occurred, but would not claim it when playing on a chess server. Crafty now does not immediately re-search the first move when it fails low. rather, it behaves like Cray Blitz, and searches all moves. if all fail low, Crafty will then relax (lower) alpha and search the complete list again. this is a simple gamble that there is another move that will "save the day" so that we avoid the overhead of finding out just how bad the first move is, only to have more overhead when a good move fails high. minor repetition bug fixed. when running test suites of problems, SetBoard() neglected to put the starting position in the repetition list, which would occasionally waste time. one notable case was Win At Chess #8, where crafty would find Nf7+ Kg8 Nh6+ Kh8 (repeating the original position) followed by Rf7 (the correct move, but 4 tempi behind.) Display() bug fixed. Crafty now displays the current board position, rather than the position that has been modified by a search in progress. castling evaluation modified including a bug in the black side that would tend to make Crafty not castle queen-side as black if the king-side was shredded. minor bug Book(). if the book was turned off (which is done automatically when using the test command since several of the Win At Chess positions are from games in Crafty's large opening book) Book() would still try to read the file and then use the data from the uninitialized buffer. this would, on occasion, cause Crafty to crash in the middle of a test suite run.

9.19

new evaluation code for passed pawns. Crafty now gives a large bonus for two or more connected passed pawns, once they reach the sixth rank, when the opponent has less than a queen remaining. this will probably be tuned as experience produces the special cases that "break" it. such things as the king too far away or the amount of enemy material left might be used to further im- prove the evaluation.

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 two bits. iterate now increments a counter modulo 3, and this counter is stored in the two 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 beginning of a search) to set the age bit. much faster in blitz games as stepping through the trans/ref table, entry by entry, would blow out cache. this idea was borrowed from Cray Blitz, which used this same technique for many years.

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.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.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 Swap()) 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.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.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.12

optimizations: history.c, other minor modifications.

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. RepetitionCheck() 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.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.

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

"vestigial code" (left over from who-knows-when) rmoved 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.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 has 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.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.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.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.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.

. . . . . . . . .