Kogge Stone Algorithm mistake on chessprogramming Wiki

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Christopher Conkie
Posts: 6068
Joined: Sat Apr 01, 2006 7:34 pm
Location: Scotland
Contact:

Kogge Stone Algorithm mistake on chessprogramming Wiki

Post by Christopher Conkie » Sun Jun 29, 2008 9:17 am

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
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Kogge Stone Algorithm mistake on chessprogramming Wiki

Post by bob » Sun Jun 29, 2008 4:27 pm

Christopher Conkie wrote:In the following link.........

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

....this

Code: Select all

U64 eastOccl&#40;U64 gen, U64 pro&#41; &#123;
   pro  = pro & notAFile;
   gen |= pro & &#40;gen  * 2&#41;;
   pro  = pro & &#40;pro  * 2&#41;;
   gen |= pro & &#40;gen  * 4&#41;;
   pro  = pro & &#40;pro  * 4&#41;;
   gen |= pro & &#40;gen  * 8&#41;;
   return gen;
&#125;
should be......

Code: Select all

U64 eastOccl&#40;U64 gen, U64 pro&#41; &#123;
   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
Posts: 6068
Joined: Sat Apr 01, 2006 7:34 pm
Location: Scotland
Contact:

Re: Kogge Stone Algorithm mistake on chessprogramming Wiki

Post by Christopher Conkie » Sun Jun 29, 2008 4:32 pm

bob wrote:
Christopher Conkie wrote:In the following link.........

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

....this

Code: Select all

U64 eastOccl&#40;U64 gen, U64 pro&#41; &#123;
   pro  = pro & notAFile;
   gen |= pro & &#40;gen  * 2&#41;;
   pro  = pro & &#40;pro  * 2&#41;;
   gen |= pro & &#40;gen  * 4&#41;;
   pro  = pro & &#40;pro  * 4&#41;;
   gen |= pro & &#40;gen  * 8&#41;;
   return gen;
&#125;
should be......

Code: Select all

U64 eastOccl&#40;U64 gen, U64 pro&#41; &#123;
   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

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Kogge Stone Algorithm mistake on chessprogramming Wiki

Post by Zach Wegner » Sun Jun 29, 2008 4:32 pm

bob wrote: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
Posts: 2113
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Kogge Stone Algorithm mistake on chessprogramming Wiki

Post by Gerd Isenberg » Mon Jun 30, 2008 11:38 am

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&#40;U64 rooks, U64 empty&#41; &#123;
   const U64 H     =  0x8080808080808080;
   U64 occInclRook =  rooks | ~empty | H;
   U64 occExclRook = &#40;rooks   &=      ~H&#41;  ^ occInclRook;
   U64 rookAttacks = &#40;occExclRook - rooks&#41; ^ occInclRook;
   return rookAttacks;
&#125;
instead

Code: Select all

U64 eastAttacks&#40;U64 rooks, U64 empty&#41; &#123;
   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
Posts: 6068
Joined: Sat Apr 01, 2006 7:34 pm
Location: Scotland
Contact:

Re: Kogge Stone Algorithm mistake on chessprogramming Wiki

Post by Christopher Conkie » Mon Jun 30, 2008 5:53 pm

Gerd Isenberg wrote: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".
Gerd Isenberg wrote: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&#40;U64 rooks, U64 empty&#41; &#123;
   const U64 H     =  0x8080808080808080;
   U64 occInclRook =  rooks | ~empty | H;
   U64 occExclRook = &#40;rooks   &=      ~H&#41;  ^ occInclRook;
   U64 rookAttacks = &#40;occExclRook - rooks&#41; ^ occInclRook;
   return rookAttacks;
&#125;
instead

Code: Select all

U64 eastAttacks&#40;U64 rooks, U64 empty&#41; &#123;
   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
Posts: 2113
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Kogge Stone Algorithm mistake on chessprogramming Wiki

Post by Gerd Isenberg » Mon Jun 30, 2008 6:47 pm

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...

Post Reply