Problem with bitboard knight attack generator

[Gerd Isenberg]

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

You should be able to fix the problem by debugging and inspecting intermediate results

What about the ones from cpw Knight Pattern, Multiple Knight Attacks to call it with knightAttacks(1ULL << sq)?

[Gerd Isenberg]

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

Bahh, what a mess, horrorfull loops and conditions, even if init stuff only

Are you a bitboarder? I guess you need some knight fillstuff anyway, so why not using it for simple initialization?

Code: Select all

U64 knightAttacks(U64 knights) {
   U64 l1 = (knights >> 1) & C64(0x7f7f7f7f7f7f7f7f);
   U64 l2 = (knights >> 2) & C64(0x3f3f3f3f3f3f3f3f);
   U64 r1 = (knights << 1) & C64(0xfefefefefefefefe);
   U64 r2 = (knights << 2) & C64(0xfcfcfcfcfcfcfcfc);
   U64 h1 = l1 | r1;
   U64 h2 = l2 | r2;
   return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}

[sje]

CookieCat's knight attack bitboard vector initialization

Code: Select all

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

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

Kings:

Code: Select all

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

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

And for pawns:

Code: Select all

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

        for color := 0 to colorrmax do
          begin
            man := synthpawn[color];
            dir0 := mantodir0[man];
            dir1 := mantodir1[man];
            for frsq := 0 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;

[ZirconiumX]

@ Gerd: Yes, I was using it for initialization, and no, the CPW method doesn't work either.

@ Steven: Hate to offend you, but PASCAL is about as much use to me as a plastic shoelace is to a plastic shoelace.

Matthew:out

[Jami]

Your code worked perfectly for me - but I had to make two changes to test...
1. 1ULL < Square
2. Changed Bitboard to a U64.

Could your definition of Bitboard be the cause?

I would break your 8 lines down into separate statements and single step through them.

Jami

[ZirconiumX]

I use a 32bit system.
My code for testing (Gerd's system):

Code: Select all

#include <iostream>

typedef unsigned long long Bitboard;

Bitboard KnightMoves(Bitboard Knights)
{
	Bitboard l1 = (Knights >> 1) & 0x7F7F7F7F7F7F7F7FULL;
	Bitboard l2 = (Knights >> 2) & 0x3F3F3F3F3F3F3F3FULL;
	Bitboard r1 = (Knights << 1) & 0xFEFEFEFEFEFEFEFEULL;
	Bitboard r2 = (Knights << 2) & 0xFCFCFCFCFCFCFCFCULL;
	Bitboard h1 = l1 | r1;
	Bitboard h2 = l2 | r2;
	return (h1 << 16) | (h1 >> 16) | (h2 << 8) | (h2 >> 8);
}

int main()
{
	for (int i = 0; i < 64; i++)
		printf("(%d) 0x%lluULL,\n", i, KnightMoves(1ULL << i));
	return 0;
}

Jami, could you dump your code to the forum, so I can examine it?

Matthew:out

[Jami]

That works fine as well, but I see the problem:

132096 = 0x00020400

You are displaying the results in decimal!

[Gerd Isenberg]

Hmm, there is something flawed. Can you please compile and run this snippet.

Code: Select all

#include <stdio.h>

// typedef unsigned __int64 U64;    // for the old microsoft compilers
typedef unsigned long long  U64; // supported by MSC 13.00+ and C99
#define C64(constantU64) constantU64##ULL


void printBB(U64 bb)
{
  printf("0x%08x%08x\n", (int)(bb >> 32), (int) bb);
}

U64 knightAttacks(U64 knights) {
  U64 l1 = (knights >> 1) & C64(0x7f7f7f7f7f7f7f7f);
  printBB(l1);
  U64 l2 = (knights >> 2) & C64(0x3f3f3f3f3f3f3f3f);
  printBB(l2);
  U64 r1 = (knights << 1) & C64(0xfefefefefefefefe);
  printBB(r1);
  U64 r2 = (knights << 2) & C64(0xfcfcfcfcfcfcfcfc);
  printBB(r2);
  U64 h1 = l1 | r1;
  printBB(h1);
  U64 h2 = l2 | r2;
  printBB(h2);
  return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}


int main(int argc, char** argv)
{
  printBB(knightAttacks(1));
  printBB(knightAttacks(C64(1)<<63));
  return 0;
}

output should look like:

Code: Select all

0x0000000000000000
0x0000000000000000
0x0000000000000002
0x0000000000000004
0x0000000000000002
0x0000000000000004
0x0000000000020400
0x4000000000000000
0x2000000000000000
0x0000000000000000
0x0000000000000000
0x4000000000000000
0x2000000000000000
0x0020400000000000

[Gerd Isenberg]

That works fine as well, but I see the problem:

132096 = 0x00020400

You are displaying the results in decimal!

hehehe

[lucasart]

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

Ypou're right, I didn'# pay close enough attention to the "bit filters" ensuring no shifting was goind "through" the edge of the board.

I use a less subtile but simple and generic code however, allowing me to generate at once king, knoght and pawn attacks.

Code: Select all

static void init_KNP_attacks()
{
	const int K_dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	const int N_dir[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
	const int P_dir[NB_COLOR][2][2] = { {{1,-1},{1,1}}, {{-1,-1},{-1,1}} };

	for (int sq = A1; sq <= H8; sq++) {
		int r = rank(sq), f = file(sq);
		KAttacks[sq] = NAttacks[sq] = 0ULL;

		for (int i = 0; i < 8; i++) {
			int dr = K_dir[i][0], df = K_dir[i][1];
			if (rank_file_ok(r+dr,f+df))
				set_bit(&KAttacks[sq], square(r+dr,f+df));

			dr = N_dir[i][0], df = N_dir[i][1];
			if (rank_file_ok(r+dr,f+df))
				set_bit(&NAttacks[sq], square(r+dr,f+df));
		}

		PAttacks[White][sq] = PAttacks[Black][sq] = 0ULL;
		for (int i = 0; i < 2; i++)
			for (int c = White; c <= Black; c++) {
				int dr = P_dir[c][i][0], df = P_dir[c][i][1];
				if (rank_file_ok(r+dr,f+df))
					set_bit(&PAttacks[c][sq], square(r+dr,f+df));
			}
	}
}

I might rewrite my code to use the same tricks. They can also be turned into a more generic function allowing king knoght and pawn attackes to be generated.