PieceLists ?

[phhnguyen]

I have just completed a quick test for measuring performances of some bitboards with/without piece lists. That is for Xiangqi (Chinese chess) but I believe the result is very close to chess too.

1) Standard BB: it is a “typical” one with rotated bitboards, using functions firstOne, takeOne... to get piece positions when generating moves, evaluating. To get piece type of a given position the code needs to check about 7 bitboards.

2) BB with piece list: it is actually (1) + a piece list. The bad point is that it has some extra code to update the piece list when making/taking back moves. It is a bit annoying since I cannot add back pointers from the board to piece list (we could do that for mailboxes) thus the code has to scan the piece list to find positions or empty slots. The good point is that now it can get benefit from piece list when generating moves and evaluating since it doesn’t need to call firstOne/takeOne and many while-loops. To get the piece type of a given position the code needs to check about 16 items in the piece list. For my implementation, look like functions incheck, getPieceType (for a given position) don’t get benefit from that piece list.

3) BB with piece list and evaluation of (1): Since my evaluation function is so simple, just count material and square scores, using only piece list may give 2 too much advantage to 1 (and may be far from real and full evaluations). Thus this implementation doesn’t use the piece list for evaluation, but copy the evaluation code of 1. I just want to make sure the board can get benefit from piece list for move generators / make / unmake instead of mainly from evaluation.

The search function of the test is implemented with straightforward / simple alphabeta, quiescent, hash table, null moves... It searches to depth 7. All statistics are collected after searching 50 game positions (which are randomly picked from real human master games). All search trees are identical (based one numbers of nodes and all other stats). Bellow is elapsed times in seconds:

Code: Select all

1) Standard BB:                           7434s (116.6%)
2) BB + a piece list:                     6372s (100%)
3) BB + a piece list + eval (1):          7406s (116.2%)

Conclusions:
1) Depend on implementation such as using a simple evaluation, bitboards + piece list may gain some performance. Otherwise it may gain very little or almost nothing
2) Look like bitboards + piece list is not a big winner but not a loser either. You may implement and improve it for better performance later

[abulmo2]

Actually, it's very hard to beat the raw performance of a well-written mailbox move generator.

Maybe, but I have not seen a really fast maibox generation yet. Do you have an example?

Bitboard serialisation is not particularly fast and magic bitboards consume a fair chunk of cache space.

Bitboard serialisation is not that slow either and if memory cache is a problem, alternatives to magic bitboard move generators exist: rotated bitboard, kindergarten, hyperbola quintessence, etc.

[hgm]

Maybe, but I have not seen a really fast maibox generation yet. Do you have an example?

qperft?

The main problem with mailbox is not general move generation, but selective capure generation for in QS. But this plays no role in perft. (Where the main problem is to do move-legality checking in the finalply, which again is irrelevant for an engine.)

The best solution for fast selective capture generation with mailbox is to keep a viewDistance data structure,which for each occupied square keeps track of the distance to the nearest obstacle in each of the 8 directions. Such a data structure can be updated incrementally quite cheaply. This then allows you to do cheap 'inverse' capture generation, where you generate the captures victim by victim, by checking the 8 neighbors on the board for being enemies moving towards you, and the two Knights from the piece list (with the usual 0x88 test).

At first glance this seems more work per enemy piece than you would have to do for generating moves for each of your own pieces (as these move often in only 4 or 2 directions, and you know which from the piece type). But because you generate in MVV order, you can limit the generation to non-futile victims. And when you start searching moves immediately after you generated them for a certain victim value class, getting a beta cutoff would save you the trouble of generating captures on all other victims. So it is very competitive.

[Sven]

When looking up what piece is on a particular square it is probably faster to look it up in an array than in a set of bit boards. How many bit boards are there ? Five or six perhaps.

I don't think there is a winner between checking 16 item-array and 6 bitboards since the number of IFs is about 3 times as many.

