Problem with bitboard knight attack generator

Discussion of chess software programming and technical issues.

Moderator: Ras

ZirconiumX
Posts: 1359
Joined: Sun Jul 17, 2011 11:14 am
Full name: Hannah Ravensloft

Problem with bitboard knight attack generator

Post by ZirconiumX »

I have been trying to make a bitboard knight attack generator to fill an array of knight attacks.

Code: Select all

Bitboard KnightMoves(int Square)
{
	Bitboard b = 1 << Square, Targets = 0;
	
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) << 17;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) << 10;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) >> 6;
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) >> 15;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) << 15;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) << 6;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) >> 10;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) >> 17;

	return Targets;
}
When I try and generate the array I get some strange figures given, e.g. for square a1 I get 0x132096...

Something at the back of my mind says that I'm suffering from wrap-around issues.

Matthew:out
tu ne cede malis, sed contra audentior ito
Gerd Isenberg
Posts: 2251
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Problem with bitboard knight attack generator

Post by Gerd Isenberg »

What value has a1?

I guess problem is the 32-bit expression 1 << square instead 1ULL << square.

Gerd
jwes
Posts: 778
Joined: Sat Jul 01, 2006 7:11 am

Re: Problem with bitboard knight attack generator

Post by jwes »

ZirconiumX wrote:I have been trying to make a bitboard knight attack generator to fill an array of knight attacks.

Code: Select all

Bitboard KnightMoves(int Square)
{
	Bitboard b = 1 << Square, Targets = 0;
	
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) << 17;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) << 10;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) >> 6;
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) >> 15;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) << 15;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) << 6;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) >> 10;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) >> 17;

	return Targets;
}
When I try and generate the array I get some strange figures given, e.g. for square a1 I get 0x132096...

Something at the back of my mind says that I'm suffering from wrap-around issues.

Matthew:out
One problem is that you are not taking into account the sides of the board, e.g. (b & 0xFCFCFCFCFCFCFCFCULL) << 6 only works for files c-h.
lucasart
Posts: 3241
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Problem with bitboard knight attack generator

Post by lucasart »

ZirconiumX wrote:I have been trying to make a bitboard knight attack generator to fill an array of knight attacks.

Code: Select all

Bitboard KnightMoves(int Square)
{
	Bitboard b = 1 << Square, Targets = 0;
	
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) << 17;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) << 10;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) >> 6;
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) >> 15;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) << 15;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) << 6;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) >> 10;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) >> 17;

	return Targets;
}
When I try and generate the array I get some strange figures given, e.g. for square a1 I get 0x132096...

Something at the back of my mind says that I'm suffering from wrap-around issues.

Matthew:out
1 << Square is a common mistake. It should be 1ULL << Square. Otherwise you shift a 32-bit int, and you lose all the 32 upper bits, and casting to a uint64_t won't solve the problem.

and as for your algorithm itself, i don't think it's correct.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Problem with bitboard knight attack generator

Post by bob »

ZirconiumX wrote:I have been trying to make a bitboard knight attack generator to fill an array of knight attacks.

Code: Select all

Bitboard KnightMoves(int Square)
{
	Bitboard b = 1 << Square, Targets = 0;
	
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) << 17;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) << 10;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) >> 6;
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) >> 15;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) << 15;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) << 6;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) >> 10;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) >> 17;

	return Targets;
}
When I try and generate the array I get some strange figures given, e.g. for square a1 I get 0x132096...

Something at the back of my mind says that I'm suffering from wrap-around issues.

Matthew:out
I don't follow the bit patterns you are using... Since this only needs to be done at startup, I use this:

Code: Select all


int64_t knight_attacks[64];
static const int knightsq[8] = { -17, -15, -10, -6, 6, 10, 15, 17 };

/*
 initialize knight attack board
 */
  for (i = 0; i < 64; i++) {
    knight_attacks[i] = 0;
    frank = Rank(i);
    ffile = File(i);
    for (j = 0; j < 8; j++) {
      sq = i + knightsq[j];
      if ((sq < 0) || (sq > 63))
        continue;
      trank = Rank(sq);
      tfile = File(sq);
      if ((Abs(frank - trank) > 2) || (Abs(ffile - tfile) > 2))
        continue;
      knight_attacks[i] = knight_attacks[i] | (uint64_t) 1 << sq;
    }
  }
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Problem with bitboard knight attack generator

Post by Sven »

bob wrote:
ZirconiumX wrote:I have been trying to make a bitboard knight attack generator to fill an array of knight attacks.

Code: Select all

Bitboard KnightMoves(int Square)
{
	Bitboard b = 1 << Square, Targets = 0;
	
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) << 17;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) << 10;
	Targets		|= (b & 0x3F3F3F3F3F3F3F3FULL) >> 6;
	Targets		|= (b & 0x7F7F7F7F7F7F7F7FULL) >> 15;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) << 15;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) << 6;
	Targets		|= (b & 0xFCFCFCFCFCFCFCFCULL) >> 10;
	Targets		|= (b & 0xFEFEFEFEFEFEFEFEULL) >> 17;

	return Targets;
}
When I try and generate the array I get some strange figures given, e.g. for square a1 I get 0x132096...

Something at the back of my mind says that I'm suffering from wrap-around issues.

Matthew:out
I don't follow the bit patterns you are using... Since this only needs to be done at startup, I use this:

Code: Select all

