Turning bitboards from potential moves into legal moves, pawn moves, and conditional rules.
The BitBoards so far have been astoundingly accurate at producing moves. But even after the moves have been produced they have to be fully validated. Take for instance, a bishop in the middle of the board. The number of potential moves for the bishop is 13 or so, but the number of valid moves, unless no spots are blocked, is much less. Further performing friendly versus non-friendly extension is extremely importan since you can't move into a friendly position, but you can move into the first occuring non-friendly position (capturing). I've found some interesting transformations here, but once I can more fully validate them I'll start to post their intricacies.
Even more frustrating are the pawns. Pawns are capable of special feats when in their original file (forward by 2), they are allowed capturing moves that are different from their standard movement rules, and they are also allowed the ability to capture en-passant. Deciding where and how to implement these extra conditions is very important. Remember the original blocking square algorithm I implemented for removing invalid moves consisted of:
uint myPieces = ...; uint notMine = ~myPieces; uint validMoves = moves & notMine;
This has to be expanded a bit, since notMine actually points to all empty and enemy squares. What we need now is a blocking region for all enemy squares (which we have to store anyway, since eventually the board swaps sides and enemy and friendly are reversed). The valid moves become something like:
uint nonCapture = pawnNonCapture[x]; uint capture = pawnCapture[x];
uint validNonCapture = (~(myPieces & enemyPieces) & nonCapture);
uint validCapture = capture & enemyPieces;
if ( board.enPassant ) { /* special case when prior moves allow */ }
uint validMoves = validNonCapture | validCapture;
Even with all of this magical bit-shifting we aren't accounting for visibility off the first rank. After all, if we are blocked forward 1 and not forward 2, this might still give that as a valid move. After all of this work on pawn movements, it might be better just to leave them to special cased code because of their intricacies compared to other pieces. What can we do then to quickly generate pawn moves? Some ideas are floating around for sure. If I have a BitBoard of all my pawns I can easily do the following:
uint validMoves = (curPawns << 8) & (~(myPieces & enemyPieces)); // one sided, but basically advance and check.
validMoves |= ((validMoves & 0xFF0000) << 8) & (~(myPieces & enemyPieces)); // all that were able to move forward 1, move 2
Some of the above information would be pregenerated, but you can see all of the gruesome details in action. Captures are a basic extension of the above. The basic premise involves 7 or 9 bit shifting operations along with clearing of the overflow file. What do I mean by overflow file? Well, take the rightmost file, h, and then tell me how a pawn would attack off the right side of the board. If we shift by 9 still the pawn in file h, would wrap around and attack the other side of the board. Clearing the pawns in the oveflow ranks is the only way I can think of getting rid of this for now.
uint validCaptures = ((curPawns & clearRank[0]) << 7) & enemyPieces;
validCaptures |= ((curPawns & clearRank[7]) << 9) & enemyPieces;
It is fairly nice to be able to calculate all pawn moves simultaneously in this manner. I'd still calculate en-passant separately because it has side-effects. The attacking square is different from the square where the enemies piece would be removed. It is an extra piece of information that the board has to carry around to make sure that it always performs the appropriate captures.
If you have questions about some of the rules, I actually found the following a bit helpful. I have a chess rules book that I tend to go to first for explanation, especially since I need to ensure accuracy in the engine. When I don't feel like leafing I'll check something out here in the FAQ and then put a little comment in the code to go back later and check the official rules http://www.chessvariants.org/d.chess/faq.html. Even if you know how to play chess, these FAQs can be algorist playgrounds, since often overlooked newbie questions can point out subtleties, patterns and optimizations you might not otherwise dream-up.