How to make movelist using bitboards

[Gerd Isenberg]

Converting target squares of a bitboard into a list is referred as Bitboard Serialization in CPW. The necessary bit scan might also be done without special bsf, aka trailing zero count instruction (using compiler intrinsics for X64 or ARM ), but portable and quite efficiently by Multiplication of the isolated LS1B with a De Bruijn Sequence, shift right 58 and small lookup.

[hgm]

BTW ~bits + 1 is also known under the name -bits (2-complements system).

[Luis Babboni]

Sorry. I do not catch the idea.
Not how to do it (that is what I feel you tried to explain me), I do not know what I need to do it!

Soberango go piece by piece and move by move and test if it is allowed or not.
Now I understand how to know all the moves that each piece could do.

What is the idea then?
First made all the bitboards with all the moves possible for each piece simultaneously in one bitboard.
Then, as in Soberango, go piece by piece and move by move and use the bitboards to see if each move of each piece is allowed or not?

[Henk]

Testing whether a move is valid because opponent can capture the king is a different story.
Has nothing to do with magic bitboard move generation.

[emadsen]

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.

This code creates a move and adds it to a previously allocated move array. A move is represented as an unsigned long (ulong), so the Move.SetFrom, Move.SetTo, Move.SetCaptureAttacker, etc static methods set various bits in the ulong move to indicate from square, to square, attacking piece and victim piece (for captures), etc. The following code generates knight moves from occupancy bitboards.

Code: Select all

private void GenerateKnightMoves(MoveGeneration MoveGeneration, ulong FromSquareMask)
{
    ulong knights;
    ulong unOrEnemyOccupiedSquares;
    ulong enemyOccupiedSquares;
    int attacker;
    if (WhiteMove)
    {
        // White Move
        knights = WhiteKnights & FromSquareMask;
        unOrEnemyOccupiedSquares = ~OccupancyWhite;
        enemyOccupiedSquares = OccupancyBlack;
        attacker = Piece.WhiteKnight;
    }
    else
    {
        // Black Move
        knights = BlackKnights & FromSquareMask;
        unOrEnemyOccupiedSquares = ~OccupancyBlack;
        enemyOccupiedSquares = OccupancyWhite;
        attacker = Piece.BlackKnight;
    }
    int fromSquare;
    while ((fromSquare = Bitwise.FindFirstSetBit(knights)) != Square.Illegal)
    {
        var knightDestinations = MoveGeneration switch
        {
            MoveGeneration.AllMoves => Board.KnightMoveMasks[fromSquare] & unOrEnemyOccupiedSquares,
            MoveGeneration.OnlyCaptures => Board.KnightMoveMasks[fromSquare] & enemyOccupiedSquares,
            MoveGeneration.OnlyNonCaptures => Board.KnightMoveMasks[fromSquare] & ~Occupancy,
            _ => throw new Exception($"{MoveGeneration} move generation not supported.")
        };
        int toSquare;
        while ((toSquare = Bitwise.FindFirstSetBit(knightDestinations)) != Square.Illegal)
        {
            var victim = GetPiece(toSquare);
            var move = Move.Null;
            Move.SetFrom(ref move, fromSquare);
            Move.SetTo(ref move, toSquare);
            if (victim != Piece.None) Move.SetCaptureAttacker(ref move, attacker);
            Move.SetCaptureVictim(ref move, victim);
            Move.SetIsQuiet(ref move, victim == Piece.None);
            Moves[MoveIndex] = move;
            MoveIndex++;
            Bitwise.ClearBit(ref knightDestinations, toSquare);
        }
        Bitwise.ClearBit(ref knights, fromSquare);
    }
}


public static class Bitwise
{
    public static int FindFirstSetBit(ulong Value)
    {
        return Value == 0
            ? Square.Illegal
            : _longBits - (int) Lzcnt.X64.LeadingZeroCount(Value) - 1;
    }

    public static void ClearBit(ref uint Value, int Index)
    {
        return Value &= ~(1u << Index);
    }
}

• ~ is C#'s bitwise complement operator.
• ?: is C#'s ternary operator. If the condition is true, the code after ? is executed. If false, the code after : is executed.
• Lzcnt.X64.LeadingZeroCount is C#'s "bitscan" operator.
• 1u << Index means shift the value 1 unsigned to the left by Index positions. 1u represented as bits is:
  00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001
  If Index is 5, shift left 5 positions, so you get:
  00000000_00000000_00000000_00000000_00000000_00000000_00000000_00100000

