The code I'd like to highlight in this example is as follows:

    U64 bishopAttacks(U64 occ, enumSquare sq) {
       occ &= mBishopTbl[sq].mask;
       occ *= mBishopTbl[sq].magic;
       occ >>= 64-9;
       return mBishopAttacks[sq][occ];
    }

Two bit-operations and one Multiply are all that is needed to "perfect hash" a bishop's position + all of the possible combinations of pieces which might block it. From there, the "occ" variable serves as a lookup-table's index, providing a pre-calculated bitmask of all of the locations a bishop can attack.

It seems like the "occ" bitboard represents the occupancy of the board. (A bitmask of 1 for every piece that could block the bishop's movement). While "enumSquare" seems to be the square the bishop is actually on.

In effect, this is a time-space tradeoff, with every single bishop (or rook) attack being precomputed in a lookup table. Then, during runtime, two-bit operations + one multiply are all that is needed to use the table.

---------------

Some notes to help decipher what is going on:

* Because a chessboard is 64 squares, a 64-bit long integer is all that's needed to represent true/false values across a board. These "true-false" collections across a chessboard are called "bitboards", and can represent anything from board state (Ex: a bitboard that represents all black pawns), to "potential moves a bishop can make" that the AI should iterate against.

* The general problem to solve here is called the Sliding Piece Attack: https://chessprogramming.wikispaces.com/Sliding+Piece+Attack... . Bishops and Rooks are complicated, because they may be blocked by enemy and/or friendly pieces. Other pieces (Knights, Pawns, or Kings) have much simpler movement patterns.

That's what makes this so magnificent: the calculation in runtime is calculated in something like ~15 clock cycles on a modern machine. (2 cycles for the two bitwise operations, 5 cycles for the multiply, and 5 cycles for an L2 lookup)

Something interesting to note is the variety of ideas based on this. What you see there is "plain" magic bitboards, where the right-shift is constant and used to index a two-dimensional array.

That's rather wasteful, because the centre squares need only around 2^5 occupancies, which is why "fancy" magic bitboards exist. In these, the right-shift is variable, and the occupancy calculation is added to a table of offsets to get the output, shrinking the tables from about 2MB to 800KiB for even the "easy" right-shift amounts.

So the question is whether we can find smaller magic numbers[1]. Niklas Fiekas has found a trick[2] that helps reduce the brute-force search space for magics, but it's still not trivial to solve.

[1]: http://chessprogramming.wikispaces.com/Best%20Magics%20so%20... [2]: http://www.talkchess.com/forum/viewtopic.php?t=65187

I could also make a write-up of Hyperbola Quintessence, which I think is a fantastic bit of bit-twiddling, if someone is interested.

> something like ~15 clock cycles

Even less with PEXT! https://chessprogramming.wikispaces.com/BMI2#PEXTBitboards

Poking around and reading through the wiki blew my mind. I hope they are archived somewhere.

Imagine an alternate history in which chessboards were always 9x9, but computers were 64 bit as here...

Ouch. I can already imagine all the painful ways in which that would be worked around.

Computers used to be 32bit, 16bit, 8bit...

But 64-bit is enough to represent essentially any value you might care to manipulate numerically, with rare exceptions such as cryptography. Given the constraints and trade-offs of real world computing, I suspect 128-bit will never become the norm.

You might want to look into AVX-512.

Yeah, 512-bits / SIMD computations. If chessboards were bigger, then we'd probably just use the SIMD registers. 128-bit SSE is quite common, and 256-bit AVX has been around for ~5 years now.

Computers used to have 6 bit bytes and 36 bit words...I don't have my mom's IBM 704 manual anymore though.

Using bit manipulation to calculate chess piece movements is really quite satisfying. If magic bitboards are too confusing, the precursor - "kindergarten bitboards" - are a bit easier to understand. I have a description here if anyone is curious: https://github.com/cglouch/snakefish#sliding-pieces

I think once you understand the principle behind kindergarten bitboards, magic bitboards start to make more sense. It's basically a more clever way of indexing into a precomputed move table, that takes advantage of the redundancy in occupancy states, and requires even fewer instructions to determine the index. Although it does still feel kinda magic!

Bitboards also work fabulously on connect-4, encoding a 7x6 position in 7x(6+1)=49 bits [1] and allowing for a win test with 8 shifts/ands:

    // return whether newboard includes a win
    final boolean haswon(long newboard)
    {
      long y = newboard & (newboard>>HEIGHT);
      if ((y & (y >> 2*HEIGHT)) != 0) // check diagonal \
        return true;
      y = newboard & (newboard>>H1);
      if ((y & (y >> 2*H1)) != 0) // check horizontal -
        return true;
      y = newboard & (newboard>>H2); // check diagonal /
      if ((y & (y >> 2*H2)) != 0)
        return true;
      y = newboard & (newboard>>1); // check vertical |
      return (y & (y >> 2)) != 0;
    }

Dominikus Herzberg offers a more detailed explanation [2] for the benefit of his students.

[1] http://tromp.github.io/c4/Connect4.java

[2] https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...

I found a notice in wikispaces that they're closing, with as reason that "it's too expensive to bring it to modern standards"

So, they're going to delete all that useful information presented on a perfect fast loading and fast scrolling website?!?!

I wonder how much nameserver + hosting is for them? I wish they would just leave it as-is and put up a go-fund-me for the hosting costs...

I've made a note to ping Jason Scott and Archiveteam about this on IRC when I get home.

At least, at static cache/render would be great.

Wikispaces, hosting this and many other invaluable wikis, is shutting down soon. It would be great if TES would open the source. There is also, it seems to me, a need for a modern alternative to MediaWiki.

What do you mean by 'modern' here? Modern seems to look worse to me: floating elements that prevent zooming in on mobile, auto playing videos, like/share buttons everywhere, ethereal (as opposed to permanent) content, things that only load as you scroll down (so it feels slower), ...

Did you mean something else by modern, if so I'm curious what :)

Don't forget the sticky bars that hide when scrolling down but suddenly reappear when scrolling up... I hate those things with a passion.

More pressingly, it looks like the Archive Team need some help on this one: https://archiveteam.org/index.php?title=Wikispaces

I found that this answer on stack exchange was the best resource for understanding magic bitboards and how/why they work. A really well written answer: https://stackoverflow.com/a/30862064/1056032

Not just bishops, also rooks (and queens).

Magic bitboards are awesome. Here's my implementation:

https://github.com/fogleman/MisterQueen/blob/master/src/bb.c...

I remember all the time searching through here when implementing my own chess AI a few years back. Good memories. Sad to hear wikispaces is closing.