更有效地检测检查（国际象棋）

我目前正在开发一个国际象棋引擎，该引擎到目前为止正在运行，但需要很长时间才能生成棋步。由于必须生成许多移动，因此检查检测花费的时间是迄今为止最长的。

在尝试了很多事情之后我陷入了困境，并且无法真正弄清楚如何提高效率。我是这样做的：

为了检查移动是否允许/合法，我检查移动的一方随后是否受到检查：

    def allowed_move(self, board, pos, move, colour):

    copy_board = copy.deepcopy(board)

    (x, y) = pos
    (new_x, new_y) = move

    if copy_board[x][y] == "k_w":
        self.white_king = (new_x, new_y)
        copy_board[new_x][new_y] = copy_board[x][y]
        copy_board[x][y] = " "
        self.in_check(colour, copy_board)
        self.white_king = (x, y)

    elif copy_board[x][y] == "k_b":
        self.black_king = (new_x, new_y)
        copy_board[new_x][new_y] = copy_board[x][y]
        copy_board[x][y] = " "
        self.in_check(colour, copy_board)
        self.black_king = (x, y)

    else:
        copy_board[new_x][new_y] = copy_board[x][y]
        copy_board[x][y] = " "
        self.in_check(colour, copy_board)


    if colour == "_w" and self.white_check:
        return False

    if colour == "_b" and self.black_check:
        return False

    return True

为了确定一方是否处于检查状态，我会生成对手一方的每一步棋，并检查他们是否能够在下一步棋中捕获国王。 （这是不好的部分）

• sq[1:] 只是确定当前方块的颜色

• self.(color).king 是国王当前的位置

• move 是一个元组，包含每次移动结束方块的坐标

   def in_check(self, colour, board):
  
   self.white_check = False
   self.black_check = False
   for x, line in enumerate(board):
       for y, sq in enumerate(line):
           if sq[1:] == "_w":
               for (move, _, _) in self.get_all_moves(board, (x, y)):
                   if move == self.black_king:
                       self.black_check = True
  
           if sq[1:] == "_b":
               for (move, _, _) in self.get_all_moves(board, (x, y)):
                   if move == self.white_king:
                       self.white_check = True
  

这是迄今为止我的引擎中最昂贵的操作，我想知道是否可以以某种方式简化它。任何感兴趣的人都可以使用此文件计算伪合法移动。为了完成所有动作，过路、施法和升级是单独生成的。我还在每次执行的移动后生成每边可能的合法移动的列表，但由于检查检测使用潜在的移动，因此无法使用这些列表。

    class Rook:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos

    def moves(self):
        pos_caps = []
        (x, y) = self.pos
        clr = self.board[x][y][1:]
        for i in range(- 1, - y - 1, -1):
            if self.board[x][y + i][1:] != clr:  
                pos_caps.append((x, y + i))
                for v in range(- 1, i, - 1):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(1, 8 - y):
            if self.board[x][y + i][1:] != clr:  
                pos_caps.append((x, y + i))
                for v in range(1, i):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(- 1, - x - 1, -1):
            if self.board[x + i][y][1:] != clr:  
                pos_caps.append((x + i, y))
                for v in range(- 1, i, - 1):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        for i in range(1, 8 - x):
            if self.board[x + i][y][1:] != clr:  
                pos_caps.append((x + i, y))
                for v in range(1, i):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        return pos_caps


