News for hackers. Stuff that matters.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by dragontamer on Tuesday April 17, 2018 @01:52PM (#16860650)
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)

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by ZirconiumX on Wednesday April 18, 2018 @02:53AM (#16865235)
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.

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by xoroshiro on Tuesday April 17, 2018 @07:25PM (#16863219)
> 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.

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by perl4ever on Tuesday April 17, 2018 @03:36PM (#16861575)
Imagine an alternate history in which chessboards were always 9x9, but computers were 64 bit as here...
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by tytytytytytytyt on Tuesday April 17, 2018 @07:57PM (#16863424)
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by ateesdalejr on Tuesday April 17, 2018 @04:58PM (#16862261)
Ouch. I can already imagine all the painful ways in which that would be worked around.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by gowld on Tuesday April 17, 2018 @07:40PM (#16863314)
Computers used to be 32bit, 16bit, 8bit...
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by eutectic on Wednesday April 18, 2018 @03:47PM (#16870484)
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.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by dragontamer on Thursday April 19, 2018 @03:23PM (#16879198)
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.

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by perl4ever on Tuesday April 17, 2018 @08:23PM (#16863583)
Computers used to have 6 bit bytes and 36 bit words...I don't have my mom's IBM 704 manual anymore though.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by cglouch on Tuesday April 17, 2018 @02:44PM (#16861120)
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!

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by tromp on Tuesday April 17, 2018 @02:33PM (#16861036)
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...

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by Aardwolf on Tuesday April 17, 2018 @03:03PM (#16861272)
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?!?!

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by ConcernedCoder on Tuesday April 17, 2018 @03:55PM (#16861724)
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...
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by cuckcuckspruce on Tuesday April 17, 2018 @04:42PM (#16862133)
I've made a note to ping Jason Scott and Archiveteam about this on IRC when I get home.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by tecleandor on Tuesday April 17, 2018 @04:06PM (#16861824)
At least, at static cache/render would be great.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by beefman on Tuesday April 17, 2018 @02:04PM (#16860779)
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.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by Aardwolf on Tuesday April 17, 2018 @03:17PM (#16861412)
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 :)

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by ateesdalejr on Tuesday April 17, 2018 @05:02PM (#16862294)
Don't forget the sticky bars that hide when scrolling down but suddenly reappear when scrolling up... I hate those things with a passion.
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by caf on Tuesday April 17, 2018 @08:41PM (#16863689)
More pressingly, it looks like the Archive Team need some help on this one: https://archiveteam.org/index.php?title=Wikispaces
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by shmageggy on Tuesday April 17, 2018 @03:40PM (#16861610)
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
Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by fogleman on Tuesday April 17, 2018 @03:38PM (#16861594)
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...

Re:Magic Bitboards: Finding all valid bishop moves in a 64-b... by darepublic on Tuesday April 17, 2018 @03:21PM (#16861455)
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.