Release of DCTL: draughts and checkers template library

[Rein Halbersma]

You know what's coming so without further ado: https://bitbucket.org/rhalbersma/dctl/src

I released this code under the Boost license. This essentially means that you can use it however you wish, even in your own closed source programs. I will be using this thread to explain the architecture and ways to use the library in upcoming posts.

Hopefully, this code will be useful or inspirational for draughts programmers. I would love to hear your feedback, on matters related to design, implementation and performance. Code proposals and feature request will also be welcomed! The source code repository is under the Mercurial distributed version control system. There is a good chance I will move this to Github in the near future.

Building the code requires the Microsoft Visual C++ 2010 compiler (Express edition works) and the Boost 1.50 or later libraries. There is no platform dependent code in the library, and it used to also compile under Eclipse/g++/Intel. But the non Microsoft compilers are a little stricter in checking template features (name lookup in particular), so you might find that it doesn't compile out of the box on Linux. If that happens to be the case, let me know and I will try to fix it.

The structure of the library consist of a build directory containt the Visual Studio solution, a src directory consisting of a C++ template headers (the entire library is header-only, so there is no library linking required), and a test directory of unit tests that show how to call and use the various library functionality.

[Rein Halbersma]

Features of the DCTL

Supported variants (the move generators for each variant has been verified for correctness in the various perft threads here):

Code: Select all

-International/Brazilian draughts
-English/American checkers
-Russian draughts ("shashki")
-Italian draughts
-Spanish/Portugese draughts
-Czech draughts
-Thai draughts
-Frisian draughts
-Killer draughts

Supported board sizes:

Code: Select all

-anything that fits within a 64-bit integer, in particular
-10x10
-8x8
-10x11 (Ktar)
-10x12 (Ktar)
-not yet supported: 12x12 and larger

Supported game objectives:

Code: Select all

-regular (not being able to move = loss)
-misere (not being able to move = win)
-Kingscourt (first to win a king = win)

[Rein Halbersma]

At the core of the library are two class templates that encode the board layout and the game mechanics:

Board class template, depending on 5 game specific parameters, most of which have defaults

Code: Select all

typedef Board< Dimensions< 8,  8> > Checkers;
typedef Board< Dimensions<10, 10> > International;

Rules class template, depending on 13 game specific parameters, most of which have defaults

Code: Select all

struct Checkers
:
        Rules<
                Checkers,
                king_range<range::distance_1>,
                pawn_jump_directions<directions::up>,
                jump_precedence<precedence::none>
        >
{};

struct International
:
        Rules<
                International,
                king_range<range::distance_N>,
                pawn_jump_directions<directions::diag>,
                jump_precedence<precedence::quantity>
        >
{};

It is very easy to define your own game rules and board layouts using these templates, by simply overriding the appropriate default parameters. Providing entirely new features requires modifying the source of the move generator, and this is considerably more involved and currently not supported (except as feature requests).

Truly exotic draughts variations with multiple piece types (Lineo) or non-alternating moves are not and probably never will be supported. This is a library for generic draughts variants, not for generic two-player zero-sum games.

[Rein Halbersma]

Setting up positions can be done using a diagram notation:

Code: Select all

        // Test position from email conversation with Wieger Wesselink
        auto const w = "O     \
            .   .   .   .   . \
          .   .   .   .   .   \
            .   .   x   x   x \
          x   .   .   x   x   \
            x   .   .   x   x \
          .   o   o   o   .   \
            .   o   o   o   o \
          .   o   .   o   o   \
            .   .   .   o   o \
          .   .   .   .   .   \
        ";

        // parse the above diagram into a position using the DamExchange protocol
        // with a modified character set (default is <'Z', 'W', 'E'>)
        auto const pos_w = read<
                rules::International, board::International,
                dxp::protocol, TokenInterface<'X', 'O', '.'>
        >()(w);

        // write the above position as a FEN string using the PDN protocol
        auto const FEN_w = write<pdn::protocol>()(pos_w);

Alternatives are using the FEN notation or simply relying on the predefined initial position:

Code: Select all

        auto const p = setup::read<rules::International, board::International, pdn::protocol>()(
                "W:B12,13,14,16,18,19,21,23,24,26:W25,27,28,30,32,33,34,35,37,38"
        );

        auto const p = Position<rules::International, board::International>::initial();

[Rein Halbersma]

Perft functionality using a hash table is defined as

Code: Select all

        template<typename Position>
        NodeCount perft(Position const& p, int depth, int ply)
        {
                statistics_.update(ply);

                auto TT_entry = TT.find(p);
                if (TT_entry && TT_entry->depth() == depth)
                        return TT_entry->leafs();

                NodeCount leafs;
                if (depth == 1) {
                        leafs = successor::count(p);
                } else {
                        auto const moves = successor::generate(p);
                        leafs = 0;
                        for (auto m = std::begin(moves); m != std::end(moves); ++m) {
                                auto q = p;
                                q.attach(p);
                                q.make(*m);
                                leafs += perft(q, depth - 1, ply + 1);
                        }
                }

                TT.insert(p, Transposition(leafs, depth));
                return leafs;
        }