There are two while loops. One loops over all knights for the side-to-move. The other loops over the destination (To) squares of one particular knight. Each while loop finds the first set bit representing a square (0 is a8, 1 is b8... 63 is h1), does some work, then clears the bit so the square is not processed again. And so the while loop doesn't run infinitely.

Do you understand the code?

Generating moves for sliders is more complex. You need to understand how magic bitboards work, which is too large a subject for here. This code generates bishop moves from occupancy bitboards.

Code: Select all

while ((fromSquare = Bitwise.FindFirstSetBit(bishops)) != Square.Illegal)
{
    var occupancy = Board.BishopMoveMasks[fromSquare] & Occupancy;
    var bishopDestinations = MoveGeneration switch
    {
        MoveGeneration.AllMoves => Board.PrecalculatedMoves.GetBishopMovesMask(fromSquare, occupancy) & unOrEnemyOccupiedSquares,
        MoveGeneration.OnlyCaptures => Board.PrecalculatedMoves.GetBishopMovesMask(fromSquare, occupancy) & enemyOccupiedSquares,
        MoveGeneration.OnlyNonCaptures => Board.PrecalculatedMoves.GetBishopMovesMask(fromSquare, occupancy) & ~Occupancy,
        _ => throw new Exception($"{MoveGeneration} move generation not supported.")
    };
    int toSquare;
    while ((toSquare = Bitwise.FindFirstSetBit(bishopDestinations)) != Square.Illegal)
    {
        var victim = GetPiece(toSquare);
        var move = Move.Null;
        Move.SetFrom(ref move, fromSquare);
        Move.SetTo(ref move, toSquare);
        if (victim != Piece.None) Move.SetCaptureAttacker(ref move, attacker);
        Move.SetCaptureVictim(ref move, victim);
        Move.SetIsQuiet(ref move, victim == Piece.None);
        Moves[MoveIndex] = move;
        MoveIndex++;
        Bitwise.ClearBit(ref bishopDestinations, toSquare);
    }
    Bitwise.ClearBit(ref bishops, fromSquare);
}

The code relies on bishop moves already calculated (for any possible occupancy) in PrecalculatedMoves.cs.

[Gerd Isenberg]

Sorry. I do not catch the idea.
Not how to do it (that is what I feel you tried to explain me), I do not know what I need to do it!

Soberango go piece by piece and move by move and test if it is allowed or not.
Now I understand how to know all the moves that each piece could do.

What is the idea then?
First made all the bitboards with all the moves possible for each piece simultaneously in one bitboard.
Then, as in Soberango, go piece by piece and move by move and use the bitboards to see if each move of each piece is allowed or not?

Then, why using bitboards at all?

With bithboards, you can faster mask the target squares for captures say in quiescence search , e.g. by ANDing the queen (or other piece) attacks with opponent pieces. So you don't need to loop over all the empty squares as with mailbox, except you use some incremental updated neighbouring piece datastructures as proposed by HGM. Anyway, this would be a typical bitboard demo serialization loop in FreeBasic, not entirely sure about the syntax:

Code: Select all

Dim As ULongInt deBruijn = &H03f79d71b4cb0a89ull
DIM AS Integer index64(0 to 63) = {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63}
Dim As ULongInt singleBit 
Dim As Integer square
Dim As ULongInt knightBB = &H0000142200221400ull

Do While knightBB <> 0ull
  singleBit = knightBB AND -knightBB
  square = index64((singleBit * deBruijn) shr 58)
  Print square
  knightBB = knightBB AND (knightBB - 1ull)
Loop

[Gerd Isenberg]

BTW ~bits + 1 is also known under the name -bits (2-complements system).

Two's complement as increment of the ones' complement is quite obvious. Adding something to its ones' complement leaves all bits in a word set. Adding one overflows to zero.

Code: Select all

(x + ~x) + 1 == 0

I wonder why there were some ones' complement machines in early times, even the CDC 6000 - CDC 6600 until the late 80s. So Chess 4.x with bitboards had to deal with 60bit registers and ones' complement arithmetic!

[Luis Babboni]

Testing whether a move is valid because opponent can capture the king is a different story.
Has nothing to do with magic bitboard move generation.

No, no, Im trying to say that a pawn could capture in diagonal to right cause there is an oppenent piece or not for example.

[Luis Babboni]

I still cant make you understand my point.

[Luis Babboni]

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

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

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.