12 ms·
Magic Bitboards: Finding all valid bishop moves in a 64-bit multiply (2008)
- beefman 9y agoWikispaces, 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.
- deleted 9y ago[deleted]
- Aardwolf 9y agoWhat 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 :)
- ateesdalejr 9y agoDon't forget the sticky bars that hide when scrolling down but suddenly reappear when scrolling up... I hate those things with a passion.
- caf 9y agoMore pressingly, it looks like the Archive Team need some help on this one: https://archiveteam.org/index.php?title=Wikispaces https://archiveteam.org/index.php?title=Wikispaces
- dragontamer 9y agoThe 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+Attacks 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)
- perl4ever 9y agoImagine an alternate history in which chessboards were always 9x9, but computers were 64 bit as here...
- ateesdalejr 9y agoOuch. I can already imagine all the painful ways in which that would be worked around.
- gowld 9y agoComputers used to be 32bit, 16bit, 8bit...
- perl4ever 9y agoComputers used to have 6 bit bytes and 36 bit words...I don't have my mom's IBM 704 manual anymore though.
- eutectic 9y agoBut 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.
- dragontamer 9y agoYou 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.
- tytytytytytytyt 9y agohttps://en.wikipedia.org/wiki/Word_(computer_architecture)#Table_of_word_sizes https://en.wikipedia.org/wiki/Word_(computer_architecture)#T...
- 9y ago
- tromp 9y agoBitboards 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 http://tromp.github.io/c4/Connect4.java [2] https://github.com/denkspuren/BitboardC4/blob/master/BitboardDesign.md https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...
- cglouch 9y agoUsing 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 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!
- Aardwolf 9y agoI 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?!?!
- ConcernedCoder 9y agoI 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...
- tecleandor 9y agoAt least, at static cache/render would be great.
- cuckcuckspruce 9y agoI've made a note to ping Jason Scott and Archiveteam about this on IRC when I get home.
- darepublic 9y agoI 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.
- fogleman 9y agoNot just bishops, also rooks (and queens). Magic bitboards are awesome. Here's my implementation: https://github.com/fogleman/MisterQueen/blob/master/src/bb.c#L275-L289 https://github.com/fogleman/MisterQueen/blob/master/src/bb.c...
- shmageggy 9y agoI 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 https://stackoverflow.com/a/30862064/1056032