No comments

MadChess 2.0 Beta Build 023 (Delay Move Generation)

  By

I added code to delay move generation if a cached position specifies a best move. The best move is played first. If it causes a beta cutoff, the expense of generating moves is avoided. If not, moves are generated and searched, skipping the best move, which has already been searched.

Also, I corrected a bug that caused all searches to use an infinite aspiration window.  The corrected code will search the first ply using an infinite aspiration window, then search subsequent plies with a narrow window around the first ply’s score.  If the score of subsequent searches lies on an aspiration boundary, the window gradually is widened from 50 to 200 to 500 to infinite centipawns.

This added 44 Elo to the playing strength of MadChess 2.0 Beta

MadChess 2.0                   1670 :    800 (+64,=100,-636),  14.3 %

vs.                                 :  games (  +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  1,   7,  92),   4.5 :   -413,  17,    0.0
Matheus-2.3                         :    100 (  6,  13,  81),  12.5 :   -389,  16,    0.0
Monarch 1.7                         :    100 (  3,  10,  87),   8.0 :   -368,  17,    0.0
BigLion 2.23w                       :    100 ( 11,  11,  78),  16.5 :   -335,  14,    0.0
Faile 1.4                           :    100 (  3,  15,  82),  10.5 :   -330,  14,    0.0
Sharper 0.17                        :    100 ( 12,   9,  79),  16.5 :   -318,  16,    0.0
Jabba13032012                       :    100 ( 15,  12,  73),  21.0 :   -259,  15,    0.0
Roce 0.0390                         :    100 ( 13,  23,  64),  24.5 :   -184,  14,    0.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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 022 (MVV / LVA Move Order)

  By

I corrected a bug in move order. Moves mistakenly were ordered by most valuable victim, then most valuable attacker (MVV / MVA). I changed the order to most valuable victim, then least valuable attacker (MVV / LVA), so pawn takes queen captures are ordered before queen takes queen captures. In addition, I added code to recognize draws by insufficient material. And I corrected an index out of bounds bug involving move arrays.

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

MadChess 2.0                   1626 :    800 (+51,=79,-670),  11.3 %

vs.                                 :  games (  +,  =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  0,  6,  94),   3.0 :   -460,  18,    0.0
Matheus-2.3                         :    100 (  1,  6,  93),   4.0 :   -443,  17,    0.0
Monarch 1.7                         :    100 (  1,  3,  96),   2.5 :   -418,  17,    0.0
BigLion 2.23w                       :    100 (  8, 15,  77),  15.5 :   -381,  16,    0.0
Faile 1.4                           :    100 (  9, 11,  80),  14.5 :   -374,  15,    0.0
Sharper 0.17                        :    100 (  7, 11,  82),  12.5 :   -365,  17,    0.0
Jabba13032012                       :    100 ( 13, 11,  76),  18.5 :   -305,  16,    0.0
Roce 0.0390                         :    100 ( 12, 16,  72),  20.0 :   -230,  15,    0.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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 021 (Tapered Evaluation)

  By

I added tapered evaluation to MadChess 2.0 Beta. The evaluation assigns a material score, a middlegame piece location score, and an endgame piece location score. Then calculates the game phase and returns a weighted average of the middlegame and endgame scores.

By separating piece location scores into middlegame and endgame phases, I can encourage MadChess to hold its queen back during the middlegame, and bring its king to the center during the endgame, for example.

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

MadChess 2.0                   1596 :    800 (+42,=72,-686),   9.8 %