IMO the point of Henk was a different one. To look up which piece (piece type + color) is on a given square is usually a loop if you only have bitboards: "Is it a pawn? No. - Is it a knight? No. - ..." While with an array of, say, 64 entries you simply have one array access. And that is the reason why bitboard engines typically also maintain a "redundant" classical board array, to also satisfy the requirement of retrieving color and type of a piece on a given square.

[abulmo2]

Maybe, but I have not seen a really fast maibox generation yet. Do you have an example?

qperft?

Of course, your program belongs to the hall of fame of chess computer history. It is indeed fast; but, for the sake of optimization, it is hardly maintainable¹ and on occasion not correct². So, despite its speed I am not sure it is a good example. Its speed is not that much extraordinary either. On my computer, qperft without hash is only 5%~10% faster than Amoeba own perft, that could be optimized further quite easily to outperform qperft (specialised bulk counting of the last move, removal of a few useless data, etc.).

The main problem with mailbox is not general move generation, but selective capure generation for in QS

Right, and the bitboard approach is much simpler to implement than any maibox one.

¹ global variables, gotos, inconsistent style, dozens of unused variables, duplicated code, wrong comments, etc.
² http://www.talkchess.com/forum/viewtopic.php?p=619313

[hgm]

It is indeed fast; but, for the sake of optimization, it is hardly maintainable¹ and on occasion not correct².

That was not a problem caused by the move generator. There was a bug with hashing, and setting the initial conditions on which the move generation was based in the root.

Who cares about 'maintainability' of a move generator? Once it works, it works,and there is no need to ever touch it again.

Right, and the bitboard approach is much simpler to implement than any maibox one.

That is a highly dubious statement. How do you define 'simpler'? Number of characters of the source code?Lines of code? Number of statements? I expect a bitboard move generator to be at least 10 times larger in any metric complexity metric than a straightforward mailbox one.

[abulmo2]

Who cares about 'maintainability' of a move generator? Once it works, it works,and there is no need to ever touch it again.

I do. You or someone else may want to improve it one day for example, or extend it to play a chess variant, or make it multithreaded, or port it to another language. All those tasks are much easier from a readable and maintainable code.

Right, and the bitboard approach is much simpler to implement than any maibox one.

That is a highly dubious statement. How do you define 'simpler'? Number of characters of the source code?Lines of code? Number of statements? I expect a bitboard move generator to be at least 10 times larger in any metric complexity metric than a straightforward mailbox one.

I was speaking of the capture move generator used in QS (and in staged move generation), much easier to implement with bitboard than with maibox, with a similar speed of course.

[phhnguyen]

I have just completed a quick test for measuring performances of some bitboards with/without piece lists. That is for Xiangqi (Chinese chess) but I believe the result is very close to chess too.

1) Standard BB: it is a “typical” one with rotated bitboards, using functions firstOne, takeOne... to get piece positions when generating moves, evaluating. To get piece type of a given position the code needs to check about 7 bitboards.

2) BB with piece list: it is actually (1) + a piece list. The bad point is that it has some extra code to update the piece list when making/taking back moves. It is a bit annoying since I cannot add back pointers from the board to piece list (we could do that for mailboxes) thus the code has to scan the piece list to find positions or empty slots. The good point is that now it can get benefit from piece list when generating moves and evaluating since it doesn’t need to call firstOne/takeOne and many while-loops. To get the piece type of a given position the code needs to check about 16 items in the piece list. For my implementation, look like functions incheck, getPieceType (for a given position) don’t get benefit from that piece list.

3) BB with piece list and evaluation of (1): Since my evaluation function is so simple, just count material and square scores, using only piece list may give 2 too much advantage to 1 (and may be far from real and full evaluations). Thus this implementation doesn’t use the piece list for evaluation, but copy the evaluation code of 1. I just want to make sure the board can get benefit from piece list for move generators / make / unmake instead of mainly from evaluation.

The search function of the test is implemented with straightforward / simple alphabeta, quiescent, hash table, null moves... It searches to depth 7. All statistics are collected after searching 50 game positions (which are randomly picked from real human master games). All search trees are identical (based one numbers of nodes and all other stats). Bellow is elapsed times in seconds:

