Discussion of chess software programming and technical issues.
Moderators: hgm , Rebel , chrisw
ZirconiumX
Posts: 1334Joined: Sun Jul 17, 2011 11:14 am
Post by ZirconiumX Wed Dec 21, 2011 4:08 pm
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
Some believe in the almighty dollar.
Gerd Isenberg
Posts: 2251Joined: Wed Mar 08, 2006 8:47 pmLocation: Hattingen, Germany
Post by Gerd Isenberg Wed Dec 21, 2011 6:55 pm
What value has a1?
jwes
Posts: 778Joined: Sat Jul 01, 2006 7:11 am
Post by jwes Wed Dec 21, 2011 8:43 pm
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: 3238Joined: Mon May 31, 2010 1:29 pmFull name: lucasart
Post by lucasart Wed Dec 21, 2011 11:42 pm
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: 20943Joined: Mon Feb 27, 2006 7:30 pmLocation: Birmingham, AL
Post by bob Thu Dec 22, 2011 12:01 am
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: 4052Joined: Thu May 15, 2008 9:57 pmLocation: Berlin, GermanyFull name: Sven Schüle
Post by Sven Thu Dec 22, 2011 12:40 am
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: 4052Joined: Thu May 15, 2008 9:57 pmLocation: Berlin, GermanyFull name: Sven Schüle
Post by Sven Thu Dec 22, 2011 12:52 am
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: 3Joined: Sun Nov 13, 2011 9:13 pm
Post by Jami Thu Dec 22, 2011 4:02 am
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: 4052Joined: Thu May 15, 2008 9:57 pmLocation: Berlin, GermanyFull name: Sven Schüle
Post by Sven Thu Dec 22, 2011 9:01 am
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: 1334Joined: Sun Jul 17, 2011 11:14 am
Post by ZirconiumX Thu Dec 22, 2011 11:22 am
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
Some believe in the almighty dollar.