0

我在做什么：我正在用 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

4

1 回答 1

1

所以我想知道，Swift 中的溢出运算符是出了名的缓慢/低效吗？

不，如果有相反的情况可能是真的。

用于乘法等的机器级指令可能会设置一个溢出标志，但它们不会做更多的事情。对于标准运算符，Swift 必须编译额外的指令来测试该标志并生成错误，并且此代码包含分支（尽管分支预测应该有效地缓解这些问题）。

您的溢出运算符版本的代码比标准运算符版本的代码短，它也是无分支的。

版本之间的性能差异是什么是另一回事，但溢出版本应该不会慢。

您可能需要在其他地方寻找您的性能差异。狩猎愉快！

注意：以上比较基于 Xcode 11.3.1 中 Swift 编译器生成的完全优化的代码（“Fastest, Smallest [-Os]”），调试构建可能会产生非常不同的结果。

于 2020-03-11T20:15:32.243 回答