PieceLists ?

[phhnguyen]

This is unfair comparison!!!

You said your capture generator simpler than the one of mailbox but actually you are hiding a lot of involving code such as firstOne, lastOne... and a lot of involving data tables... You ignored a huge code to initialise those data tables. You forgot the fact that you have pushed a lot of complexity of bitboards into other places such as board structure, make/takeback functions...

If I do a similar comparison, I can easily pick up many functions of mailboxes (such as moveMake, getPieceTypeAt...) to say mailboxes are much simpler than bitboards

[ZirconiumX]

This is unfair comparison!!!

You said your capture generator simpler than the one of mailbox but actually you are hiding a lot of involving code such as firstOne, lastOne... and a lot of involving data tables...

Actually no, this is all done entirely as part of my board representation. No data tables required, other than that. As for things like CountTrailingZeroes, I'll admit, it's just a mask for a GCC intrinsic.

You ignored a huge code to initialise those data tables.

If you want me to include the code for all of those tables, I would have to include both my attack table update code and my FEN parser. To be honest, the former is just "go through all pieces, calculate the squares they attack".

You forgot the fact that you have pushed a lot of complexity of bitboards into other places such as board structure, make/takeback functions...

I have no takeback function, I just copy the board. MakeMove is difficult only because of maintaining piecelists, but I can take some liberties here and there since I don't need to undo the move.

If I do a similar comparison, I can easily pick up many functions of mailboxes (such as moveMake, getPieceTypeAt...) to say mailboxes are much simpler than bitboards

But there is a practical limit between "showing your code" and "dumping your code". If I included absolutely everything, I would only get a warning from the mods.

[hgm]

It does seem unfair comparison to me. Ad I don't understand the code at all. Where do you generate moves? You extract from-squares from 'attacks', but it is a mystery tome how they get there. All the code says is

Code: Select all

attacks= b->bitlist[dest] & b->sidemask[b->side];

So it seems the set of capturesmust have been pre-existing in b->bitlist.

This way my entire mailbox move generator can be just a single line:

Code: Select all

memcopy(moveList + 256*ply, captures, 4*nrOfCaptures);

[Sven]

It does seem unfair comparison to me. Ad I don't understand the code at all. Where do you generate moves? You extract from-squares from 'attacks', but it is a mystery tome how they get there. All the code says is

Code: Select all

attacks= b->bitlist[dest] & b->sidemask[b->side];

So it seems the set of capturesmust have been pre-existing in b->bitlist.

This way my entire mailbox move generator can be just a single line:

Code: Select all

memcopy(moveList + 256*ply, captures, 4*nrOfCaptures);

As Matthew explained above, "bitlist", "sidemask" and "piecelist" are part of his board representation and are obviously updated incrementally with each move that is made. So his capture move generator is actually both very simple and very clever. Read also the comments inside the code and you can understand how it works. The question "Where do you generate moves?" can be answered by reading as well. The outer loop determines the current target square "dest", the inner loop the current source square "from", and AddMove() adds the move (from+dest) to the move list pointed to by "m". A capture with promotion is handled by AddCapturePromotions() instead. Additionally EP generation is handled fully outside the loop, as everyone else does in his own move generator. Not hard to understand, I think.

Unfair? Because you don't understand the code at all? I thought the competition was mainly about speed ... That you are less experienced in reading bitboard code is not Matthew's fault Of course his makeMove() code will be bigger than it would be for other approaches. Your "memcopy" example would work in a similar way if you would maintain a "captures" array that is updated incrementally during makeMove().

I can imagine that this approach is hard to beat speed-wise under the given rules (currently it only seems to lack support for the "generate in victim value order" requirement). Whether everyone considers it "simple" or not is certainly a matter of taste - in my view it is one of the most simple move generator implementations I have seen so far. One has to consider that it does not follow a "pure bitboard" approach but is based on an attack table that is incrementally updated.

Wasn't it yourself who stated a while ago that you would prefer such an attack table approach over both pure mailbox and pure bitboard approaches?

[phhnguyen]

This is unfair comparison!!!

You said your capture generator simpler than the one of mailbox but actually you are hiding a lot of involving code such as firstOne, lastOne... and a lot of involving data tables...

Actually no, this is all done entirely as part of my board representation. No data tables required, other than that. As for things like CountTrailingZeroes, I'll admit, it's just a mask for a GCC intrinsic.

You ignored a huge code to initialise those data tables.

