我目前正在开发一个国际象棋引擎，该引擎目前正在运行，但需要很长时间才能生成棋步。由于必须生成许多移动，因此检查检测花费的时间最长。
在尝试了很多事情之后，我陷入了困境，并且无法真正弄清楚如何使其更有效率。这是我如何做到的：
要检查移动是否允许/合法，我会检查进行移动的一方是否在之后受到检查：
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
这是迄今为止我引擎中最昂贵的操作，我想知道是否可以以某种方式简化它。任何有兴趣的人都可以使用此文件计算伪合法移动。为完成所有动作，分别生成en-passant、casting和promotion。我还在每次执行移动后生成每边可能的合法移动列表，但由于检查检测使用潜在移动，因此不能使用这些列表。
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
我希望我清楚地说明了我的问题/代码。任何帮助表示赞赏。
Ala*_* T. 12
预先计算的数据结构还有很多工作要做。例如，您可以准备一个字典，其中包含每个工件类型和方向的任何位置的可能目的地。有了它，您就不需要复杂的代码来检查可用的动作。
[有关统一和调整的代码，请参阅我的第二个答案]
您也可以使用它来执行第一次验证检查！。你可以通过检查国王可以达到的位置来做到这一点，如果它是另一件的话。例如，如果您在车可以从国王的位置移动的位置发现车，那么就有可能进行过牌！。对每种棋子类型执行此操作将使您知道是否需要评估实际移动。
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”，但大部分代码应该更简单（并且可能更快）。
这是我的第一个答案中的合并（和部分验证）代码。我到处都将 (r,c) 倒置为 (c,r)。
设置
from collections import defaultdict
targets = dict()
positions = [ (c,r) for c in range(8) for r in range(8) ]
def valid(P):
return [(c,r) for c,r in P if c in range(8) and r in range(8)]
targets["up"] = { (c,r):valid( (c,r+v) for v in range(1,8))
for c,r in positions }
targets["down"] = { (c,r):valid( (c,r-v) for v in range(1,8))
for c,r in positions }
targets["left"] = { (c,r):valid( (c-h,r) for h in range(1,8))
for c,r in positions }
targets["right"] = { (c,r):valid( (c+h,r) for h in range(1,8))
for c,r in positions }
targets["upleft"] = { (c,r):[(cl,ru) for (_,ru),(cl,_) in zip(targets["up"][c,r],targets["left"][c,r])]
for c,r in positions }
targets["upright"] = { (c,r):[(cr,ru) for (_,ru),(cr,_) in zip(targets["up"][c,r],targets["right"][c,r])]
for c,r in positions }
targets["downleft"] = { (c,r):[(cl,rd) for (_,rd),(cl,_) in zip(targets["down"][c,r],targets["left"][c,r])]
for c,r in positions }
targets["downright"] = { (c,r):[(cr,rd) for (_,rd),(cr,_) in zip(targets["down"][c,r],targets["right"][c,r])]
for c,r in positions }
targets["vhPaths"] = ["up","down","left","right"]
targets["diagPaths"] = ["upleft","upright","downleft","downright"]
targets["allPaths"] = targets["vhPaths"]+targets["diagPaths"]
targets["rook"] = { (c,r):[p for path in targets["vhPaths"] for p in targets[path][c,r]]
for c,r in positions }
targets["bishop"] = { (c,r):[p for path in targets["diagPaths"] for p in targets[path][c,r]]
for c,r in positions }
targets["queen"] = { (c,r):[p for path in targets["allPaths"] for p in targets[path][c,r]]
for c,r in positions }
targets["king"] = { (c,r):[p for path in targets["allPaths"] for p in targets[path][c,r][:1]]
for c,r in positions }
targets["knight"] = { (c,r):valid((c+h,r+v) for v,h in [(2,1),(2,-1),(1,2),(1,-2),(-2,1),(-2,-1),(-1,2),(-1,-2)])
for c,r in positions }
targets["wpawn"] = { (c,r):valid([(c,r+1)]*(r>0) + [(c,r+2)]*(r==1))
for c,r in positions }
targets["bpawn"] = { (c,r):valid([(c,r-1)]*(r<7) + [(c,r-2)]*(r==6))
for c,r in positions }
targets["wptake"] = { (c,r):valid([(c+1,r+1),(c-1,r+1)]*(r>0))
for c,r in positions }
targets["bptake"] = { (c,r):valid([(c+1,r-1),(c-1,r-1)]*(r<7))
for c,r in positions }
targets["wcastle"] = defaultdict(list,{ (4,0):[(2,0),(6,0)] })
targets["bcastle"] = defaultdict(list,{ (4,7):[(2,7),(6,7)] })
targets["breakCastle"] = defaultdict(list,{ (4,7):[(2,7),(6,7)],
(7,7):[(6,7)], (0,7):[(2,7)],
(4,0):[(2,0),(6,0)],
(7,0):[(6,0)], (1,0):[(2,0)]})
targets["rook"]["paths"] = targets["vhPaths"]
targets["bishop"]["paths"] = targets["diagPaths"]
targets["queen"]["paths"] = targets["allPaths"]
targets["q_w"] = targets["q_b"] = targets["queen"]
targets["k_w"] = targets["k_b"] = targets["king"]
targets["r_w"] = targets["r_b"] = targets["rook"]
targets["b_w"] = targets["b_b"] = targets["bishop"]
targets["n_w"] = targets["n_b"] = targets["knight"]
targets["p_w"],targets["p_w!"] = targets["wpawn"],targets["wptake"]
targets["p_b"],targets["p_b!"] = targets["bpawn"],targets["bptake"]
for r,c in positions:
targets[(r,c)] = defaultdict(list)
for direction in targets["allPaths"]:
path = targets[direction][r,c]
for i,(tr,tc) in enumerate(path):
targets[(r,c)][tr,tc]=path[:i]
查看！检测
def lineOfSight(board,A,B,ignore=None):
return all(board[c][r]=="" or (c,r)==ignore for c,r in targets[A][B])
def getKingPos(board,player):
king = "k_"+player
return next((c,r) for c,r in positions if board[c][r]==king)
# also used to avoid self check! in king move generation
def isCheck(board,player,kingPos=None,ignore=None):
paths = ("q_b","r_b","b_b","n_b",f"p_{player}!")
if kingPos is None: kingPos = getKingPos(board,player)
return any( board[c][r][:1]==path[:1]
and board[c][r][-1:] != player
and lineOfSight(board,kingPos,(c,r),ignore)
for path in paths
for c,r in targets[path][kingPos] )
移动生成
辅助函数...
# { pinnedPosition : pinnedByPosition }
def getPinned(board,player):
opponent = "b" if player=="w" else "w"
kingPos = getKingPos(board,player)
pinned = dict()
for piece in ("q_"+opponent, "r_"+opponent, "b_"+opponent):
for tc,tr in targets[piece][kingPos]:
if board[tc][tr] != piece: continue
span = [board[sc][sr][-1:] for sc,sr in targets[tc,tr][kingPos]]
if span.count(player)==1 and opponent not in span:
pinnedPos = targets[tc,tr][kingPos][span.index(player)]
pinned[pinnedPos] = (tc,tr)
return pinned
def linearMoves(board,position,player,piece):
for path in targets[piece]["paths"]:
for c,r in targets[path][position]:
if board[c][r][-1:] != player : yield (position,(c,r))
if board[c][r] != "" : break
def directMoves(board,position,player,piece,condition=lambda *p:True):
for c,r in targets[piece][position]:
if board[c][r][-1:] == player: continue
if condition(c,r): yield (position,(c,r))
def switch(v): yield lambda *c: v in c
实际移动生成...
def getMoves(board,player):
enPassant,brokenCastles = board[8:] or (None,set())
moves = []
for c,r in positions:
if board[c][r][-1:] != player: continue
piece = board[c][r]
for case in switch(piece[0]):
if case("b","r","q"):
moves += linearMoves(board,(c,r),player,piece)
elif case("n"):
moves += directMoves(board,(c,r),player,piece)
elif case("p"):
moves += directMoves(board,(c,r),player,piece,
lambda tc,tr:board[tc][tr]==""
and lineOfSight(board,(c,r),(tc,tr)))
moves += directMoves(board,(c,r),player,piece+"!",
lambda tc,tr:board[tc][tr] != "" or (tc,tr) == enPassant )
elif case("k"):
moves += directMoves(board,(c,r),player,piece,
lambda tc,tr: not isCheck(board,player,(tc,tr),(c,r)))
if isCheck(board,player): continue
moves += directMoves(board,(c,r),player,player+"castle",
lambda tc,tr: board[tc][tr] == ""
and not (tc,tr) in brokenCastles
and lineOfSight(board,(c,r),(tc,tr))
and not isCheck(board,player,(tc,tr),(c,r))
and not isCheck(board,player,targets[c,r][tc,tr][0],(c,r)))
pinned = getPinned(board,player)
if pinned: # Pinned pieces can only move on the threat line
kingPos = getKingPos(board,player)
moves = [ (p,t) for p,t in moves if p not in pinned
or t == pinned[p] or t in targets[kingPos][pinned[p]] ]
return moves
要完成移动生成条件，必须由先前的移动设置一些状态：
enPassant是最后一个两格棋子移动所跳过的位置。当一个棋子移动两个格子时应该分配它，并设置为None每隔一个移动。
enPassant = next(iter(targets[fromPosition][toPosition]*(piece=="p")),None)
brokenCastles是一组因移动国王或车而失效的城堡的目标国王城堡位置。if 可以在每次移动后无条件更新：
brokenCastles.update(targets["breakCastle"][fromPosition])
这些状态必须保存在与当前董事会相关的某个地方。这可能证明为板创建一个类而不是使用简单的列表列表是合理的。如果您发现创建类是矫枉过正的话，该信息也可以保存在板列表的第 9 项及后续项目中
漂亮的印花
def boardLines(board):
symbol = { "":".....","r":".[…].", "n":". />.", "b":". ? .",
"q":".{Ö}.", "k":". † .","p":". o .",
"_b":".(?).", "_w":".(_)."}
lines = []
lines += [" 0 1 2 3 4 5 6 7 "]
lines += [" ?????????????????????????????????????????????????"]
def fill(c,r,p):
return symbol[board[c][r][p:1+2*p]].replace("."," ?"[(r&1)==(c&1)])
for r in reversed(range(8)):
lines += [" ?????????????????????????????????????????????????"]*(r<7)
lines += [" ?" + "?".join(fill(c,r,0) for c in range(8))+ "?"]
lines += [f"{r} ?"+ "?".join(fill(c,r,1) for c in range(8))+ f"? {r}"]
lines += [" ?????????????????????????????????????????????????"]
lines += [" 0 1 2 3 4 5 6 7 "]
return lines
def printBoard(board,indent=" "):
for line in boardLines(board):print(indent+line)
...
"""
0 1 2 3 4 5 6 7
?????????????????????????????????????????????????
? […] ?? />?? ? ??{Ö}?? † ?? ? ?? /> ??[…]??
7 ? (?) ??(?)?? (?) ??(?)?? (?) ??(?)?? (?) ??(?)?? 7
?????????????????????????????????????????????????
?? o ?? o ?? o ?? o ?? o ?? o ?? o ?? o ?
6 ??(?)?? (?) ??(?)?? (?) ??(?)?? (?) ??(?)?? (?) ? 6
?????????????????????????????????????????????????
? ??????? ??????? ??????? ???????
5 ? ??????? ??????? ??????? ??????? 5
?????????????????????????????????????????????????
??????? ??????? ??????? ??????? ?
4 ??????? ??????? ??????? ??????? ? 4
?????????????????????????????????????????????????
? ??????? ??????? ??????? ???????
3 ? ??????? ??????? ??????? ??????? 3
?????????????????????????????????????????????????
??????? ??????? ??????? ??????? ?
2 ??????? ??????? ??????? ??????? ? 2
?????????????????????????????????????????????????
? o ?? o ?? o ?? o ?? o ?? o ?? o ?? o ??
1 ? (_) ??(_)?? (_) ??(_)?? (_) ??(_)?? (_) ??(_)?? 1
?????????????????????????????????????????????????
??[…]?? /> ?? ? ?? {Ö} ?? † ?? ? ?? />?? […] ?
0 ??(_)?? (_) ??(_)?? (_) ??(_)?? (_) ??(_)?? (_) ? 0
?????????????????????????????????????????????????
0 1 2 3 4 5 6 7
"""
表面测试：
board = [ ["q_b", "", "", "", "", "", "", "" ],
["", "", "", "", "", "", "", "" ],
["", "", "", "", "", "", "", "" ],
["", "", "", "", "", "", "", "" ],
["k_w", "", "", "", "", "", "", "k_b"],
["", "", "", "", "", "", "", "n_b"],
["", "", "", "", "", "", "", "" ],
["", "", "", "", "", "", "", "r_w"]]
...
printBoard(board)
"""
0 1 2 3 4 5 6 7
?????????????????????????????????????????????????
? ??????? ??????? † ?? />?? ??[…]??
7 ? ??????? ??????? (?) ??(?)?? ??(_)?? 7
?????????????????????????????????????????????????
??????? ??????? ??????? ??????? ?
6 ??????? ??????? ??????? ??????? ? 6
?????????????????????????????????????????????????
? ??????? ??????? ??????? ???????
5 ? ??????? ??????? ??????? ??????? 5
?????????????????????????????????????????????????
??????? ??????? ??????? ??????? ?
4 ??????? ??????? ??????? ??????? ? 4
?????????????????????????????????????????????????
? ??????? ??????? ??????? ???????
3 ? ??????? ??????? ??????? ??????? 3
?????????????????????????????????????????????????
??????? ??????? ??????? ??????? ?
2 ??????? ??????? ??????? ??????? ? 2
?????????????????????????????????????????????????
? ??????? ??????? ??????? ???????
1 ? ??????? ??????? ??????? ??????? 1
?????????????????????????????????????????????????
??{Ö}?? ??????? ?? † ?? ??????? ?
0 ??(?)?? ??????? ??(_)?? ??????? ? 0
?????????????????????????????????????????????????
0 1 2 3 4 5 6 7
"""
……白人……
for (c,r),(tc,tr) in getMoves(board,"w"):
print(board[c][r],(c,r),"-->",(tc,tr))
k_w (4, 0) --> (4, 1)
k_w (4, 0) --> (3, 1)
k_w (4, 0) --> (5, 1)
r_w (7, 7) --> (7, 6)
r_w (7, 7) --> (7, 5)
r_w (7, 7) --> (7, 4)
r_w (7, 7) --> (7, 3)
r_w (7, 7) --> (7, 2)
r_w (7, 7) --> (7, 1)
r_w (7, 7) --> (7, 0)
r_w (7, 7) --> (6, 7)
r_w (7, 7) --> (5, 7)
print(isCheck(board,"w")) # True
……黑人……
for (c,r),(tc,tr) in getMoves(board,"b"):
print(board[c][r],(c,r),"-->",(tc,tr))
q_b (0, 0) --> (0, 1)
q_b (0, 0) --> (0, 2)
q_b (0, 0) --> (0, 3)
q_b (0, 0) --> (0, 4)
q_b (0, 0) --> (0, 5)
q_b (0, 0) --> (0, 6)
q_b (0, 0) --> (0, 7)
q_b (0, 0) --> (1, 0)
q_b (0, 0) --> (2, 0)
q_b (0, 0) --> (3, 0)
q_b (0, 0) --> (4, 0)
q_b (0, 0) --> (1, 1)
q_b (0, 0) --> (2, 2)
q_b (0, 0) --> (3, 3)
q_b (0, 0) --> (4, 4)
q_b (0, 0) --> (5, 5)
q_b (0, 0) --> (6, 6)
q_b (0, 0) --> (7, 7)
k_b (4, 7) --> (4, 6)
k_b (4, 7) --> (3, 7)
k_b (4, 7) --> (3, 6)
k_b (4, 7) --> (5, 6)
k_b (4, 7) --> (2, 7)
print(isCheck(board,"b")) # False
print(getPinned(board,"b")) # {(5, 7): (7, 7)}
[编辑]奖金代码...
如果您存储合法移动并且只想为受上次移动影响的位置重新计算它们......
# Return positions of first piece in line of sight
# for a list of path names
def nextInLine(board,pathNames,position,ignore=None):
for path in pathNames:
pos = next(((c,r) for c,r in targets[path][position]
if board[c][r] and (c,r) != ignore),None)
if pos: yield pos
# Determine which positions may need move recalculation after making a move
# - moves associated with the fromPosition are assumed to be cleared
# - both kings should be re-evaluated after every move
# - this may include a few extra positions (speed/precision trade-off)
def moveRecalc(board,player,fromPosition,toPosition):
recalc = {toPosition, getKingPos(board,"w"), getKingPos(board,"b")}
for position in (fromPosition,toPosition,*filter(None,[enPassant])):
recalc.update(nextInLine(board,targets["allPaths"],position))
recalc.update((c,r) for c,r in targets["knight"][position]
if board[c][r][:1]=="n")
return recalc
检测固定位置的更快功能（从国王的位置辐射）：
# { pinnedPosition : pinnedByPosition }
def getPinned(board,player):
kingPos = getKingPos(board,player)
pinned = dict()
for path in targets["allPaths"]:
inLine = ((c,r) for c,r in targets[path][kingPos] if board[c][r])
pc,pr = next(inLine,(None,None)) # own piece
if pc is None or board[pc][pr][-1:] != player: continue
ac,ar = next(inLine,(None,None)) # opponent attacker
if ac is None or board[ac][ar][-1:] == player: continue
aPiece = board[ac][ar][:1]
if aPiece == "q" \
or aPiece == "r" and (ac == pc or ar == pr) \
or aPiece == "b" and (ac != pc and ar != pr):
pinned[pc,pr] = (ac,ar)
return pinned
在给定位置威胁玩家的坐标：
def getThreat(board,position,player="",ignore=None,pinned=None):
c,r = position
for ac,ar in nextInLine(board,targets["allPaths"],position,ignore=ignore):
piece = board[ac][ar]
if piece[-1:] == player: continue
for case in switch(board[ac][ar][:1]):
if case("n") : break
if case("r") and (ac-c)*(ar-r) : break
if case("b") and not (ac-c)*(ar-r): break
if case("p","k") and (c,r) not in targets[piece][ac,ar]: break
if pinned and (ac,ar) in pinned:
pc,pr = pinned[ac,ar]
if (ar-r)*(ac-pc) != (ac-c)*(ar-pr): break
yield ac,ar
for ac,ar in targets["knight"][position]:
if board[ac][ar][:1]=="n" and board[ac][ar][:1]!=player:
yield ac,ar
# print(any(getThreat(board,(5,7))),*getThreat(board,(5,7)))
# True (4, 7) (7, 7)
# print(any(getThreat(board,(2,1)))) # False
# print(any(getThreat(board,getKingPos(board,"w"),"w"))) # True
# could be used to implement isCheck (may be faster too):
def isCheck(board,player,kingPos=None,ignore=None):
if kingPos is None: kingPos = getKingPos(board,player)
return any(getThreat(board,kingPos,player,ignore))
把所有东西放在一起
设置：（初始板位置）
initialBoard = [ ["r_w","p_w","","","","","p_b","r_b"],
["n_w","p_w","","","","","p_b","n_b"],
["b_w","p_w","","","","","p_b","b_b"],
["q_w","p_w","","","","","p_b","q_b"],
["k_w","p_w","","","","","p_b","k_b"],
["b_w","p_w","","","","","p_b","b_b"],
["n_w","p_w","","","","","p_b","n_b"],
["r_w","p_w","","","","","p_b","r_b"],
None,set()] # enPassant, brokenCastles
采取行动，更新特殊动作：
from copy import deepcopy
def playMove(board,fromPosition,toPosition,promotion=""):
(fromC,fromR),(toC,toR) = fromPosition,toPosition
piece,player = board[fromC][fromR].split("_")
board = [deepcopy(r) for r in board]
board[toC][toR],board[fromC][fromR] = board[fromC][fromR],""
# promotion
if piece == "p" and toR in (0,7):
while promotion not in ("q","r","n","b"):
promotion = input("Promote pawn to (q,r,n,b): ")[:1]
piece = promotion
board[toC][toR] = piece+"_"+player
# en passant
enPassant,brokenCastles = board[8:] or (None,set())
if piece=="p" and toPosition == enPassant:
print("enPassant!")
board[toC][fromR] = ""
enPassant = next(iter(targets[fromPosition][toPosition]*(piece=="p")),None)
# castle
if piece=="k" and abs(toC-fromC)>1:
rookFrom = ((fromC>toC)*7,fromR)
rookTo = targets[fromPosition][toPosition][0]
board = playMove(board,player,rookFrom,rookTo)
brokenCastles = brokenCastles.union(targets["breakCastle"][fromPosition])
board[8:] = (enPassant,brokenCastles)
return board
一个愚蠢的电脑对手：
import random
def computerMove(board,player,legalMoves):
return random.choice(legalMoves),"q"
简单的游戏实现...
def playChess(board=None,player="white",computer=None):
if board is None: board = initialBoard
opponent = "black" if player == "white" else "white"
while True:
printBoard(board)
legalMoves = getMoves(board,player[:1])
if isCheck(board,player[:1]):
legalMoves = [ move for move in legalMoves
if not isCheck(playMove(board,*move,"q"),player[:1])]
if not legalMoves: print("CHECK MATE!");return opponent
print("CHECK!")
elif not legalMoves:
print("STALEMATE!");return "DRAW"
while True:
print(f"{player}'s move: (cr-cr):",end=" ")
if player==computer:
move,promote = computerMove(board,player,legalMoves)
print( "-".join(f"{c}{r}" for c,r in move))
break
| 归档时间： |
|
| 查看次数： |
449 次 |
| 最近记录： |