Move generation for bitboards

[emadsen]

I am not sure if I am clear. When I generate moves I want to get all possible moves in a moves list which I can then loop over in negamax function. The questions are regarding how to encode a move to put in the list, and how to retrieve the move parameters from the bitboard with possible attack/quit squares.

I just pack everything into a ulong. This has the advantage that sorting the ulong[] of moves gives the highest priority moves first (TT move, captures by MVV/LVA, pawn promotions, killer value, then history value).

I assign most move properties during pseudo-legal move generation. However, I assign killer value and history value (then sort) immediately before searching moves. Motivated by separation of concerns: I don't want move generation code to know anything about search heuristics.

As my code demonstrate, I retrieve move properties via static methods that bitmask and shift contents in and out of the move ulong.

[pedrojdm2021]

For move generation i basically just followed the guide from Code Monkey King in his youtube series, and also i took a little of inspiration from cosette ( for move formatting )

My move formatting is as follows:

Code: Select all

/* 
        A chess movement is encoded in 16 bits:                           binary:
        
        bit 0-6   : square from                                           0000 000000 111111
        bit 7-12  : square to                                              0000 111111 000000
        bit 13-16 : Flag                                                     1111 000000 000000
*/

The flag is very similar as the moveFlag in cosette, an enum starting from index 0, to index 12

