World Draughts Forum

It is currently Mon Dec 17, 2018 20:56

All times are UTC+01:00




Post new topic  Reply to topic  [ 9 posts ] 
Author Message
PostPosted: Sun Oct 28, 2012 22:00 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 90
Location: Mountain View
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:
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:
             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.


Top
   
PostPosted: Sun Oct 28, 2012 23:12 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 90
Location: Mountain View
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:
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:
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:
             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. 


Top
   
PostPosted: Mon Oct 29, 2012 17:42 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 90
Location: Mountain View
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:
             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:
             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


Top
   
PostPosted: Mon Oct 29, 2012 18:58 
Offline

Joined: Thu Nov 27, 2008 19:22
Posts: 221
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.

_________________
http://slagzet.com


Top
   
PostPosted: Mon Oct 29, 2012 19:04 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 90
Location: Mountain View
Maurits Meijer wrote:
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!


Top
   
PostPosted: Mon Oct 29, 2012 19:32 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1612
AartBik wrote:

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:
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:
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


Top
   
PostPosted: Tue Oct 30, 2012 04:27 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 90
Location: Mountain View
Rein Halbersma wrote:
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:
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


Top
   
PostPosted: Thu Nov 08, 2012 21:50 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 90
Location: Mountain View
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.


Top
   
PostPosted: Thu Nov 08, 2012 22:08 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1612
AartBik wrote:
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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 9 posts ] 

All times are UTC+01:00


Who is online

Users browsing this forum: Google Adsense [Bot] and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited