BikDam (engine for international checkers)

[AartBik]

Inspired by Rein Halbersma's kind encouragement, I have started some work on an international checkers engine. After all, "dammen" is the variant I grew up with in The Netherlands. Since I have implemented BikJump for chess, BikMove for American checkers, I decided to name this upcoming engine BikDam. I already had some fun hacking a, hopefully, efficient move generator. The rules for captures were very interesting to implement and, as strongly encouraged on this forum, duplicate captures are removed (in contrast with the approach I took for American checkers).

Here are some preliminary results.

Start position.

Code: Select all

perft(1) = 9 in 0 ms. 
perft(2) = 81 in 0 ms. 
perft(3) = 658 in 0 ms.
perft(4) = 4265 in 0 ms.
perft(5) = 27117 in 1 ms. 27117.0 KN/s
perft(6) = 167140 in 3 ms. 55713.3 KN/s
perft(7) = 1049442 in 22 ms. 47701.9 KN/s
perft(8) = 6483961 in 78 ms. 83127.7 KN/s
perft(9) = 41022423 in 434 ms. 94521.7 KN/s
perft(10) = 258895763 in 2599 ms. 99613.6 KN/s
perft(11) = 1665861398 in 17090 ms. 97475.8 KN/s

And, my favorite, the "Turkse slag".

Code: Select all

             BLACK
+--+--+--+--+--+--+--+--+--+--+ [5] 0(0)
|  |--|  |--|  |--|  |--|  |--|
|--|  |bb|  |--|  |--|  |--|  |
|  |--|  |--|  |bb|  |--|  |--|
|--|  |bb|  |bb|  |--|  |--|  |
|  |--|  |--|  |--|  |--|  |--|
|--|  |--|  |bb|  |--|  |--|  |
|  |--|  |--|  |--|  |--|  |--|
|--|  |--|  |--|  |--|  |--|  |
|  |--|  |--|  |--|  |--|  |--|
|WW|  |--|  |--|  |--|  |--|  |
+--+--+--+--+--+--+--+--+--+--+ [1]
         **  WHITE **

perft(1) = 1 in 0 ms. 
perft(2) = 1 in 0 ms. 
perft(3) = 0 in 0 ms. 

[AartBik]

Some more interesting positions found on this forum.

B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24.

Code: Select all

perft(1) = 14 in 0 ms.
perft(2) = 55 in 0 ms. 
perft(3) = 1168 in 0 ms.
perft(4) = 5432 in 0 ms.
perft(5) = 87195 in 1 ms. 87195.0 KN/s
perft(6) = 629010 in 4 ms. 157252.5 KN/s
perft(7) = 9041010 in 56 ms. 161446.6 KN/s
perft(8) = 86724219 in 551 ms. 157394.2 KN/s
perft(9) = 1216917193 in 7151 ms. 170174.4 KN/s

W:W25,27,28,30,32,33,34,35,37,38:B12,13,14,16,18,19,21,23,24,26. (Woldouby)

Code: Select all

perft(1) = 6 in 0 ms.    
perft(2) = 12 in 0 ms.   
perft(3) = 30 in 0 ms.    
perft(4) = 73 in 0 ms.    
perft(5) = 215 in 0 ms.    
perft(6) = 590 in 0 ms.    
perft(7) = 1944 in 0 ms.  
perft(8) = 6269 in 1 ms. 6269.0 KN/s
perft(9) = 22369 in 1 ms. 22369.0 KN/s
perft(10) = 88050 in 4 ms. 22012.5 KN/s
perft(11) = 377436 in 14 ms. 26959.7 KN/s
perft(12) = 1910989 in 33 ms. 57908.8 KN/s
perft(13) = 9872645 in 161 ms. 61320.8 KN/s
perft(14) = 58360286 in 880 ms. 66318.5 KN/s
perft(15) = 346184885 in 5118 ms. 67640.7 KN/s 

Rein's test position.

Code: Select all

             BLACK