Note that the above code uses some new C++11 featurs, such as auto for type-deduction, and move semantics when returning a vector of legal moves by-value instead of passing a pointer to the move list. The code also uses the copy-make framework (with a linked-list on the various stack frames, hence the attach() call) instead of make-undo, since I believe this will make it easier to a parallel search.

[Rein Halbersma]

The search() function is a Principal Variation Search skeleton with iterative deepening, hash tables, move ordering, mate distance pruning and zero-window searches for non-PV modes.

The returned search value distinguishes between wins of different search depths. I have tested the correctness of the search() function on a set of extremal wins in the 2-4 piece endgame databases provided by Michel Grimminck.

The search is called as:

Code: Select all

        auto const p = Position<rules::International, board::International>::initial();
        root_.analyze(p, 15);

and generate XBoard type of output:

Code: Select all

  info score   4 depth 15 nodes    26822522 time  35906 nps  747021
   1. 34-29 16-21  2. 31-26 11-16  3. 36-31 20-24  4. 29x20 14x25  5. 31-27 15-20
   6. 35-30 25x34  7. 39x30 18-23  8. 32-28 
     b   b   b   b   b
   b   b   b   b   b
     .   b   b   .   .
   b   b   .   b   b
     b   .   b   .   .
   w   w   w   .   w
     .   .   w   .   .
   .   w   w   .   w
     w   w   w   w   w
   w   w   w   w   w

The diagram displayed at the end of the output is the end of the PV that the program is considering. You notice that this is not a very sensible PV. The reason is that the evaluation is not very sophisticated, and that the search does not use a quiescence search yet.

[Rein Halbersma]

A roadmap for future development is roughly as follows
-finishing a generalized BitBoard class that supports arbitrarily large board sizes (in particular 12x12)
-finishing the search() framework (quiescence search, LMR, and other enhancements)
-writing a generalized root driver for the search() based on priority queues
-expanding the evaluation function (only has material, tempo, center, balance and mobility now)
-an opening book generator
-an endgame database generator
-providing GUI functionality (hopefully the GUIDE protocol)
-providing DamExchange functionality (the message layer has already been written)

Any help or ideas are greatly appreciated in this areas!

[jj]

Hi Rein,

An ambitious but very nice project! As I am committed to 10x10 and Java, I won't look into it in more detail. Good luck with 12x12 etc. My first program used an NxN matrix and was able to play any NxN variant using the international rules. Great fun to see the program play itself at 20x20 (2 x 90 men). BTW, can you beat your own program at 10x10?

JJ

[Rein Halbersma]

Hi Rein,

An ambitious but very nice project! As I am committed to 10x10 and Java, I won't look into it in more detail. Good luck with 12x12 etc. My first program used an NxN matrix and was able to play any NxN variant using the international rules. Great fun to see the program play itself at 20x20 (2 x 90 men). BTW, can you beat your own program at 10x10?

JJ

Hi Jan-Jaap,

With an NxN array, things are a lot easier than trying to fit such boards into a 64-bit bitboard
I have a private engine under development that uses the C++ library, but it is not ready to play a full game under a (G)UI. I mainly use it to analyze positions.

Rein

[Rein Halbersma]

DCTL now compiles and runs all unit tests without errors for both Visual C++ 2012 Express and gcc 4.7.2, in both cases with the Boost 1.51.0 libraries. The source can be downloaded from https://bitbucket.org/rhalbersma/dctl/get/gcc-dev.zip

My own environment is Eclipse-CDT with the MinGW gcc compiler (incl. Boost from Stephan T. Lavavej's Nuwen distro at http://nuwen.net/files/mingw/mingw-9.4.exe ) with compiler flags

Code: Select all

g++ -I"C:\MinGW\include\boost" -I"YOUR_HOME_DIR\dctl" -O3 -g3 -pedantic -pedantic-errors -Wall -Wextra -Werror -c -fmessage-length=0

and linker flags

Code: Select all

g++ -L"C:\MinGW\lib" -lboost_unit_test_framework

Here, YOUR_HOME_DIR is the absolute path to your dctl directory. This directory in turn also contains another dctl directory. This enables calling library headers in the notation <dctl/header.hpp> (the famous "stutter" effect used by Boost itself).

In test/test_config.hpp, I have defined several unit tests macros. Setting them to 1 should work except SUCCESSOR_TEST because of an outside error in boost/tr1/detail/config_all.hpp It is possible to comment this out yourself, but I haven't checked in the fix into version control. I suspect that the MinGW combination of Windows platform and Linux conventions is the culprit, so you might have luck under regular linux-gcc. Visual C++ 2012 also could not compile a few Boost headers (but it's not an official Boost compiler). I still have to make header guards for that.

