MadChess 3.0 Beta 4478cb8 (Late Move Pruning)

I added late move pruning to MadChess 3.0 Beta. Quiet moves (not captures, pawn promotions, castling, or check) near the search horizon that are sorted near the bottom of the move list- in order words, “late” moves- are skipped. These moves are “late” because history heuristics have recorded few instances of them causing a beta cutoff. Most likely they are futile (they will not raise the score to alpha), so the engine doesn’t waste time searching them.

The search only examines two quiet moves immediately next to the search horizon, five quiet moves two ply from the horizon, up to 20 quiet moves five ply from the horizon. Actually, fewer quiet moves may be examined due to futility pruning conditions.

This code increased the playing strength of MadChess 3.0 Beta by 29 ELO.

 

Feature Category Date Rev1 WAC2 ELO Rating3 Improvement
Late Move Pruning Search 2020 Feb 08 4478cb8 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location
Baseline 2018 Nov 08 58 269 2096 0
  1. GitHub (hash) or Subversion (integer) source code revision
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

MadChess 3.0 Beta 5c5d4fc (Piece Mobility)

I have not worked on my chess engine in over a year. I had other, more important, priorities. In the last year, my wife and I bought a new home closer to the city, sold our old home, moved (*), started new jobs in the summer, and ran the Chicago Marathon in the autumn. The little free time I had for hobby programming I spent on general interest projects, not on MadChess. I’m especially proud of Leaderless Replication, an essay I published on my general programming blog, ErikTheCoder.

Lately I’ve had time to do some chess programming. I added piece mobility evaluation to MadChess 3.0 Beta. This particular evaluation feature really demonstrates the benefits of bitboards over mailbox board representation. I can calculate the mobility of knights, bishops, rooks, and queens essentially for free- that is, with no negative impact on performance. I do not need to generate any moves or scan any piece arrays (along ranks, files, or diagonals). I simply lookup pseudo-legal candidate moves (not checked for move legality, i.e. does move expose own king to check?) via the PrecalculatedMoves class (for sliding pieces) and move bit masks (for knights). Then lookup piece mobility scores in two arrays per piece type (middlegame and endgame) based on the number of moves available to the piece. Each piece mobility array is calculated at engine startup using a non-linear formula. The piece mobility scores are centered so the average number of moves is assigned zero score, less than average is assigned a negative score, and more than average is assigned a positive score. I tuned piece mobility configuration parameters against a database of about 54,000 Grandmaster games using the particle swarm algorithm I discussed in a previous blog post.

The following code calculates a mobility score for each piece on the board. By scoring mobility per piece, and not simply based on the total count of moves per side, the chess engine is encouraged to develop all of its pieces and cramp the position of its opponent.

It references the following code which determines the pseudo-legal candidate moves of each piece on the board, returned as a bit mask (where a 1 indicates a “to” square).

The above code references the following configuration parameters.

I changed source control from a local Subversion repository to a public GitHub repository. So that’s why the version stamp in the title of this post is a hash (used by GitHub) instead of an integer (used by Subversion) seen in my earlier posts about MadChess 3.0 Beta.

This code increased the playing strength of MadChess 3.0 Beta by 62 ELO.

 

Feature Category Date Rev1 WAC2 ELO Rating3 Improvement
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location
Baseline 2018 Nov 08 58 269 2096 0
  1. GitHub (hash) or Subversion (integer) source code revision
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

(*) I know most people consider this one event: moving to a new home. However, because the sale, purchase, and move happened on three separate days over one month; and we had to purchase our new home before selling our old one (causing some anxiety and stress), it felt like three separate events.

Elephant Rides

MadChess 2.2 participated in a special tournament Graham Banks arranged, named Elephant Rides.