Code: Select all

1) Standard BB:                           7434s (116.6%)
2) BB + a piece list:                     6372s (100%)
3) BB + a piece list + eval (1):          7406s (116.2%)

Conclusions:
1) Depend on implementation such as using a simple evaluation, bitboards + piece list may gain some performance. Otherwise it may gain very little or almost nothing
2) Look like bitboards + piece list is not a big winner but not a loser either. You may implement and improve it for better performance later

In my latest test with double data , [3] is actually a winner, faster than [1] over 10%. I am going to do some steps to check and explain the results as well as testing with higher depths and bigger data.

[hgm]

I was speaking of the capture move generator used in QS (and in staged move generation), much easier to implement with bitboard than with maibox, with a similar speed of course.

Well, I also doubt that. Bitboard generators are intrinsically complex, bacause of all the tables they need.

So I am willing to take up the challenge: I claim I can write a capture generator that is both faster and simpler than any bitboard generator could ever be. (And maintainable! ) The question is how to measure it. Perhaps this should be done in a captures-only perft from some positions with many captures. To not contaminate the matter with issues of little relevace for the speed of an engine, we could count pseudo-legal moves. (I.e. assume moving in check is legal, and that King capture terminates the game.) As a requirement the captures should be generated in victim value order, so that staged move generation is possible. (Which would have no advantage at all in perft.)

[ZirconiumX]

Here's the Dorpsgek capture generator, which is neither here nor there.

Since this relies on attack tables, it might not be considered all that fast...

Code: Select all

int GenerateCaptures(struct Board * b, struct Move * m)
{
    int index, attacks, movecount, type;
    int from, dest, bit;

    movecount = 0;

    /* Iterate over all enemy piece */
    index = b->sidemask[!b->side];

    while (index) {
        bit = CountTrailingZeroes(index); /* Retrieve index of lowest attacker. */
        dest = b->piecelist[bit];    /* Retrieve the square it is on. */
        index &= index - 1;

        /* Friendly attacks to this square. */
        attacks = b->bitlist[dest] & b->sidemask[b->side];
        while (attacks) {
            bit = CountTrailingZeroes(attacks); /* Retrieve index of lowest attacker. */
            from = b->piecelist[bit];    /* Retrieve the square it is on. */
            attacks &= attacks - 1;

            /* Captures with promotion */
            if (&#40;1 << bit&#41; & b->piecemask&#91;PAWN&#93; &&
                (&#40;b->side == WHITE && ROW&#40;from&#41; == 6&#41; ||
                &#40;b->side == BLACK && ROW&#40;from&#41; == 1&#41;)) &#123;

                AddCapturePromotions&#40;b, m, &movecount, from, dest&#41;;

                continue;
            &#125;

            /* Add this move to the list and increment the pointer. */
            AddMove&#40;b, m, &movecount, from, dest, MoveTypeCapture&#41;;
        &#125;
    &#125;

    /* En passant */
    if &#40;b->ep != INVALID&#41; &#123;
        dest = b->ep;

        /* Friendly pawn attacks to the EP square. */
        attacks = b->bitlist&#91;dest&#93; & b->sidemask&#91;b->side&#93; & b->piecemask&#91;PAWN&#93;;
        while &#40;attacks&#41; &#123;
            bit = CountTrailingZeroes&#40;attacks&#41;; /* Retrieve index of lowest attacker. */
            from = b->piecelist&#91;bit&#93;;    /* Retrieve the square it is on. */
            attacks &= attacks - 1;

            /* Add this move to the list and increment the pointer. */
            AddMove&#40;b, m, &movecount, from, dest, MoveTypeEnPassant&#41;;
        &#125;
    &#125;

    return movecount;
&#125;

(fluff like move bonuses removed.)

...But I consider it reasonably elegant. Loop over all enemy pieces, loop over all possible attacks to that square, and add any promotions if needed.