Adapting the library for your own purposes is best done through studying the tests under successor, walk and search. These tests set up positions, and walk or search the game tree from there.

I would be interested in any kind of feedback from users compiling this under LInux or other platforms/compilers (Clang 3.1 should work, lower versions miss some essential C+11 features) Any questions can be posted here or emailed to me.

[AartBik]

This is extremely interesting work! It is nice to see so many variants supported in a single library.
The unit test framework is nice as well.

The library compiles well on Linux, provided, as Rein said, a recent gcc compiler and boost library are used.

[Rein Halbersma]

This is extremely interesting work! It is nice to see so many variants supported in a single library.
The unit test framework is nice as well.

The library compiles well on Linux, provided, as Rein said, a recent gcc compiler and boost library are used.

Thanks Aart, for reporting your experiences.

Prodded by your experiences and those of others, I have ironed out some Windows-specific oddities and cleaned up some bugs. All filenames are completely lowercase now, the SUCCESSOR_TEST macro should now work correctly, and the gcc requirements have been lowered to 4.6 (I got a report from someone of a gcc 4.6.1 success on Linux, and I have checked this with MinGW gcc 4.6.3). Any lower version will not work because of heavily used C++11 features such as lambdas.

Hopefully, the next milestone will be a successful Android compilation, which should be possible as the default Android NDK toolchain is based on gcc 4.6. I hope to report back on that in the coming weeks. Stay tuned...

[Walter Thoen]

Hoi Rein,

I am trying to compile dctl using Visual Studio 2012 Premium. I think I came a long way, but I keep getting errors in intrinsic.hpp. I tried to put the target platform to x64 every where I could see but the compiler intrinsics __popcnt64 and _BitScanForward64 are still not recognised. Any suggestion on how to fix that?

In the version of intrinsic.hpp that I downloaded there also is a problem with the undeclared "mask" in the _BitScanForward64 call. I think "mask" should be "b".

Regards,
Walter

[Walter Thoen]

Hoi Rein,

I am trying to compile dctl using Visual Studio 2012 Premium. I think I came a long way, but I keep getting errors in intrinsic.hpp. I tried to put the target platform to x64 every where I could see but the compiler intrinsics __popcnt64 and _BitScanForward64 are still not recognised. Any suggestion on how to fix that?

In the version of intrinsic.hpp that I downloaded there also is a problem with the undeclared "mask" in the _BitScanForward64 call. I think "mask" should be "b".

Regards,
Walter

I found the problem. x64 was still not set everywhere

Got past intrinsic.hpp, now I need to figure out where all the boost related errors are coming from.

[Rein Halbersma]

Hoi Rein,

I am trying to compile dctl using Visual Studio 2012 Premium. I think I came a long way, but I keep getting errors in intrinsic.hpp. I tried to put the target platform to x64 every where I could see but the compiler intrinsics __popcnt64 and _BitScanForward64 are still not recognised. Any suggestion on how to fix that?

In the version of intrinsic.hpp that I downloaded there also is a problem with the undeclared "mask" in the _BitScanForward64 call. I think "mask" should be "b".

Regards,
Walter

I found the problem. x64 was still not set everywhere

Got past intrinsic.hpp, now I need to figure out where all the boost related errors are coming from.

Hi Walter,

Thanks for trying out my C++ template library! I just made a quick fix consisting of 5 commits in my repository. The latest source is available at https://bitbucket.org/rhalbersma/dctl/get/gcc-dev.zip Notice that this is the feature-branch "gcc-dev" that I am currently developing on. I have now backported all that code to compile and run correctly with Visual C++ 2012 (November 2012 CTP). Apart from a missing #pragma intrinsic(), I also had some type-cast errors for my memory allocators. The latest build is now correctly passing all unit tests. Could you try the latest build?

To run the unit-tests, you need to link against 64-bit Boost libraries. You could consult http://stackoverflow.com/questions/2322 ... it-windows, and replace toolset=msvc-9.0 with toolset=msvc-11.0 in the first answer. There is also a mysterious error in Boost.MPL that I had to patch (and which I didn't document yet, sorry!): you need to replace the file YOUR_PATH_TO\boost_1_52_0\boost\mpl\aux_\preprocessed\plain\arg.hpp with the code below. The only change is that I out-commented a static_assert macro in the struct arg<1>

Spoiler:

Code: Select all

// Copyright Peter Dimov 2001-2002
// Copyright Aleksey Gurtovoy 2001-2004
//
// Distributed under the Boost Software License, Version 1.0. 
// (See accompanying file LICENSE_1_0.txt or copy at 
// http://www.boost.org/LICENSE_1_0.txt)
//