Cross table, sorted by score percentage, Buchholz, SB

                                 Detr Jumb Jikc Axol Capi Rook Dork Fran Ghos Cybe Mave MadC  
 1. Detroid 1.0.1 64-bit         #### 0=== 01=1 1==1 1111 1==0 ===0 01=1 01=1 01=0 1=1= 11=1  62%  27.5 (946.0, 580.0)
 2. Jumbo 0.7.0 64-bit           1=== #### 1==1 1=1= 0==0 01=0 111= 00=0 1=== =100 11=1 1111  60%  26.5 (950.0, 555.8)
 3. Jikchess 0.02 64-bit         10=0 0==0 #### 11== 1=0= 1=00 =1=1 111= 0101 11=1 0101 11=0  58%  25.5 (954.0, 541.5)
 4. Axolotl 1.9 64-bit           0==0 0=0= 00== #### 0111 110= 01=0 1=11 11=0 1111 1=00 =011  55%  24.0 (960.0, 507.3)
 5. Capivara LK 0.09b02g 64-bit  0000 1==1 0=1= 1000 #### 10== 01=1 1=01 1011 ==10 1110 =110  53%  23.5 (962.0, 493.8)
 6. RookieMonster 1.6.9 64-bit   0==1 10=1 0=11 001= 01== #### 1011 0000 0101 1=1= 1=01 1=00  51%  22.5 (966.0, 497.3)
 7. Dorky 4.8 64-bit             ===1 000= =0=0 10=1 10=0 0100 #### 010= 1=== 111= =1=1 011=  50%  22.0 (968.0, 463.3)
 8. FrankWalter 2.4.0 64-bit     10=0 11=1 000= 0=00 0=10 1111 101= #### =000 =0=0 1110 1011  49%  21.5 (970.0, 458.5)
 9. Ghost 3.1 64-bit             10=0 0=== 1010 00=1 0100 1010 0=== =111 #### 0010 10=1 1011  48%  21.0 (972.0, 446.0)
10. CyberPagno 3.0 64-bit        10=1 =011 00=0 0000 ==01 0=0= 000= =1=1 1101 #### 11=0 1==1  47%  20.5 (974.0, 436.5)
11. Maverick 0.51 64-bit         0=0= 00=0 1010 0=11 0001 0=10 =0=0 0001 01=0 00=1 #### 1100  35%  15.5 (994.0, 342.8)
12. MadChess 2.2 64-bit          00=0 0000 00=1 =100 =001 0=11 100= 0100 0100 0==0 0011 ####        32%  14.0 (1000.0, 306.5)

Games

Graham Banks 74th Amateur Tournament Division 7

MadChess 2.2 participated in Graham Banks’ 74th Amateur Tournament in Division 7.

Cross table, sorted by score percentage, Buchholz, SB

                                Orio Jumb Dork Rook Fran Bets Lozz Neme Dros MadC Galj Axol 
 1. Orion 0.6 64-bit            #### 1010 0==1 0110 ===1 0101 1==1 101= 111= =11= 1111 ===1  66%  29.0 (940.0, 598.0)
 2. Jumbo 0.6.107 64-bit        0101 #### ==== 1=== 1==1 10=1 1101 0=1= 1101 1101 101= =1=1  65%  28.5 (942.0, 598.0)
 3. Dorky 4.8 64-bit            1==0 ==== #### =110 =11= =11= =10= =101 00== 11== 1=0= 1111  61%  27.0 (948.0, 570.5)
 4. RookieMonster 1.6.7 64-bit  1001 0=== =001 #### 0=10 =111 010= ==10 1=11 11== =1== 1110  58%  25.5 (954.0, 530.3)
 5. FrankWalter 2.4.0 64-bit    ===0 0==0 =00= 1=01 #### 0101 11=0 1=11 =000 =111 =10= =1==  51%  22.5 (966.0, 472.3)
 6. Betsabe II 1.84             1010 01=0 =00= =000 1010 #### 11=1 101= 1101 10=0 1==1 =01=  51%  22.5 (966.0, 471.5)
 7. Lozza 1.18 64-bit           0==0 0010 =01= 101= 00=1 00=0 #### 1==1 1==1 011= 0=1= =0=1  48%  21.0 (972.0, 444.5)
 8. Nemeton 1.81                010= 1=0= =010 ==01 0=00 010= 0==0 #### =11= =0=0 1111 1===  47%  20.5 (974.0, 434.0)
 9. Drosophila 1.5.1 64-bit     000= 0010 11== 0=00 =111 0010 0==0 =00= #### 0111 0=11 01==  43%  19.0 (980.0, 402.0)
