python - 更有效地检测支票(国际象棋)

Question

我目前正在开发国际象棋引擎，目前该引擎一直在工作，但要花很多时间才能产生移动。由于必须生成许多移动，因此检查检测花费的时间最长。
我尝试了很多事情后陷入困境，无法真正弄清楚如何提高效率。这是我的方法:
要检查是否允许/合法举动，我随后检查是否做出举动的一方:

    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。(colour).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

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

    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

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

Answer 1

预先计算的数据结构有很多工作要做。例如，您可以为每种作品类型和方向从任何位置准备一个带有可能目的地的字典。这样，您就不需要复杂的代码来检查可用的移动。
[有关合并和调整后的代码，请参阅我的第二个答复]
您也可以使用它来执行首次验证以进行检查!您可以通过检查国王是否可以胜任其他职位来做到这一点。例如，如果您在一个可以从国王的位置移动车子的位置找到一个车子，那么就有可能进行检查!对每种类型的零件执行此操作将使您知道是否需要评估实际移动。

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)    
...

[编辑]
为了利用这一点来生成移动，您仍然必须添加一些条件，但是我相信字典应该使逻辑更简单，更快速:

# 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”，但是大多数代码应该更简单(并且可能更快)。