Wasp Release Notes

Author: John Stanback

License: This chess engine is free for anyone to use.

Executable files:
  wasp300-x64-modern.exe  : 64-bit Windows for Intel Haswell or newer CPU
                            (uses popcnt, ctz, clz instructions)
  wasp300-x64.exe         : 64-bit Windows for Intel Nehalem or newer CPU
                            (uses popcnt, bsf, bsr instructions)
  wasp300-x64-ancient.exe : 64-bit Windows for older CPU's
                            (uses software popcnt, ctz, clz)
  wasp300-x32.exe         : 32-bit Windows
  wasp300-linux           : 64-bit linux for Intel Nehalem or newer CPU

Wasp 3.0: May 10, 2018
 - added "wasp.rc" runtime configuration file to allow users to modify
   some search and evaluation parameters
 - added "-bench" command-line option.
     bench nodes = 40907656
     bench speed = 1665 Knps on i5-4690K at 3.9 Ghz
                   1542 Knps on Ryzen7-1700 at 3.7 Ghz
 - modified lazy SMP. slave threads skip an iteration if
   2/3 of total threads are already searching at that iteration
 - limit search extension for safe checks and pawn to 7th to
   pv nodes or for depth <= 8.
 - combined razor and futility pruning -- at low depth, if eval is
   well below alpha prune if qsearch cannot bring score near alpha,
   otherwise search using normal lmp rules
 - allow cutoff from hash table at pv nodes if hash depth >= depth+2
 - reduced minimum aspiration window at root from 24cp to 15cp
 - allow search to play moves which have unresolved fail-high when the
   (extended) time limit is reached
 - added static null-move pruning for depth <= 2 and eval >= beta+25cp
   if enemy has no capture good enough to prevent cutoff (sort of similar
   to Senpai).
 - added ProbCut pruning for depth >= 4 and static eval >= beta.
   safe captures are searched to depth-3 and node is pruned if score >= beta+100
 - tweaked lmp and lmr formulas
 - modified hash replacement strategy slightly
 - improved candidate passed pawn evaluation
 - tweaked king safety algorithm
 - tweaked many evaluation function parameters
 - simplified code in quite a few places
 
Wasp 2.60: Nov 21, 2017
 - added UCI option MultiPV
 - added UCI output for hashfull, currmove, currmovenumber
 - added "easy" move to save time when only one legal move or
   capture that appears to be much better than any other move
 - modified king safety evaluation
 - tuned piece values, piece square tables and many other eval parameters 
 - tweaked lmp and lmr rules and formula
 - search speedup for positions with lots of mate positions by
   enabling hash cutoffs for mate scores regardless of depth searched 
 - modified time management routine
 - modified lazy SMP implementation to designate the first thread as
   the "master" thread which updates the PV and score. other threads
   do iterative deepening loop on root position, but skip an iteration
   if more than half the threads are already searching that iteration.
   if master thread completes an iteration and another thread has a
   different move with better score it will redo that iteration hoping to
   pick up the better move quickly due to many hash table cutoffs.

Wasp 2.01: May 3, 2017
  - fixed bug when pondering and search times out (usually due to mate score)
  - fixed typo in blocked passed pawn penalty
  
Wasp 2.00: April 18, 2017
  - added multi-threading using very lazy SMP approach where each
    thread simply does an iterative deepening loop on the root
    position and the only communication between threads is the shared
    main hash table. as others have found, this works surprisingly well.
  - modified futility pruning, late-move pruning, and late-move reduction
    formulas to increase selectivity and reduce effective branching
    factor slightly
  - simplified extensions-- extend safe checks, safe pawn to 7th, and capture
    of last enemy piece by one ply. 
  - tweaked many evaluation parameters
  - move generator now has 3 stages where moves are generated & searched:
      1. hash move, 2. captures/promotions, 3. quiet moves

Wasp 1.25: Sep 29, 2016
  - compiled using new version of gcc (6.1.0)
	- generate and try hash move (if any) before generating all other moves
	- slight change to history table updating
	- slight change to pruning in quiescence search
	- allow late move pruning and reduction for unsafe checks
	- changed late move pruning:
   	 prune non-tactical moves after 1+3*depth moves have been tried
		 prune if moves_searched >= 3 and eval < alpha-100*depth (futility pruning)
	- changed late move reduction to reduce by 3 plies if depth >= 6 and
	  moves_searched >= 40 - 2*depth
	- minor tweaks to most evaluation parameters such as piece values,
   	mobility, king safety, passed pawns ...
  - added term for king mobility in endgame
  - removed special KRPKR evaluation function
	- modified draw adjustment calculation

