Confusion about 'decoding' move bitboards

[Mpsey]

I am new in this community and I wanted to clear up some confusion I had with bitboards. Generating move bitboards is pretty straight forward. However, I cannot seem to wrap my head around how these are actually made usable by an engine.

When move bitboards are generated how is it that an engine can get all the moves the bitboard contains and utilize them in terms of make and unmake functions.

It seems like I'm missing a rather large piece of the puzzle here.

Also, how can a list of all moves (those encoded in the move bitboards) be compiled?

I cannot think of efficient solutions to these problems.

My questions are as follows:

1. How can bitboard moves be decoded into physical moves in terms of make/unmake functions?

2. How can a list of all encoded moves be generated

[Aleks Peshkov]

You have to have a function that returns the index (square number) of the first set bit inside a bitboard.
http://chessprogramming.wikispaces.com/BitScan

Using this function you can loop through all set bits.

[Gerd Isenberg]

I am new in this community and I wanted to clear up some confusion I had with bitboards. Generating move bitboards is pretty straight forward. However, I cannot seem to wrap my head around how these are actually made usable by an engine.

When move bitboards are generated how is it that an engine can get all the moves the bitboard contains and utilize them in terms of make and unmake functions.

It seems like I'm missing a rather large piece of the puzzle here.

Also, how can a list of all moves (those encoded in the move bitboards) be compiled?

I cannot think of efficient solutions to these problems.

My questions are as follows:

1. How can bitboard moves be decoded into physical moves in terms of make/unmake functions?

2. How can a list of all encoded moves be generated

Assuming you have the source- or from-square of the piece, and its move-target bitboard, the common way is to serialize the bitboard inside a loop with bitscan, as mentioned by Aleks, and reset-bit of the target squares until target is empty. Inside the loop body, depending on your move-coding you pack from- and to-squares inside a move-structure to append it to the move list ...
i.e.:
http://www.cis.uab.edu/hyatt/bitmaps.html
6. Using bitmaps in a chess engine.

Code: Select all

    piecebd=WhiteQueens;
    while (piecebd) {
      from=LastOne(piecebd);
      moves=AttacksQueen(from);
      temp=from+(queen<<12);
      while (moves) {
        to=LastOne(moves);
        move_list[i++]=temp+to<<6;
        Clear(to,moves);
      }
      Clear(from,piecebd);
    }

see also:
https://chessprogramming.wikispaces.com ... ialization

[Mpsey]

This makes sense to me now thanks. This just didn't seem like an efficient solution.

[hgm]

Well, bitboards are not known for their efficiency...

The efficiency must come from the fact that you don't do it often, because you can select moves through set operations utill there are almost no left, and only then you start to do this.

[Don]

Well, bitboards are not known for their efficiency...

The efficiency must come from the fact that you don't do it often, because you can select moves through set operations utill there are almost no left, and only then you start to do this.

I'm not sure I understand your nomenclature here or how you define efficiency - but the primary benefit of bit-boards is its "data parallel" operations. They probably are not as efficient as simple arrays when you cannot take advantage of that.

Here is one example: Count how many empty square are in front of white pawns. In a typical bit-board program you have a piece array with locations of pieces and you can loop over that, get the address of each pawn, compute an index of the square in front of each of these pawns and count them one by one.

With bit-boards you do most of those operations in parallel, it's sure to be at least 2 or 3 times faster and perhaps more. For example to look at ALL the squares in front of the white pawns is simple, you shift the white pawn bitboard left 8 and compare that with an empty board. The slowest part will be counting the bits - which is still FAR faster than looping over arrays with 2 levels of indirection and having a separate test for each square.

The evidence is pretty strong that bit-board programs are the best way to write chess programs for 64 bit computers but there is no clear way to prove this because you will write programs differently in each case - it's an apples to oranges comparison. So I'm not 100% convinced that bit-board are better, just 90% or something like that. It could just be a fad - the thing to do because the best program happen to currently do it that way. If someone came along and built a chess program that was far stronger than everything else and it did not use bit-boards I think you would see that the new fad would be to avoid using bit-boards!

Bob Hyatt claimed (a long time ago) that bit-boards are superior even on 32 bit computers. I don't know if he still feels that way but if 32 bit machines were all I had to work with I would not be writing a bit-board program.

Don

[Mpsey]

I am enjoying coding with bitboards! I find them to be refreshingly elegant and am enjoying the performance improvements over arrays, even before using magics/rotated boards.

As a continuation of my original question.. I am still not sure at how some problems are solved with bitboards. For instance: when serializing moves how do you detect lets say two knights converging on the same square or perhaps two rooks converging on e1 (Rae1 and Rfe1 for example)?

It seems as if disabiguating here is a costly procedure... I am asking, perhaps from someone who has experience with this problem, If there is a good way of doing this without bottlenecking my engine.

[kbhearn]

You'd do one piece at a time usually. so you'd generate all the moves for the R on a1 and through your serialising with bitscan get Ra1e1 (among others). and then you'd generate all the moves for the R on f1 and get Rf1e1 (among others).

You can also do one direction at a time instead (although honestly it just seems messier for at most 3 pieces per direction usually, backing it up to the correct origin square is also a nuisance) and then you'd get e1 when generating moves along a rank towards h-side, and again when generating moves along a rank towards a-side, and in both cases would be able to back it up to the correct rook.

[Codesquid]

As a continuation of my original question.. I am still not sure at how some problems are solved with bitboards. For instance: when serializing moves how do you detect lets say two knights converging on the same square or perhaps two rooks converging on e1 (Rae1 and Rfe1 for example)?

Doing it the other way around. Let's assume e4 is the convergence square. I'm calculating (lookup in a table actually) all knight moves from e4 on the empty board, intersect it with the knight bitboard and all set bits are then the knights able to reach e4.

Same with rooks. If I want to know whether two rooks converge on e1, I calculate all possible rook moves from that square given the actual occupancy and intersect it with the rook bitboard.

[Gerd Isenberg]

I am enjoying coding with bitboards! I find them to be refreshingly elegant and am enjoying the performance improvements over arrays, even before using magics/rotated boards.

As a continuation of my original question.. I am still not sure at how some problems are solved with bitboards. For instance: when serializing moves how do you detect lets say two knights converging on the same square or perhaps two rooks converging on e1 (Rae1 and Rfe1 for example)?

It seems as if disabiguating here is a costly procedure... I am asking, perhaps from someone who has experience with this problem, If there is a good way of doing this without bottlenecking my engine.

If you focus on a target square with the question which pieces control or can move to this square, you usually put a super piece on that target-square to generate its attacks to intersect it with appropriate pieces. In case of one piece kind of interest, you virtually put that piece on the target-square, generate it knight- or rook-attacks to intersect them with own knights or rooks to see if one or more can move to that target square.

Specially at the tips in qsearch, where it is about to determine (winning) captures in stages, you don't serialize that much, due to intersection of attacks with target pieces to capture. Those intersections, if not empty, are sparsely populated, and if you found the winning capture early in the setwise world of bitboards, it is likely you don't need to serialize other moves at all.