My moves are not in an struct, i encode the moves in just an unsinged int of 16 bits. ( 'ushort' type in C# ), i encode them using binary shifts and operators.

I basically have a flag to generate or not quiet moves in the generate moves function (that flag is disabled in QS, you'll know that later)

In my experience is better to encapsulate the pseudo-legal move generation in a single function, rather than having separate functions and call them all in the main "generateMoves()" function.

i first generate:

- King moves
if there's double check, return the list early, if not i countinue generating the remaining moves.

i just use bitmasks to check if the piece is attacking another piece, and i substract the attacks from my friendly pieces ( we don't want friendly fire )

To give you an example, this is for attacks for knights:

Code: Select all

  // ---------------- [  Knight ] --------------------

           pieces = bitboards[sideToMove] & bitboards[ChessPiece.Knight];

            while(pieces > 0)
            {
                square_from = BitUtility.GetLS1BIndex(pieces);
                BitUtility.RemoveLS1B(ref pieces);
                moves = GetKnightMoves(square_from) & ~bitboards[sideToMove];
                while(moves > 0)
                {
                    square_to = BitUtility.GetLS1BIndex(moves);
                    BitUtility.RemoveLS1B(ref moves);
                    flag = BitUtility.ContainsBit(bitboards[sideToMove ^ 1], square_to) ? MoveFlag.Capture : MoveFlag.Quiet;
                    if (flag == MoveFlag.Quiet && !_GenerateQuiets) continue;
                    moveslist[++moveIndex] = MoveUtility.Encode_move(square_from, square_to, flag);
                }
          }

My bitboard representation is an array of 8 bitboards:
index 0 = blakck bitboard
index 1 = white bitboard
index 2 = all pawns bitboard
index 3 = all knights bitboards
and so on...

so to get just the black pawns you have to do (bitboards[pawn] & bitboards[black]) and it will give you the correct bitboards.

I hope my information helps a little. Good luck with your engine and have fun!

[eligolf]

Thank you guys for the inspiration!

Yes I ended up choosing something similar to Code Monkey King with saving it as a ulong and encode/decode with bitshifts. It seems easy enough to understand and fast enough to be used in an engine

Fun, frastrating and addictive, I guess that sums up creating a chess engine haha...

[hgm]

So what is the attraction of encoding the piece locations as an array of bitboard[pieceType], rather than just an array of piece locations (pieceList[pieceType][n])? In the latter case you would just loop through the list to get the from-squares of the pieces, which doesn't seem any slower than extracting the bits from the bitboards. I do of course see that having the total occupancy of the board as a bitboard can be useful, for generating slider moves.

[lithander]

So what is the attraction of encoding the piece locations as an array of bitboard[pieceType], rather than just an array of piece locations (pieceList[pieceType][n])? In the latter case you would just loop through the list to get the from-squares of the pieces, which doesn't seem any slower than extracting the bits from the bitboards. I do of course see that having the total occupancy of the board as a bitboard can be useful, for generating slider moves.

One thing I liked about the bitboards is that it makes copy/make really feasible. It's possible to encode all pieces in just four bitboards but even if you use more it's still quite fast to copy the full boardstate.

And it's just fun to learn/come up with all these bit-fiddling techniques that rely on the lucky coincidence that the 64 squares of a chessboard correspond exactly to the 64bit of long and everybody is using 64bit systems these days.

[dangi12012]

So what is the attraction of encoding the piece locations as an array of bitboard[pieceType], rather than just an array of piece locations (pieceList[pieceType][n])? In the latter case you would just loop through the list to get the from-squares of the pieces, which doesn't seem any slower than extracting the bits from the bitboards. I do of course see that having the total occupancy of the board as a bitboard can be useful, for generating slider moves.

One thing I liked about the bitboards is that it makes copy/make really feasible. It's possible to encode all pieces in just four bitboards but even if you use more it's still quite fast to copy the full boardstate.

And it's just fun to learn/come up with all these bit-fiddling techniques that rely on the lucky coincidence that the 64 squares of a chessboard correspond exactly to the 64bit of long and everybody is using 64bit systems these days.

You can also do 3 Bitboards. With this config: 64bits occupy, 32x4bits of 4 bit nibble data = 3x64bit.
A move would just be a nibble insert and one mask clear.

For my fast movegenerator I had the board in the native expanded 12x uint64_t form. A move is one uint64_t corresponding to from | to.
So you just have to XOR the target BB to apply a move. Board.Pawns ^= (from | to). So a native move (which can move any amount of pieces really) is just one uint64_t

[hgm]

One thing I liked about the bitboards is that it makes copy/make really feasible. It's possible to encode all pieces in just four bitboards but even if you use more it's still quite fast to copy the full boardstate.

And it's just fun to learn/come up with all these bit-fiddling techniques that rely on the lucky coincidence that the 64 squares of a chessboard correspond exactly to the 64bit of long and everybody is using 64bit systems these days.

Well, a bitboard is 8 bytes, so four bitboards is 32 bytes. The location of a piece can be stored in a single byte. To do that for all pieces is also only 32 bytes. So w.r.t. copy-make there doesn't seem to be any advantage at all.

[lithander]

Well, a bitboard is 8 bytes, so four bitboards is 32 bytes. The location of a piece can be stored in a single byte. To do that for all pieces is also only 32 bytes. So w.r.t. copy-make there doesn't seem to be any advantage at all.

So there's no other data structure other than piece lists in your suggested board representation? No mailbox array that you can index by square for example? How do you lookup the piece on a specific square, then, without looking through all of the 32 slots? (or maybe that's fast enough?)

[dangi12012]

One thing I liked about the bitboards is that it makes copy/make really feasible. It's possible to encode all pieces in just four bitboards but even if you use more it's still quite fast to copy the full boardstate.

And it's just fun to learn/come up with all these bit-fiddling techniques that rely on the lucky coincidence that the 64 squares of a chessboard correspond exactly to the 64bit of long and everybody is using 64bit systems these days.

Well, a bitboard is 8 bytes, so four bitboards is 32 bytes. The location of a piece can be stored in a single byte. To do that for all pieces is also only 32 bytes. So w.r.t. copy-make there doesn't seem to be any advantage at all.

Piecelist is the worst board structure. No way to do rayscan and you still need to maintain neighbour tables - which you also need to copy for copy make or you have to recalculate those.
Moving a piece on a bitboard is this operation: BB ^= move. = 1 instruction
Moving a piece on a mailbox is: brd[to] = brd[from]; brd[from] = 0; = 3 lookups and 2 assignments

[eligolf]

Short update for those interested:

- Move generation completed
- Make and unmake move functions done
- All perfts from https://www.chessprogramming.org/Perft_Results completed (with depths that gives nodes < 50.000.000 or so
- Nodes/s is around 1-2 million right now.

Should I try to make the move generation and make/unmake move functions faster than this before continuing with next phases of incorporating the engine itself? Or is this good enough in C# to continue?

Thanks all for the support so far, the helpfullness of people here always amazes me. I hope to one day be able to help people too here when being more experienced