5 ms·
The code I'd like to highlight in this example is as follows: U64 bishopAttacks(U64 occ, enumSquare sq) { occ &= mBishopTbl[sq].mask; occ *=
by dragontamer 9y ago
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+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...
- xoroshiro 9y ago> something like ~15 clock cycles Even less with PEXT! https://chessprogramming.wikispaces.com/BMI2#PEXTBitboards https://chessprogramming.wikispaces.com/BMI2#PEXTBitboards Poking around and reading through the wiki blew my mind. I hope they are archived somewhere.
- ZirconiumX 9y agoSomething 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%20far http://chessprogramming.wikispaces.com/Best%20Magics%20so%20... [2]: http://www.talkchess.com/forum/viewtopic.php?t=65187 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.