Bitboard of a bishops target squares.

[lithander]

I'm experimenting with bitboard based move generation. To unerstand the material better I would like to generate the attacks and moves algorithmically first before using extensive lookup-tables like magic bitboards.

I managed to generate rook moves and I think the bishop targets could be implemented similarly but I struggle with the very first step: generating the bitboards that store the diagonals going through a specific square.

For the rook the solution looks like this:

Code: Select all

int file = square % 8;
ulong bbHorizontal = 0x00000000000000FFUL << (square - file);
ulong bbVertical = 0x0101010101010101UL << file;

So for example with square being 'c3' this would give me the following bitboards:

Code: Select all

Horizontal:         Vertical:
. . . . . . . .     . . X . . . . .
. . . . . . . .     . . X . . . . .
. . . . . . . .     . . X . . . . .
. . . . . . . .     . . X . . . . .
. . . . . . . .     . . X . . . . .
X X X X X X X X     . . X . . . . .
. . . . . . . .     . . X . . . . .
. . . . . . . .     . . X . . . . .

Now I'm looking for the equivalent function for the diagonal and anti-diagonal of a bishop.

Code: Select all

Diagonal:           Anit-Diagonal:
. . . . . . . .     . . . . . . . X     
. . . . . . . .     . . . . . . X .
. . . . . . . .     . . . . . X . .
X . . . . . . .     . . . . X . . .
. X . . . . . .     . . . X . . . .
. . X . . . . .     . . X . . . . .
. . . X . . . .     . X . . . . . .
. . . . X . . .     X . . . . . . .

At first I thought I'd find something simple (like for the rook) quickly but I haven't yet. If all fails a lookup table accessed by square would do the trick, I guess. But I'm really wondering what the best algorithmic solution would be? Am I dense or is there really no simple solution?

[Mergi]

Are you looking to just generate rays on an empty board? Then this page this page might be of interest to you. It's easier to divide the problem into first generating attacks in each direction from a source square, and then combining these as needed to generate bishop/rook rays.

If you want to generate actual attacks, that take occupancy into consideration, i found hyperbola quitessence to perform quite well. And i still use this method to generate the magic lookup tables in my engine on startup.

[lithander]

Are you looking to just generate rays on an empty board? Then this page this page might be of interest to you. It's easier to divide the problem into first generating attacks in each direction from a source square, and then combining these as needed to generate bishop/rook rays.

Yes, just rays on an empty board. Your link was very helpful and covered my problem but it seems that indeed for the bishops there's no simple solution like for the rooks.

Code: Select all

U64 diagonalMask(int sq) {
   const U64 maindia = C64(0x8040201008040201);
   int diag =8*(sq & 7) - (sq & 56);
   int nort = -diag & ( diag >> 31);
   int sout =  diag & (-diag >> 31);
   return (maindia >> sout) << nort;
}

U64 antiDiagMask(int sq) {
   const U64 maindia = C64(0x0102040810204080);
   int diag =56- 8*(sq&7) - (sq&56);
   int nort = -diag & ( diag >> 31);
   int sout =  diag & (-diag >> 31);
   return (maindia >> sout) << nort;
}

vs for Rooks it's only:

Code: Select all

U64 rankMask(int sq) {return  C64(0xff) << (sq & 56);}
U64 fileMask(int sq) {return C64(0x0101010101010101) << (sq & 7);}

Given how similar geometrically diagonals seem to be to straight lines I thought I was just overlooking some simpler solution.

[Mergi]

Yeah, it's a bit of a pain with all the masking of wrapped bits.

Maybe not the solution you were looking for, but i prefer a small hardcoded lookup table. It's not too bad, since you only need 15 entries for diagonal and 15 for antidiagonal rays. It's probably less lines of code than calculating them in a function somewhere.

Code: Select all

    Bitboard diag_masks[15]{
            0x1, 0x102, 0x10204, 0x1020408, 0x102040810, 0x10204081020, 0x1020408102040,
            0x102040810204080, 0x204081020408000, 0x408102040800000, 0x810204080000000,
            0x1020408000000000, 0x2040800000000000, 0x4080000000000000, 0x8000000000000000
    };

    Bitboard anti_diag_masks[15]{
            0x80, 0x8040, 0x804020, 0x80402010, 0x8040201008, 0x804020100804, 0x80402010080402,
            0x8040201008040201, 0x4020100804020100, 0x2010080402010000, 0x1008040201000000,
            0x804020100000000, 0x402010000000000, 0x201000000000000, 0x100000000000000
    };

And the bishop ray lookup becomes

Code: Select all

Bitboard GetBishopRays(Square s) {
        File f = FileFromSquare(s);
        Rank r = RankFromSquare(s);
        return diag_masks[f + r] | anti_diag_masks[r + 7 - f];
    }

[tcusr]

Are you looking to just generate rays on an empty board? Then this page this page might be of interest to you. It's easier to divide the problem into first generating attacks in each direction from a source square, and then combining these as needed to generate bishop/rook rays.

If you want to generate actual attacks, that take occupancy into consideration, i found hyperbola quitessence to perform quite well. And i still use this method to generate the magic lookup tables in my engine on startup.

why does hyperbola quitessence use _byteswap_uint64 instead of reversing the bits to generate negative rays?

Code: Select all

uint64_t ratt(int s, uint64_t o)
{
	uint64_t mask = 0xffull << (s & 56) ^ 0x0101010101010101ull << (s & 7);
	o &= mask;

	uint64_t a = (o - 2 * (1ull << s)) ^ reverse(reverse(o) - 2 * reverse(1ull << s));
	a &= mask;

	return a;
}

