Wasp
Author: John Stanback

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

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.

Wasp is a new 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 37 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".
 
The UCI options are:
  Hash   = N            where N is amount of memory in MB for main hash table
  Ponder = true/false   default is true
	Log    = true/false   default is false

  
Here is a bit of info about Wasp.

Wasp is single-threaded and 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 is 
compiled for modern 64 bit CPU's with popcnt and bitscan instructions.

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.  A hash table is used in both the main and the
quiescence searches and is not cleared between moves.  To improve move
ordering, if no hash move is available, internal iterative deepening with
R=3 for PV nodes and R=4 for other nodes is done.

Moves are ordered as follows:
  hash move
  iid_move
  good captures in MVV-LVA order
  queen promotions
  3 killer moves
  moves with OK history score
  bad captures
  and remaining moves

For move ordering and futility pruning 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 by one ply when in check or if the last move was
pawn to 7th rank and remaining depth is low.  It extends captures and PV
nodes by 1/8 ply each for the first 10 moves from the root.

Wasp has an effective branching factor of about 2:1 which is achieved using
the selective search methods listed below.
 
1. Razor pruning is done at expected ALL nodes which are thought likely to
   fail low.  The primary conditions used for razoring are:
     depth <= 2 &&
     eval <= alpha-margin &&
     qsearch_score <= alpha
	 where margin is 175 for depth 1 and 250 for depth 2.	 

2. Early Stand-Pat pruning (beta pruning) is done at expected CUT nodes
   which are thought likely to fail high. This is similar to forward pruning
   that was used in all versions of Zarkov, except that Zarkov reduced the
   search depth for depths 2-5 by one ply instead of simply pruning the node.
   The primary conditions used for ESPP are:
     depth <= 4 &&
     eval >= beta+margin &&
     !in_check &&
     !mate_threat &&
     !promotion_threat
     !pawn_ending
   where margin = MAX(hung_material/2,50*depth).
	
3. Null move pruning (R=3) is done at expected CUT nodes in the hopes
   that the reduced depth search will fail high and produce a quick cutoff.
   The conditions for NMP are:
  	 depth >= 3 &&
  	 eval >= beta &&
     !pawn_ending
	 If the null move fails high and depth >= 5, a verification search with 
   depth reduced by 4 plies is done.
  
4. Late move / futility pruning is done at non-PV nodes.
   The conditions are: 
	   depth <= 4 &&
     moves_searched >= 3 &&
     !in_check &&
     !move_gives_check &&
     !move_is_capture &&
     !move_is_safe_pawn_push_to_6th_or_beyond &&
     !move_is_safe_attack_to_bigger_piece &&
     !move_is_safe_attack_near_enemy_king &&
     eval <= alpha-margin
   where margin = 128*depth - 32*moves_searched

5. Late move reduction is done with these conditions:
	   depth >= 4 &&
     moves_searched >= 3 &&
     !in_check &&
     !move_gives_check &&
     !move_is_capture &&
     !move_is_safe_pawn_push_to_6th_or_beyond &&
     !move_is_safe_attack_to_bigger_piece &&
     !move_is_safe_attack_near_enemy_king
   The depth reduction is one ply for PV nodes or if moves_searched <= 6.
   Otherwise the reduction is two plies.  I've tried larger reductions,
   but the size of the search tree was 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.
The hit rate for the eval hash table is about 15% and the hit rate for
the pawn hash table is over 95% on average.  Wasp differs from Zarkov in
that it does not use lazy evaluation.  The evaluation function uses
units of centipawns.  

The values for material in opening/ending are:
  pawn   =       85 /  100
  knight =      335 /  320
  bishop =      335 /  325
  rook   =      465 /  535
  queen  =      975 / 1035
  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 typically ranges
from about 90 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.  These terms are all pretty small.

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 -30 and +30 centipawns.

Rook evaluation includes only PST, mobility, open/half-open file bonus,
7th rank bonus, and trapped penalty and typicall falls withing a range
from about -30 to +60 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, distance to pawns in endgame,
and trapped penalty.  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, enemy
pawns on nearby files, and available checks. The king safety term ranges
from about 0 to -300 centipawns.  The endgame PST is pretty important and
the values range from about -35 in the corner to +35 cp in the center.

Wasp assigns a penalty of 12 centipawns for each hung or pinned
piece and and extra penalty of about 24 centipawns for multiple hung
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 KRPKR. 

Wasp multiplies the evaluation by a "draw factor" from 0.0 to 1.0 to
scale the evaluation for drawish endings such as pawnless endings where
the winning side has a minor or less advantage, bishops of opposite color,
pawns only on a or h files with wrong color bishop, and endings where
the losing side can trade a minor piece for the last enemy pawn.

I've tried tuning evaluation function parameters using very large numbers 
of super-fast games but without much success.  However I did gain some 
improvement (probably about 30 ELO) by tuning parameters using the "Texel" 
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 use a 
binary search to find the optimum value for each parameter (with all other 
parameters fixed at the best-known value), then manually changing a few 
parameters part-way toward their optimum value, and repeating the
procedure. I don't change a parameter too far from a value that intuitively
feels right unless the tuning result improves by enough to warrant further
testing using lot of fast games.   

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 use a time control of Game in 15 seconds
with 0.150 second increment and usually get in about 6000 games overnight
using two 4-core computers.  I'm not very diligent and frequently don't run
enough games to statistically verify that a change is actually good.  This
often gets me into trouble, but that's what I deserve for my lack of
patience.
 
Thanks very much to Frank Quisinsky for testing Wasp against a large
number of chess engines at a more rational time control than I usually
use.
 