Wasp 1.02: July 1, 2016
   fixed bug with sudden-death time control when no "ucinewgame" received
	 compiled 32-bit version for older architecture (use -march=athlon-xp)
                   
Wasp 1.01: June 21, 2016, Initial release.


****************************************************************************
Here is a bit of info about Wasp
John Stanback, updated 20180419


The following Windows compiles are supplied:
  wasp280-x64-modern.exe  : for CPU's with popcnt and ctlz/cttz instructions (haswell)
  wasp280-x64.exe         : for CPU's with popcnt and bsf/bsr instructions (nehalem)
  wasp280-x64-ancient.exe : for older 64 bit CPU's
  wasp280-x32.exe         : for 32 bit CPU's
  
The UCI options are:
  Hash   = N Mbytes          default is 64, max is 8192
  Ponder = true/false        default is true
  MultiPV = N                default is 1
  Clear Hash
  Communication Overhead = N ms   default is 25
  OwnBook = true/false       default is false
	Log    = true/false        default is false

  
Wasp is a chess engine which uses the UCI protocol. It is a complete 
rewrite of my previous chess engine called Zarkov. Although some search 
and evaluation ideas are similar, most things have been improved.  While 
Wasp is at least 300 ELO better than any versions of Zarkov it is much
weaker than the current top programs.  Although I've been doing chess
programming for about 40 years, I obviously still have a lot to learn!
The search and evaluation concepts used in Wasp are not unique,
but the implementation is original, giving Wasp it's own "personality".

Wasp supports multi-threading (up to 64 threads) and large hash
tables (up to 8192 Mbyte).  It does not use endgame tablebases other than
a built-in KPK table that is created when the program starts.  Bitboards 
are used for move generation, attacks, and evaluation. The Bitboard
implementation is simple with no magic or rotated bitboards.  

Wasp uses a standard alpha-beta search framework with PVS and aspiration
window.  A quiescence search is used for depth <= 0 unless the side to
move is in check in which case the main search routine is used.
The hash table is used only for the main search, not for quiescence,
and is not cleared between moves.  To improve move ordering, if no hash move is
available, internal iterative deepening is done with R=3 for PV nodes and R=4 for
non-PV nodes.

Wasp generates and tries moves in stages to save time when a cutoff occurs.
Moves are generated and tried in the following order:
  1. hash move or iid_move (if available)
  2. captures and promotions, sorted in MVV-LVA order
  3. pawn to 7th rank
  4. quiet moves, sorted by killer and history score

Unsafe tactical moves are not tried in stages 1-3, but deferred until stage 4
after killers and moves with good history have been tried.

To detect whether moves are safe, Wasp uses a recursive swapoff
routine (a very simple alpha-beta search on a single square) to determine
the expected gain or loss for a move.

Wasp extends the search depth by one ply for safe checks, pawn to 7th, and
captures of the last remaining enemy piece. The extension is limited to
2 plies except at PV nodes or for depth <= 4.  Wasp also extends
captures and moves at PV nodes by 1/10 ply.

I have not yet been able to get improvements when trying various singular
extension methods. 

Wasp has an effective branching factor of about 1.75 which is achieved using
the selective search methods listed below.
 