class Knight:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = self.board[self.x_pos][self.y_pos][1:]

    def moves(self):
        pos_moves = []
        (x, y) = self.pos
        if x < 6 and y < 7:
            pos_moves.append((x + 2, y + 1))
        if x < 6 and y > 0:
            pos_moves.append((x + 2, y - 1))
        if x > 1 and y < 7:
            pos_moves.append((x - 2, y + 1))
        if x > 1 and y > 0:
            pos_moves.append((x - 2, y - 1))
        if x < 7 and y < 6:
            pos_moves.append((x + 1, y + 2))
        if x < 7 and y > 1:
            pos_moves.append((x + 1, y - 2))
        if x > 0 and y < 6:
            pos_moves.append((x - 1, y + 2))
        if x > 0 and y > 1:
            pos_moves.append((x - 1, y - 2))
            
        for mv in reversed(pos_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                pos_moves.remove(mv)

        return pos_moves


class King:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = self.board[self.x_pos][self.y_pos][1:]

    def moves(self):
        all_moves = []
        (x, y) = self.pos
        if x > 0:
            all_moves.append((x - 1, y))
            if y > 0:
                all_moves.append((x - 1, y - 1))
            if y < 7:
                all_moves.append((x - 1, y + 1))

        if x < 7:
            all_moves.append((x + 1, y))
            if y > 0:
                all_moves.append((x + 1, y - 1))
            if y < 7:
                all_moves.append((x + 1, y + 1))

        if y > 0:
            all_moves.append((x, y - 1))

        if y < 7:
            all_moves.append((x, y + 1))

        for mv in reversed(all_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                all_moves.remove(mv)

        return all_moves


class Queen:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = self.board[self.x_pos][self.y_pos][1:]

    def moves(self):
        pos_caps = []
        (x, y) = self.pos
        clr = self.board[x][y][1:]
        for i in range(- 1, - y - 1, -1):
            if self.board[x][y + i][1:] != clr:   
                pos_caps.append((x, y + i))
                for v in range(- 1, i, - 1):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(1, 8 - y):
            if self.board[x][y + i][1:] != clr:   
                pos_caps.append((x, y + i))
                for v in range(1, i):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(- 1, - x - 1, -1):
            if self.board[x + i][y][1:] != clr:   
                pos_caps.append((x + i, y))
                for v in range(- 1, i, - 1):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        for i in range(1, 8 - x):
            if self.board[x + i][y][1:] != clr:  
                pos_caps.append((x + i, y))
                for v in range(1, i):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        com = min(x, y)
        for i in range(1, com + 1):
            if self.board[x - i][y - i][1:] != clr:
                pos_caps.append((x - i, y - i))
                for v in range(1, i):
                    if self.board[x - v][y - v] != " ":
                        pos_caps.remove((x - i, y - i))
                        break

        com = min(7 - x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x + i][y + i][1:] != clr:
                pos_caps.append((x + i, y + i))
                for v in range(1, i):
                    if self.board[x + v][y + v] != " ":
                        pos_caps.remove((x + i, y + i))
                        break

        com = min(7 - x, y)
        for i in range(1, com + 1):
            if self.board[x + i][y - i][1:] != clr:
                # print(str((x + i, y - i)) + "Appending")
                pos_caps.append((x + i, y - i))
                for v in range(1, i):
                    if self.board[x + v][y - v] != " ":
                        # print(str((x + i, y - i)) + "Removing")
                        pos_caps.remove((x + i, y - i))
                        break

        com = min(x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x - i][y + i][1:] != clr:
                pos_caps.append((x - i, y + i))
                for v in range(1, i):
                    if self.board[x - v][y + v] != " ":
                        pos_caps.remove((x - i, y + i))
                        break

        return pos_caps


class Pawn_white:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = "_w"

    def moves(self):        
        all_moves = []
        (x, y) = self.pos
        if y > 0:
            if y == 6:
                all_moves.append((x, y - 1))
                all_moves.append((x, y - 2))

            else:
                all_moves.append((x, y - 1))

            if x > 0:
                if self.board[x - 1][y - 1][1:] != self.clr:
                    all_moves.append((x - 1, y - 1))
            if x < 7:
                if self.board[x + 1][y - 1][1:] != self.clr:
                    all_moves.append((x + 1, y - 1))

        for mv in reversed(all_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                all_moves.remove(mv)

        return all_moves


class Pawn_black:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = "_b"

    def moves(self):
        all_moves = []
        (x, y) = self.pos

        if y == 1:
            all_moves.append((x, y + 1))
            all_moves.append((x, y + 2))

        elif y < 7:
            all_moves.append((x, y + 1))

            if x > 0:
                if self.board[x - 1][y + 1] != self.clr:
                    all_moves.append((x - 1, y + 1))
            if x < 7:
                if self.board[x + 1][y + 1] != self.clr:
                    all_moves.append((x + 1, y + 1))
                    
        for mv in reversed(all_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                all_moves.remove(mv)

        return all_moves


class Bishop:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos

    def moves(self):
        pos_caps = []
        (x, y) = self.pos
        clr = self.board[x][y][1:]

        com = min(x, y)
        for i in range(1, com + 1):
            if self.board[x - i][y - i][1:] != clr:
                pos_caps.append((x - i, y - i))
                for v in range(1, i):
                    if self.board[x - v][y - v] != " ":
                        pos_caps.remove((x - i, y - i))
                        break

        com = min(7 - x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x + i][y + i][1:] != clr:
                pos_caps.append((x + i, y + i))
                for v in range(1, i):
                    if self.board[x + v][y + v] != " ":
                        pos_caps.remove((x + i, y + i))
                        break

        com = min(7 - x, y)
        for i in range(1, com + 1):
            if self.board[x + i][y - i][1:] != clr:
                pos_caps.append((x + i, y - i))
                for v in range(1, i):
                    if self.board[x + v][y - v] != " ":
                        pos_caps.remove((x + i, y - i))
                        break

        com = min(x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x - i][y + i][1:] != clr:
                pos_caps.append((x - i, y + i))
                for v in range(1, i):
                    if self.board[x - v][y + v] != " ":
                        pos_caps.remove((x - i, y + i))
                        break

        return pos_caps

我希望我已经清楚地说明了我的问题/代码。任何帮助表示赞赏。

对于预先计算的数据结构还有很多工作要做。例如，您可以准备一个字典，其中包含每种工件类型和方向的任何位置的可能目的地。这样，您就不需要复杂的代码来检查可用的移动。

[有关合并和调整后的代码，请参阅我的第二个答案]

您还可以使用它来执行第一次验证以进行检查！。如果是另一颗棋子，您可以通过检查国王可以到达的位置来做到这一点。例如，如果您发现车处于可以从王位置移动的位置，那么就有可能进行过牌！对每种棋子类型执行此操作将使您知道是否有必要评估实际移动。

from collections import defaultdict
targets   = dict()
positions = [ (r,c) for r in range(8) for c in range(8) ]
def valid(positions): 
    return [(r,c) for r,c in positions if r in range(8) and c in range(8)]

从基本轨迹开始......

targets["up"]    = { (r,c):valid( (r+v,c) for v in range(1,8))
                           for r,c in positions }
targets["down"]  = { (r,c):valid( (r-v,c) for v in range(1,8))
                           for r,c in positions }
targets["vertical"]  = { (r,c):targets["up"][r,c]+targets["down"][r,c]
                           for r,c in positions }

targets["left"]  = { (r,c):valid( (r,c+h) for h in range(1,8))
                           for r,c in positions }
targets["right"] = { (r,c):valid( (r,c+h) for h in range(1,8))
                           for r,c in positions }
targets["horizontal"] = { (r,c):targets["left"][r,c]+targets["right"][r,c]
                           for r,c in positions }

targets["upleft"]  = { (r,c):[(ru,cl) for (ru,_),(_,cl) in zip(targets["up"][r,c],targets["left"][r,c])]
                           for r,c in positions }

targets["upright"] = { (r,c):[(ru,cr) for (ru,_),(_,cr) in zip(targets["up"][r,c],targets["right"][r,c])]
                           for r,c in positions }

targets["downleft"] = { (r,c):[(rd,cl) for (rd,_),(_,cl) in zip(targets["down"][r,c],targets["left"][r,c])]
                           for r,c in positions }

targets["downright"] = { (r,c):[(rd,cr) for (rd,_),(_,cr) in zip(targets["down"][r,c],targets["right"][r,c])]
                           for r,c in positions }

targets["diagUL"] = { (r,c):targets["upleft"][r,c]+targets["downright"][r,c]
                           for r,c in positions }
targets["diagDL"] = { (r,c):targets["downleft"][r,c]+targets["upright"][r,c]
                           for r,c in positions }

然后将它们组合成每种类型......

targets["king"]    = { (r,c):valid( (r+v,c+h) for v in (-1,0,1) for h in (-1,0,1) if v or h)
                           for r,c in positions }
targets["rook"]    = { (r,c):targets["horizontal"][r,c]+targets["vertical"][r,c]
                           for r,c in positions }
targets["bishop"]  = { (r,c):targets["diagUL"][r,c]+targets["diagDL"][r,c]
                           for r,c in positions }
targets["queen"]   = { (r,c):targets["rook"][r,c]+targets["bishop"][r,c]
                           for r,c in positions }
targets["knight"]  = { (r,c):valid((r+v,c+h) for v,h in [(2,1),(2,-1),(1,2),(1,-2),(-2,1),(-2,-1),(-1,2),(-1,-2)])
                           for r,c in positions } 
targets["wpawn"]   = { (r,c):valid([(r+1,c)]*(r>0) + [(r+2,c)]*(r==1))
                           for r,c in positions }
targets["bpawn"]   = { (r,c):valid([(r-1,c)]*(r<7) + [(r-2,c)]*(r==6))
                           for r,c in positions }
targets["wptake"]  = { (r,c):valid([(r+1,c+1),(r+1,c-1)]*(r>0))
                           for r,c in positions }
targets["bptake"]  = { (r,c):valid([(r-1,c+1),(r-1,c-1)]*(r<7))
                           for r,c in positions }
targets["wcastle"] = defaultdict(list,{ (0,4):[(0,2),(0,6)] })
targets["bcastle"] = defaultdict(list,{ (7,4):[(7,2),(7,6)] }) 

这将允许您直接获取棋盘上任何位置的任何棋子的潜在移动位置列表。

例如：

 targets["bishop"][5,4]
 # [(6, 3), (7, 2), (4, 5), (3, 6), (2, 7), (4, 3), (3, 2), (2, 1), (1, 0), (6, 5), (7, 6)]

要了解白王在 5,4 处是否有潜在的检查，您可以在进入移动模拟之前执行快速验证：

 kingPos = (5,4)
 checkByQueen  = any(board[r][c]=="q_b" for r,c in targets["queen"][kingPos])
 checkByKnight = any(board[r][c]=="n_b" for r,c in targets["knight"][kingPos])
 checkByRook   = any(board[r][c]=="r_b" for r,c in targets["rook"][kingPos])
 checkByBishop = any(board[r][c]=="b_b" for r,c in targets["bishop"][kingPos])
 checkByPawn   = any(board[r][c]=="p_b" for r,c in targets["wptake"][kingPos])

如果这些都不是真的，那么对白王就没有威胁。如果 checkByQueen、checkByRook 或 checkByBishop 为 True，那么您需要验证中间另一块的遮挡，但这已经大大减少了案例数量。

您还可以增强字典，使用位置作为键（而不是字符串）为您提供棋盘上两个方块之间的位置。

for r,c in positions:
    targets[(r,c)] = defaultdict(list)
    for direction in ("up","down","left","right","upleft","upright","downleft","downright"):
        path = targets[direction][r,c]
        for i,(tr,tc) in enumerate(path):
            targets[(r,c)][tr,tc]=path[:i]

这将使您可以轻松检查两个位置之间是否有一块。例如，如果您在 (5,0) 处找到皇后，您可以使用以下命令检查国王是否在视线范围内：

queenPos = next((r,c) for r,c in targets["queen"][kingPos] 
                      if board[r][c]=="q_b") # (5,0)

targets[kingPos][queenPos] # [(5, 3), (5, 2), (5, 1)]

lineOfSight = all(board[r][c]=="" for r,c in targets[kingPos][queenPos])

这可以结合以上条件来综合验证：

def lineOfSight(A,B): 
    return all(board[r][c]=="" for r,c in targets[A][B])

checkByQueen  = any(board[r][c]=="q_b" and lineOfSight(kingPos,(r,c))
                    for r,c in targets["queen"][kingPos] )
checkByRook   = any(board[r][c]=="r_b" and lineOfSight(kingPos,(r,c))
                    for r,c in targets["rook"][kingPos]  )
checkByBishop = any(board[r][c]=="b_b" and lineOfSight(kingPos,(r,c))
                    for r,c in targets["bishop"][kingPos])

使用所有这些，您根本不需要模拟移动来检测检查！，您可以在一行中完成：

isCheck = any( board[r][c]==opponent and lineOfSight(kingPos,(r,c))
               for opponent,piece in [("q_b","queen"),("r_b","rook"),("b_b","bishop"),("n_b","knight"),("p_b","wptake")]
               for r,c in target[piece][kingPos] )    
  

样本内容：

for r,c in positions:
    print("FROM",(r,c))
    for piece in targets:
        print(f"  {piece:10}:",*targets[piece][r,c])

...

FROM (2, 4)
  up        : (3, 4) (4, 4) (5, 4) (6, 4) (7, 4)
  down      : (1, 4) (0, 4)
  vertical  : (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4)
  left      : (2, 3) (2, 2) (2, 1) (2, 0)
  right     : (2, 5) (2, 6) (2, 7)
  horizontal: (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7)
  upleft    : (3, 3) (4, 2) (5, 1) (6, 0)
  upright   : (3, 5) (4, 6) (5, 7)
  downleft  : (1, 3) (0, 2)
  downright : (1, 5) (0, 6)
  diagUL    : (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6)
  diagDL    : (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
  king      : (1, 4) (1, 5) (2, 3) (2, 5) (3, 3) (3, 4)
  rook      : (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7) (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4)
  bishop    : (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6) (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
  queen     : (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7) (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4) (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6) (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
  wpawn     : (3, 4)
  bpawn     : (1, 4)
  wptake    : (3, 5) (3, 3)
  bptake    : (1, 5) (1, 3)
  knight    : (4, 5) (4, 3) (3, 6) (3, 2) (0, 5) (0, 3) (1, 6) (1, 2)    
...

[EDIT]

要利用它来生成移动，您仍然需要添加一些条件，但我相信字典应该使逻辑更简单、更快：

# add to setup ...
targets["bishop"]["paths"] = ["upleft","upright","downleft","downright"]
targets["rook"]["paths"]   = ["up","down","left","right"]
targets["queen"]["paths"]  = targets["bishop"]["paths"]+targets["rook"]["paths"]

def linearMoves(position,opponent,piece):
    if position in pinnedPositions: return # see below
    for direction in targets[piece]["paths"]
        for r,c in targets[direction][position]:
              if board[r][c]=="": yield (position,(r,c)); continue
              if board[r][c].endswith(opponent): yield(position,(r,c))
              break

...初始化移动生成周期

# flag white pieces that are pinned 
# (do this before each move generation)

pinnedPositions = set()
for piece,path in [("q_b","queen"),("r_b","rook"),("b_b","bishop"):
    for T in targets[path][kingPos]:
        if board[T] != piece: continue
        pinned = [[board[r][c][-1:] for r,c in targets[T][kingPos]]
        if pinned.count("w")==1 and "b" not in pinned:
            pinnedPositions.add(targets[T][kingPos][pinned.index("w")])

...对于棋盘上的每个棋子...

moves = []
# Move white bishop from position bishosPos ...
moves += linearMoves(bishopPos,"b","bishop")

# Move white rook from position rookPos ...
moves += linearMoves(rookPos,"b","rook")

# Move white queen from position queenPos ...
moves += linearMoves(queenPos,"b","queen")

# Move white knight from position knightPos ...
moves += ( (knightPos,(r,c)) for r,c in targets["knight"][knightPos]
           if board[r][c][-1:]!="w" )    

# Move white pawn from position pawnPos ...
moves += ( (pawnPos,(r,c)) for r,c in targets["wpawn"][pawnPos]
           if board[r][c][-1:]=="" and lineOfSight(pawnPos,(r,c)) )    
moves += ( (pawnPos,(r,c)) for r,c in targets["wptake"][pawnPos]
           if board[r][c][-1:]=="b" )    

# Move white king from position kingPos ... 
# (need to filter this so king doesn't place itself in check!)
moves += ( (kingPos,(r,c)) for r,c in targets["king"][kingPos]
           if board[r][c][-1]!="w" )    

      

还有更多例外需要管理，例如“castling”和“en passant”，但大多数代码应该更简单（并且可能更快）。