MadChess 2.0 Beta Build 001 (Procedural Code)

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.

Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *