Position invariants

[Rein Halbersma]

Apart from the obligatory perft() testing of my move generator, I also have a test function to test the validity of a legal position. My position class has member functions pieces() that take a color and a piece argument (or only one of them, or the special constants occup_c or empty_c) and return the corresponding bitboard. I also maintain global (templated) constants squares_v and promotion_v that are bitboards of all squares and the promotion lines for black and white.

I have a special function assert_invariants() that checks whether the position is legally valid. There are 16 assert() statements inside that function, and it is called inside every constructor and inside make_move(). In debug mode this checks that I am always in a valid position. See below for the code. Note that disjoint(a,b) means !(a & b), using bitwise-AND.

Code: Select all

        void assert_invariants() const noexcept
        {
                assert(squares_v<board_type> == (pieces(occup_c) | pieces(empty_c)));

                assert(pieces(occup_c) == (pieces(black_c) | pieces(white_c)));
                assert(pieces(occup_c) == (pieces(pawns_c) | pieces(kings_c)));

                assert(pieces(black_c) == (pieces(black_c, pawns_c) | pieces(black_c, kings_c)));
                assert(pieces(white_c) == (pieces(white_c, pawns_c) | pieces(white_c, kings_c)));
                assert(pieces(pawns_c) == (pieces(black_c, pawns_c) | pieces(white_c, pawns_c)));
                assert(pieces(kings_c) == (pieces(black_c, kings_c) | pieces(white_c, kings_c)));

                assert(disjoint(pieces(occup_c), pieces(empty_c)));

                assert(disjoint(pieces(black_c), pieces(white_c)));
                assert(disjoint(pieces(pawns_c), pieces(kings_c)));

                assert(disjoint(pieces(black_c, pawns_c), pieces(black_c, kings_c)));
                assert(disjoint(pieces(white_c, pawns_c), pieces(white_c, kings_c)));
                assert(disjoint(pieces(black_c, pawns_c), pieces(white_c, pawns_c)));
                assert(disjoint(pieces(black_c, kings_c), pieces(white_c, kings_c)));

                assert(disjoint(pieces(black_c, pawns_c), promotion_v<board_type, black_>));
                assert(disjoint(pieces(white_c, pawns_c), promotion_v<board_type, white_>));
        }

Does anyone else have such validity testing in their position class?

[Fabien Letouzey]

Hi Rein,

Does anyone else have such validity testing in their position class?

Nothing as thorough!

My "Pos" class is immutable however, so "invariant" doesn't really apply. Therefore I only checked the constructor arguments, but skipped the promotion row by laziness. Most member functions are one liners and, as such, their own "assert" if that makes sense.

I have a mutable "Board" whose responsibility is mostly incremental update (but also game history for repetition detection), and that's what my assertions focus on.

To make it clear, I find what you're doing perfect IF your class is mutable.

Fabien.

[Rein Halbersma]

Hi Rein,

Does anyone else have such validity testing in their position class?

Nothing as thorough!

My "Pos" class is immutable however, so "invariant" doesn't really apply. Therefore I only checked the constructor arguments, but skipped the promotion row by laziness. Most member functions are one liners and, as such, their own "assert" if that makes sense.

I have a mutable "Board" whose responsibility is mostly incremental update (but also game history for repetition detection), and that's what my assertions focus on.

To make it clear, I find what you're doing perfect IF your class is mutable.

Fabien.

