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 | – |
- Subversion source code revision
- Win At Chess position test, 3 seconds per position
- Bullet chess, 2 min / game + 1 sec / move
Why is Madchess 2.0 beta http://www.madchess.net/2015/01/04/madchess-2-0-beta-build-40-history-heuristic-late-move-reductions/ not available on the download site http://www.madchess.net/downloads/ ?
I was interrupted while I was moving the website to a new blogging platform (work got busy). I am working on the website this weekend.