Eubos v2.14

Full Changelog: v2.13...v2.14

Features

• Added evaluation for connected passed pawns
• Added full implementation for creating masks of square control, including own piece batteries. In Eubos these are referred to as 'Counted Attack Masks'
• Add evaluation for pawn storm and pawn shields into the king safety algorithm
• Designed and implemented a new method of efficiently finding positions where there is a passed pawn present, used as a parameter in attack mask computation

Tuning / Optimisation / Tweaks

• Revise King Safety evaluation into 3 parts; 1) exposure, 2) vulnerability and 3) mate threat
• Counted attack masks are only used for evaluation of positions where there is a passed pawn present, otherwise use simple attacks mask
• Don't compute lazy evaluation for alpha threshold, it isn't worth the overhead
• Remove prioritisation of pieces attacked by a knight or pawn in the MoveList generation, it isn't worth the overhead
• Increase evalaution contribution of piece mobility - this gave a large improvement in playing strength

Fixes

Quality

• Refactor the lazy evaluation threshold tuning code
• Refactor lazy evaluation into the Position Evaluator class, from the Ply Searcher class
• Refactor the Board class to extract a Mobility and Attacks Evaluator class

Potential Improvements

Eubos v2.13

Full Changelog: v2.12...v2.13

Eubos v2.12

Features