After studying your code a bit, your "Pos" class is almost identical to what I call "State" (using the naming convention of Russell & Norvig's AI book). Your "Board" class is what I call "Node" (again using the R&N naming). I can see several of the asserts that I also have, nice!

There are some points I'd like to understand a bit better. In your Board class, you have a member pos of type Pos, similar to how my Node has a member State. However, you also have a whole set of bitboards inside Board that seem to duplicate some of the bitboards inside Pos. It seems like you could eliminate either Pos or some of those bitboards, and thereby save some copying around of those bitboards.

Oh, and regarding copying: I noticed that your Pos class has an init function instead of a constructor, and a copy function instead of a copy constructor. Why are you doing the compiler's work? Also you could emphasize the immutability of your Pos class by eliminating the init() functions and replacing them by constructors. Eg instead of

Code: Select all

class Pos {
     void init(color+bitboards)
     void do_move(Pos&, Pos const&, Move)
};

Pos::do_move(Pos& dst, Pos const& src, Move m)
{
    color + bitboard declarations
    compute color + bitboards from src and m
    dst.init(color+bitboards);
}

Pos dst;
do_move(dst, src, m);

you could do

Code: Select all

class Pos {
     void Pos(color+bitboards)
};

Pos successor(Pos const& src, Move m)
{
   color+bitboard declarations
   compute color+bitboards from src and m
   return Pos(color+bitboards);
}

Pos dst = successor(src, m);

In C++11 the return value is in practice always optimized away (called "return value optimization") and dst is constructed in place (in C++17 it will be guaranteed by the language rules, called "mandatory copy elision").

I use this "functional programming" style excusively. It helps the compiler with aliasing analysis: eg in your do_move, the compiler has to be able to prove that dst and src are not pointing to the same Pos. The compiler cannot always do that without whole-program-optimization.

[Rein Halbersma]

My State class has roughly the following interface (constructor omitted, as well as a few template tricks to select specific bitboards at compile-time):

Code: Select all

enum class color : unsigned char { black, white };
enum class piece : unsigned char { pawn, king };

class set_type /* private bitset implementation wrapping (array of) 64-bit bitboards */;

class State {
     Position m_position;
     color m_color;
public:
     set_type pieces(color) const;
     set_type pieces(piece) const;
     set_type pieces(color, piece) const;
     set_type pieces(occup_c) const;
     set_type pieces(emtpy_c) const;
     color to_move() const;
};

My Position class holds the various bitboards. I have 5 different implementations that I can use, that all provide the various pieces() member functions. The most compact one is holding black and white pieces and kings (which is what Ed and Fabien are using, IIRC):

Code: Select all

        set_type m_color[2];
        set_type m_kings;

Another possibility is to also hold an extra empty bitboard with that (Gerard used to do that). Yet another way of doing this is how Bert once described it by holding 5 bitboards:

Code: Select all

        set_type m_color_piece[2][2];
        set_type m_empty;

For games with more piece types, this does not scale very well (it would have 2 * 6 + 1 = 13 bitboards for chess e.g). I used to prefer what is also done by Stockfish:

Code: Select all

        set_type m_color[2];
        set_type m_piece[2];
        set_type m_empty;

So again 5 bitboards, but it scales as 2 + 6 + 1 = 9 bitboards for chess. But my preferred way of doing things is to use the late Feike Boomstra's representation of

Code: Select all

        set_type m_white;
        set_type m_pawns;
        set_type m_occup;

This is only 3 bitboards, and it is a few percent faster than the good old fashioned black/white/kings method. It is rather counter-intuitive and providing the various pieces() member functions requires a bit of special casing. But it is very fast! For those interested, see the 5 headers at https://github.com/rhalbersma/dctl/tree ... e/position for how I implemented this.

[Fabien Letouzey]

There are some points I'd like to understand a bit better. In your Board class, you have a member pos of type Pos, similar to how my Node has a member State. However, you also have a whole set of bitboards inside Board that seem to duplicate some of the bitboards inside Pos. It seems like you could eliminate either Pos or some of those bitboards, and thereby save some copying around of those bitboards.

The code I started Scan with comes from the time I was writing Fruit, so indexing by piece type seemed natural. The engine, which never went past material only, used both an array and bitboards which explains the unusual (for this community) square numbering for instance.

Pos was a late addition to Scan and I didn't take the time to integrate it properly. As an easy fix to have Board and Pos compatible, I decided to keep the old code and add a separate Pos field.

What you see in the code is a halfway transition from full-Board to full-Pos. Recently I converted Scan to 10x10 Othello and eventually removed Board completely, in big part thanks to repetitions not being possible (not that they matter much in draughts anyway). With that experience, I should be able to choose a clear path to refactor Scan next year.

Oh, and regarding copying: I noticed that your Pos class has an init function instead of a constructor, and a copy function instead of a copy constructor. Why are you doing the compiler's work? Also you could emphasize the immutability of your Pos class by eliminating the init() functions and replacing them by constructors. ...

You're right. I guess Pos was mutable at the beginning (basically Board without the incremental updates and repetition stack) and I didn't notice the change crawling up on me.

In C++11 the return value is in practice always optimized away (called "return value optimization") and dst is constructed in place (in C++17 it will be guaranteed by the language rules, called "mandatory copy elision").

I use this "functional programming" style excusively. It helps the compiler with aliasing analysis: eg in your do_move, the compiler has to be able to prove that dst and src are not pointing to the same Pos. The compiler cannot always do that without whole-program-optimization.

I think Pos started as a subset of Board, then changed little by little. I never took the time to look back at the class as a whole, since in my mind I was in mid-transition anyway. There was no obvious solution to the pattern-index problem however, so I didn't carry it to completion.

[Rein Halbersma]

Oh, and regarding copying: I noticed that your Pos class has an init function instead of a constructor, and a copy function instead of a copy constructor. Why are you doing the compiler's work? Also you could emphasize the immutability of your Pos class by eliminating the init() functions and replacing them by constructors. ...

You're right. I guess Pos was mutable at the beginning (basically Board without the incremental updates and repetition stack) and I didn't notice the change crawling up on me.

Thanks for your explanations on the code history.

Here's how I do repetition detection (inspired by some of Don Dailey's old CCC posts): my Node class is basically a wrapper around State like this

Code: Select all

struct Node {
    State m_state;
    Node* m_parent;
    uint64_t m_hash;
    int m_conversion_ply;
    // some other stuff for exotic draughts variations
};

I do copy-make on Node (which is an immutable class) and trace the m_parent pointers for as long as m_conversion_ply is not reached, checking the stored m_hash keys to detect repetition. It's a bit cache unfriendly when the ply count is high, but copy-make should be making parallelism easier in the future.