Moderator: Ras
I somehow mixed up my sources in confusion. The ones I posted don't quite work. My mental ability may be too far gone for me to finish this on my own.dangi12012 wrote: ↑Fri Jan 20, 2023 9:57 am Any updates on this topic ? I am looking very much forward to a new original movegenerator!
OMG, I managed to fix the bishops, again. And here's the proof!dangi12012 wrote: ↑Fri Jan 20, 2023 9:57 am Any updates on this topic ? I am looking very much forward to a new original movegenerator!
It is 5am! I surprised myself! I was able to finish the rook.dangi12012 wrote: ↑Fri Jan 20, 2023 9:57 am Any updates on this topic ? I am looking very much forward to a new original movegenerator!
Once I realized the vertical bits were not bcdefg but rather gfedcb I was able to flip the initialization. Perft(6) = 119060324. The name is Kindergarten Super SISSY Bitboards. But this time SISSY stands for Split Index Sub Set Yielding. Code: Select all
static uint64_t Rook(int sq, uint64_t occ)
{
uint64_t vBlockers = (occ >> (sq & 7)) & 0x0101010101010101ull;
uint64_t hBlockers = occ & hMask[sq];
uint64_t vIndex = ((vBlockers * 0x0080402010080400ull) >> 58);
uint64_t hIndex = (hBlockers >> (((sq >> 3) << 3)) + 1);
return (vSubset[sq][vIndex] | hSubset[sq][hIndex]) & ~(1ull << sq);
}First, thanks for the write up in your main thread!dangi12012 wrote: ↑Sat Jan 21, 2023 8:05 pm Very very cool - I tried this code and it worked perfectly on the first try!
https://www.talkchess.com/forum3/viewto ... 13#p941913
Performance is looking very good - essentially only magic and pext are faster -
I have some questions. Bishop is perfect - only rook is open in my mind:1) vBlockers could be masked the same way? uint64_t vBlockers = occ & vMask[sq]; (I tried with vmask it does not work)Code: Select all
static uint64_t Rook(int sq, uint64_t occ) { uint64_t vBlockers = (occ >> (sq & 7)) & 0x0101010101010101ull; uint64_t hBlockers = occ & hMask[sq]; uint64_t vIndex = ((vBlockers * 0x0080402010080400ull) >> 58); uint64_t hIndex = (hBlockers >> (((sq >> 3) << 3)) + 1); return (vSubset[sq][vIndex] | hSubset[sq][hIndex]) & ~(1ull << sq); }
2) can hIndex get the same code? uint64_t hIndex = (hBlockers * magic) >> 58); ?
If that were the case all 4 rays for rook and bishop could be consolidated into the same instructions which all cpus like very much.
And with other algos if it is a "array of structs" for the vhda Masks the compilesr will emit avx2 code making it faster still. Thats why a uniform 4 Mask approach would be great.
Code: Select all
static uint64_t dMask[64];
static uint64_t aMask[64];
static uint64_t vSubset[64][64];
static uint64_t hSubset[64][64];
static uint64_t dSubset[64][64];
static uint64_t aSubset[64][64];
static void InitSquare(int sq)
{
int ts, dx, dy;
uint64_t occ, index;
int x = sq % 8;
int y = sq / 8;
// Initialize Kindergarten Super SISSY Bitboards
// diagonals
for (ts = sq + 9, dx = x + 1, dy = y + 1; dx < FILEh && dy < RANK8; dMask[sq] |= 1ull << ts, ts += 9, dx++, dy++);
for (ts = sq - 9, dx = x - 1, dy = y - 1; dx > FILEa && dy > RANK1; dMask[sq] |= 1ull << ts, ts -= 9, dx--, dy--);
// anti diagonals
for (ts = sq + 7, dx = x - 1, dy = y + 1; dx > FILEa && dy < RANK8; aMask[sq] |= 1ull << ts, ts += 7, dx--, dy++);
for (ts = sq - 7, dx = x + 1, dy = y - 1; dx < FILEh && dy > RANK1; aMask[sq] |= 1ull << ts, ts -= 7, dx++, dy--);
// diagonal indexes
for (index = 0; index < 64; index++) {
dSubset[sq][index] = 0;
occ = index << 1;
if ((sq & 7) != FILEh && (sq >> 3) != RANK8) {
for (ts = sq + 9; ; ts += 9) {
dSubset[sq][index] |= (1ull << ts);
if (occ & (1ull << (ts & 7))) break;
if ((ts & 7) == FILEh || (ts >> 3) == RANK8) break;
}
}
if ((sq & 7) != FILEa && (sq >> 3) != RANK1) {
for (ts = sq - 9; ; ts -= 9) {
dSubset[sq][index] |= (1ull << ts);
if (occ & (1ull << (ts & 7))) break;
if ((ts & 7) == FILEa || (ts >> 3) == RANK1) break;
}
}
}
// anti diagonal indexes
for (index = 0; index < 64; index++) {
aSubset[sq][index] = 0;
occ = index << 1;
if ((sq & 7) != FILEa && (sq >> 3) != RANK8) {
for (ts = sq + 7; ; ts += 7) {
aSubset[sq][index] |= (1ull << ts);
if (occ & (1ull << (ts & 7))) break;
if ((ts & 7) == FILEa || (ts >> 3) == RANK8) break;
}
}
if ((sq & 7) != FILEh && (sq >> 3) != RANK1) {
for (ts = sq - 7; ; ts -= 7) {
aSubset[sq][index] |= (1ull << ts);
if (occ & (1ull << (ts & 7))) break;
if ((ts & 7) == FILEh || (ts >> 3) == RANK1) break;
}
}
}
// vertical indexes
for (index = 0; index < 64; index++) {
vSubset[sq][index] = 0;
uint64_t blockers = 0;
for (int i = 0; i <= 5; i++) {
if (index & (1ull << i)) {
blockers |= (1ull << (((5 - i) << 3) + 8));
}
}
if ((sq >> 3) != RANK8) {
for (ts = sq + 8; ; ts += 8) {
vSubset[sq][index] |= (1ull << ts);
if (blockers & (1ull << (ts - (ts & 7)))) break;
if ((ts >> 3) == RANK8) break;
}
}
if ((sq >> 3) != RANK1) {
for (ts = sq - 8; ; ts -= 8) {
vSubset[sq][index] |= (1ull << ts);
if (blockers & (1ull << (ts - (ts & 7)))) break;
if ((ts >> 3) == RANK1) break;
}
}
}
// horizontal indexes
for (index = 0; index < 64; index++) {
hSubset[sq][index] = 0;
occ = index << 1;
if ((sq & 7) != FILEh) {
for (ts = sq + 1; ; ts += 1) {
hSubset[sq][index] |= (1ull << ts);
if (occ & (1ull << (ts & 7))) break;
if ((ts & 7) == FILEh) break;
}
}
if ((sq & 7) != FILEa) {
for (ts = sq - 1; ; ts -= 1) {
hSubset[sq][index] |= (1ull << ts);
if (occ & (1ull << (ts & 7))) break;
if ((ts & 7) == FILEa) break;
}
}
}
}
static void Init()
{
for (int i = 0; i < 64; i++) {
InitSquare(i);
}
}
static uint64_t Bishop(int sq, uint64_t occ)
{
return
dSubset[sq][(((occ & dMask[sq]) * 0x0202020202020202ull) >> 58)] +
aSubset[sq][(((occ & aMask[sq]) * 0x0202020202020202ull) >> 58)];
}
static uint64_t Rook(int sq, uint64_t occ)
{
uint64_t hIndex = (occ >> ((sq & 0b11111000u) + 1)) & 0x000000000000003f;
uint64_t vIndex = ((((occ >> (sq & 7)) & 0x0101010101010101ull) * 0x0080402010080400ull) >> 58);
return vSubset[sq][vIndex] | hSubset[sq][hIndex];
}
static uint64_t Queen(int sq, uint64_t occ)
{
return Rook(sq, occ) | Bishop(sq, occ);
}
Code: Select all
// GenMoves.cpp
__forceinline
void WPawn2(Thread* t) {
tsBits[ply][fsq] = ((0x0000000000000100ull << fsq) & empty) |
((tsBits[ply][fsq] << 8) & empty) | (wpCaptures[fsq] & enemy);
atkBits[ply] |= wpCaptures[fsq];
}
__forceinline
void WPawn3467(Thread* t) {
tsBits[ply][fsq] = ((0x0000000000000100ull << fsq) & empty) | (wpCaptures[fsq] & enemy);
atkBits[ply] |= wpCaptures[fsq];
}
__forceinline
void WPawn5(Thread* t) {
tsBits[ply][fsq] = ((0x0000000000000100ull << fsq) & empty) | (wpCaptures[fsq] & (enemy | epBit[ply]));
atkBits[ply] |= wpCaptures[fsq];
}
typedef void (*Wp[])(Thread*);
Wp WPawns = { nullptr, WPawn2, WPawn3467, WPawn3467, WPawn5, WPawn3467, WPawn3467 };
__forceinline
void WPawn(Thread* t) {
WPawns[fsq >> 3](t);
}
__forceinline
void BPawn7(Thread* t) {
tsBits[ply][fsq] = ((1ull << (fsq - 8)) & empty);
tsBits[ply][fsq] |= ((tsBits[ply][fsq] >> 8) & empty) | (bpCaptures[fsq] & enemy);
atkBits[ply] |= bpCaptures[fsq];
}
__forceinline
void BPawn6532(Thread* t) {
tsBits[ply][fsq] = ((1ull << (fsq - 8)) & empty) | (bpCaptures[fsq] & enemy);
atkBits[ply] |= bpCaptures[fsq];
}
__forceinline
void BPawn4(Thread* t) {
tsBits[ply][fsq] = ((1ull << (fsq - 8)) & empty) | (bpCaptures[fsq] & (enemy | epBit[ply]));
atkBits[ply] |= bpCaptures[fsq];
}
typedef void (*Bp[])(Thread*);
Bp BPawns = { nullptr, BPawn7, BPawn6532, BPawn6532, BPawn4, BPawn6532, BPawn6532 };
__forceinline
void BPawn(Thread* t) {
BPawns[fsq >> 3](t);
}
__forceinline
void Knight(Thread* t) {
tsBits[ply][fsq] = knightMoves[fsq] & notme;
atkBits[ply] |= knightMoves[fsq];
}
__forceinline
void Bishop(Thread* t) {
atkBits[ply] |= tsBits[ply][fsq] =
dSubset[fsq][(((occ & dMask[fsq]) * 0x0202020202020202ull) >> 58)] +
aSubset[fsq][(((occ & aMask[fsq]) * 0x0202020202020202ull) >> 58)];
tsBits[ply][fsq] &= notme;
}
__forceinline
void Rook(Thread* t) {
u64 hIndex = (occ >> ((fsq & 0b11111000u) + 1)) & 0x000000000000003f;
u64 vIndex = ((((occ >> (fsq & 7)) & 0x0101010101010101ull) * 0x0080402010080400ull) >> 58);
atkBits[ply] |= tsBits[ply][fsq] = vSubset[fsq][vIndex] | hSubset[fsq][hIndex];
tsBits[ply][fsq] &= notme;
}
__forceinline
void Queen(Thread* t) {
Bishop(t);
Rook(t);
}
__forceinline
void King(Thread* t) {
tsBits[ply][fsq] = kingMoves[fsq] & notme;
atkBits[ply] |= kingMoves[fsq];
}
__forceinline
void WKingC(Thread* t) {
tsBits[ply][fsq] = kingMoves[fsq] & notme;
atkBits[ply] |= kingMoves[fsq];
tsBits[ply][fsq] |= (u64)(((board[h1] == WRC) + !(occ & f1g1) + (AttackedByBlack(t, e1f1g1) == 0)) == 3) << g1;
tsBits[ply][fsq] |= (u64)(((board[a1] == WRC) + !(occ & d1c1) + (AttackedByBlack(t, e1d1c1) == 0)) == 3) << c1;
}
__forceinline
void BKingC(Thread* t) {
tsBits[ply][fsq] = kingMoves[fsq] & notme;
atkBits[ply] |= kingMoves[fsq];
tsBits[ply][fsq] |= (u64)(((board[h8] == BRC) + !(occ & f8g8) + (AttackedByBlack(t, e8f8g8) == 0)) == 3) << g8;
tsBits[ply][fsq] |= (u64)(((board[a8] == BRC) + !(occ & d8c8) + (AttackedByWhite(t, e8d8c8) == 0)) == 3) << c8;
}
typedef void (*Gen[])(Thread*);
Gen Generate = {
WPawn, Knight, Bishop, Rook, Rook, Queen, WKingC, King,
BPawn, Knight, Bishop, Rook, Rook, Queen, BKingC, King,
};
s32 GenAllMoves(Thread* t) {
u64 me = fsBits[stm];
enemy = fsBits[1 - stm];
occ = me | enemy;
empty = ~occ;
atkBits[ply] = 0;
notme = enemy | empty;
do {
fsq = std::countr_zero(me);
me ^= 1ull << fsq;
Generate[board[fsq]](t);
} while (me);
return ((atkBits[ply] & pcBits[1 - stm][KING]) == 0);
}
I'm trying to follow your C++ code and if I understand correctly, you are generating a mask that indicates what squares a side controls or can capture. I do that just for pawns because it is needed for my mobility calculations since I only want to count moves that don't move a piece to a square controlled by the other side's pawns. I had wanted to come up with some way to update this mask incrementally every time a pawn is moved, but the problem I ran into was that each bit in the mask could be the combined control of more than one piece. So just because the moving piece no longer attacks that square doesn't mean some other piece is no longer attacking it. So, currently I end up recalculating that mask every time I need to calculate mobility. From reading your post it sounded like maybe you had a different way of updating the mask. Am I understanding you correctly?Mike Sherwin wrote: ↑Wed Jan 25, 2023 12:01 am Now, class we are getting into the really fun stuff actually teaching the chess engine how to generate moves! We are taking a bit of a novel approach in that we are not going to create a list of moves right away. Instead we are going to store the to-square bits by ply and the from-square. This saves a lot of time when there is a quick alpha-beta cut. Also we don't lose valuable information in the process.
That sounds correct but to recap.JoAnnP38 wrote: ↑Thu Jan 26, 2023 4:04 pm I'm trying to follow your C++ code and if I understand correctly, you are generating a mask that indicates what squares a side controls or can capture. I do that just for pawns because it is needed for my mobility calculations since I only want to count moves that don't move a piece to a square controlled by the other side's pawns. I had wanted to come up with some way to update this mask incrementally every time a pawn is moved, but the problem I ran into was that each bit in the mask could be the combined control of more than one piece. So just because the moving piece no longer attacks that square doesn't mean some other piece is no longer attacking it. So, currently I end up recalculating that mask every time I need to calculate mobility. From reading your post it sounded like maybe you had a different way of updating the mask. Am I understanding you correctly?