2 Comments

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

  By

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
No comments

MadChess 2.0 Beta Build 038 (Killer Moves)

  By

I added killer moves to MadChess 2.0 Beta. Killer moves are quiet moves (not captures or pawn promotions) that cause a beta cutoff. Two killer moves are saved for each ply. They are searched immediately after captures and pawn promotions.

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

MadChess 2.0                   2065 :    800 (+396,=136,-268),  58.0 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  36,  21,  43),  46.5 :    -26,  11,    0.8
Matheus-2.3                         :    100 (  40,  20,  40),  50.0 :     -7,  11,   27.3
Monarch 1.7                         :    100 (  38,  19,  43),  47.5 :    +14,  11,   90.3
BigLion 2.23w                       :    100 (  49,  15,  36),  56.5 :    +44,  12,  100.0
Sharper 0.17                        :    100 (  61,   5,  34),  63.5 :    +60,  11,  100.0
Faile 1.4                           :    100 (  52,  23,  25),  63.5 :    +85,  11,  100.0
Jabba13032012                       :    100 (  62,  14,  24),  69.0 :   +117,  11,  100.0
Roce 0.0390                         :    100 (  58,  19,  23),  67.5 :   +182,  11,  100.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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
No comments

Banks 50th Amateur Series Division 7

  By

MadChess 1.4 participated in Graham Banks’ 50th amateur tournament in division 7.

                                  1    2    3    4    5    6    7    8    9    0    1    2    
1   Gibbon 2.60a 64-bit           **** 0001 0½½0 1½1½ 1½01 ½01½ 011½ 1111 ½111 1110 ½111 1½½1  29.0/44
2   FireFly 2.7.0 64-bit          1110 **** 0011 0½½½ ½0½1 01½½ 1111 101½ 1011 ½111 0½1½ 1½10  28.0/44
3   Fischerle 0.9.60 64-bit       1½½1 1100 **** ½1½½ ½0½1 1010 1010 ½110 ½011 ½00½ ½101 11½1  25.5/44  551.50
4   Orion 0.2 64-bit              0½0½ 1½½½ ½0½½ **** 01½0 0110 0½½0 ½½1½ 1011 1½1½ 11½1 1111  25.5/44  517.25
5   EveAnn 1.71a                  0½10 ½1½0 ½1½0 10½1 **** 011½ ½111 1101 1½0½ 00½1 ½½½½ 0½11  25.0/44
6   MadChess 1.4 64-bit           ½10½ 10½½ 0101 1001 100½ **** 1½00 1½1½ 0½11 1½½1 1½½½ 10½0  23.5/44
7   Carballo 0.8                  100½ 0000 0101 1½½1 ½000 0½11 **** ½01½ 1½½½ ½½01 0110 ½½01  20.0/44  426.75
8   MangoPaolaAjedrez 4.1         0000 010½ ½001 ½½0½ 0010 0½0½ ½10½ **** 11½1 001½ ½½11 111½  20.0/44  400.75
9   Absolute Zero 2.4.0.0 64-bit  ½000 0100 ½100 0100 0½1½ 1½00 0½½½ 00½0 **** 1½11 1½1½ 0111  19.0/44
10  Protej 0.5.8c                 0001 ½000 ½11½ 0½0½ 11½0 0½½0 ½½10 110½ 0½00 **** ½010 ½100  17.0/44  377.75
11  Exacto 0.e 64-bit             ½000 1½0½ ½010 00½0 ½½½½ 0½½½ 1001 ½½00 0½0½ ½101 **** 110½  17.0/44  364.50
12  NGplay 9.86 64-bit            0½½0 0½01 00½0 0000 1½00 01½1 ½½10 000½ 1000 ½011 001½ ****  14.5/44

Games

No comments

MadChess 2.0 Beta Build 037 (Futility Pruning)

  By

I added futility pruning to MadChess 2.0 Beta. In the main search, for non-capture moves, if the static score plus the futility margin is less than alpha, the move is considered too weak and is skipped. In the quiescence search, for capture moves, if the static score plus the material value of the captured piece plus the futility margin is less than alpha, the move is considered too weak and is skipped. The futility margin depends on the distance to the horizon, and is subject to other constraints, illustrated in the code below.

To Horizon Futility Margin (centipawns)
<1 (Quiescence Search) 100
1 150
2 250
3 400
4 600
>4 Not Futile

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

MadChess 2.0                   2004 :    800 (+322,=144,-334),  49.3 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  18,  18,  64),  27.0 :    -98,  12,    0.0
Matheus-2.3                         :    100 (  28,  17,  55),  36.5 :    -75,  11,    0.0
Monarch 1.7                         :    100 (  26,  16,  58),  34.0 :    -54,  13,    0.0
BigLion 2.23w                       :    100 (  45,  11,  44),  50.5 :    -17,  10,    5.6
Sharper 0.17                        :    100 (  50,  13,  37),  56.5 :     -1,  12,   46.4
Faile 1.4                           :    100 (  42,  32,  26),  58.0 :    +24,  10,   98.8
Jabba13032012                       :    100 (  54,  22,  24),  65.0 :    +58,  11,  100.0
Roce 0.0390                         :    100 (  59,  15,  26),  66.5 :   +123,  11,  100.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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
No comments

MadChess 2.0 Beta Build 034 (Null Move)

  By

I added null move search to MadChess 2.0 Beta. In addition, I limited the quiescence search to recaptures if the distance from the horizon is four or more moves. If the king is in check, all moves are searched. If not, and the distance from the horizon is four or more moves, only recaptures are searched (captures of the last piece that moved).

These enhancements added 46 Elo to the playing strength of MadChess 2.0 Beta.

MadChess 2.0                   1950 :    800 (+271,=150,-379),  43.3 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  23,  20,  57),  33.0 :   -132,  12,    0.0
Matheus-2.3                         :    100 (  27,  17,  56),  35.5 :   -114,  12,    0.0
Monarch 1.7                         :    100 (  22,  17,  61),  30.5 :    -95,  13,    0.0
BigLion 2.23w                       :    100 (  27,  20,  53),  37.0 :    -64,  11,    0.0
Faile 1.4                           :    100 (  36,  27,  37),  49.5 :    -50,  10,    0.0
Sharper 0.17                        :    100 (  46,  15,  39),  53.5 :    -37,  12,    0.1
Jabba13032012                       :    100 (  48,   9,  43),  52.5 :    +16,  11,   92.1
Roce 0.0390                         :    100 (  42,  25,  33),  54.5 :    +90,  11,  100.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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