MadChess

I increased the playing strength of MadChess 3.0 by improving the history heuristics used by Late Move Reductions (LMR).

First, I added a flag that indicates if a move was played during search (indicated below with “!”). This implies the move is legal (doesn’t expose own king to check) and search examined it (as opposed to moves appearing in the move list after a move that causes a beta cutoff). Moves are encoded as ulong primitives like so:

Next, I altered the search function to flag played moves.

Then I modified the search function so it not only increments move history for quiet moves that cause a beta cutoff, but also decrements move history for quiet moves that failed to cause a beta cutoff. The decrement is applied only if a later quiet move actually caused a beta cutoff.

Finally, I modified the Move class to allow negative history values (though stored internally as a positive value to avoid complications with twos complement bit notation used by the .NET Core runtime to represent negative integers).

The listmoves command demonstrates the search function will assign negative history values.

listmoves
Rank   Move  Best  Cap Victim  Cap Attacker  Promo  Killer  History              Priority
====  =====  ====  ==========  ============  =====  ======  =======  ====================
  01   d7d4  True       Queen         Queen              0       -1  12141986070363407779
  02   f6d5                                              2     2857    433752951094266523
  03   h7h5                                              1      -56    433189988923033503
  04   f8e7                                              0    15940    432627106061501068
  05   e8e7                                              0     7705    432627071521931788
  06   a8b8                                              0     2985    432627051724292097
  07   d7d6                                              0      794    432627042534573459
  08   c6c5                                              0       -1    432627039200168218
  09   d7d5                                              0       -6    432627039179130267
  10   a8a7                                              0       -8    432627039170740232
  11   f6g4                                              0       -9    432627039166548646
  12   f6g8                                              0      -10    432627039162354310
  13   f6e4                                              0      -11    432627039158160036
  14   f6h5                                              0      -13    432627039149771423
  15   f8d6                                              0      -13    432627039149769363
  16   d7e7                                              0      -20    432627039120409996
  17   d7c7                                              0      -20    432627039120409994
  18   d7b7                                              0      -21    432627039116215689
  19   f8c5                                              0      -24    432627039103632026
  20   c8b7                                              0      -24    432627039103631625
  21   d7a7                                              0      -34    432627039061689736
  22   d7d8                                              0      -34    432627039061689731
  23   g7g5                                              0      -41    432627039032526622
  24   e6e5                                              0      -44    432627039019813404
  25   g7g6                                              0      -53    432627038982063894
  26   b4b3                                              0      -56    432627038969483433
  27   a6a5                                              0      -56    432627038969481240
  28   h7h6                                              0      -56    432627038969481111
  29   h8g8                                              0      -56    432627038969414534

29 legal moves

This improved MadChess 3.0 Beta’s tactical awareness and gained 28 Elo points. The evaluation function still is limited to material, piece location, draw detection, and checkmate.

I made two other changes that did not greatly affect the strength of MadChess 3.0 Beta. I added detection of drawish pawnless endgames. This may have contributed 5 of the 28 Elo, but I don’t really know because the error margins for 4,000 games are +/- 20 Elo. If a drawish endgame is encountered, MadChess 3.0 Beta assigns a zero score but allows the search to continue (as opposed to dead drawn endgames such as Kk, KBk, or KNk; threefold repetition; 50 moves without a capture or pawn move; or insufficient material to checkmate, where the search is terminated).

• KQkq
• KQkrr
• KRRkrr
• KRBkrb
• KRBkrn
• KRNkrn
• KRBkr
• KRNkr
• KRBNkr
• KRkr
• KRkb
• KRkn
• KNNkb
• KNNkn
• KNNk

Also, I changed the Board.IsMoveLegal function so it plays a null move when determining if a move checks the enemy king. Previously, Board.IsMoveLegal had determined check without actually playing a null move. This caused a subtle bug, though. As a consequence of this change, move legality checking searches an additional node, so the engine reports increased search speed in Nodes Per Second (NPS). This of course is an artificial speed increase, but it does align MadChess 3.0 Beta’s node counting with MadChess 2.x’s. MadChess 3.0 Beta searches the WAC position test at 4.31 million NPS on my PC.

1. Subversion source code revision
2. Win At Chess position test, 3 seconds per position
3. Bullet chess, 2 min / game + 1 sec / move