Tricky Optimization Question

[Mike Sherwin]

But but but I do not spin the bits into a bulk move list. I store the raw bits into genbb[ply][fs] for later use that still won't make a bulk move list. No move list.

Later you will have to differentiate between a move and a push because that marks a pawn as Enpassant. If you store both in a single bitboard how do you store that information?

Also there will have to be promotion - how do you store that too?

Please look at my previous post.

[Mike Sherwin]

You left a small detail out.

Yeah, I don't even know your board geometry, and that determines whether to shift left or right, and whether by 1 or by 8 bits. So I figured just posting the general idea would do the trick because you'd know your implementation best, and it would also be most helpful for people who later find that via the forum search function.

I thought about it and I do appreciate the idea a lot, I really do. However, no matter what the board representation is and what direction the shift is there are two constants and that is occ has the fs bit set and the fs bit has to be zero or the idea won't work. Edit: Or fs + 8 set to zero after the shift

[Ras]

However, no matter what the board representation is and what direction the shift is there are two constants and that is occ has the fs bit set and the fs bit has to be zero or the idea won't work.

Ah, that's because if you shift up the occ just like that, then the pawn itself appears as fake pawn on the square immediately ahead so that it will erroneously block the single step forward. Actually, I overlooked that catch.

[Mike Sherwin]

However, no matter what the board representation is and what direction the shift is there are two constants and that is occ has the fs bit set and the fs bit has to be zero or the idea won't work.

Ah, that's because if you shift up the occ just like that, then the pawn itself appears as fake pawn on the square immediately ahead so that it will erroneously block the single step forward. Actually, I overlooked that catch.

+1

[Mike Sherwin]

Oh Nooooo!
It still does not work because of the spurious bits in occ.
But not to worry! I fixed it and optimixed it at the same time

bb = (occ & (0x00100ull << fs)) ? 0 : empty & (0x10100ull << fs);

Let's verify:
00000 false - 10100
00100 true -- 00000
10000 false - 00100
10100 true -- 00000

Please check or optimix further.

Mike: Well that wasn't all that tricky afterall!
Someone: Then why did it take you almost 3 days?

[Mike Sherwin]

I said please!
Oh well, so what.

Anyway, this is the line of code in my engine.

genbb[ply][fs] = (occ & (0x00100ull << fs)) ? 0 : empty & (0x10100ull << fs);

I was able to verify in the debugger that it works perfectly in all possible arrangements of blockers.

So unless anyone can come up with something faster for a single pawn on the second rank this thread looks to be finished.

[dangi12012]

So unless anyone can come up with something faster for a single pawn on the second rank this thread looks to be finished.

You still have a real conditional in there. So that will not be so fast.
What do you write into the BB? The pawns that can move - or the attacked squares?

Both can be done unconditionally.

[Mike Sherwin]

So unless anyone can come up with something faster for a single pawn on the second rank this thread looks to be finished.

You still have a real conditional in there. So that will not be so fast.
What do you write into the BB? The pawns that can move - or the attacked squares?

Both can be done unconditionally.

The moves the pawn can make.

[dangi12012]

The moves the pawn can make.

Code: Select all

genbb[ply][fs] = (pawns << 8 & ~occ)
genbb[ply][fs] |= ((genbb[ply][fs] & SecondRank) << 8 & ~occ)

Alternative:

Code: Select all

const auto forward = pawns << 8;
const auto forward2 = forward | ((pawns & ~FirstRank) << 16);
const auto empty = ~occ;

genbb[ply][fs] = (forward & empty) | (forward2 & empty);

Any reasonable compiler (Clang) should produce the same assembly for both.
But as I said its wasteful to do that for all 8 pawns seperately. The functions above does not care it its 1 pawn or 8 pawns or even more.

If you want to depend the shift on the color so (<< 8 or >> 8) check my signature how that is done without runtime cost.

[Mike Sherwin]

I took some time off because I was worn out. Today I decided to check the CPW again to see if I missed anything. Well I overlooked the multipawn code that can work on a single pawn.

Code: Select all

U64 wSinglePushTargets(U64 wpawns, U64 empty) {
   return nortOne(wpawns) & empty;
}

U64 wDblPushTargets(U64 wpawns, U64 empty) {
   const U64 rank4 = C64(0x00000000FF000000);
   U64 singlePushs = wSinglePushTargets(wpawns, empty);
   return nortOne(singlePushs) & empty & rank4;
}

U64 bSinglePushTargets(U64 bpawns, U64 empty) {
   return soutOne(bpawns) & empty;
}

U64 bDoublePushTargets(U64 bpawns, U64 empty) {
   const U64 rank5 = C64(0x000000FF00000000);
   U64 singlePushs = bSinglePushTargets(bpawns, empty);
   return soutOne(singlePushs) & empty & rank5;
}

For a white pawn singlePushs is basically this.
((1ull << fs << 8) & empty);

Which reduces to this.
u64 bb = ((0x0000000000000100 << fs) & empty);

Then adding the check for double move it becomes.

bb = ((0x0000000000000100 << fs) & empty);
bb = bb | ((bb << 8) & empty);

For black.

bb = ((1ull << fs >> 8) & empty);
bb = bb | ((bb >> 8) & empty);