vs.                                 :  games (  +,  =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  0,  2,  98),   1.0 :   -490,  18,    0.0
Matheus-2.3                         :    100 (  3, 10,  87),   8.0 :   -467,  17,    0.0
Monarch 1.7                         :    100 (  2,  2,  96),   3.0 :   -446,  18,    0.0
BigLion 2.23w                       :    100 (  5, 11,  84),  10.5 :   -413,  17,    0.0
Faile 1.4                           :    100 (  7, 10,  83),  12.0 :   -404,  16,    0.0
Sharper 0.17                        :    100 (  4,  9,  87),   8.5 :   -396,  17,    0.0
Jabba13032012                       :    100 (  7, 12,  81),  13.0 :   -337,  17,    0.0
Roce 0.0390                         :    100 ( 14, 16,  70),  22.0 :   -258,  16,    0.0
Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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 020 (Baseline)

  By

I’ve reached an important milestone in the development of my new chess engine. MadChess 2.0 Beta can play a timed game of chess.

I’ve implemented an alpha / beta negamax search with aspiration windows and a capture / check evasion quiescence search. Evaluation is limited to material and middlegame piece square tables. No tapered evaluation, no passed pawn bonus, no piece mobility, no king safety, no reductions or pruning of moves, etc.

I ran a gauntlet tournament, pitting MadChess 2.0 Beta against weak chess engines.

MadChess 2.0                   1489 :    800 (+17,=56,-727),   5.6 %

vs.                                 :  games (  +,  =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  1,  7,  92),   4.5 :   -589,  21,    0.0
Matheus-2.3                         :    100 (  2,  4,  94),   4.0 :   -572,  21,    0.0
Monarch 1.7                         :    100 (  1,  8,  91),   5.0 :   -545,  21,    0.0
BigLion 2.23w                       :    100 (  2,  5,  93),   4.5 :   -520,  21,    0.0
Faile 1.4                           :    100 (  2,  8,  90),   6.0 :   -511,  21,    0.0
Sharper 0.17                        :    100 (  1,  5,  94),   3.5 :   -502,  21,    0.0
Jabba13032012                       :    100 (  7,  6,  87),  10.0 :   -441,  21,    0.0
Roce 0.0390                         :    100 (  1, 13,  86),   7.5 :   -367,  20,    0.0

This establishes a baseline rating.

Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
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 001 (Procedural Code)

  By

I’ve been writing a new version of MadChess. For this 2.0 version, I’m writing code using procedural techniques rather than the object-oriented techniques I used in MadChess 1.x. When I say the code is “procedural”, I mean it has two primary traits.

  1. The code uses primitive data structures instead of classes.
  2. The code emphasizes performance over readability and maintainability.

I’m writing the code in C# with a mailbox board representation, similar to MadChess 1.x.

The board has an array of Positions. Each Position has an integer array of Squares.

Moves are encoded into an unsigned integer.

I’m using a copy-make technique to play moves, instead of the make-unmake technique used by MadChess 1.x. Playing a move involves copying the Squares array (a fast memory operation), then updating Position data structures. Undoing a move is as simple as decrementing an index.

I’m satisfied with the speed of the move generator. MadChess 1.x could generate moves at 850K per second. MadChess 2.0 Beta generates moves at 3.6M per second, a 4x speedup. This includes pseudo-legal move creation, move legality testing (does move expose own king to check), incremental update of Zobrist position keys, and check detection (does move check enemy king), which isn’t strictly required for a move generator but will be used by the search function to prevent reductions of moves that give check. I haven’t examined the code using a profiler, so perhaps the speed can be improved some. But I don’t want to fall into the trap of premature optimization.

I wrote a function to verify the code generates correct legal moves in a variety of positions. Thanks to Martin Sedlak for providing test positions and correct legal move counts.