in this code if reverse is a byte swap function it doesn't generate rank attacks but the other rays are generated correctly, instead if it actually reversed the bits it generates rank attacks but on some squares it gives random numbers.

[gflohr]

Given how similar geometrically diagonals seem to be to straight lines I thought I was just overlooking some simpler solution.

A necessary but not sufficient precondition is that the two pieces are on squares of the same color. I know that there is some clever formula for that check in Stockfish but I forgot where. But that may be a good starting point for a a solution without a lookup table.

[dangi12012]

Just write loops like a 64 slot array.
You can check if its blocked on a bitboard with:

(1ull << sq) & occupy

With loops you can also do it in normal xy space.

int sq = y * 8 + x

[gflohr]

Given how similar geometrically diagonals seem to be to straight lines I thought I was just overlooking some simpler solution.

A necessary but not sufficient precondition is that the two pieces are on squares of the same color. I know that there is some clever formula for that check in Stockfish but I forgot where. But that may be a good starting point for a a solution without a lookup table.

And not that this would help you in any respect with your problem, but here's a fun fact:

If the side length of the chess board was not 8 but any odd number, then it would be a completely different story. 7x7 would look like this:

Code: Select all

oxoxoxo
xoxoxox
oxoxoxo
xoxoxox
oxoxoxo
xoxoxox
oxoxoxo

Finding out whether the two squares s1 and s2 are of different color then boils down to

Code: Select all

((1 << s1) | (1 << s2)) % 3 == 0

Remember: A binary number is dividable by 3 if the difference between the number of odd bits and the number of even bits is dividable by 3. If we have just two bits, the only combination that fulfills this condition is 1 - 1.

So, one solution to your problem would be to change the rules of chess to use a 7x7 instead of the 8x8 board. I would like to add that I opt for pruning the d file, because the d file hosts the queen that I always tend to lose, no matter whether I play myself or my engine plays.

[emadsen]

I'm experimenting with bitboard based move generation. To unerstand the material better I would like to generate the attacks and moves algorithmically first before using extensive lookup-tables like magic bitboards.

In the constructor of my Board class, I create a 12x12 board and direction offsets, map its squares to an 8x8 board, then map the neighbors of each 8x8 board square in every direction. Like this:

1. Create an array that represents a 12x12 board (ring of 2 squares around 8x8 board).
2. Create an array that represents an 8x8 board.
3. Iterate from file = -2 to 9 and rank = -2 to 9. If the rank and file are >= 0 and <= 7 (in other words, in bounds), map the square indices of the 12x12 board to the 8x8 board in a jagged array. Else mark the square as illegal. The square88 index is a counter that starts at 0 and is incremented when the rank & file are in-bounds.
4. Define direction offsets for the 12x12 board for each of 16 directions (compass + knights).
5. Create a neighbor squares jagged array. For each square in 12x12 board, lookup the 8x8 index. If it's a legal square, for each direction, lookup the 8x8 index of its neighbor via neighborSquares[square88][direction] = squareIndices1212To88[square1212 + directionOffset1212].

The point of the 12x12 board is to ensure a piece move in a compass or knight direction from a legal (8x8) square never goes out of bounds of the 12x12 board.

Now you have a neighborSquares[square88][direction] jagged array. You can lookup the neighbor square of any legal square in any direction. The lookup will indicate the 8x8 index of the neighbor square, or Square.Illegal if out of bounds. Use that to create any bitmask you need: files, ranks, diagonals, piece moves, passed pawns, castling destinations and in-between squares, king shields or rings, etc. For sliding rays, simply loop through neighbor squares until the neighbor is Square.Illegal, indicating you've reached the edge of the board.

Pre-calculate bitmasks during startup using neighborSquares because you can afford to be slow. Then during search & eval, when your code must be fast, rely on the pre-calculated bitmasks.

[Mergi]

why does hyperbola quitessence use _byteswap_uint64 instead of reversing the bits to generate negative rays?

Code: Select all

uint64_t ratt(int s, uint64_t o)
{
	uint64_t mask = 0xffull << (s & 56) ^ 0x0101010101010101ull << (s & 7);
	o &= mask;

	uint64_t a = (o - 2 * (1ull << s)) ^ reverse(reverse(o) - 2 * reverse(1ull << s));
	a &= mask;

	return a;
}

in this code if reverse is a byte swap function it doesn't generate rank attacks but the other rays are generated correctly, instead if it actually reversed the bits it generates rank attacks but on some squares it gives random numbers.

Because byte swap is a very fast instruction, but there's no hardware support for reversing bits. If you use Hyperbola Quintessence just to initialize magic lookup tables, you don't need to worry about speed and you can use a custom bit reversal function. But if are using it to generate attacks on the fly, this might be a bit slow compared to other techniques. This is how the bit reversal function looks in my code. It's not very fast.

Code: Select all

Bitboard ReverseBits(Bitboard b) {
        b = ((b >> 1) & 0x5555555555555555ULL) | ((b & 0x5555555555555555ULL) << 1);
        b = ((b >> 2) & 0x3333333333333333ULL) | ((b & 0x3333333333333333ULL) << 2);
        b = ((b >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((b & 0x0F0F0F0F0F0F0F0FULL) << 4);
        b = ((b >> 8) & 0x00FF00FF00FF00FFULL) | ((b & 0x00FF00FF00FF00FFULL) << 8);
        b = ((b >> 16) & 0x0000FFFF0000FFFFULL) | ((b & 0x0000FFFF0000FFFFULL) << 16);
        b = (b >> 32) | (b << 32);
        return b;
    }