Kogge Stone Algorithm mistake on chessprogramming Wiki

[Christopher Conkie]

In the following link.........

http://chessprogramming.wikispaces.com/ ... +Algorithm

....this

Code: Select all

U64 eastOccl(U64 gen, U64 pro) {
   pro  = pro & notAFile;
   gen |= pro & (gen  * 2);
   pro  = pro & (pro  * 2);
   gen |= pro & (gen  * 4);
   pro  = pro & (pro  * 4);
   gen |= pro & (gen  * 8);
   return gen;
}

should be......

Code: Select all

U64 eastOccl(U64 gen, U64 pro) {
   pro  = pro & notAFile;
   gen |= pro & &#40;gen << 1&#41;;
   pro  = pro & &#40;pro << 1&#41;;
   gen |= pro & &#40;gen << 2&#41;;
   pro  = pro & &#40;pro << 2&#41;;
   gen |= pro & &#40;gen << 4&#41;;
   return gen;
&#125;

Christopher

[bob]

In the following link.........

http://chessprogramming.wikispaces.com/ ... +Algorithm

....this

Code: Select all

U64 eastOccl(U64 gen, U64 pro) {
   pro  = pro & notAFile;
   gen |= pro & (gen  * 2);
   pro  = pro & (pro  * 2);
   gen |= pro & (gen  * 4);
   pro  = pro & (pro  * 4);
   gen |= pro & (gen  * 8);
   return gen;
}

should be......

Code: Select all

U64 eastOccl(U64 gen, U64 pro) {
   pro  = pro & notAFile;
   gen |= pro & &#40;gen << 1&#41;;
   pro  = pro & &#40;pro << 1&#41;;
   gen |= pro & &#40;gen << 2&#41;;
   pro  = pro & &#40;pro << 2&#41;;
   gen |= pro & &#40;gen << 4&#41;;
   return gen;
&#125;

Christopher

that last shift is a big change. *8 becomes <<3. Is the <<4 correct? If not, I don't see any difference in the two since the compiler will change *2 into <<1 anyway...

[Christopher Conkie]

In the following link.........

http://chessprogramming.wikispaces.com/ ... +Algorithm

....this

Code: Select all

U64 eastOccl(U64 gen, U64 pro) {
   pro  = pro & notAFile;
   gen |= pro & (gen  * 2);
   pro  = pro & (pro  * 2);
   gen |= pro & (gen  * 4);
   pro  = pro & (pro  * 4);
   gen |= pro & (gen  * 8);
   return gen;
}

should be......

Code: Select all

U64 eastOccl(U64 gen, U64 pro) {
   pro  = pro & notAFile;
   gen |= pro & &#40;gen << 1&#41;;
   pro  = pro & &#40;pro << 1&#41;;
   gen |= pro & &#40;gen << 2&#41;;
   pro  = pro & &#40;pro << 2&#41;;
   gen |= pro & &#40;gen << 4&#41;;
   return gen;
&#125;

Christopher

that last shift is a big change. *8 becomes <<3. Is the <<4 correct?

I believe so Bob. You can see it here....

http://64.68.157.89/forum/viewtopic.php ... 57&t=16002

[Zach Wegner]

that last shift is a big change. *8 becomes <<3. Is the <<4 correct? If not, I don't see any difference in the two since the compiler will change *2 into <<1 anyway...

Yes, that's the only mistake. It should be *16.

[Gerd Isenberg]

Sorry Christopher, that was my dumb error.
Thanks for mentioning it. Pradu already corrected it in the Wiki.
One should keep the shifts, rather than trying to outperform the compiler to use leas

The attack getter might be done cheaper by "Fill right with Subtraction" anyway, the reason the bug didn't manifest inside my code:
http://chessprogramming.wikispaces.com/ ... ubtraction
where the bug was still alive in the Kogge-Stone routine for comparison:

Code: Select all

U64 eastAttacks(U64 rooks, U64 empty) {
   const U64 H     =  0x8080808080808080;
   U64 occInclRook =  rooks | ~empty | H;
   U64 occExclRook = (rooks   &=      ~H)  ^ occInclRook;
   U64 rookAttacks = (occExclRook - rooks) ^ occInclRook;
   return rookAttacks;
}

instead

Code: Select all

U64 eastAttacks(U64 rooks, U64 empty) {
   empty  = empty & notAFile;
   rooks |= empty & &#40;rooks << 1&#41;;
   empty  = empty & &#40;empty << 1&#41;;
   rooks |= empty & &#40;rooks << 2&#41;;
   empty  = empty & &#40;empty << 2&#41;;
   rooks |= empty & &#40;rooks << 4&#41;; // instead of * 8
   return notAFile& &#40;rooks << 1&#41;;
&#125;

Cheers,
Gerd

[Christopher Conkie]

One should keep the shifts, rather than trying to out perform the compiler to use leas

Well you know, I still did not take you up on the offer but i can see a day for an LSB assembler function. Bitboards of a Kogge variety are coming with Azrael. I will never forget those words you said...."future processors".

The attack getter might be done cheaper by "Fill right with Subtraction" anyway, the reason the bug didn't manifest inside my code:
http://chessprogramming.wikispaces.com/ ... ubtraction
where the bug was still alive in the Kogge-Stone routine for comparison:

Code: Select all

U64 eastAttacks(U64 rooks, U64 empty) {
   const U64 H     =  0x8080808080808080;
   U64 occInclRook =  rooks | ~empty | H;
   U64 occExclRook = (rooks   &=      ~H)  ^ occInclRook;
   U64 rookAttacks = (occExclRook - rooks) ^ occInclRook;
   return rookAttacks;
}

instead

Code: Select all

U64 eastAttacks(U64 rooks, U64 empty) {
   empty  = empty & notAFile;
   rooks |= empty & &#40;rooks << 1&#41;;
   empty  = empty & &#40;empty << 1&#41;;
   rooks |= empty & &#40;rooks << 2&#41;;
   empty  = empty & &#40;empty << 2&#41;;
   rooks |= empty & &#40;rooks << 4&#41;; // instead of * 8
   return notAFile& &#40;rooks << 1&#41;;
&#125;

Cheers,
Gerd

Yes, nice new stuff to think about. You know something? A complete Kogge-Stone movegen would be nice (regardless of if it's fast of slow. I don't know why, but it's the way i think. You know this from past posts in the old CCC. I can understand it all like mailbox. Rotated is too complex for me. At least I know my limitations. Ask anyone who knows me, I only made an engine to see if it would encourage others to do the same. It became a benchmark at ChessWar for those who were starting out. Me? I care not about grandure. I'm just glad Azrael plays without crashing and that it slowly improves just to dunt them all along a bit and give them something to aspire to.

I am too busy in other ways really.....but it's still alot of fun. That is what it's all about for me....FUN with a big fat F.

Regards

Christopher

[Gerd Isenberg]

Yes, it is big fun. I do it with SIMD and quadbitboards. Generating attack-sets for both sides + legal movegen, while waiting for a pre-fetched cacheline of the hashtable probe...