Page 1 of 1

Sliding pieces move generation

Posted: Fri Jul 27, 2012 10:20 pm
by crybot
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:

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);
        }
    }
I use a delegate to abstract move serialization, cause every piece type has his own "GetTargets" method.

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);
        }
    }
and here are my King and Knight classes:

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;
        }
    }
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.

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;
    }
}

Re: Sliding pieces move generation

Posted: Mon Jul 30, 2012 9:52 pm
by Gerd Isenberg
Sometimes you need to read some stuff x times to get it.

I start with the rank attacks of a rook, assuming a1 = 0, b1 = 1, ..., h1 = 7, a2 = 8, ... h8 = 63 square versus bitindex mapping.

The idea is to use the inner six occupied bits as a relevant index in a 0..63 range, since the outer squares are not relevant. Those squares are attacked or not, no matter whether they are occupied or not. One could also use all 8 bits as index, but that makes the tables four times bigger.

For the first rank with rank index zero, with consecutive bits along that rank, and the sliding piece (rook) on square (file) 0 to 7, we can construct a two-dimensional lookup table for 8 files times 64 occupancies (occupancy may include or exclude the sliding piece). Attacks for one rank only needs one byte, and can be zero extended to a bitboard at compile (eight fold bigger tables) or run-time.

Code: Select all

rook
file      occupancy        occidx    attacks         as decimal          
0        [x 0 0 0 0 0 0 x]    0  -> [0 1 1 1 1 1 1 1]   (254)
1        [x 0 0 0 0 0 0 x]    0  -> [1 0 1 1 1 1 1 1]   (253)
2        [x 0 0 0 0 0 0 x]    0  -> [1 1 0 1 1 1 1 1]   (251)
...
7        [x 0 0 0 0 0 0 x]    0  -> [1 1 1 1 1 1 1 0]   (127)

0        [x 1 0 0 0 0 0 x]    1  -> [0 1 0 0 0 0 0 0]   (  2)
1        [x 1 0 0 0 0 0 x]    1  -> [1 0 1 1 1 1 1 1]   (253) 
2        [x 1 0 0 0 0 0 x]    1  -> [0 1 0 1 1 1 1 1]   (250)
...
7        [x 1 0 0 0 0 0 x]    1  -> [0 1 1 1 1 1 1 0]   (126)
...
0        [x 0 0 0 0 0 1 x]   32  -> [0 1 1 1 1 1 1 0]   (126)
1        [x 0 0 0 0 0 1 x]   32  -> [1 0 1 1 1 1 1 0]   (125)
2        [x 0 0 0 0 0 1 x]   32  -> [1 1 0 1 1 1 1 0]   (123)
...
7        [x 0 0 0 0 0 1 x]   32  -> [0 0 0 0 0 0 1 0]   ( 64)
...
0        [x 1 1 1 1 1 1 x]   63  -> [0 1 0 0 0 0 0 0]   (  2)
1        [x 1 1 1 1 1 1 x]   63  -> [1 0 1 0 0 0 0 0]   (  5)
2        [x 1 1 1 1 1 1 x]   63  -> [0 1 0 1 0 0 0 0]   ( 10)
...
7        [x 1 1 1 1 1 1 x]   63  -> [0 0 0 0 0 0 1 0]   ( 64)
The occupancy index is actually occidx := (occupancy >> 1) & 63 for the inner six bits.

If that is clear, the other ranks only need some shifting. First shifting the rank down (8 times rank index right) to the first rank. And after getting the attack on the first rank as described above, shifting it back to the original rank.

Another idea to safe the final shift is to lookup bitboards not indexed by 8 files, but 64 squares. With rankidx = square / 8, one gets 8*rankidx by square & ~7, that is reset the three least significant bits of a square (here the file index).

Code: Select all

Bitboard rankLookup[64][64]; /* 32 Kibis instead of 1/2 */
occidx     := (occupancy >> ((square & ~7) + 1)) & 63;
horattacks := rankLookup[square][occidx];
The next step are attacks along the files or diagonals ...
Where i refer to rotated or kindergarten bitboards.

Re: Sliding pieces move generation

Posted: Mon Jul 30, 2012 11:07 pm
by crybot
thanks for the reply, i found the solution yesterday :)
now I'm triyng to implement move generation for files, but I'm using all 8 bits for the occupancy state and I can't find the magic multipliers that can trasform an 8 bit file in a rank, can anyone help me?
thanks ;)

Re: Sliding pieces move generation

Posted: Tue Jul 31, 2012 7:14 am
by Gerd Isenberg
crybot wrote:thanks for the reply, i found the solution yesterday :)
now I'm triyng to implement move generation for files, but I'm using all 8 bits for the occupancy state and I can't find the magic multipliers that can trasform an 8 bit file in a rank, can anyone help me?
thanks ;)
shift the file to the least significant one, the A-File, mask it, multiply it with the main-diagonal and shift the result down ...

Code: Select all

masked bits                             mapped to 8th rank
bits on A-file   *  main-diagonal    =  with garbage     -> 1st rank
A . . . . . . .     . . . . . . . 1     A B C D E F G H     . . . . . . . .
B . . . . . . .     . . . . . . 1 .     B C D E F G H .     . . . . . . . .
C . . . . . . .     . . . . . 1 . .     C D E F G H . .     . . . . . . . .
D . . . . . . .     . . . . 1 . . .     D E F G H . . .  >> . . . . . . . .
E . . . . . . .  *  . . . 1 . . . .  =  E F G H . . . .  56 . . . . . . . .
F . . . . . . .     . . 1 . . . . .     F G H . . . . .     . . . . . . . .
G . . . . . . .     . 1 . . . . . .     G H . . . . . .     . . . . . . . .
H . . . . . . .     1 . . . . . . .     H . . . . . . .     A B C D E F G H
see further
https://chessprogramming.wikispaces.com ... 20a%20Rank
https://chessprogramming.wikispaces.com ... ed%20Ranks
https://chessprogramming.wikispaces.com ... ed%20Ranks