Problem with bitboard knight attack generator

[Sven]

In theory, it would have worked. In practice however...

The error for being ahead of the square should be fixed by replacing 8 with 7, and wraparound by ANDing with the file ahead. So we get this:

Code: Select all

void InitPawnAttacks()
{
   const Bitboard a = 0x5ULL;
   for (int i = a2; i < h7; i++) {
      PawnAttacks[0][i] = (a << (i + 7)) bitand (FileMaskForSquare(i) + 1);
   for (int i = a2; i < h7; i++) {
      PawnAttacks[1][i] = (a << (i - 7)) bitand (FileMaskForSquare(i) - 1);
}

Which is somewhat less elegant...

... but does not work as well!

Your loop should terminate by "i <= h7", not "i < h7". I would also use only one loop for white and black.

For black the shifting by (i-7) looks wrong to me, I think it should be (i-9). Example: i=b3 (17), 0x5ULL << (17-7) = 0x1400ULL which is (c2|e2) but you want to get (a2|c2) and that can't be corrected by any subsequent ANDing. Shifting by "i" puts a three-bit pattern to square positions i, i+1, i+2 and you always want to move that pattern one file to the left and either one rank up or down, so (i+7) for white and (i-9) for black seems to be appropriate.

Also I am not sure about the proper handling of a- and h-file wraparound, your FileMaskForSquare(i) must be somewhat tricky to catch that case after having already shifted across the border.

Instead of always using the pattern 0x5ULL together with "FileMaskForSquare(i)" which complicates the usage I would use a pattern depending on the rank of square i, and simply always shift it by i+7 resp. i-9 (assuming a1=0 orientation):

Code: Select all

void InitPawnAttacks()
{
    static Bitboard const a[8] = {
        0x4ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x1ULL
    };
    for (int i = a2; i <= h7; i++) {
        PawnAttacks[0][i] = a[rank(i)] << (i+7);
        PawnAttacks[1][i] = a[rank(i)] << (i-9);
    }
}

Sven

[lucasart]

In theory, it would have worked. In practice however...

The error for being ahead of the square should be fixed by replacing 8 with 7, and wraparound by ANDing with the file ahead. So we get this:

Code: Select all

void InitPawnAttacks()
{
   const Bitboard a = 0x5ULL;
   for (int i = a2; i < h7; i++) {
      PawnAttacks[0][i] = (a << (i + 7)) bitand (FileMaskForSquare(i) + 1);
   for (int i = a2; i < h7; i++) {
      PawnAttacks[1][i] = (a << (i - 7)) bitand (FileMaskForSquare(i) - 1);
}

Which is somewhat less elegant...

... but does not work as well!

+1

Morality: *always test* your code. If you don't test it now, the pain of testing will be much greater when you have to recursively debug your perft to figure out why they are wrong... Another reason to test your code before posting it, is to avoid getting blasted on the forum

[Sven]

In theory, it would have worked. In practice however...

The error for being ahead of the square should be fixed by replacing 8 with 7, and wraparound by ANDing with the file ahead. So we get this:

Code: Select all

void InitPawnAttacks()
{
   const Bitboard a = 0x5ULL;
   for (int i = a2; i < h7; i++) {
      PawnAttacks[0][i] = (a << (i + 7)) bitand (FileMaskForSquare(i) + 1);
   for (int i = a2; i < h7; i++) {
      PawnAttacks[1][i] = (a << (i - 7)) bitand (FileMaskForSquare(i) - 1);
}

Which is somewhat less elegant...

... but does not work as well!

+1

Morality: *always test* your code. If you don't test it now, the pain of testing will be much greater when you have to recursively debug your perft to figure out why they are wrong... Another reason to test your code before posting it, is to avoid getting blasted on the forum

Hi Lucas,

I fully agree.

As to your last sentence: one of my main reasons to post corrections of wrong code is not to "blast" anyone but to avoid letting the wrong code live forever in the archives, from where someone else picks it up a couple of years later. Also, whenever I post code that has an error I am usually glad if someone else points out my fault and corrects it. I have observed the opposite (someone not liking to be corrected) only very few times so far.

Sven

[lucasart]

As to your last sentence: one of my main reasons to post corrections of wrong code is not to "blast" anyone but to avoid letting the wrong code live forever in the archives, from where someone else picks it up a couple of years later. Also, whenever I post code that has an error I am usually glad if someone else points out my fault and corrects it. I have observed the opposite (someone not liking to be corrected) only very few times so far.

Sven

I was just trying to make a little emphasis, but of course you didn't blast anyone for writing wrong code

[sje]

Uh, I posted an old version. The current code employs more named constants:

Code: Select all

        { Initialize the pawn attack-to-squares bitboard vector }

        for color := colorrmin to colorrmax do
          begin
            man := synthpawn[color];
            dir0 := mantodir0[man];
            dir1 := mantodir1[man];
            for frsq := sqmin to sqmax do
              begin
                BbReset(pawnatkbbvec[color, frsq]);
                for dir := dir0 to dir1 do
                  begin
                    tosq := advance[frsq, dir];
                    if tosq <> sqnil then
                      BbSetSq(pawnatkbbvec[color, frsq], tosq)
                  end
              end
          end;

        { Initialize the knight attack-to-squares bitboard vector }

        for frsq := sqmin to sqmax do
          begin
            BbReset(knightatkbbvec[frsq]);
            for dir := crookdirmin to crookdirmax do
              begin
                tosq := advance[frsq, dir];
                if tosq <> sqnil then
                  BbSetSq(knightatkbbvec[frsq], tosq)
              end
          end;

        { Initialize the king attack-to-squares bitboard vector }

        for frsq := sqmin to sqmax do
          begin
            BbReset(kingatkbbvec[frsq]);
            for dir := sweepdirmin to sweepdirmax do
              begin
                tosq := advance[frsq, dir];
                if tosq <> sqnil then
                  BbSetSq(kingatkbbvec[frsq], tosq)
              end
          end;

        { Initialize the open ray bitboard vector }

        for frsq := sqmin to sqmax do
          for dir := sweepdirmin to sweepdirmax do
            begin
              BbReset(openraybbvec[frsq, dir]);
              tosq := frsq;
              repeat
                tosq := advance[tosq, dir];
                if tosq <> sqnil then
                  BbSetSq(openraybbvec[frsq, dir], tosq)
              until tosq = sqnil
            end;

        { Initialize the intersquare pathway bitboard vector }

        for frsq := sqmin to sqmax do
          for tosq := sqmin to sqmax do
            begin
              dir := compass[frsq, tosq];
              if IsDirxSweep(dir) then
                BbAnd2(
                    pathwaybbvec[frsq, tosq],
                    openraybbvec[frsq, dir],
                    openraybbvec[tosq, otherdir[dir]])
              else
                BbReset(pathwaybbvec[frsq, tosq])
            end;

[Lasse Hansen]

Yet another pawn initialization version:

Code: Select all

for (sqr=H8; sqr<=A1; sqr++) { // sqr map H8, G8, .... A1
	PawnAttacks[BLACK][sqr] = ((5ULL<<7) << sqr) & KingAttacks[sqr];
	PawnAttacks[WHITE][63-sqr] = ((5ULL<<54) >> sqr) & KingAttacks[63-sqr];
}

I guess my square mapping is not normal, but works for me.
Regards, Lasse

[ZirconiumX]

ATM my code is cluttered to say the least (and wrong (probably)).

Code: Select all

void InitKnightAttacks()
{
	Bitboard b;
	for (int Square = a1; Square <= h8; Square++) {
		b = 1ULL << Square;
		
		KnightAttacks[Square] = ((b bitand compl(FileMask(A_FILE))) << 17)
			bitor ((b bitand compl(FileMask(G_FILE) bitor FileMask(H_FILE))) << 10)
			bitor ((b bitand compl(FileMask(G_FILE) bitor FileMask(H_FILE))) >> 6)
			bitor ((b bitand compl(FileMask(H_FILE))) >> 15)
			bitor ((b bitand compl(FileMask(A_FILE))) << 15)
			bitor ((b bitand compl(FileMask(A_FILE) bitor FileMask(B_FILE))) << 6)
			bitor ((b bitand compl(FileMask(A_FILE) bitor FileMask(B_FILE))) >> 10)
			bitor ((b bitand compl(FileMask(A_FILE))) >> 17);
	}
} 
void InitKingAttacks()
{
	Bitboard b;
	Bitboard a;
	for (int Square = a1; Square <= h8; Square++) {
		b	= 1ULL << Square;
		a	= b << 1 bitor b >> 1;
		b   or_eq a;
		a   or_eq b << 8 bitor b >> 8;
		KingAttacks[Square] = a;
	}
}

void InitPawnAttacks()
{
	static Bitboard const a[8] = {
		0x4ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x1ULL
	};
	for (int i = a2; i <= h7; i++) {
		PawnAttacks[0][i] = a[Rank(i)] << (i + 7);
		PawnAttacks[1][i] = a[Rank(i)] << (i - 9);
	}
}

I have decided that I'm going to go for the lazy option w.r.t Sliding Pieces, then upgrade later.

I'm going to use Dumb7Fill. Just because.

Matthew:out

Merry Christmas, everyone, I hope Santa has/will bring you nice things! (I got coal because I insulted the bitboarder communtity by being lazy)

[lucasart]

ATM my code is cluttered to say the least (and wrong (probably)).

Code: Select all

void InitKnightAttacks()
{
	Bitboard b;
	for (int Square = a1; Square <= h8; Square++) {
		b = 1ULL << Square;
		
		KnightAttacks[Square] = ((b bitand compl(FileMask(A_FILE))) << 17)
			bitor ((b bitand compl(FileMask(G_FILE) bitor FileMask(H_FILE))) << 10)
			bitor ((b bitand compl(FileMask(G_FILE) bitor FileMask(H_FILE))) >> 6)
			bitor ((b bitand compl(FileMask(H_FILE))) >> 15)
			bitor ((b bitand compl(FileMask(A_FILE))) << 15)
			bitor ((b bitand compl(FileMask(A_FILE) bitor FileMask(B_FILE))) << 6)
			bitor ((b bitand compl(FileMask(A_FILE) bitor FileMask(B_FILE))) >> 10)
			bitor ((b bitand compl(FileMask(A_FILE))) >> 17);
	}
} 
void InitKingAttacks()
{
	Bitboard b;
	Bitboard a;
	for (int Square = a1; Square <= h8; Square++) {
		b	= 1ULL << Square;
		a	= b << 1 bitor b >> 1;
		b   or_eq a;
		a   or_eq b << 8 bitor b >> 8;
		KingAttacks[Square] = a;
	}
}

void InitPawnAttacks()
{
	static Bitboard const a[8] = {
		0x4ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x5ULL, 0x1ULL
	};
	for (int i = a2; i <= h7; i++) {
		PawnAttacks[0][i] = a[Rank(i)] << (i + 7);
		PawnAttacks[1][i] = a[Rank(i)] << (i - 9);
	}
}

I have decided that I'm going to go for the lazy option w.r.t Sliding Pieces, then upgrade later.

I'm going to use Dumb7Fill. Just because.

Matthew:out

Merry Christmas, everyone, I hope Santa has/will bring you nice things! (I got coal because I insulted the bitboarder communtity by being lazy)

I haven't tested, but shouldn't it be a[File(i)] rather than a[Rank(i)] ?
As for coding style, everyone has their own, and it's up to you. But I'm not sure that replacing all the bitwise operators by your macros: bitand, bitor, or_eq etc. makes it easier to read, no ?
Also I strongly recommend you to clarify the operator associativity. For example:

Code: Select all

a   or_eq b << 8 bitor b >> 8;

is somewhat easier to read written like this:

Code: Select all

a  |= (b << 8) | (b >> 8);

[ZirconiumX]

Lucas,

Blame the CPW for that:

U64 kingAttacks(U64 kingSet) {
U64 attacks = eastOne(kingSet) | westOne(kingSet);
kingSet |= attacks;
attacks |= nortOne(kingSet) | soutOne(kingSet);
return attacks;
}

I don't have a nortOne or a SoutOne function, so I subsituted the actual code for it.

I'm currently converting it to C, as I don't use the C++ features.

Out of interest, if you declare a typedef struct as extern, which order do the keywords go in? (I think typedef extern struct is correct, but I'll ask anyway)

Matthew:out

[ZirconiumX]

I admit defeat...

Lucas was right.

Code: Select all

void InitKnightAttacks()
{
	Bitboard b;
	for (int Square = a1; Square < h8; Square++) {
		b = 1ULL << Square;
		
		KnightAttacks[Square] = ((b & ~(FileMask(0)				 )) << 17)
							  | ((b & ~(FileMask(6) | FileMask(7))) << 10)
							  | ((b & ~(FileMask(6) | FileMask(7))) >> 6)
							  | ((b & ~(FileMask(7)				 )) >> 15)
							  | ((b & ~(FileMask(0)				 )) << 15)
							  | ((b & ~(FileMask(0) | FileMask(1))) << 6)
							  | ((b & ~(FileMask(0) | FileMask(1))) >> 10)
							  | ((b & ~(FileMask(0)				 )) >> 17);
	}
}

void InitKingAttacks()
{
	Bitboard b;
	Bitboard a;
	for (int Square = a1; Square <= h8; Square++) {
		b	 = 1ULL << Square;
		a	 = (b << 1) | (b >> 1);
		b   |= a;
		a   |= (b << 8) | (b >> 8);
		KingAttacks[Square] = a;
	}
}

void InitPawnAttacks()
{
	static Bitboard const a[8] = {
		0x4ULL, 0x5ULL, 0x5ULL, 0x5ULL,
		0x5ULL, 0x5ULL, 0x5ULL, 0x1ULL
	};
	for (int i = a2; i <= h7; i++) {
		PawnAttacks[0][i] = a[File(i)] << (i + 7);
		PawnAttacks[1][i] = a[File(i)] << (i - 9);
	}
}

Matthew:out