Python象棋引擎滑动棋子Bitboard走法生成优化疑问

我正在Python中优化一款象棋引擎，核心是优化车、象这类滑动棋子的Bitboard走法生成逻辑。

初始循环实现 #

最初采用循环遍历的方式生成走法，代码如下：

def get_rook_moves(self, color, position_bitboard):
    self.update_occupied_sqaures()
    original_position_bitboard = position_bitboard
    moves = 0
    rank_8 = 0xff00000000000000
    rank_1 = 0x00000000000000ff
    file_a = 0x101010101010101
    file_h = 0x8080808080808080
    enemy_occupied_sqaures = self.occupied_black_sqaures if color == 'w' else self.occupied_white_sqaures
    friendly_occupied_sqaures = self.occupied_white_sqaures if color == 'w' else self.occupied_black_sqaures
    # 北方向遍历
    while not position_bitboard & rank_8:
      position_bitboard <<= 8
      if position_bitboard & enemy_occupied_sqaures:
        moves |= position_bitboard
        break
      elif position_bitboard & friendly_occupied_sqaures:
        break
      moves |= position_bitboard
    # 其余方向遍历逻辑类似
    return moves

尝试的高效填充算法 #

之后我尝试了两种Bitboard走法生成的高效填充算法：subtraction fill和kogge stone fill。

Subtraction Fill实现 #

def east_fill (position_bitboard, occupied_sqaures):
    occInclRook = position_bitboard | occupied_sqaures | h
    occExclRook = (position_bitboard & ~h)  ^ occInclRook
    rookAttacks = (occExclRook - position_bitboard) ^ occInclRook
    return rookAttacks

Kogge Stone Fill实现 #

def north_fill (position_bitboard, occupied_sqaures, enemy_occupied_sqaures):
    fillnorth = position_bitboard 
    fillnorth |= fillnorth << 8
    fillnorth |= fillnorth << 16
    fillnorth |= fillnorth << 32
    blockers = fillnorth & occupied_sqaures
    closest_blocker = blockers & -blockers
    backfillnorth = closest_blocker
    backfillnorth |= backfillnorth << 8
    backfillnorth |= backfillnorth << 16
    backfillnorth |= backfillnorth << 32
    fillnorth &= ~(backfillnorth^(closest_blocker & enemy_occupied_sqaures))
    return fillnorth

棋盘旋转复用单方向算法 #

为了减少重复代码，我通过棋盘旋转来复用单方向的填充算法生成全方向走法，示例代码如下：

fos = r.flipVertical(occupied_sqaures)
fes = r.flipVertical(enemy_occupied_sqaures)
fpb = r.flipVertical(position_bitboard)
fillsouth = r.flipVertical(north_fill (fos, fes, fpb))

测试数据与问题 #

测试数据显示，单方向下两种填充算法的速度都比循环快，但添加旋转操作后，整体耗时反而超过了循环实现；移除旋转后，两种算法的耗时和循环接近。我不确定是旋转实现本身效率太低，还是应该完全放弃旋转复用的方案。

具体测试耗时数据 #

• 单方向平均耗时：
  • subtraction_fill：1.4904μs
  • kogge_fill：2.3934μs
  • loop：2.7866μs
• 带旋转全方向耗时：
  • subtraction_fill：3.5131μs
  • kogge_fill：6.5326μs
  • loop：2.8232μs
• 各旋转操作平均耗时：
  • 顺时针90°：1.3400μs
  • 逆时针90°：1.3547μs
  • 镜像：0.7112μs
  • 垂直翻转：0.6649μs
• 无旋转全方向耗时：
  • subtraction_fill：1.6139μs
  • kogge_fill：2.5905μs
  • loop：2.5690μs

内容的提问来源于stack exchange，提问作者Smillyone