10. MadChess 2.2 64-bit         =00= 0010 00== 00== =000 01=1 100= =1=1 1000 #### =101 =011  40%  17.5 (986.0, 367.0)
11. Galjoen 0.39.2 64-bit       0000 010= 0=1= =0== =01= 0==0 1=0= 0000 1=00 =010 #### 1==1  36%  16.0 (992.0, 344.3)
12. Axolotl 1.8 64-bit          ===0 =0=0 0000 0001 =0== =10= =1=0 0=== 10== =100 0==0 ####  34%  15.0 (996.0, 329.3)

Games

Schooner Scourge Versus Arasan Aristocrats (Teams Match)

MadChess 2.2 participated in a special tournament Graham Banks arranged, named Schooner Scourge Versus Arasan Aristocrats (Teams Match).

Cross table, sorted by score percentage, Buchholz, SB

                              Galjoe Arasan RuyDos Horizo Nemori FrankW Ares G France GreKo  Orion  Rookie MadChe Zevra  Pedone Gogobe Isa 2. Schoon Myrddi    
 1. Galjoen 0.39.2 64-bit     ######                                                                                                                 11111=       
                              ######                                                                                                                 0==111          79%   9.5 ( 30.0, 23.8)

 2. Arasan 21.3 64-bit               ######                                                                                                   =111==              
                                     ######                                                                                                   ====11                 71%   8.5 ( 42.0, 29.8)

 3. RuyDos 1.1.9 64-bit                     ######                                                                              ==1=11                            
                                            ######                                                                              1==0==                               62%   7.5 ( 54.0, 33.8)

 4. Horizon 4.4                                    ######                                                                              0=100=                     
                                                   ######                                                                              11111=                        62%   7.5 ( 54.0, 33.8)

 5. Nemorino 5.00 64-bit                                  ######                                                         01====                                   
                                                          ######                                                         110===                                      54%   6.5 ( 66.0, 35.8)

 6. FrankWalter 2.3.5 64-bit                                     ######                                    =1=1=1                                                 
                                                                 ######                                    000==1                                                    54%   6.5 ( 66.0, 35.8)

 7. Ares GB 64-bit                                                      ######                                    =10111                                          
                                                                        ######                                    101000                                             54%   6.5 ( 66.0, 35.8)

 8. Francesca MAD 0.23 64-bit                                                  ###### 1=101=                                                                      
                                                                               ###### 010001                                                                         50%   6.0 ( 72.0, 36.0)

 9. GreKo 2018 64-bit                                                          0=010= ######                                                                      
                                                                               101110 ######                                                                         50%   6.0 ( 72.0, 36.0)

10. Orion 0.5 64-bit                                                                         ###### 010001                                                        
                                                                                             ###### 1=01=1                                                           50%   6.0 ( 72.0, 36.0)

11. RookieMonster 1.6.6 64-bit                                                                101110 ######                                                        
                                                                                             0=10=0 ######                                                           50%   6.0 ( 72.0, 36.0)

12. MadChess 2.2 64-bit                                          =0=0=0                                    ######                                                 
                                                                 111==0                                    ######                                                    46%   5.5 ( 78.0, 35.8)

13. Zevra 2.1.1 r216 64-bit                                             =01000                                    ######                                          
                                                                        010111                                    ######                                             46%   5.5 ( 78.0, 35.8)

14. Pedone 1.9 64-bit                                     10====                                                         ######                                   
                                                          001===                                                         ######                                      46%   5.5 ( 78.0, 35.8)

15. Gogobello 2.0 64-bit                    ==0=00                                                                              ######                            
                                            0==1==                                                                              ######                               37%   4.5 ( 90.0, 33.8)

16. Isa 2.0.64 64-bit                              1=011=                                                                              ######                     
                                                   00000=                                                                              ######                        37%   4.5 ( 90.0, 33.8)

17. Schooner 2.0.34 64-bit           =000==                                                                                                   ######              
                                     ====00                                                                                                   ######                 29%   3.5 (102.0, 29.8)

18. Myrddin 0.87 64-bit       00000=                                                                                                                 ######       
                              1==000                                                                                                                 ######          21%   2.5 (114.0, 23.8)

Games