// Preprocessed version of "boost/mpl/arg.hpp" header
// -- DO NOT modify by hand!

BOOST_MPL_AUX_ADL_BARRIER_NAMESPACE_OPEN
template<> struct arg< -1 >
{
    BOOST_STATIC_CONSTANT(int, value  = -1);
    BOOST_MPL_AUX_ARG_TYPEDEF(na, tag)
    BOOST_MPL_AUX_ARG_TYPEDEF(na, type)

    template<
          typename U1 = na, typename U2 = na, typename U3 = na
        , typename U4 = na, typename U5 = na
        >
    struct apply
    {
        typedef U1 type;
        BOOST_MPL_AUX_ASSERT_NOT_NA(type);
    };
};

template<> struct arg<1>
{
    BOOST_STATIC_CONSTANT(int, value  = 1);
    typedef arg<2> next;
    BOOST_MPL_AUX_ARG_TYPEDEF(na, tag)
    BOOST_MPL_AUX_ARG_TYPEDEF(na, type)

    template<
          typename U1 = na, typename U2 = na, typename U3 = na
        , typename U4 = na, typename U5 = na
        >
    struct apply
    {
        typedef U1 type;
        //BOOST_MPL_AUX_ASSERT_NOT_NA(type);
    };
};

template<> struct arg<2>
{
    BOOST_STATIC_CONSTANT(int, value  = 2);
    typedef arg<3> next;
    BOOST_MPL_AUX_ARG_TYPEDEF(na, tag)
    BOOST_MPL_AUX_ARG_TYPEDEF(na, type)

    template<
          typename U1 = na, typename U2 = na, typename U3 = na
        , typename U4 = na, typename U5 = na
        >
    struct apply
    {
        typedef U2 type;
        BOOST_MPL_AUX_ASSERT_NOT_NA(type);
    };
};

template<> struct arg<3>
{
    BOOST_STATIC_CONSTANT(int, value  = 3);
    typedef arg<4> next;
    BOOST_MPL_AUX_ARG_TYPEDEF(na, tag)
    BOOST_MPL_AUX_ARG_TYPEDEF(na, type)

    template<
          typename U1 = na, typename U2 = na, typename U3 = na
        , typename U4 = na, typename U5 = na
        >
    struct apply
    {
        typedef U3 type;
        BOOST_MPL_AUX_ASSERT_NOT_NA(type);
    };
};

template<> struct arg<4>
{
    BOOST_STATIC_CONSTANT(int, value  = 4);
    typedef arg<5> next;
    BOOST_MPL_AUX_ARG_TYPEDEF(na, tag)
    BOOST_MPL_AUX_ARG_TYPEDEF(na, type)

    template<
          typename U1 = na, typename U2 = na, typename U3 = na
        , typename U4 = na, typename U5 = na
        >
    struct apply
    {
        typedef U4 type;
        BOOST_MPL_AUX_ASSERT_NOT_NA(type);
    };
};

template<> struct arg<5>
{
    BOOST_STATIC_CONSTANT(int, value  = 5);
    typedef arg<6> next;
    BOOST_MPL_AUX_ARG_TYPEDEF(na, tag)
    BOOST_MPL_AUX_ARG_TYPEDEF(na, type)

    template<
          typename U1 = na, typename U2 = na, typename U3 = na
        , typename U4 = na, typename U5 = na
        >
    struct apply
    {
        typedef U5 type;
        BOOST_MPL_AUX_ASSERT_NOT_NA(type);
    };
};

BOOST_MPL_AUX_NONTYPE_ARITY_SPEC(1,int, arg)

BOOST_MPL_AUX_ADL_BARRIER_NAMESPACE_CLOSE

Even though this file clearly states *not to edit this file by hand*, it was impossible for me to patch this any other way . These errors were introduced with the Visual C++ 2012 compiler. Unfortunately, the codebase is now too much dependent on C+11 features in Visual C++ 2012 for me to go back to using Visual C++ 2010. I should document this more clearly, sorry again. Note that Boost does not officially support the Visual C++ 2012 compiler yet, nor are there binaries from BoostPro available yet. You should get 100% error-free builds on eiter Linux/gcc or on Windows/MinGW. For the latter, I can recommend http://nuwen.net/mingw.html in combination with Eclipse. However, this only compiles in 32-bit mode.

Hopefully, with the above instructions, you can get it to work correctly. Let me know if you run into any more problems! C++11 support on Visual C++ is still quite flaky and incomplete. I have recently switched to a VirtualBox with Linux Mint 14.1 and the Eclipse IDE with the g++ 4.7.2 compiler (all running inside a Windows host OS). I am still supporting Visual C++, but hopefully the Boost patches will not be necessary after the 1.53 release.

Rein