How to make movelist using bitboards
Moderators: hgm, Rebel, chrisw
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: How to make movelist using bitboards
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How to make movelist using bitboards
BTW ~bits + 1 is also known under the name -bits (2-complements system).
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: How to make movelist using bitboards
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?
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?
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: How to make movelist using bitboards
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.
Has nothing to do with magic bitboard move generation.
-
- Posts: 434
- Joined: Thu Apr 26, 2012 1:51 am
- Location: Oak Park, IL, USA
- Full name: Erik Madsen
Re: How to make movelist using bitboards
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.Luis Babboni wrote: ↑Fri Feb 19, 2021 3:15 pm 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.
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
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);
}
My C# chess engine: https://www.madchess.net
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: How to make movelist using bitboards
Then, why using bitboards at all?Luis Babboni wrote: ↑Fri Feb 19, 2021 6:35 pm 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?
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
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: How to make movelist using bitboards
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
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: How to make movelist using bitboards
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.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: How to make movelist using bitboards
I still cant make you understand my point.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: How to make movelist using bitboards
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.
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.