+--+--+--+--+--+--+--+--+--+--+ [19] 0(0)
|  |WW|  |--|  |--|  |--|  |--|
|--|  |--|  |bb|  |bb|  |bb|  |
|  |bb|  |bb|  |--|  |--|  |--|
|--|  |--|  |--|  |bb|  |bb|  |
|  |bb|  |bb|  |bb|  |--|  |--|
|--|  |--|  |--|  |--|  |bb|  |
|  |bb|  |bb|  |bb|  |bb|  |--|
|--|  |--|  |--|  |--|  |--|  |
|  |bb|  |bb|  |bb|  |bb|  |--|
|--|  |--|  |--|  |--|  |--|  |
+--+--+--+--+--+--+--+--+--+--+ [1]
         **  WHITE **

perft(1) = 3 in 0 ms.  
perft(2) = 0 in 1 ms.  

[AartBik]

And two more of Rein's excellent test cases.
Are there any other interesting corner cases I should look at?

Pieces ready to promote.

Code: Select all

             BLACK
+--+--+--+--+--+--+--+--+--+--+ [5] 0(0)
|  |--|  |--|  |--|  |--|  |--|
|ww|  |ww|  |ww|  |ww|  |ww|  |
|  |--|  |--|  |--|  |--|  |--|
|--|  |--|  |--|  |--|  |--|  |
|  |--|  |--|  |--|  |--|  |--|
|--|  |--|  |--|  |--|  |--|  |
|  |--|  |--|  |--|  |--|  |--|
|--|  |--|  |--|  |--|  |--|  |
|  |bb|  |bb|  |bb|  |bb|  |bb|
|--|  |--|  |--|  |--|  |--|  |
+--+--+--+--+--+--+--+--+--+--+ [5]
         **  WHITE **

perft(1) = 9 in 0 ms.   
perft(2) = 81 in 0 ms.    
perft(3) = 795 in 0 ms.   
perft(4) = 7578 in 0 ms. 
perft(5) = 86351 in 2 ms. 43175.5 KN/s
perft(6) = 936311 in 13 ms. 72023.9 KN/s
perft(7) = 11448262 in 100 ms. 114482.6 KN/s
perft(8) = 138362698 in 1111 ms. 124538.9 KN/s
perft(9) = 1799526674 in 14361 ms. 125306.5 KN/s

All kings at piece positions.

Code: Select all

             BLACK
+--+--+--+--+--+--+--+--+--+--+ [20] 0(0)
|  |BB|  |BB|  |BB|  |BB|  |BB|
|BB|  |BB|  |BB|  |BB|  |BB|  |
|  |BB|  |BB|  |BB|  |BB|  |BB|
|BB|  |BB|  |BB|  |BB|  |BB|  |
|  |--|  |--|  |--|  |--|  |--|
|--|  |--|  |--|  |--|  |--|  |
|  |WW|  |WW|  |WW|  |WW|  |WW|
|WW|  |WW|  |WW|  |WW|  |WW|  |
|  |WW|  |WW|  |WW|  |WW|  |WW|
|WW|  |WW|  |WW|  |WW|  |WW|  |
+--+--+--+--+--+--+--+--+--+--+ [20]
         **  WHITE **

perft(1) = 17 in 0 ms.  
perft(2) = 79 in 0 ms.  
perft(3) = 352 in 0 ms.
perft(4) = 1399 in 1 ms. 1399.0 KN/s
perft(5) = 7062 in 1 ms. 7062.0 KN/s
perft(6) = 37589 in 5 ms. 7517.8 KN/s
perft(7) = 217575 in 20 ms. 10878.8 KN/s
perft(8) = 1333217 in 83 ms. 16062.9 KN/s
perft(9) = 8558321 in 499 ms. 17150.9 KN/s
perft(10) = 58381162 in 3193 ms. 18284.1 KN/s
perft(11) = 417920283 in 21388 ms. 19539.9 KN/s

[Maurits Meijer]

Cool, what language and machine are you using?
The perft topic is amazing when building an engine, maybe there should be a sticky topic with the right perft numbers for 5 or six positions that included all the edge cases.

