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