How to make movelist using bitboards

[emadsen]

What i do not understand is how to produce EACH possible move.

That’s what I explained in my previous post.

[phhnguyen]

What i do not understand is how to produce EACH possible move.

How use the byte with ALL (say 3) possible moves for some piece to have EACH move separately.
I think I need them separately.

Some previous posts have explained already: you need to find indexes of all bit 1s. An index of a bit 1 is the square your piece will move to.

For example, the bitmap:

Code: Select all

01001000
10000000
00000000
00000000
00000000
00000000
00000000
00000000

have 1s indexes are 1, 4, 8. Thus your piece will have 3 moves with targets 1, 4, 8.

To calculate indexes of bit 1s you need a bitscan algorithm, depend on programming languages and hardware, sometimes it is fast and easy but sometimes may become complicated and slow.

Usually, programmers use a function name pop (or similar), it is a combination of Bitscan and bit-removing, after getting an index it will remove that bit 1 too. For example, after getting the index of the first bit 1, the bitmap becomes:

Code: Select all

00001000
10000000
00000000
00000000
00000000
00000000
00000000
00000000

Suppose you have a Knight attacking from the square "from" and aBB is the bitmap of all attacked points. It may have 3 bits 1 as you mentioned. The code to pickup:

Code: Select all

while aBB != 0 {
  to = pop(aBB);
  move = createMove(from, to);
  store the move in the moveList  
}

More info: https://www.chessprogramming.org/BitScan

[Desperado]

Hi!

I´m a little ashamed cause I cant find what Im looking for so I suspect is very obvious or I missing something important.

I think I´m able to find a bitboard with, for example, a 1 in each of possible moves (say 8) for a given knight and a 0 in all other positions.

My question is how, from that, I could make a list move with those 8 possible moves.
I mean, how to separate each move from others.

Sorry if it is a very stupid question, but I could not find the idea of how make it anywhere. it seems is as obvious that it is not needed to explain it (or as I said, I´m missing something very important)

Thank!

Hello Luis,

Code: Select all

bitboard tmpsrc,tmpdst;

// 1. the source squares are related to a piece for example
tmpsrc = bb_white_knights;

// 2.loop that bitboard
while (tmpsrc) {

    // 2.1 pick every (piece) bit you find, you get the source square
    src = scan_and_remove_bit(tmpsrc)
    
    // 2.2 use the source square to generate the attacked  squares
    // target can be empty squares or opponent squares to be captured for example
    tmpdst = AttackN(src) & target
    
    // 2.3 loop the destination squares
    while (tmpdst) {
        dst = scan_and_remove_bit(tmpdst)
        
        // here you have the pair of squares... store the move in your list.
        AddMove(src,dst...)
    }
}

As pointed out by others you need a function to get the index (0...63) of a bit (like bitscan).

Hope that helps.

Let me ask you, what do need to know to follow the description above?
Maybe i or someone else is able to provide the answer to that piece of your puzzle.

[hgm]

Would you understand the following pseudo-code?

Code: Select all

onebit = 1
for tosquare=0 to 63 do
  if (onebit & bitboard) != 0 then
    GenerateMove(fromsquare, tosquare);
  endif
  onebit = 2*onebit
next tosquare

where GenerateMove would be a function that places the move between the mentioned squares into your move list. The & is the bitwise AND operator, and since onebit is always a word with only a single non-zero bit (which shifts to the next higher bit on every iteration), this AND effectively testst whether the corresponding bit in the bitboard was set.

Now this gives the idea, but unfortunately it is excruciatingly slow (way slower than mailbox). I actually know a program that does it this way: mShogi, the main competitor to my mailbox engine Inferno for Tenjiku Shogi. It runs at 5knps, while in the same position Inferno does about 500knps.

But in short, you don't want to run 64 iterations to extract (maximally) 8 Knight moves from the bitboard. You would want to do that in 8 iterations. (Or in 3, if the Knight is in a location where it only has 3 moves.) So you don't want to work your way through a possibly very large number of 0 bits, (as these give you no moves), but directly skip to the next 1 bit in the bitboard (which then gives you a move):

Code: Select all

while bitboard != 0 do
  tosquare = NumberOfTrailingZeros(bitboard)
  GenerateMove(fromsquare, tosquare)
  bitboard = bitboard & (bitboard - 1)
loop

The bitboard & bitboard-1 trick obliterates the lowest 1 bit in the bitboard. (This is a destructive method; if you wanted to keep the original bitboard, you should have made a copy first.) The following example shows how binary arithmetic makes this work:

00001000010010000000 bitboard
00001000010001111111 bitboard-1
00001000010000000000 bitboard & bitboard-1: rightmost 1 bit is cleared

The secret of course is hidden in NumberOfTrailingZeros(). Modern CPUs have an instruction that does that.

[Sven]

I understand that the use of bitboards allow you to make a faster move generator than not use it. Is this correct?

The move generator might be faster with bitboards than without it. But it is possible that the speed gain for move generation is not as big as you might expect. Usually the bigger gain of using bitboards in a chess engine comes from the evaluation function.

I understand how to produce 64 bits byte with ALL possible moves for each piece.

The word "byte" may be misleading in this context since in our understanding a byte typically has 8 bits. The 64 bit number you produce is usually called "bitboard".

What i do not understand is how to produce EACH possible move.

How use the byte with ALL (say 3) possible moves for some piece to have EACH move separately.
I think I need them separately.

I guess there is something too obvious or too wrong in my thought that you suppouse I obviously know but I do not know.

The bitboard you produce for all possible moves of a given piece represents a set of N target squares (N >= 0), where the position of each "1" relates to one target square. To convert this into a list of N moves you need to create N "move objects" where each object consists of the "from" square that you already know (the square of the given piece), the "to" square which corresponds to one of the 1s in your bitboard, and possibly more information that you store in your "move object" (e.g. a move type, maybe also the type of the captured piece, etc.). If your square representation stored in a move object is not a number between 0 and 63 but something else then you would have to map the 0..63 number to your other representation (but typically a bitboard engine uses 0..63 square encoding everywhere).

Now the only remaining task is to loop over the bitboard, extract the positions of all "1" bits and create a move object from each one. How that works has been explained here by several people. The typical algorithm of looping over a bitboard (not only for move generation - could as well be evaluation etc.) takes the number of the LSB (least significant bit) of your bitboard, does the processing related to the extracted bit position (in your case create a move object), clears the bit, and continues the same way while the bitboard is not zero (i.e. still contains more "1" bits).

[lithander]

Would you understand the following pseudo-code?

I love your explanations!

Step 1: "The slow, intuitive approach would be this." (Yeah, I get that. Easy.)
Step 2: "But you can be smart and do it like this instead!" (Oh, wow! That's genius!)

Have you considered writing a book? I'm sure I would buy it! =)

[Luis Babboni]

"... you need to find indexes of all bit 1s..."

I think that now I understand all!!

Sorry to not understand answeres yet did

[Luis Babboni]

What i do not understand is how to produce EACH possible move.

That’s what I explained in my previous post.

Very sorry.
I read your post again.
It seems you explain me how to do, not what to do.
Of course, Iif I understand how to do, I understand what to do.
But my code understand is as poor that was not possible.
Sorry again.

[Luis Babboni]

Thanks for the time taken for all comments!!

[emadsen]

It seems you explain me how to do, not what to do.

The title of your post is How to make movelist using bitboards.

OK, well hopefully the comments and code here have helped you understand the concept and possible implementations. Let us know if you get it working or get stuck. This community is helpful. Good luck!