MadChess 2.0 Beta Build 040 (History Heuristic + Late Move Reductions)

I added a history heuristic and late move reductions to MadChess 2.0 Beta. When a move causes a beta cutoff, the move’s history value is incremented by the distance to the horizon squared. (Distance to the horizon squared is used to prevent moves deep in the search tree from having too much influence over move order.) A history value is saved for each combination of piece type and move destination square. Moves are ordered by their history values descending (after cached best move, capture victim, capture attacker, promoted piece, and killer moves). The search horizon is reduced for moves that appear late in the ordered move list. The later the move, the more the search horizon is reduced. Because the move does not have a history of causing a beta cutoff, it is likely to fail low and less time is spent searching it.

History values are aged (reduced by a percentage) during iterative deepening of the search, to prevent moves from shallow searches from having too much influence over the move order of deeper searches.

In addition, I changed the move representation from unsigned integers to unsigned longs to provide more bits for recording move history values.

This added 50 Elo to the playing strength of MadChess 2.0 Beta.

MadChess 2.0                   2115 :    800 (+305,=170,-325),  48.8 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
Glass 1.6                           :     50 (   3,  10,  37),  16.0 :   -273,  24,    0.0
Capivara LK 0.09a01a                :     50 (   3,  18,  29),  24.0 :   -196,  14,    0.0
Sungorus 1.4                        :     50 (  12,   9,  29),  33.0 :   -195,  11,    0.0
Mediocre v0.34                      :     50 (  14,   7,  29),  35.0 :    -99,  14,    0.0
FireFly v2.6.0                      :     50 (  13,  10,  27),  36.0 :    -93,  13,    0.0
ZCT 0.3.2450                        :     50 (  14,  13,  23),  41.0 :    -86,  15,    0.0
Jazz v444                           :     50 (  11,  12,  27),  34.0 :    -75,  13,    0.0
Wing 2.0                            :     50 (  19,   9,  22),  47.0 :     -6,  13,   32.2
BikJump v2.01                       :     50 (  20,   6,  24),  46.0 :    +18,  14,   89.2
Matheus-2.3                         :     50 (  19,  14,  17),  52.0 :    +37,  13,   99.7
Monarch 1.7                         :     50 (  20,   8,  22),  48.0 :    +60,  13,  100.0
BigLion 2.23w                       :     50 (  24,  17,   9),  65.0 :    +92,  12,  100.0
Sharper 0.17                        :     50 (  39,   4,   7),  82.0 :   +110,  12,  100.0
Faile 1.4                           :     50 (  29,  16,   5),  74.0 :   +135,  11,  100.0
Jabba13032012                       :     50 (  30,  10,  10),  70.0 :   +162,  13,  100.0
Roce 0.0390                         :     50 (  35,   7,   8),  77.0 :   +233,  12,  100.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
History Heuristic
Late Move Reductions
Search 2015 Jan 04 40 275 2115 +50
Killer Moves Search 2015 Jan 03 38 275 2065 +61
Futility Pruning Search 2014 Dec 29 37 256 2004 +54
Null Move
Quiescence Recaptures
Search 2014 Dec 28 34 242 1950 +46
King Safety Evaluation 2014 Dec 24 32 225 1904 +27
Piece Mobility Evaluation 2014 Dec 16 29 225 1877 +64
Draw By Repetition Bug Evaluation 2014 Dec 10 27 225 1813 +47
Passed Pawns Evaluation 2014 Dec 09 26 225 1766 +72
Time Management Search 2014 Dec 08 25 231 1694 +24
Delay Move Generation
Aspiration Window Bug
Search 2014 Dec 02 23 231 1670 +44
MVV / LVA Move Order
Draw By Insufficient Material
Move List Overflow Bug
Search 2014 Dec 01 22 235 1626 +30
Tapered Evaluation
MG and EG Piece Location
Evaluation 2014 Nov 29 21 234 1596 +107
Alpha / Beta Negamax
Aspiration Windows
Quiescence, Hash
Material, Piece Squares
Baseline 2014 Nov 25 20 236 1489
  1. Subversion source code revision
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move
Bookmark the permalink.

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *