Extracting moves from bitboards

[CDaley11]

If I am using a bit board to represent my pieces, then how would I go about extracting the moves from those bit boards? What I mean is this:

Let's say I have a bitboard representing how a white knight on e4 can move. This bit board is calculated right when my program starts. It would look something like this:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0

Then let's say that while generating moves for a position, I AND it with all squares that don't have white pieces and come up with:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0

So it ends up having only 3 legal moves (let's for the moment forget about checks and all that). How would I go about extracting the three moves from this bit board? It seems expensive to loop through this new bitboard and find each of the individual squares it can move to. And even if I do that, how do I store the moves? I'm thinking of storing them as either a separate bit board with only two bits, a from and too. But that would cause problems for castling, promotion, en passant, etc. I could also store it such as:

move = fromSquare * 64 + toSquare

And be able to then take this apart to find what piece is moving where, but this still seems like it would be slow. I've been searching online for quite some time, but I haven't found anything that can help me. There are a plethora of guides on how to generate bitboards that have the legal moves on them, but pretty much nil on how to extract each individual move from these bit boards.

[lucasart]

If I am using a bit board to represent my pieces, then how would I go about extracting the moves from those bit boards? What I mean is this:

Let's say I have a bitboard representing how a white knight on e4 can move. This bit board is calculated right when my program starts. It would look something like this:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0

Then let's say that while generating moves for a position, I AND it with all squares that don't have white pieces and come up with:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0

So it ends up having only 3 legal moves (let's for the moment forget about checks and all that). How would I go about extracting the three moves from this bit board? It seems expensive to loop through this new bitboard and find each of the individual squares it can move to. And even if I do that, how do I store the moves? I'm thinking of storing them as either a separate bit board with only two bits, a from and too. But that would cause problems for castling, promotion, en passant, etc. I could also store it such as:

move = fromSquare * 64 + toSquare

And be able to then take this apart to find what piece is moving where, but this still seems like it would be slow. I've been searching online for quite some time, but I haven't found anything that can help me. There are a plethora of guides on how to generate bitboards that have the legal moves on them, but pretty much nil on how to extract each individual move from these bit boards.

If you can't figure it out, then it's best you do not use bitboards. Bitboards are not for beginners.

Besides, if you use Java forget about bitboards! There are going to be some pretty hairy bit operations to do, and Java is certainly not up to the job (Java is a language for beginners, if you are serious about bitboards you should be a pretty skilled C programmer)

[CDaley11]

I am using C++. Bitboards do seem complicated. How much faster are bitboards than, say, 0x88? I'm really going for speed.

[lucasart]

I am using C++. Bitboards do seem complicated. How much faster are bitboards than, say, 0x88? I'm really going for speed.

Speed is that last thing that matters in a chess engine. Of course, all things equal, speed is a plus.

As for bitboards, read this before writing *any* code

First solve the problem, then write the code!

Generating knight moves is a *trivial* problem!
How are you going to generate bishop moves ?

[ThinkingALot]

then how would I go about extracting the moves from those bit boards?

The best way to learn something about chess engines is to study one. Crafty http://www.craftychess.com/, for example, has a very well commented source code.

[Gerd Isenberg]

Hi,

some related cpw links:
https://chessprogramming.wikispaces.com/BitScan
https://chessprogramming.wikispaces.com ... ialization
for knight moves see
https://chessprogramming.wikispaces.com ... ple%20Bits

Cheers,
Gerd

[CDaley11]

Ok, thank you everyone for putting up with my huge slew of questions lately. I don't think I'll be bothering you much anymore. One last question: While I am using 0x88, is there a huge performance difference between 0x88 and bitboard? I read that bitboard can sometimes be almost twice as efficient as 0x88 using an array with piece codes. Because of there is a big difference, then after I finish my 0x88 engine I may take a look at bitboards again.

[User923005]

You don't bother people by asking questions. Ask until you run out of them. Hopefully, you'll never run out of questions, because that will mean that you are bored of chess programming. Even Robert Hyatt and Don Dailey still ask questions, and they have been chess programming for quite a while now.

The biggest advantage of bitboards is the synergy with all phases of the program.

For instance, you have a built-in piece list so you don't have to invent one and manage it. Further, the piece list is nicely split by types, since the white knights bitboard has all the white knights and nothing else on it. With an array based chess engine, you will have to store this information somewhere, and it will be difficult to make it as efficient as a bitboard storage for processing. Also, evaluation benefits from many bitboard techniques. Consider, for instance, that you can do two shifts with two masks (which guard the far edge where the pawns would go off the board) and generate every single pawn attack. This also tells you which pawns support each other in chains, because if they attack their brothers, then they are a strong defensive line. On the other hand, your bitboard program will probably retain an array board of some kind, since there is still array based information that must be calculated for each cycle.

In the end, what you will probably end up with is a chess engine that has both bitboards and some kind of array for storage and processing of information. The Chess Programming Wiki is a wonderful source of information about almost everything related to chess programming. Really, it is better than any book on it that I have read (Scalable Search in Computer Chess by Heinz is probably the best of those).