3

What I Am Trying To Do I am trying to perform some bitwise operations to create a chess engine. To make this engine, I need to be able to generate moves for pieces, like rooks. There is a handy formula for creating a bitboard of squares available for the rook to move to: bitboardOfOccupiedSquares ^ (bitboardOfOccupiedSquares - 2 * bitboardOfPieceToMove).

Consider the following chess board position:enter image description here

I am trying to generate all of the squares that the rook on h1 can move to. So this should be easy, I simply grab the bitboard of occupied squares (18410433801713942527) and grab the bitboard for the rook on h1 (2^63 or 9223372036854775808) and plug them into the equation:

let bitboardOfOccupiedSquares: UInt64 = 18410433801713942527
let bitboardOfPieceToMove: UInt64 = 9223372036854775808
let bitboardOfSquaresPieceCanMoveTo: UInt64 = bitboardOfOccupiedSquares ^ (bitboardOfOccupiedSquares - 2 * bitboardOfPieceToMove)

My Issue The problem I am facing is that there is no value for bitboardOfOccupiedSquares that is larger than 2 * (2^63), so the operation (bitboardOfOccupiedSquares - 2 * bitboardOfPieceToMove) always produces a negative number when passing 2^63 as the value for bitboardOfPieceToMove. Of course, negative numbers cannot be represented with unsigned integers, so the program crashes on me whenever a piece on h1 is passed.

I have seen a youtuber accomplish this method by using signed integers in Java (as seen here and here). I have tried using signed bitboards instead of unsigned bitboards throughout my engine, but this simply causes other issues to crop up in other places. Plus I know that most engines make use of unsigned bitboards with no issues.

Furthermore, 2 * (2^63) equals 18446744073709551616, which is one above the UInt64 max of 18446744073709551615, which I figure has to do with the whole "2s complement" idea.

What I'm Wondering Has anybody in the chess engine programming world worked with this o^(o-2r) formula, especially with unsigned bitboards? I am able to grasp the ideas conveyed in the article and youtube videos, but can't seem to make it work in practice with unsigned bitboards.

David Chopin
  • 2,780
  • 2
  • 19
  • 40
  • 1
    I am not familiar with that formula or the underlying mechanism, but “overflow operators” may be what you are looking for: `let bitboardOfSquaresPieceCanMoveTo = bitboardOfOccupiedSquares ^ (bitboardOfOccupiedSquares &- 2 &* bitboardOfPieceToMove)` – Martin R Mar 11 '20 at 09:11
  • Awesome! I'll check them out. – David Chopin Mar 11 '20 at 09:13
  • 1
    Documentation: https://docs.swift.org/swift-book/LanguageGuide/AdvancedOperators.html#ID37 – Martin R Mar 11 '20 at 09:18
  • I was just reading that. I'll see if I can make these guys work and get back to you. It seems most languages don't have these sorts of operators? – David Chopin Mar 11 '20 at 09:19
  • In C this “wrap around” is the default behavior for arithmetic with *unsigned* integers, and in Java it is (I think) the default behavior for all arithmetic integer operations. – Martin R Mar 11 '20 at 09:21
  • See also https://stackoverflow.com/q/31417588/1187415. – Martin R Mar 11 '20 at 09:26
  • It worked! It seems I can use any of these operators indiscriminately in the place of any other operator, even in scenarios that would never cause an overflow, and get the desired result. I imagine there is no &/ operator because one can never cause an overflow via division. If you'd like to provide an answer, I'll accept it as correct! – David Chopin Mar 11 '20 at 10:16

1 Answers1

0

This trick only works on positive rays (East, North, North East, North West). For a piece on E4 these look like this:

      East             North           North East       North West
0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0   0 0 0 0 0 0 0 0   1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0   0 0 0 0 0 0 0 1   0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0   0 0 0 0 0 0 1 0   0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0   0 0 0 0 0 1 0 0   0 0 0 1 0 0 0 0
0 0 0 0 x 1 1 1   0 0 0 0 x 0 0 0   0 0 0 0 x 0 0 0   0 0 0 0 x 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0

The technique relies upon the propagation of borrowing caused by the subtraction. During subtraction, in any base, you always borrow from more significant digits. Therefore, the borrow propagation will only affect those bits of the bitboard that are more significant than the bit representing the square the piece is on.

Negative rays only use bits that are less significant:

      West             South           South East       South West
0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
1 1 1 1 x 0 0 0   0 0 0 0 x 0 0 0   0 0 0 0 x 0 0 0   0 0 0 0 x 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0   0 0 0 0 0 1 0 0   0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0   0 0 0 0 0 0 1 0   0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0   0 0 0 0 0 0 0 1   0 1 0 0 0 0 0 0

If the rook bitboard is valued 2^63, then the rook is on the H8 square, and has no attacks along any positive rays.

The multiplication by two would also be implemented as a left shift of one:

0x8000000000000000 << 1 = 0x0000000000000000

Giving zero rather than a negative number, which would result in:

o^(o-2r) = OCCUPANCY ^ (OCCUPANCY - (2 * 0x8000000000000000))
         = OCCUPANCY ^ (OCCUPANCY - (0x8000000000000000 << 1))
         = OCCUPANCY ^ (OCCUPANCY - 0)
         = OCCUPANCY ^ OCCUPANCY
         = 0

The xor of the occupancy board with itself is zero, meaning no attacks are found.

44stonelions
  • 192
  • 1
  • 10