[AartBik]

Cool, what language and machine are you using?
The perft topic is amazing when building an engine, maybe there should be a sticky topic with the right perft numbers for 5 or six positions that included all the edge cases.

I wrote the move generator in C++ with some intrinsics/asm extensions for a few common bit operations.
These perft numbers are on a single core of a Intel Xeon X5650 2.67GHz, but optimized with "bulk counting" (nothing else though).

I would be very interested in seeing more corner cases for perft validation!

[Rein Halbersma]

I would be very interested in seeing more corner cases for perft validation!

Aart,

Great to see you moving along so quickly with your new BikDam engine! Within my draughts and checkers template library, I maintain a list of FEN strings corresponding to the test positions from the Italian translation of the official FMJD rulebook

Spoiler:

Code: Select all

BOOST_AUTO_TEST_SUITE(TestInternational)

// Positions from the official International rules (Italian translation):
// http://www.fid.it/regolamenti/2008/RegTec_CAPO_II.pdf

BOOST_FIXTURE_TEST_CASE(TestKingMoveRange, FixtureInternational)
{
        // Art. 3.9 (king move range)
        auto const FEN = "W:WK23";
        std::string const legal[] = {
                "23-18", "23-12", "23-7", "23-1",
                "23-19", "23-14", "23-10", "23-5",
                "23-28", "23-32", "23-37", "23-41", "23-46",
                "23-29", "23-34", "23-40", "23-45"
        };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestPawnJumpDirections, FixtureInternational)
{
        // Art. 4.2 (pawn jump directions)
        auto const FEN = "W:W35:B30,K40";
        std::string const legal[] = { "35x24", "35x44" };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestKingJumpRange, FixtureInternational)
{
        // Art. 4.3 (king jump range)
        auto const FEN = "W:WK41:B23";
        std::string const legal[] = { "41x19", "41x14", "41x10", "41x5" };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestPawnJumpContinuation, FixtureInternational)
{
        // Art. 4.5 (pawn jump continuation)
        auto const FEN = "W:W47:B13,14,22,24,31,34,K41,44";
        std::string const legal[] = { "47x49" };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestKingJumpContinuation, FixtureInternational)
{
        // Art. 4.6 (king jump continuation)
        auto const FEN = "W:WK1:B7,9,17,19,20,30,31,33,43,44";
        std::string const legal[] = { "1x15" };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestJumpRemoval, FixtureInternational)
{
        // Art. 4.8 (jump removal NOT en-passant)
        auto const FEN = "B:W27,28,38,39,42:BK25";
        std::string const legal[] = { "25x33" };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestJumpMostPieces, FixtureInternational)
{
        // Art. 4.13 (jump most pieces)
        auto const FEN = "W:WK48:B7,8,31,34,K42,44";
        std::string const legal[] = { "48x50" };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestJumpMostKings, FixtureInternational)
{
        // Art. 4.14 (jump most kings NOT applicable)
        auto const FEN = "W:W26:B12,K21,31,32";
        std::string const legal[] = { "26x8", "26x28" };
        run(FEN, legal);
}

BOOST_FIXTURE_TEST_CASE(TestPawnPromotion, FixtureInternational)
{
        // Art. 4.15 (pawn promotion NOT en-passant)
        auto const FEN = "W:W15:B9,10";
        std::string const legal[] = { "15x13" };
        run(FEN, legal);
}

BOOST_AUTO_TEST_SUITE_END()

The fixture code sets up the position, generates the moves and checks whether their PDN notation is a permutation of the supplied string array of legal moves.

Spoiler:

Code: Select all