PS C:\Users\Erik\My Documents\...\Chess2\bin\release> .\MadChess.exe
test
Number                                                                     Position  Depth     Expected        Moves  Correct    Pct
======  ===========================================================================  =====  ===========  ===========  =======  =====
     1                                           8/5bk1/8/2Pp4/8/1K6/8/8 w - d6 0 1      6      824,064      824,064     True  100.0
     2                                           8/8/1k6/8/2pP4/8/5BK1/8 b - d3 0 1      6      824,064      824,064     True  100.0
     3                                          8/8/1k6/2b5/2pP4/8/5K2/8 b - d3 0 1      6    1,440,467    1,440,467     True  100.0
     4                                          8/5k2/8/2Pp4/2B5/1K6/8/8 w - d6 0 1      6    1,440,467    1,440,467     True  100.0
     5                                               5k2/8/8/8/8/8/8/4K2R w K - 0 1      6      661,072      661,072     True  100.0
     6                                               4k2r/8/8/8/8/8/8/5K2 b k - 0 1      6      661,072      661,072     True  100.0
     7                                               3k4/8/8/8/8/8/8/R3K3 w Q - 0 1      6      803,711      803,711     True  100.0
     8                                               r3k3/8/8/8/8/8/8/3K4 b q - 0 1      6      803,711      803,711     True  100.0
     9                                    r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1      4    1,274,206    1,274,206     True  100.0
    10                                    r3k2r/7b/8/8/8/8/1B4BQ/R3K2R b KQkq - 0 1      4    1,274,206    1,274,206     True  100.0
    11                                     r3k2r/8/3Q4/8/8/5q2/8/R3K2R b KQkq - 0 1      4    1,720,476    1,720,476     True  100.0
    12                                     r3k2r/8/5Q2/8/8/3q4/8/R3K2R w KQkq - 0 1      4    1,720,476    1,720,476     True  100.0
    13                                            2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1      6    3,821,001    3,821,001     True  100.0
    14                                            3K4/8/8/8/8/8/4p3/2k2R2 b - - 0 1      6    3,821,001    3,821,001     True  100.0
    15                                          8/8/1P2K3/8/2n5/1q6/8/5k2 b - - 0 1      5    1,004,658    1,004,658     True  100.0
    16                                          5K2/8/1Q6/2N5/8/1p2k3/8/8 w - - 0 1      5    1,004,658    1,004,658     True  100.0
    17                                               4k3/1P6/8/8/8/8/K7/8 w - - 0 1      6      217,342      217,342     True  100.0
    18                                               8/k7/8/8/8/8/1p6/4K3 b - - 0 1      6      217,342      217,342     True  100.0
    19                                                8/P1k5/K7/8/8/8/8/8 w - - 0 1      6       92,683       92,683     True  100.0
    20                                                8/8/8/8/8/k7/p1K5/8 b - - 0 1      6       92,683       92,683     True  100.0
    21                                                K1k5/8/P7/8/8/8/8/8 w - - 0 1      6        2,217        2,217     True  100.0
    22                                                8/8/8/8/8/p7/8/k1K5 b - - 0 1      6        2,217        2,217     True  100.0
    23                                               8/k1P5/8/1K6/8/8/8/8 w - - 0 1      7      567,584      567,584     True  100.0
    24                                               8/8/8/8/1k6/8/K1p5/8 b - - 0 1      7      567,584      567,584     True  100.0
    25                                            8/8/2k5/5q2/5n2/8/5K2/8 b - - 0 1      4       23,527       23,527     True  100.0
    26                                            8/5k2/8/5N2/5Q2/2K5/8/8 w - - 0 1      4       23,527       23,527     True  100.0
    27                     rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1      6  119,060,324  119,060,324     True  100.0
    28         r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1      5  193,690,690  193,690,690     True  100.0
    29                                    8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1      6   11,030,083   11,030,083     True  100.0
    30             r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1      5   15,833,292   15,833,292     True  100.0
    31                rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 1      3       53,392       53,392     True  100.0
    32      r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 1      5  164,075,551  164,075,551     True  100.0
Counted 1,105,116,435 moves (3,632,999 moves per second).

Next, I’d like to add a simple evaluation function (material only- doesn’t get any simpler than that) and a simple search function. Then play games to establish an Elo rating. Then slowly add one feature at a time, careful to measure its impact on playing strength.