1. Cut Node Pruning (CNP) is done at expected CUT nodes which are likely
   to fail high. This is similar to the forward pruning used in all versions
   of Zarkov, except that Zarkov pruned at depth 1 and reduced the search
   depth by one ply at depths 2-5.
   The primary conditions used for CNP are:
     depth <= 3
     eval >= beta+margin    (margin = MAX(hung_material/2,75*depth)
     !in_check
     !mate_or_promotion threat
     !pawn_ending

2. If CNP does not give a cutoff, Static Null Move pruning is tried.  The conditions
   are the same as for CNP except that the margin becomes either 25 centipawns or
   the swapoff value of the best safe capture the enemy could make plus 100 centipawns. 
     
3. Null move pruning is done at expected CUT nodes with these conditions:
  	 depth >= 3
  	 eval >= beta
     !in_check
     !pawn_ending
   For the null move search, depth is reduced by 3 plies for depth < 8,
   otherwise 4 plies.  If the null move fails high and depth >= 5, a
   verification search with depth reduced by 4 plies is done.
  
4. Futility pruning is done at non-PV nodes and low depth when eval < alpha-margin
   (margin = 100+100*depth).  For these nodes the move generator only generates
   captures, checks, promotions, and pawn to 7th.  Quiet moves are not generated
   or searched.
   
5. Late move pruning is done at non-PV nodes.
   The conditions are: 
	   depth <= 4
     moves_searched >= 1+3*depth
     !in_check
     !pv_node
     !tactical      (capture,check,promotion,pawn to 6th or 7th)
     !move_gives_check
     !move_is_safe_attack_to_bigger_piece
 
6. Late move reduction is done with these conditions:
	   depth >= 3
     moves_searched >= 1
     !in_check
   The depth reduction varies from 0 to 3 plies and is a function of depth and
   #moves already searched.  Tactical moves such as captures, checks, promotions,
   and pawn to 7th rank are not reduced at PV nodes and the reduction is limited
   to one ply at non_PV nodes.  PV nodes get about one ply less reduction than
   non-PV nodes.  I've tried more aggressive LMR, but for Wasp the size of the
   search tree is not reduced enough to warrant the additional risk.
	
Wasp has a rather simple evaluation function, but includes the terms that
are of highest importance. A small evaluation hash table of 16K positions
and a small pawn hash table of 8K positions are used to save time.  Each thread
has its own Eval and Pawn hash tables.  The hit rate for the eval hash table is
about 15-25% and the hit rate for the pawn hash table is over 95% on average.
The evaluation function uses units of centipawns.  

The values for material in opening/ending are:
  pawn   =       80 /  102
  knight =      335 /  325
  bishop =      335 /  330
  rook   =      470 /  550
  queen  =     1000 / 1080
  bishop_pair =  35 /   35
  
Passed pawn evaluation depends on the pawn rank, whether it can safely 
advance one or more squares, friendly and enemy king proximity to the
square in front, whether it is blocked, and whether the enemy king is in
the square of pawn. The bonus for a pawn on the 7th rank can range
from about 80 to 250 centipawns.

Pawn evaluation terms include Piece-Square tables (PST), penalties for
doubled, isolated, backward, and weak pawns, and a bonus for candidate
pawns. 

Knight evaluation includes only PST, mobility, and outpost bonus and
the total value typically falls between about -25 and +25 centipawns.
  
Bishop evaluation includes only PST, mobility, outpost bonus, and a
penalty if trapped on squares a7, b8, h7, g8 (mirrored for black). The
evaluation is generally between about -15 and +30 centipawns.

Rook evaluation includes only PST, mobility, open/half-open file bonus,
7th rank bonus, and trapped penalty.  The rook eval typically falls
within a range from about -30 to +50 centipawns.

Queen evaluation includes only PST, mobility, and 7th rank bonus and
the value typically falls between about -15 to +25 centipawns.
 
King evaluation includes PST, king safety, mobility and distance to
pawns in endgame.  The king safety eval is fairly complex, taking into
account the number and type of enemy pieces attacking nearby squares,
pieces defending each attacked square, friendly pawn shield, and safe
checks by the enemy. The king safety term ranges from about +100 to
over -300 centipawns.
  
Wasp assigns a penalty for hung and/or pinned pieces.

Wasp assigns a draw value to very simple endgames such as KK, KBK, KNK,
KBKN, and KNNK.  The only special endgame functions are for KBNK and
a mopup function when one side has major pieces and the other side has
only a king. 

Wasp multiplies the evaluation by a scale factor from 0.0 to 1.0 to
scale the evaluation for drawish endings such as when the winning side has
a minor or less advantage and no pawns or where the losing side can
capture the last pawn with a minor, and endings with bishops of opposite color.

I've tried tuning evaluation function parameters using very large numbers 
of super-fast or fixed depth games but without much success.  I periodically
use the "Texel" parameter tuning method where the average error between a
quiescence search score (adjusted to a range of 0..1 using sigmoid function)
and the game result (either 0.0, 0.5, or 1.0) is minimized over a large set
of positions. I used a few sets of about 2M positions each taken from
ultra-blitz games between Wasp and several other engines.  My preferred method
for optimization is to use a binary search to find the optimum value for each
parameter (with all other parameters fixed at the best-known value), then
manually change a few parameters part-way toward their optimum value, and
repeat the procedure.

To determine with some degree of confidence whether changes to the engine
are beneficial to playing strength I run ultra-blitz matches against a
handful of other engines. I usually run a match of 4000-10000 games at
Game/5s + 0.080s and if the results are decent I run a match of 10000+ games
at Game/15s + 0.280s.  I have two Ryzen7-1700 computers, but it still takes
a long time.  And most changes are rejected...
 
Thanks very much to Frank Quisinsky for hosting Wasp on his web site and for
testing Wasp against a large number of chess engines at a more rational time
control than I usually use.
 
