Что я делаю: Я пишу шахматный движок на Swift. Одна из самых важных частей написания сильного шахматного движка - это способность генерировать как можно больше будущих позиций на доске за минимально возможное время. Чем больше позиций ваш движок может генерировать и оценивать за более короткое время, тем мощнее движок.
При этом я написал функции для генерации ходов для скользящих фигур (слонов, ладей и ферзей). ). В этих функциях используются операторы переполнения (&+, &-, &*), поскольку обычные побитовые операторы часто вызывают ошибки переполнения .
Генерация для указанных перемещений требуются две функции: одна для генерации всех допустимых вертикальных и горизонтальных перемещений для скользящей фигуры и одна для генерации всех допустимых диагональных перемещений для скользящей фигуры. Эти две функции эффективно go делают одно и то же, мы просто по-разному манипулируем аргументами. Вот как выглядит функция для генерации горизонтальных и вертикальных перемещений:
//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])
}
Единственная важная вещь, которую вам нужно распознать в приведенной выше функции, - это то, что она дает нам ожидаемый результат и делает это, используя операторы переполнения .
Теперь моя предыдущая итерация этого же метода (до того, как я понял, как обойти переполнения с помощью операторов переполнения) была гораздо более продолжительной. Требовалось запустить четыре цикла while, которые бы отошли от текущего куска в направлении «север», «юг», «восток» или «запад», пока он не соприкоснется с клочком, который блокирует дальнейшее движение в соответствующем направлении. , Вот как выглядела эта итерация функции horizontalAndVerticalMoves:
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
}
Я полагал, что моя недавно реализованная версия этой функции (та, которая использует операторы переполнения) будет не только более краткой, но и намного больше эффективнее . Единственное важное, что вы должны отметить в этой итерации той же функции, это то, что она дает нам ожидаемый результат, но выглядит намного более вытянутой и не использует операторов переполнения.
What I ' ve Замечено: Как уже упоминалось, я ожидал, что мой новый, более чистый код, использующий операторы переполнения, будет работать намного быстрее, чем итерация, использующая кучу циклов while. Выполняя тесты, чтобы увидеть, как быстро я могу генерировать шахматные ходы, я обнаружил, что версия, которая использует циклы while вместо операторов переполнения, была значительно быстрее. Для вычисления каждой комбинации первых трех ходов в шахматной игре требуется оригинальная функция , чуть меньше 6 секунд , в то время как более новая функция , которая использует операторы переполнения, требует чуть меньше 13 секунд .
Что я интересуюсь: Поскольку я хочу создать самый сильный шахматный движок из всех возможных, я ищу кусочки своего кода что я могу сделать выполнить быстрее. Старая функция, выполняющая быстрее новой, кажется мне нелогичной. Поэтому мне интересно, оператор переполнения в Swift, как известно, медленный / неэффективный?
Вот как выглядит рассматриваемый класс, который генерирует эти ходы: https://github.com/ChopinDavid/Maestro/blob/master/Maestro/Moves.swift