If you want me to include the code for all of those tables, I would have to include both my attack table update code and my FEN parser. To be honest, the former is just "go through all pieces, calculate the squares they attack".

The problem is that your initial code for those attack tables is basically the code of (or very closed to) mailbox generators (if your implementation is not a very special one). I guess that code alone should be as long as mailbox generators.

You forgot the fact that you have pushed a lot of complexity of bitboards into other places such as board structure, make/takeback functions...

I have no takeback function, I just copy the board. MakeMove is difficult only because of maintaining piecelists, but I can take some liberties here and there since I don't need to undo the move.

Come on. Copying of takeback is not the point to compare since both bitboards and mailboxes can do the same.

I have just implemented bitboards with a piece list thus I have some understanding about them. Piece list may add some few more lines of code to your MakeMove, BUT the main complexity of this function comes from maintaining multi bitboards - thus it should be several times as long as ones of mailboxes. If you use rotated bitboards, your code may be longer at least 1/3.

If I do a similar comparison, I can easily pick up many functions of mailboxes (such as moveMake, getPieceTypeAt...) to say mailboxes are much simpler than bitboards

But there is a practical limit between "showing your code" and "dumping your code". If I included absolutely everything, I would only get a warning from the mods.

No, I don't want to look into your code since you are not ready to show. Just want to add, the comparison of just few function codes says almost nothing, especially about simpleness

[Aleks Peshkov]

I do not consider given code reasonably elegant. Generating attacks of pieces is not equal to generating legal moves.

What is elegant is to transform attacks bitboards into legal move bitboards generically as possible.

[Sven]

I do not consider given code reasonably elegant. Generating attacks of pieces is not equal to generating legal moves.

The challenge set up by HGM in this thread ("I claim I can write a capture generator that is both faster and simpler than any bitboard generator could ever be.") was not about legal moves but only about pseudo-legal captures. The given code must be seen in that context.

[Sven]

If I do a similar comparison, I can easily pick up many functions of mailboxes (such as moveMake, getPieceTypeAt...) to say mailboxes are much simpler than bitboards

But there is a practical limit between "showing your code" and "dumping your code". If I included absolutely everything, I would only get a warning from the mods.

No, I don't want to look into your code since you are not ready to show. Just want to add, the comparison of just few function codes says almost nothing, especially about simpleness

"Not ready to show" is a brave statement, considering that Dorpsgek (the engine from which that special capture generator code was derived) is open source ...

[ZirconiumX]

It seems I need to explain how the code works, since I have a lot of people saying a lot of wildly different things about my code.

It is based on an old post by Andrew Tridgell (https://groups.google.com/forum/#!msg/r ... yOjo4ybE0J) in RGCC in 1999, but contains a few innovations of my own (so far as I can tell).

Here is my board structure:

Code: Select all

struct Board {
    uint32_t bitlist[64]; /* For each square, what pieces attack it? */
    char piecelist[32];   /* For each piece, which square is it on? */
    char index[64];       /* For each square, which piece is on it? */
    uint32_t sidemask[2];
    char side;
    char castle;
    char ep;
    char fifty;
    uint32_t piecemask[6];
    uint64_t hash;
    uint32_t rep[100];
};

Most of it is reasonably self-explanatory, I think.

Bitlist is my attack table, which states which pieces attack this square for a given square. Each piece has its own unique bit. This gets updated after MakeMove().

Sidemask is a mask that contains all the piece bits for a given side. Likewise, piecemask is a mask that contains all the piece bits for a given piece type.

Bitlist, sidemask and piecemask all have a one-to-one correlation in that the Nth bit refers to the Nth piece for all of them. (What N actually is does not matter, so long as it is less than 32 for my case.) In Tridgell's post, sidemask and piecemask were fixed macro constants that I felt were too inflexible, so I took the liberty of making them variables of the board structure instead.

Of course, these bits alone are meaningless - they do not correlate to a square at all. For this, I have index and piecelist. Index is about as close to a mailbox as I get - it states what N is for a given square, or INVALID if there is no piece on that square. Likewise, piecelist is a piecelist, that states what square a piece is on for a given N, or INVALID if there is no piece there.

With all this in mind, let's revisit the capture generator I posted earlier. The algorithmic skeleton looks like this, with how the code does it in comments:

Code: Select all

int GenerateCaptures(...)
{
    enemy_pieces = GetEnemyPieces(); // Done by a sidemask lookup.

    for each enemy in enemy_pieces { // Done by LSB counting of enemy_pieces.
        enemy_square = GetPieceSquare(enemy); // Done by a piecelist lookup.
        attacks = GetFriendlyAttacksToSquare(enemy_square); // Done by the intersection of the attack table entry
                                                            // and sidemask for the friendly side.
        for each friend in attacks { // More LSB counting.
            // Remember that my attack table stores an entry as a piece attack to this square.
            friendly_square = GetPieceSquare(friend); // Piecelist lookup.
        
            if (IsPawn(friend) && // Piecemask intersection.
                IsCapturePromotion(friendly_square)) { // Rank calculation.
                
                AddCapturePromotions(friendly_square, enemy_square); // Add to movelist.
                
                continue;
            }
            
            AddCapture(friendly_square, enemy_square); // Add to movelist.
        }
    }
    
    if (CanEnPassant()) { // b->ep != INVALID
        enemy_square = EnPassantSquare();
        attacks = GetFriendlyPawnAttacksToSquare(enemy_square); // More mask intersection.
        
        for each friend in attacks { // More LSB counting. Max 2 iterations.
            friendly_square = GetPieceSquare(friend); // Piecelist lookup.
            
            AddEnPassant(friendly_square, enemy_square);
        }
    }
    
    return MoveList(); // I actually return movecount, with movelist as an out parameter.
}

Is it perfect? No. I do still rely on the attack table code heavily and pay in speed, but I think this elegance is worth it, and it relies on no external tables - all of the data is within the board representation.

[hgm]

As Matthew explained above, "bitlist", "sidemask" and "piecelist" are part of his board representation and are obviously updated incrementally with each move that is made. So his capture move generator is actually both very simple and very clever.

Except that it is not a capture generator. It is just code that extracts moves from an attack map. An attack map is just a data structure to hold previously generated moves. My mailbox code would practically look the same. The nested loops over victims (outer) and attackers (inner) is forced by the requirement of the problem (generating captures in MVV order).

Read also the comments inside the code and you can understand how it works. The question "Where do you generate moves?" can be answered by reading as well. The outer loop determines the current target square "dest", the inner loop the current source square "from", and AddMove() adds the move (from+dest) to the move list pointed to by "m". A capture with promotion is handled by AddCapturePromotions() instead. Additionally EP generation is handled fully outside the loop, as everyone else does in his own move generator. Not hard to understand, I think.

Sure,I understand all that, of course. At least enough to see that none of this code has anything to do with move generation. More like move sorting.

Unfair? Because you don't understand the code at all? I thought the competition was mainly about speed ...

Where did you get that silly idea? For one, it was about simplicity + spead. Secondly the shown code is just a tiny fraction of the code needed, which only covers an insignificant fractio of the task. So to present it as an example of how simple a bitboard generator is is totally misleading. My guess is that ther real code needed to do the job is at least 20 times larger (if not 50).

That you are less experienced in reading bitboard code is not Matthew's fault Of course his makeMove() code will be bigger than it would be for other approaches. Your "memcopy" example would work in a similar way if you would maintain a "captures" array that is updated incrementally during makeMove().

When you generate moves incrementally, MakeMove of course becomes an integral part of the move generator. If not, my code would be infinitely simpler than what Matthew presents, because it takes exactly zero lines, and zero clock cycles to execute. Because I would store the move list as an incrementally updated bit set, and after the incremental update there is nothing left to to than making the moves. (Move extraction is not needed, because the bits corresponding to the captures are already in MVV/LVA order.

I can imagine that this approach is hard to beat speed-wise under the given rules (currently it only seems to lack support for the "generate in victim value order" requirement).

That depends completely on how he updates the attacks map. If he uses bitboards for that I could probably do it much faster.

Whether everyone considers it "simple" or not is certainly a matter of taste - in my view it is one of the most simple move generator implementations I have seen so far. One has to consider that it does not follow a "pure bitboard" approach but is based on an attack table that is incrementally updated.

Wasn't it yourself who stated a while ago that you would prefer such an attack table approach over both pure mailbox and pure bitboard approaches?

Sure, incrementally updated attack tables can be much faster than move generation from scratch. Which has exactly zero bearing on the issue, which was whether mailbox is faster and simpler than bitboards. Plus that the attack maps usually badly lose on simplicity, which was also an issue in the original formulation of the problem. The challenge was to come with something that was both simpler and faster. That complex solutions can be faster than simple ones is hardly a world-shocking discovery.