Sliding pieces move generation
Posted: Fri Jul 27, 2012 10:20 pm
I'm trying to develop my own chess engine in C#. Recently I switched to bitboards and I'm rewriting my move generator: I implemented pawn, knight and king move generation, but now I'm stuck with sliding piece move generation (queen, rook and bishop)... I would like to use an occupancy look-up approach like shown here: https://chessprogramming.wikispaces.com ... nk+Attacks
but, maybe for my english, I really can't understand how should I proceed. I really need a clear explanation about all this stuff, maybe with some pseudo-code implementation (or better in C#, Java, C++, ecc.). More specifically I can't understand how sould I initialize the attack array for files and ranks (but please, don't focus only on this topic
)... I would be very grateful to anyone who will explain clearly and in depth Sliding piece move generation.
if needed, I post my implementation of NON-Sliding piece move generation:
Here is my MoveGenerator static class:
I use a delegate to abstract move serialization, cause every piece type has his own "GetTargets" method.
this is my color-generalized Pawn class:
and here are my King and Knight classes:
I would like to emphasize that a clear and detailed answer would be a LOT BETTER than an "useful link", for me and for everyone who will visit this thread
thanks to all
Edit: this is my BitBoard wrapper for UInt64, it is responsible to display bitboards, calculate population count, bitscan,ecc.ecc.
but, maybe for my english, I really can't understand how should I proceed. I really need a clear explanation about all this stuff, maybe with some pseudo-code implementation (or better in C#, Java, C++, ecc.). More specifically I can't understand how sould I initialize the attack array for files and ranks (but please, don't focus only on this topic
)... I would be very grateful to anyone who will explain clearly and in depth Sliding piece move generation.if needed, I post my implementation of NON-Sliding piece move generation:
Here is my MoveGenerator static class:
Code: Select all
internal static class MoveGenerator
{
private static List<Move> moveList = new List<Move>();
private static BitBoard targets;
private static Square fromSquare;
private static Square toSquare;
private static int fromIndex;
private static int toIndex;
private delegate BitBoard GetTargetsDelegate(PieceColor color, BitBoard pieces, Board board);
private static List<Move> ExtractMoves(PieceColor color, PieceType type, BitBoard pieces, Board board, GetTargetsDelegate getTargets)
{
moveList.Clear();
while (pieces != 0)
{
fromIndex = BitBoard.BitScanForwardReset(ref pieces); // search for LS1B and then reset it
fromSquare = new Square(fromIndex);
targets = getTargets.Invoke(color, BitBoard.ToBitBoard(fromIndex), board);
while (targets != 0)
{
toIndex = BitBoard.BitScanForwardReset(ref targets); // search for LS1B and then reset it
toSquare = new Square(toIndex);
moveList.Add(new Move(fromSquare, toSquare, type));
}
}
return moveList;
}
internal static List<Move> GetAllMoves(PieceColor color, Board board)
{
List<Move> allMoves = new List<Move>(30);
allMoves.AddRange(GetPawnMoves(color, board.GetPieceSet(color, PieceType.Pawn), board));
allMoves.AddRange(GetKnightMoves(color, board.GetPieceSet(color, PieceType.Knight), board));
allMoves.AddRange(GetKingMoves(color, board.GetPieceSet(color, PieceType.King), board));
return allMoves;
}
internal static List<Move> GetPawnMoves(PieceColor color, BitBoard pawns, Board board)
{
return ExtractMoves(color, PieceType.Pawn, pawns, board, Pawn.GetAllTargets);
}
internal static List<Move> GetKingMoves(PieceColor color, BitBoard king, Board board)
{
return ExtractMoves(color, PieceType.King, king, board, King.GetAllTargets);
}
internal static List<Move> GetKnightMoves(PieceColor color, BitBoard knights, Board board)
{
return ExtractMoves(color, PieceType.Knight, knights, board, Knight.GetAllTargets);
}
}this is my color-generalized Pawn class:
Code: Select all
internal static class Pawn
{
internal static BitBoard GetAllTargets(PieceColor color, BitBoard pawns, Board board)
{
BitBoard empty = board.GetEmptySquares();
BitBoard enemyPieces = board.GetEnemyPieces(color);
return GetQuietTargets(color, pawns, empty) | GetAnyAttack(color, pawns, board);
}
private static BitBoard GetQuietTargets(PieceColor color, BitBoard pawns, BitBoard empty)
{
return GetSinglePushTargets(color, pawns, empty) | GetDoublePushTargets(color, pawns, empty);
}
private static BitBoard GetSinglePushTargets(PieceColor color, BitBoard pawns, BitBoard empty)
{
switch (color)
{
case PieceColor.White:
{
return CompassRose.OneStepNorth(pawns) & empty;
}
case PieceColor.Black:
{
return CompassRose.OneStepSouth(pawns) & empty;
}
default:
throw new NotImplementedException();
}
}
private static BitBoard GetDoublePushTargets(PieceColor color, BitBoard pawns, BitBoard empty)
{
switch (color)
{
case PieceColor.White:
{
BitBoard singlePush = GetSinglePushTargets(color, pawns, empty);
return CompassRose.OneStepNorth(singlePush) & empty & Constants.Ranks.Four;
}
case PieceColor.Black:
{
BitBoard singlePush = GetSinglePushTargets(color, pawns, empty);
return CompassRose.OneStepSouth(singlePush) & empty & Constants.Ranks.Five;
}
default:
throw new NotImplementedException();
}
}
private static BitBoard GetPawnsAbleToSinglePush(PieceColor color, BitBoard pawns, BitBoard empty)
{
switch (color)
{
case PieceColor.White:
return CompassRose.OneStepSouth(empty) & pawns;
case PieceColor.Black:
return CompassRose.OneStepNorth(empty) & pawns;
default:
throw new NotImplementedException();
}
}
private static BitBoard GetPawnsAbleToDoublePush(PieceColor color, BitBoard pawns, BitBoard empty)
{
switch (color)
{
case PieceColor.White:
{
BitBoard emptyRank3 = CompassRose.OneStepSouth(empty & Constants.Ranks.Four) & empty;
return GetPawnsAbleToSinglePush(color, pawns, emptyRank3);
}
case PieceColor.Black:
{
BitBoard emptyRank6 = CompassRose.OneStepNorth(empty & Constants.Ranks.Six) & empty;
return GetPawnsAbleToSinglePush(color, pawns, emptyRank6);
}
default:
throw new NotImplementedException();
}
}
private static BitBoard GetEastAttacks(PieceColor color, BitBoard pawns)
{
switch (color)
{
case PieceColor.White:
return CompassRose.OneStepNorthEast(pawns);
case PieceColor.Black:
return CompassRose.OneStepSouthEast(pawns);
default:
throw new NotImplementedException();
}
}
private static BitBoard GetWestAttacks(PieceColor color, BitBoard pawns)
{
switch (color)
{
case PieceColor.White:
return CompassRose.OneStepNorthWest(pawns);
case PieceColor.Black:
return CompassRose.OneStepSouthWest(pawns);
default:
throw new NotImplementedException();
}
}
private static BitBoard GetAnyAttack(PieceColor color, BitBoard pawns, Board board)
{
return (GetEastAttacks(color, pawns) | GetWestAttacks(color, pawns)) & board.GetEnemyPieces(color);
}
}Code: Select all
internal static class King
{
internal static BitBoard GetAllTargets(PieceColor pieceColor, BitBoard king, Board board)
{
BitBoard kingMoves = MovePackHelper.KingAttacks[(BitBoard.BitScanForward(king))];
return kingMoves & ~board.GetPlayerPieces(pieceColor);
}
internal static void InitKingAttacks()
{
for (int sq = 0; sq < 64; sq++)
{
MovePackHelper.KingAttacks[sq] = GetKingAttacks(BitBoard.ToBitBoard(sq));
}
}
private static BitBoard GetKingAttacks(BitBoard king)
{
BitBoard attacks = CompassRose.OneStepEast(king) | CompassRose.OneStepWest(king);
king |= attacks;
attacks |= CompassRose.OneStepNorth(king) | CompassRose.OneStepSouth(king);
return attacks;
}
}
internal static class Knight
{
internal static BitBoard GetAllTargets(PieceColor pieceColor, BitBoard knights, Board board)
{
BitBoard targets = Constants.Empty;
while (knights != 0)
{
// accede all'array di mosse precalcolate cercando il primo bit attivo all'interno della bitboard
targets |= MovePackHelper.KnightAttacks[(BitBoard.BitScanForwardReset(ref knights))];
}
return targets & ~board.GetPlayerPieces(pieceColor);
}
internal static void InitKnightAttacks()
{
// inizializza l'array di mosse precalcolate
for (int sq = 0; sq < 64; sq++)
{
MovePackHelper.KnightAttacks[sq] = GetKnightAttacks(BitBoard.ToBitBoard(sq));
}
}
private static BitBoard GetKnightAttacks(BitBoard knights)
{
BitBoard west, east, attacks;
east = CompassRose.OneStepEast(knights);
west = CompassRose.OneStepWest(knights);
attacks = (east | west) << 16;
attacks |= (east | west) >> 16;
east = CompassRose.OneStepEast(east);
west = CompassRose.OneStepWest(west);
attacks |= (east | west) << 8;
attacks |= (east | west) >> 8;
return attacks;
}
}thanks to all
Edit: this is my BitBoard wrapper for UInt64, it is responsible to display bitboards, calculate population count, bitscan,ecc.ecc.
Code: Select all
internal struct BitBoard
{
private UInt64 value;
internal BitBoard(UInt64 board)
{
this.value = board;
}
public static implicit operator BitBoard(UInt64 board)
{
return new BitBoard(board);
}
public static implicit operator UInt64(BitBoard board)
{
return board.value;
}
private static bool IsBitSet(BitBoard bitBoard, int posBit)
{
return (bitBoard & ((UInt64)1 << (posBit))) != 0;
}
internal static BitBoard ToBitBoard(int toConvert)
{
return (UInt64)1 << toConvert;
}
internal static void Display(BitBoard bitBoard)
{
for (int r = 7; r >= 0; r--)
{
Console.WriteLine("------------------------");
for (int c = 0; c <= 7; c++)
{
Console.Write('[');
if (IsBitSet(bitBoard,Square.GetSquareIndex(c, r)))
{
Console.ForegroundColor = ConsoleColor.Green;
Console.Write('1');
}
else
{
Console.ForegroundColor = ConsoleColor.DarkRed;
Console.Write('0');
}
Console.ResetColor();
Console.Write(']');
}
Console.WriteLine();
}
}
internal static int PopCount(BitBoard bitBoard)
{
UInt64 M1 = 0x5555555555555555; // 1 zero, 1 one ...
UInt64 M2 = 0x3333333333333333; // 2 zeros, 2 ones ...
UInt64 M4 = 0x0f0f0f0f0f0f0f0f; // 4 zeros, 4 ones ...
UInt64 M8 = 0x00ff00ff00ff00ff; // 8 zeros, 8 ones ...
UInt64 M16 = 0x0000ffff0000ffff; // 16 zeros, 16 ones ...
UInt64 M32 = 0x00000000ffffffff; // 32 zeros, 32 ones
bitBoard = (bitBoard & M1) + ((bitBoard >> 1) & M1); //put count of each 2 bits into those 2 bits
bitBoard = (bitBoard & M2) + ((bitBoard >> 2) & M2); //put count of each 4 bits into those 4 bits
bitBoard = (bitBoard & M4) + ((bitBoard >> 4) & M4); //put count of each 8 bits into those 8 bits
bitBoard = (bitBoard & M8) + ((bitBoard >> 8) & M8); //put count of each 16 bits into those 16 bits
bitBoard = (bitBoard & M16) + ((bitBoard >> 16) & M16); //put count of each 32 bits into those 32 bits
bitBoard = (bitBoard & M32) + ((bitBoard >> 32) & M32); //put count of each 64 bits into those 64 bits
return (int)bitBoard.value;
}
internal static int BitScanForward(BitBoard bitBoard)
{
return Constants.DeBrujinTable[((ulong)((long)bitBoard.value & -(long)bitBoard.value) * Constants.DeBrujinValue) >> 58];
}
internal static int BitScanForwardReset(ref BitBoard bitBoard)
{
int bitIndex = Constants.DeBrujinTable[((ulong)((long)bitBoard.value & -(long)bitBoard.value) * Constants.DeBrujinValue) >> 58];
bitBoard &= bitBoard -1;
return bitIndex;
}
}