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

MadChess 2.0 Beta Build 032 (King Safety)

  By

I added king safety evaluation to MadChess 2.0 Beta. Defects in king protection (missing pawn shield, semi-open files adjacent to king, squares near king attacked by enemy pieces) are counted, then used as an index into a non-linear piece coordination table.

It took me several attempts to calibrate the weights and the non-linear penalty, but eventually I found an improvement. This added 27 Elo to the playing strength of MadChess 2.0 Beta.

MadChess 2.0                   1904 :    800 (+233,=127,-440),  37.1 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (   6,  18,  76),  15.0 :   -190,  12,    0.0
Matheus-2.3                         :    100 (  17,  18,  65),  26.0 :   -165,  12,    0.0
Monarch 1.7                         :    100 (  18,  15,  67),  25.5 :   -142,  13,    0.0
BigLion 2.23w                       :    100 (  29,  16,  55),  37.0 :   -107,  12,    0.0
Faile 1.4                           :    100 (  33,  19,  48),  42.5 :    -96,  10,    0.0
Sharper 0.17                        :    100 (  32,  18,  50),  41.0 :    -87,  12,    0.0
Jabba13032012                       :    100 (  46,   8,  46),  50.0 :    -28,  11,    0.5
Roce 0.0390                         :    100 (  52,  15,  33),  59.5 :    +49,  11,  100.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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
3 Comments

MadChess 2.0 Beta Build 029 (Piece Mobility)

  By

I added piece mobility evaluation to MadChess 2.0 Beta. The candidate moves of each piece are counted (move legality is not tested) and a non-linear bonus is assigned. Pieces with few moves are penalized. Pieces with many moves are awarded. Assigning a non-linear bonus encourages MadChess to develop all of its pieces, as opposed to maximizing the candidate moves of a few pieces. For example, more centipawns are awarded for increasing the candidate moves of a knight from three to six moves than for increasing the candidate moves of a queen from 14 to 20.

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

MadChess 2.0                   1877 :    800 (+208,=134,-458),  34.4 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  13,  17,  70),  21.5 :   -204,  12,    0.0
Matheus-2.3                         :    100 (  12,  22,  66),  23.0 :   -186,  13,    0.0
Monarch 1.7                         :    100 (  31,  10,  59),  36.0 :   -151,  13,    0.0
BigLion 2.23w                       :    100 (  30,  15,  55),  37.5 :   -127,  12,    0.0
Faile 1.4                           :    100 (  17,  29,  54),  31.5 :   -123,  11,    0.0
Sharper 0.17                        :    100 (  43,   9,  48),  47.5 :   -104,  12,    0.0
Jabba13032012                       :    100 (  35,  11,  54),  40.5 :    -55,  11,    0.0
Roce 0.0390                         :    100 (  27,  21,  52),  37.5 :    +16,  10,   94.1
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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
2 Comments

MadChess 2.0 Beta Build 027 (Draw By Repetition Bug)

  By

Yes! I found and exterminated the bug I mentioned in my previous post.

I corrected a bug that caused MadChess to play a losing move in a drawn by repetition position. MadChess evaluates the first repetition of a position as drawn, even though the rules of chess state the second repetition is drawn. This search optimization avoids wasting a ply to determine the position is drawn by repetition.

MadChess’ recursive search method checks if a position is repeated before searching any moves. If the position is a repeat of an earlier position, the search returns a zero score.

I forgot to prevent MadChess from considering the root position as drawn. If the root position was drawn, the game would be over and MadChess would have nothing to search. It’s not legally drawn. MadChess considers it drawn due to a search optimization. Because MadChess considers the root position drawn, it does not search any root moves. The score of each root move remains -Score.Max, which represents the nonsensical mate in zero I mentioned in my previous post. Because each move is considered equal, essentially a random move is played. Since many drawn by repetition positions are dependent on a single move that holds the draw, this bug often caused MadChess to play a losing move.

The bug fix was trivial.

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

MadChess 2.0                   1813 :    800 (+161,=104,-535),  26.6 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  10,  11,  79),  15.5 :   -270,  13,    0.0
Matheus-2.3                         :    100 (  10,   7,  83),  13.5 :   -256,  13,    0.0
Monarch 1.7                         :    100 (  13,  13,  74),  19.5 :   -226,  14,    0.0
BigLion 2.23w                       :    100 (  27,   7,  66),  30.5 :   -193,  13,    0.0
Faile 1.4                           :    100 (  17,  20,  63),  27.0 :   -187,  12,    0.0
Sharper 0.17                        :    100 (  26,  18,  56),  35.0 :   -173,  13,    0.0
Jabba13032012                       :    100 (  33,  13,  54),  39.5 :   -116,  12,    0.0
Roce 0.0390                         :    100 (  25,  15,  60),  32.5 :    -47,  12,    0.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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