What I Am Doing: I am writing a chess engine in Swift. One of the most important parts of writing a strong chess engine is the ability to generate as many possible future board positions in as little time possible. The more positions your engine can generate and evaluate in a shorter amount of time, the stronger the engine is.
That being said, I've written functions for generating moves for sliding pieces (bishops, rooks, and queens). These functions make use of overflow operators (&+, &-, &*), as using normal bitwise operators frequently cause overflow errors.
Generating said moves requires two functions, one for generating all legal vertical and horizontal moves for a sliding piece, and one for generating all legal diagonal moves for a sliding piece. These two functions effectively go about doing the same thing, we just manipulate the arguments slightly differently. Here is what the function for generating horizontal and vertical moves looks like:
//occupied is a bitboard that represents every square on the chess board that is occupied
//this value is set somewhere before our move generation functions are ever called
var occupied: UInt64 = 0
//the rankMasks and fileMasks are simply arrays of bitboards that represent each individual file and rank on a chess board
//rankMasks8[0] would represent the squares a8-h8, rankMasks8[1] would represent the squares a7-h7
//fileMasks8[0] would represent the squares a1-a8, fileMasks8[1] would represent the squares b1-b8
let rankMasks8: [UInt64] = [ 255, 65280, 16711680, 4278190080, 1095216660480, 280375465082880, 71776119061217280, 18374686479671623680 ]
let fileMasks8: [UInt64] = [ 72340172838076673, 144680345676153346, 289360691352306692, 578721382704613384, 1157442765409226768, 2314885530818453536, 4629771061636907072, 9259542123273814144 ]
...
//We pass a square (0 - 63) as s and we are returned a UInt64, the bitboard representing all the squares that the piece on the passed square can move to.
func horizontalAndVerticalMoves(s: Int) -> UInt64 {
//convert the passed square into a bitboard that represents its location, by raising 2 to the power of s
let binaryS: UInt64 = 1<<s
//formula for generating possible horizontal moves
let possibilitiesHorizontal: UInt64 = (occupied &- (2 &* binaryS)) ^ UInt64.reverse(UInt64.reverse(occupied) &- 2 &* UInt64.reverse(binaryS))
//formula for generating vertical moves
let possibilitiesVertical: UInt64 = ((occupied & fileMasks8[s % 8]) &- (2 &* binaryS)) ^ UInt64.reverse(UInt64.reverse(occupied & fileMasks8[s % 8]) &- (2 &* UInt64.reverse(binaryS)))
//we return possible horizontal moves OR possible vertical moves
return (possibilitiesHorizontal & rankMasks8[s / 8]) | (possibilitiesVertical & fileMasks8[s % 8])
}
The only important thing you need to recognize about the above function is that it gives us the expected output and it does so using overflow operators.
Now, my previous iteration of this same method (before I understood how to circumvent the overflows using overflow operators) was much more drawn out. It required running four while loops that would move away from the current piece in either the "north", "south", "east", or "west" direction until it came into contact with a piece that blocks further movement in the respective direction. Here's what this iteration of the horizontalAndVerticalMoves function looked like:
func horizontalAndVerticalMoves(s: Int) -> UInt64 {
let rankMask: UInt64 = rankMasks8[s/8]
let fileMask: UInt64 = fileMasks8[s%8]
let pseudoPossibleMoves: UInt64 = rankMask ^ fileMask
var unblockedRanks: UInt64 = 0
var unblockedFiles: UInt64 = 0
var direction: Direction! = Direction.north
var testingSquare: Int = s - 8
while direction == .north {
if testingSquare < 0 || testingSquare%8 != s%8 {
direction = .east
} else {
if 1<<testingSquare&occupied != 0 {
unblockedRanks += rankMasks8[testingSquare/8]
direction = .east
} else {
unblockedRanks += rankMasks8[testingSquare/8]
testingSquare -= 8
}
}
}
testingSquare = s + 1
while direction == .east {
if testingSquare > 63 || testingSquare/8 != s/8 {
direction = .south
} else {
if 1<<testingSquare&occupied != 0 {
unblockedFiles += fileMasks8[testingSquare%8]
direction = .south
} else {
unblockedFiles += fileMasks8[testingSquare%8]
testingSquare += 1
}
}
}
testingSquare = s + 8
while direction == .south {
if testingSquare > 63 || testingSquare%8 != s%8 {
direction = .west
} else {
if 1<<testingSquare&occupied != 0 {
unblockedRanks += rankMasks8[testingSquare/8]
direction = .west
} else {
unblockedRanks += rankMasks8[testingSquare/8]
testingSquare += 8
}
}
}
testingSquare = s - 1
while direction == .west {
if testingSquare < 0 || testingSquare/8 != s/8 {
direction = .north
} else {
if 1<<testingSquare&occupied != 0 {
unblockedFiles += fileMasks8[testingSquare%8]
direction = .north
} else {
unblockedFiles += fileMasks8[testingSquare%8]
testingSquare -= 1
}
}
}
let mask = unblockedRanks | unblockedFiles
let possibleMoves = pseudoPossibleMoves&mask
return possibleMoves
}
I figured my newly implemented version of this function (the one that makes use of overflow operators) would be not only more succinct, but also much more efficient. The only important things you need to note about this iteration of the same function is that it gives us the expected output, but appears much more drawn out and doesn't use overflow operators.
What I've Noticed: As mentioned, I expected that my newer, cleaner code using overflow operators would perform much more quickly than the iteration that uses a bunch of while loops. When running tests to see how quickly I can generate chess moves, I've found that the version that uses while loops instead of overflow operators was significantly faster. Calculating every combination of the first three moves in a chess game takes the original function a little less than 6 seconds, while the newer function that uses overflow operators takes a little under 13 second.
What I'm Wondering: As I am wanting to create the strongest chess engine possible, I am hunting for bits of my code that I can make execute faster. The old function performing quicker than the new function seems counterintuitive to me. So I am wondering, are overflow operator in Swift notoriously slow/inefficient?
Here is what the class in question that generates these moves looks like: https://github.com/ChopinDavid/Maestro/blob/master/Maestro/Moves.swift
So I am wondering, are overflow operator in Swift notoriously slow/inefficient?
No, if anything the opposite might be true.
The machine-level instructions for multiply etc. may set an overflow flag but they don't do any more than that. For the standard operators Swift has to compile additional instructions to test that flag and generate an error and this code includes branches (though branch prediction should mitigate those effectively).
The code for your overflow operator version is shorter than that for the standard operator version, its also branch-free.
What the performance difference is between versions is another matter, but the overflow version should not be slower.
You probably need to look for your performance difference elsewhere. Happy hunting!
Note: the above comparison is based on fully optimised code ("Fastest, Smallest [-Os]") produced by the Swift compiler in Xcode 11.3.1, a debug build might produce very different results.