int64_t knight_attacks[64];
static const int knightsq[8] = { -17, -15, -10, -6, 6, 10, 15, 17 };

/*
 initialize knight attack board
 */
  for (i = 0; i < 64; i++) {
    knight_attacks[i] = 0;
    frank = Rank(i);
    ffile = File(i);
    for (j = 0; j < 8; j++) {
      sq = i + knightsq[j];
      if ((sq < 0) || (sq > 63))
        continue;
      trank = Rank(sq);
      tfile = File(sq);
      if ((Abs(frank - trank) > 2) || (Abs(ffile - tfile) > 2))
        continue;
      knight_attacks[i] = knight_attacks[i] | (uint64_t) 1 << sq;
    }
  }
I think the bit patterns of Matthew are correct, the only problem "1ULL << Square" has already been mentioned. Also his solution looks quite elegant to me. Personally I would write it like this (assuming a1=0, h1=7 in the comments - the patterns are independent from that):

Code: Select all

Bitboard KnightMoves(int Square)
{
   Bitboard const b = 1ULL << Square;

   return ((b & 0x00007F7F7F7F7F7FULL) << 17)  // up   -up   -right
        | ((b & 0x003F3F3F3F3F3F3FULL) << 10)  // up   -right-right
        | ((b & 0x3F3F3F3F3F3F3F00ULL) >>  6)  // down -right-right
        | ((b & 0x7F7F7F7F7F7F0000ULL) >> 15)  // down -down -right
        | ((b & 0x0000FEFEFEFEFEFEULL) << 15)  // up   -up   -left
        | ((b & 0x00FCFCFCFCFCFCFCULL) <<  6)  // up   -left -left
        | ((b & 0xFCFCFCFCFCFCFC00ULL) >> 10)  // down -left -left
        | ((b & 0xFEFEFEFEFEFE0000ULL) >> 17); // down -down -left
}
and then something like this:

Code: Select all

for (int i = 0; i < 64; i++) {
   knightAttacks[i] = KnightMoves(i);
}
Sven
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Problem with bitboard knight attack generator

Post by Sven »

lucasart wrote:and as for your algorithm itself, i don't think it's correct.
Why do you think so?

For each rank those patterns do the following, assuming a1=0 and h1=7:

Code: Select all

For << 17 and >> 15, 7F masks out bit  7   (h-file).
For << 10 and >>  6, F3 masks out bits 0+1 (a/b-file).
For << 15 and >> 17, FE masks out bit  0   (a-file).
For <<  6 and >> 10, FC masks out bits 6+7 (g/h-file).
Seems ok to me.

Sven
Jami
Posts: 3
Joined: Sun Nov 13, 2011 9:13 pm

Re: Problem with bitboard knight attack generator

Post by Jami »

I think your only problem is the "1 << Square" which should be 1ULL < Square". I tried it here and it works great up to Square = 31.
I am assuming Square = 0 is a1, 1 is b1, etc.

My logic for building the moves is the same, but I build the masks as well. Something like this:

Code: Select all

      NMoves[i] =
         ((src & ~(Rank7 | Rank8 | FileH)) << 17) |  /* Up    2, Right 1 */
         ((src & ~(Rank7 | Rank8 | FileA)) << 15) |  /* Up    2, Left  1 */
         ((src & ~(FileG | FileH | Rank8)) << 10) |  /* Right 2, Up    1 */
         ((src & ~(FileG | FileH | Rank1)) >>  6) |  /* Right 2, Down  1 */
         ((src & ~(Rank1 | Rank2 | FileH)) >> 15) |  /* Down  2, Right 1 */
         ((src & ~(Rank1 | Rank2 | FileA)) >> 17) |  /* Down  2, Left  1 */
         ((src & ~(FileA | FileB | Rank8)) <<  6) |  /* Left  2, Up    1 */
         ((src & ~(FileA | FileB | Rank1)) >> 10);   /* Left  2, Down  1 */
With comments so I don't lose my mind!
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Problem with bitboard knight attack generator

Post by Sven »

Sven Schüle wrote:
lucasart wrote:and as for your algorithm itself, i don't think it's correct.
Why do you think so?

For each rank those patterns do the following, assuming a1=0 and h1=7:

Code: Select all

For << 17 and >> 15, 7F masks out bit  7   (h-file).
For << 10 and >>  6, F3 masks out bits 0+1 (a/b-file).
For << 15 and >> 17, FE masks out bit  0   (a-file).
For <<  6 and >> 10, FC masks out bits 6+7 (g/h-file).
Seems ok to me.

Sven
Only if I had quoted the patterns correctly ... I should have written this:

Code: Select all

For << 17 and >> 15, 7F masks out bit  7   (h-file).
For << 10 and >>  6, 3F masks out bits 6+7 (g/h-file).
For << 15 and >> 17, FE masks out bit  0   (a-file).
For <<  6 and >> 10, FC masks out bits 0+1 (a/b-file).
Sven
ZirconiumX
Posts: 1359
Joined: Sun Jul 17, 2011 11:14 am
Full name: Hannah Ravensloft

Re: Problem with bitboard knight attack generator

Post by ZirconiumX »

The patterns are still wrong:
for a1 (square 0) I get 0x132096ULL, which corresponds to (a1 top left)

Code: Select all

0 1 1 0 1 0 0 1
0 0 0 0 0 1 0 0
1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Which is just a mess.

Matthew:out
tu ne cede malis, sed contra audentior ito