template<typename Rules, typename Board>
struct Fixture
{
        template<std::size_t N>
        void run(std::string const& FEN, std::string const (&legal)[N])
        {
                // setup the position and generate all legal moves
                auto const p = setup::read<Rules, Board, pdn::protocol>()(FEN);
                auto const moves = successor::generate(p);

                // check whether the number of generated moves is equal to the number of legal moves
                BOOST_CHECK(moves.size() == N);

                // write each move as a string into the vector notations
                std::vector<std::string> notations;
                std::transform(
                        std::begin(moves), std::end(moves),
                        std::back_inserter(notations),
                        [&](Move const& m) {
                                return notation::write(p, m);
                        }
                );

                // check whether the vector of generated moves is a permutation of the array of legal moves
                BOOST_CHECK(
                        boost::algorithm::is_permutation(
                                std::begin(legal), std::end(legal),
                                std::begin(notations), 
                                [](std::string const& lhs, std::string const& rhs) {
                                        return boost::algorithm::trim_copy(lhs) == boost::algorithm::trim_copy(rhs);
                                }
                        )
                );
        }
};

Rein

[AartBik]

Great to see you moving along so quickly with your new BikDam engine! Within my draughts and checkers template library, I maintain a list of FEN strings corresponding to the test positions from the Italian translation of the official FMJD rulebook
....
Rein

Thanks Rein! Excellent stuff. BikDam passes all the tests.

Code: Select all

rule    :   Art. 3.9 (king move range)
FEN     :   W:WK23
computed:   23-18  23-12  23-7  23-1  23-19  23-14  23-10  23-5  23-29  23-34  23-40  23-45  23-28  23-32  23-37  23-41  23-46
expected:   23-18  23-12  23-7  23-1  23-19  23-14  23-10  23-5  23-28  23-32  23-37  23-41  23-46  23-29  23-34  23-40  23-45

rule    :   Art. 4.2 (pawn jump directions)
FEN     :   W:W35:B30,K40
computed:   35x24  35x44
expected:   35x24  35x44

rule    :   Art. 4.3 (king jump range)
FEN     :   W:WK41:B23
computed:   41x19  41x14  41x10  41x5
expected:   41x19  41x14  41x10  41x5

rule    :   Art. 4.5 (pawn jump continuation)
FEN     :   W:W47:B13,14,22,24,31,34,K41,44
computed:   47x49
expected:   47x49

rule    :   Art. 4.6 (king jump continuation)
FEN     :   W:WK1:B7,9,17,19,20,30,31,33,43,44
computed:   1x15
expected:   1x15

rule    :   Art. 4.8 (jump removal NOT en-passant)
FEN     :   B:W27,28,38,39,42:BK25
computed:   25x33
expected:   25x33

rule    :   Art. 4.13 (jump most pieces)
FEN     :   W:WK48:B7,8,31,34,K42,44
computed:   48x50
expected:   48x50

rule    :   Art. 4.14 (jump most kings NOT applicable)
FEN     :   W:W26:B12,K21,31,32
computed:   26x8  26x28
expected:   26x8  26x28

rule    :   Art. 4.15 (pawn promotion NOT en-passant)
FEN     :   W:W15:B9,10
computed:   15x13
expected:   15x13

[AartBik]

BikDam is making good progress and now plays a decent game of international checkers (for some definition of "decent" at least). I obviously would like to play some tournaments with other engines, and hope others are interested in this too. Any recommendations for a protocol, preferably one that is used by active players? After consulting with Rein, some possible options are Xboard alien edition, which uses an extended Win/Xboard protocol, a 10x10 version of Martin Fierz' CheckerBoard, as done by Ed Gilbert (I used the 8x8 CheckBoard protocol for my engine BikMove by the way), or the GUIDE protocol. Perhaps there are others.

[Rein Halbersma]

BikDam is making good progress and now plays a decent game of international checkers (for some definition of "decent" at least). I obviously would like to play some tournaments with other engines, and hope others are interested in this too. Any recommendations for a protocol, preferably one that is used by active players? After consulting with Rein, some possible options are Xboard alien edition, which uses an extended Win/Xboard protocol, a 10x10 version of Martin Fierz' CheckerBoard, as done by Ed Gilbert (I used the 8x8 CheckBoard protocol for my engine BikMove by the way), or the GUIDE protocol. Perhaps there are others.

A non-GUI protocol is of course DamExchange http://www.mesander.nl/damexchange/edxpmain.htm