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.

No comments

Banks 49th Amateur Series Division 5

  By

MadChess 1.4 participated in Graham Banks’ 49th amateur tournament in division 5.

                             1    2    3    4    5    6    7    8    9    0    1    2    3    4    
1   Jazz 721 64-bit          **** 1011 1½10 ½1½1 010½ 0100 110½ 1111 ½0½1 1100 ½11½ 1½11 1101 0100  32.0/52
2   Bagatur 1.3a 64-bit      0100 **** ½10½ ½½1½ 0½½1 1½½½ 10½½ 11½1 00½1 1½10 1111 1110 ½10½ 0111  31.5/52  783.50
3   Waxman 2014              0½01 ½01½ **** 1011 ½½½0 1000 1110 ½½11 0110 11½½ 1011 ½11½ 1110 ½110  31.5/52  781.00
4   Tigran 2.4n 64-bit       ½0½0 ½½0½ 0100 **** ½½½½ ½111 1111 1½½1 111½ 1½½1 ½½½½ 0011 ½½0½ 0½11  30.5/52
5   Ares 1.005 64-bit        101½ 1½½0 ½½½1 ½½½½ **** 1011 100½ ½0½1 ½00½ 0101 ½½0½ 111½ 10½1 1111  30.0/52
6   Myrddin 0.86 64-bit      1011 0½½½ 0111 ½000 0100 **** 0½½1 00½1 1110 ½110 1011 1½10 110½ ½111  29.5/52
7   NoraGrace 1.0 64-bit     001½ 01½½ 0001 0000 011½ 1½½0 **** 100½ 1½½1 1111 0100 111½ ½10½ 001½  25.5/52
8   EveAnn 1.71a             0000 00½0 ½½00 0½½0 ½1½0 11½0 011½ **** 1½01 0½0½ 10½1 11½1 110½ 111½  25.0/52
9   Maverick 0.51 64-bit     ½1½0 11½0 1001 000½ ½11½ 0001 0½½0 0½10 **** ½0½0 10½1 1100 1011 ½½0½  23.5/52
10  Orion 0.2 64-bit         0011 0½01 00½½ 0½½0 1010 ½001 0000 1½1½ ½1½1 **** ½½00 ½0½0 0½11 0111  22.5/52
11  Gibbon 2.60a 64-bit      ½00½ 0000 0100 ½½½½ ½½1½ 0100 1011 01½0 01½0 ½½11 **** ½½00 ½½½1 ½001  21.5/52  547.00
12  FireFly 2.7.0 64-bit     0½00 0001 ½00½ 1100 000½ 0½01 000½ 00½0 0011 ½1½1 ½½11 **** 11½½ 1½1½  21.5/52  522.00
13  MadChess 1.4 64-bit      0010 ½01½ 0001 ½½1½ 01½0 001½ ½01½ 001½ 0100 1½00 ½½½0 00½½ **** ½011  20.5/52
14  Fischerle 0.9.60 64-bit  1011 1000 ½001 1½00 0000 ½000 110½ 000½ ½½1½ 1000 ½110 0½0½ ½100 ****  19.0/52

Games

No comments

A Game with All the Right Moves

  By

I played a blitz game recently on Chess.com where throughout the entire game I felt a sense of heightened alertness- that I just understood the position and was quickly spotting threats and tactics. My opponent made a number of weak moves (yes, we’re both patzers), but I felt I found all the right moves- the most forcing, decisive replies to capitalize on his mistakes. After the game I asked my chess engine, MadChess, to analyze the game and suggest where I could have played better. To my surprise, MadChess could not find any improvements in my play.

OK, I thought, I did feel confident throughout the game. However, a super-grandmaster strength engine, Komodo 5.1, nearly 900 Elo stronger than MadChess, is certain to find improvements. Nope.

I ran the analysis in Hiarcs Chess Explorer using the “find only errors, not inaccuracies” setting. I don’t know how many centipawns Hiarcs Chess Explorer considers an error. Nonetheless, I’m proud I played a game so accurately with so little time on the clock.

Even with the “show inaccuracies” setting enabled, MadChess cannot find any improvement in my play from the 23rd move through checkmate on the 37th move. Komodo finds one improvement, suggesting 24. Bc1 instead of 24. Nxd8, to avoid the trade of bishops, I guess.

I played white. Time control was 5 min + 2 sec / move.

No comments

Banks 48th Amateur Series Division 6

  By

MadChess 1.4 participated in Graham Banks’ 48th amateur tournament in division 6.

                                  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5  6  
1   Bagatur 1.3a 64-bit           ** 10 ½1 1½ 01 11 0½ 01 10 10 10 11 11 11 11 ½1  21.0/30
2   MadChess 1.4 64-bit           01 ** ½0 ½0 1½ ½1 ½½ 0½ 11 11 10 11 ½1 ½0 11 11  19.5/30
3   Fischerle 0.9.50 64-bit       ½0 ½1 ** 1½ ½1 1½ 1½ 1½ 10 ½1 11 1½ ½0 01 01 10  19.0/30
4   Gibbon 2.60a 64-bit           0½ ½1 0½ ** 00 0½ ½1 11 01 ½1 1½ 11 11 ½1 1½ ½½  18.5/30
5   Orion 0.2 64-bit              10 0½ ½0 11 ** 1½ 00 11 01 0½ ½1 00 10 11 11 11  17.5/30
6   Waxman 2013                   00 ½0 0½ 1½ 0½ ** 10 11 0½ 1½ 01 ½1 ½1 11 1½ ½1  17.0/30
7   Absolute Zero 2.4.0.0 64-bit  1½ ½½ 0½ ½0 11 01 ** 00 ½½ 11 ½1 ½½ 1½ ½1 00 1½  16.5/30  242.50
8   FireFly 2.7.0 64-bit          10 1½ 0½ 00 00 00 11 ** ½1 10 ½1 0½ 11 11 11 01  16.5/30  225.00
9   Mango Paola Ajedrez 4.1       01 00 01 10 10 1½ ½½ ½0 ** 10 00 ½½ 11 10 11 11  16.0/30
10  Protej 0.5.8c                 01 00 ½0 ½0 1½ 0½ 00 01 01 ** 10 10 01 1½ 1½ 11  14.0/30
11  ProChess 1.02AD               01 01 00 0½ ½0 10 ½0 ½0 11 01 ** 11 ½0 10 01 01  13.5/30
12  Exacto 0.e 64-bit             00 00 0½ 00 11 ½0 ½½ 1½ ½½ 01 00 ** 1½ 1½ ½1 ½½  13.0/30
13  Carballo 0.8                  00 ½0 ½1 00 01 ½0 0½ 00 00 10 ½1 0½ ** 1½ ½1 ½½  11.0/30
14  NGplay 9.85 64-bit            00 ½1 10 ½0 00 00 ½0 00 01 0½ 01 0½ 0½ ** 10 ½1   9.5/30
15  K2 0.57                       00 00 10 0½ 00 0½ 11 00 00 0½ 10 ½0 ½0 01 ** 1½   9.0/30
16  Napoleon 1.5.0 64-bit         ½0 00 01 ½½ 00 ½0 0½ 10 00 00 10 ½½ ½½ ½0 0½ **   8.5/30

Games