• Added simplified evaluation of candidate passed pawns to the pawn evaluation
• Add bespoke evaluation for KPK endgames (disabled in the release as it is over-simplified)
• Added standard algorithm (from Chess Programming Wiki) for computing the manhattan distance between squares (with intention of using it in KPK endgames for square of pawn evaluation
• Added King Tropism aspects to the bespoke Eubos king safety algorithm using the manhattan distance for Queens and Knights
• Added capability to send just a single best move at a position, rather than a full principal variation

Tuning / Optimisation / Tweaks

• Create a different set of piece material values for the Endgame material evaluation
• Modify the piece material values to disincentivise trading minor pieces for pawns or major pieces for minor pieces plus pawns
• No longer update the PV at a position if we didn't increase alpha, previously Eubos tracked the score at a position from provisional alpha, even when it was outside the current search window.
• Modify move timing computation to assign fewer milliseconds to each time quanta when evaluating the current search progress. This conserves more clock, and reduces per move think time.
• Optimised pawn attack aggregaton out of the per pawn evaluation - it is now just done once for the position
• Modified the traditional Eubos king safety algorithm to not discount attacking bishops on the opposite square colour to our king
• Optimise the check during move generation to see if a move could be illegal because the piece is pinned to the king, now it only considers diagonal/ranke and file attacking sliders if they are present in the position
• Search at least 6 quiet moves before doing LMR
• Increase default LMR to depth/3

Fixes

• Move timing change, if an aspiration window fails, wait for the re-search with a wider window to complete before terminating the search
• No longer assign 'exact' score type when updating the Trasposition Table, as current LMR algorithm means we can't know the true depth searched (it can be reduced multiple times)

Quality

• Added various EPD Test Suites as optional unit tests, derived from the Chess Programming Wiki
• Fix up perft tests, which were failing due to not including under promotions in the move generation in Eubos v2.11
• Refactored and simplified the Transposition static class
• Use Eubos internal types in the Search Metrics class, not JCPI package types
• Refactored the Test.Eubos.Main package to extract common code into a base class

Potential Improvements

• Further development of KPK
• Analys the frontspan of passed pawns and account for attacks/piece blocks in the evaluation thereof

Eubos v2.11

Features

• Removed Principal Variation Transposition class and the code surrounding them.

Tuning / Optimisation / Tweaks

• Staged move generation significantly improved, the stages are now:

1. hash move
2. pawn promotions
3. captures
4. killers
5. quiet moves

• Optimised move generation functions to remove any unnecessary local variables, created explicit functions for adding black and white moves
• Don't add under promotions in extended search
• Optimise isPlayable check for simple move pieces (non-sliders)
• Alpha/Beta and some other search variables stored in arrays indexed by ply to optimise search and allow greater function extraction
• Transposition is refactored to a static class based on a primitive long for speed/memory improvements
• Optimised MoveAdders to exclude best/killers before checking move legality
• Optimised MoveAdders by adding under promotions automatically when a queen promotion is encountered
• Optimised MoveAdders by ensuring the attacked piece mask is only generated once for each position, not for each piece at that position

Fixes

• Bug fix for an error in correctly determining whether an en passant move is playable. This caused issues in synchronisation between piece lists and bitboards where an en pasant capture was the best move in a position.
• A castling move could be determined as playable, even if the king was in check. This caused illegal move errors following from defective best and killer move stages of the staged move generation.

Quality

• Added isPresent check in the asserts enabled build to find errors in the synchronisation of piece list and bitboards
• Added more sophisticated exception handling for OutOfMemory Exceptions, including back-off to small hash tables if out of mem
• Various functions extracted from PlySearcher, for example a common Transposition Evaluation function for root, search and extended search is now used
• Refactored perft and unit tests to use staged move generation
• Log exception failures to a file with full stack backtrace and, if in search, move stack unwind

Potential Improvements

Eubos v2.10

Features

• Null Move Pruning added to the search, based on the implementation fromm the Chess Programming Wiki Engine
• Added support for the 'move overhead' UCI configuration option, this is used for Eubos on Lichess
• Added statistics collection for more advanced Lazy Evaluation tuning
• Mate Distance Pruning

Tuning / Optimisation / Tweaks

• Staged move generation implemented for the hash move at non-root and extended search nodes
• Extracted a specific function for the search at the root node
• Now tracks whether the Principal continuation has been fully searched and flags this using a boolean
• Tweaked the lazy evaluation threshold, to produce more evaluation cut-offs
• Use an auto-flushing stream for the UCI protocol output (send direction) to the chess GUI. This reduces time forfeits on Lichess.

Fixes

• Bug fix for en passant hash moves, the en passant flag in the move integer was not getting set from the board state when retrieving from the hash table.

Quality

Potential Improvements

• I would like to more fully utilise the staged move generation. For example it isn't too much work to include promotions as a special case in the move generation.
• I would also like to refactor the staged move generation to use a loop rather than duplicating code in the search functions
• The search node functions need to be optimised, I have some ideas about passing alpha and beta in an array, to help breaking down some function sizes and possibly better utilising hotspot compilation.

Eubos v2.9

Features

• This is the first Eubos release which incorporates a selective search. All previous releases have been Shannon type-A searches, only utilising Beta pruning
• Added Late Move Reductions to the PlySearcher
• After the first 6 moves at any ply deeper than 3, the search depth can be reduced by depth/4
• There are the usual exemptions

Tuning / Optimisation / Tweaks

• DrawChecker is now expanded as the game progresses

Fixes

• Bug fixed where, if the game length exceeded 150 moves, the DrawChecker would cause a crash

Eubos v2.8

Features

• Aspiration window is now progressively widened on a failure; as per 25 centipawn; 2 pawns; 1 rook, fully open window.
• Attribute a 25 centipawn bonus for the bishop pair in the evaluation function.
• Lazy evaluation; try to optimise by avoiding performing a full evaluation if the crude evaluation score is outside a threshold of alpha/beta. This threshold was empirically derived at 350 centipawns, assessed by sampling the delta between full and crude evaluations during play and post-processing the logs.
• Passed pawn scoring in the evaluation function is now weighted by game phase. That is, when deep in the endgame, then passed pawns are subject to a multiplier. The thresholds for increasing the multiplication are when we reach KQ endgames and KB, KN endgames respectively.

Tuning / Optimisation / Tweaks

• Pieces attacked by a knight, king or pawn are now sequenced in the MoveList at the start of the quiet/regular moves.
• When assessing whether a valid capture exists in a position (required for alpha lazy evaluation check), check knight, king or pawn atacks first, as these are low hanging fruit.
• Changed passed pawn scoring to 12/8 centipawns, for regular/rook pawns accordingly.
• IsAttacked method refactored to improve likelihood of early termination.
• Optimised the Piece static class
• Optimised the Move static class

Fixes

• Bug fix for potential corruption of the previous best move retrieved from the last principal continuation. This could occur at non-PV nodes for which there was no hash move. The defect was caused by assuming the move was valid in the position - it often wouldn't be, as its validity is inherently path dependent - and trying to populate the origin piece and target piece from the board, regardless of validity.
• Fixed a time management defect which could cause flags in high depth searches when clock time is low. Because we try to increase the previous reference score at each ply, in a high-depth search, when we don't have good hash information, the search time could exceed the sample rate at which we try to stop the search, causing Eubos to flag.

Quality

• Moved to JUnit 5 for unit test framework
• Tightened assertions in ENABLE_ASSERTS builds, particularly regarding move encoding (Move.valueOf and friends)

Potential Improvements

• The empirically-derived lazy valuation threshold could be self-monitored by Eubos in a debug mode (i.e. when a static const is set). This debug mode would compute the delta at each leaf and maintain statistics like the leaf count, the number of times it was outside the threshold, the min/max delta and the number of times we saved a full evaluation hit. These could then be reported in the log.

Full Changelog: v2.7...V2.8

Eubos v2.7

Features

• Introduce tapered evaluation, based on the version from the Fruit engine (from Chess Programming Wiki), but with optimisation for unsigned 16 bit width scores (to aid incremental udates).
• Introduce dynamic tracking of game phase through the search. Previously this was just a static boolean flag indicating whehter we were in an endgame or not (based on material assessment on the FEN position received from the GUI at the start of search).
• Differentiated piece square tables for rooks and pawns depending on game phase. For example, in the opening centralise the rooks on the D and E files, and avoid a2, h2, a7, h7 squares. Incentivise rooks on 7th rank. For pawns, don't over extend in the opening. Don't push wing pawns.
• Incrementally update game phase.

Tuning / Optimisation / Tweaks

• Bug fix so that the MoveList class, which was modified to use static memory allocation for each ply level (as opposed to dumb dynamic allocation) in version 2.5, works corrently in multithreaded searches. Each worker thread has their own instance ofthe MoveList class, it is no longer static.
• Reduced default size of transposition table from 4000 to 256 MBytes.
• Aspiration window tightened to 25 from 50 centipawns.
• Refactor the MoveList class to include a MoveAdder interface. This allows different (and optimised) functions to be used for adding quiescent/extended and normal search node moves to the MoveList.
• Change the order of move insertion for quiet moves into the MoveList. Use the static order of Pawn moves ahead of Queen moves in the endgame, for example. In the middlegame add queen moves after bishop and knight moves.
• Do piece mobility calculation even in the endgame. Previously this wasn't done to aid mate search. Ihave now introduced an explicit mate search mode for when one side has only King on the board.
• Tweaked time management to use more clock in positions when losing.
• Significant optimisations and simplification to creation of the MoveList at each ply.

Fixes

• Bug fix for cloning the DrawChecker, which is needed for multi-threaded mode.
• Bug fix for situations where we would not use the hash move as the best move in the Move List if a path dependent three fold repetition occured whilst performing the search. We should still use this move if no better information is present (for example if the previous principal continuation is not set).

Quality

• Removed various obsolete classes (e.g. Search Context) and refactored for removal of the isEndgame flag.

Potential Improvements

• Experimented with incorporating opposing side pawn and knight attacks when computing piece mobility. Although this seems to be a logical improvement to merely counting squares available for movement, in testing I found this regressed playing strength. Perhaps this could be revisited later?

Eubos v2.6

The release was pushed forward due to a defect in v2.5. If you tried to use Eubos on a multi-core system, by default it would run as multithreaded. I don't normally test this configuration, and as a result, I had missed that the refactor I did to remove dynamic allocation of Move Lists caused a crash when running with more than one search thread.

I have temporarily removed the capability to run configure or run multithreaded searches.

Apart from that, I have a couple of algorithmic improvements and optimisations:

• Material balance and piece square tables are now incrementally updated
• Lazy evaluation is employed in the opening and middlegame, though only beta refutations are checked at present
• The pseudo-legal move generation has been greatly optimised (yielding a 20% increase in speed!)

Eubos v2.5

This is mainly a release focused on delivering optimisation of the move generation and transposition hashing:

• Reworked 3-fold draw checker to use an array based implementation indexed by ply, as opposed to a hash map keyed by Zobrist hash, this is more efficient.
• Reworked the transposition table to use a primitive open hash set using the fastutils Java package (that is the reason for the increase in the size of the Eubs.jar file). This allows a more efficient linked hash map implementation, where the full hash table can be utilised (previously the hash utilisation varied between 35% to 80% based on the Transposition ageing).
• Reworked the MoveList generation so that static arrays are used instead of dynamically creating and destroying objects at each node of the search.

However there are a few algorithmic changes:

• Dumb7Fill based King Safety evaluation (scored as per the previous algorithm)
• Allow transposition hits that are drawing due to three-fold to cause refutations (previously they were re-searched)