更有效地检测支票（国际象棋）
Detecting checks more efficiently (Chess)
我目前正在研究国际象棋引擎，该引擎目前正在运行，但需要很长时间才能生成动作。检查检测花费的时间最长，因为必须生成许多移动。
我尝试了很多东西后卡住了，无法真正弄清楚如何提高效率。这是我的做法：
要检查移动是否 allowed/legal，我检查移动的一方是否在之后检查：
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
这是迄今为止我的引擎中最昂贵的操作，我想知道我是否可以以某种方式简化它。伪合法移动是使用此文件计算的，供任何感兴趣的人使用。为完成所有移动，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
我希望我把我的 problem/code 的一切都说清楚了。感谢任何帮助。
使用预先计算的数据结构还有很多工作要做。例如，您可以为每种棋子类型和方向准备一个字典，其中包含来自任何位置的可能目的地。这样，您就不需要复杂的代码来检查可用的移动。
[请参阅我对合并和调整后的代码的第二个答案]
您还可以使用它来执行第一次验证以进行检查！。如果它是另一块棋子，您可以通过检查国王可以到达的位置来做到这一点。例如，如果您在车可以从国王的位置移动的位置找到车，那么就有可能进行检查！。对每种棋子类型执行此操作将使您知道是否有必要评估实际移动。
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])
如果 none 为真，则白王没有威胁。如果 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”，但大部分代码应该更简单（并且可能更快）。
看起来你在移动生成和检查检测中使事情变得复杂，这使得它真的很慢。
更好的检查检测方法
现在你说给对方生成所有的合法走法，看对方能不能擒王。这是非常慢的，更好的方法是从你自己的国王的角度来看，看看在你移动后任何方向是否有任何敌人的棋子，它可能看起来像这样（广场是你的国王广场）：
def is_in_check(square):
enemy_color, friendly_color = ('b', 'w') if self.is_white_turn else ('w', 'b')
# Check out from all directions from the king
for i, d in enumerate(s.directions):
for j in range(1, 8): # Check the entire row/column in that direction
end_square = square + d*j
piece_color, piece_type = self.board[end_square][0], self.board[end_square][1]
if is_on_board(end_square ):
if piece_color == friendly_color and piece_type != 'K':
break
elif piece_color == enemy_color:
# 5 different cases:
# 1. Orthogonally from king and piece is a rook
# 2. Diagonally from king and piece is a bishop
# 3. 1 square away diagonally from king and piece is a pawn
# 4. Any direction and piece is a queen
# 5. Any direction 1 square away and piece is a king
if (0 <= i <= 3 and piece_type == 'R') or \
(4 <= i <= 7 and piece_type == 'B') or \
(j == 1 and piece_type == 'p' and ((enemy_color == 'w' and 6 <= i <= 7) or (enemy_color == 'b' and 4 <= i <= 5))) or \
(piece_type == 'Q') or \
(j == 1 and piece_type == 'K'):
return True
else: # Enemy piece that is not applying check or pin
break
else: # i, j is off board
break
# Check for knight checks
for d in s.knight_moves:
end_piece = self.board[square + d]
if is_on_board(end_square):
if end_piece[1] == 'N' and end_piece[0] == enemy_color: # Enemy knight attacking king
return True
return False
如果代码不清楚，请在评论中提问，我从我的早期引擎中复制了大部分内容，因此它可能与您的表示不完全一样。这个想法是从国王的各个方向看。如果您找到自己的棋子或不在棋盘上，请休息并继续下一个方向。如果你找到敌方棋子，那么代码中有 5 种情况：如果你斜向看，敌方棋子是主教等。这个查找非常快，因为如果国王在棋盘中间，你最多需要查看 27 个位置没有块阻塞，但通常要少得多。
移动一代
我花了很多时间试图使我的 Python 引擎尽可能快，并开始像你一样使用 2D 阵列板表示。它可以工作，但是一维板表示更快（虽然有点难以理解）。
但是对于您的 2D 表示，我认为有 2 种方法：
- 生成伪合法移动，然后在搜索时测试它们是否合法。
- 生成所有固定的棋子，然后只生成合法的移动。
1。稍后通过合法检查生成伪合法移动
看起来你有一个可行的方法。我发现通过可能的方向循环而不是将它放在 4 个单独的循环中更好一点，例如对于女王来说是这样的（很抱歉展示我的一维方法，但它对你来说是相似的，只是其他方向）：
def get_queen_moves(square):
# Up, left, down, right, up/left, up/right, down/left, down/right
for d in [-10, -1, 10, 1, -11, -9, 9, 11]:
for i in range(1, 8): # At most 7 squares in each direction
end_square = square + d*i
end_piece = self.board[end_square]
# If square is enemy piece or empty square, append move
if end_piece in [enemy_pieces, empty_square]:
moves.append(square, end_square)
# If enemy piece, then break the direction since we can't go further here
if end_piece in enemy_pieces:
break
# Found own piece, can't move here so move on to next direction
else:
break
在你的 minimax（在我的例子中是 negamax，无论如何都是相同的方法）搜索你会做这样的事情：
def negamax(depth, alpha, beta):
# Depth = 0, return value from the quiescence search
if depth == 0:
return self.quiescence(alpha, beta)
# Get pseudo legal moves
children = gen_moves(self.gamestate)
# Negamax recursive loop
for child in children:
# If move is legal, make it. Otherwise move on to the next candidate.
# In my make_move function I return 1 if I am not left in check, otherwise I unmake the move there and return 0.
if self.gamestate.make_move(child):
# Do a normal search
score = -self.negamax(depth - 1, -beta, -alpha, True)
# Take back move
self.gamestate.unmake_move()
如果您实施移动顺序和 alpha/beta 等，您很可能会节省很多时间，而不是检查所有移动的合法性，而只检查您正在考虑的移动。我希望我在这里说清楚。
2。生成大头针和仅合法移动
我喜欢先生成图钉，然后只生成合法的移动。它有点复杂，所以请询问我的代码是否有任何不清楚的地方。这个想法是像以前一样从国王四面八方去。如果我们在例如对角线方向我们继续走更多次，看看我们是否在那个方向找到敌方主教或女王。如果我们这样做，我们的主教就被固定了。我们保存棋子以及它被发现的方向（如果像这种情况下它是主教，固定的棋子仍然可以移动，朝向和远离国王）。
这里是生成合法走法以及查找图钉和支票的代码：
# Get all moves considering checks and pins
def get_valid_moves(self):
king_pos = self.white_king_location if self.is_white_turn else self.black_king_location
# Find if is in check and all the possible pinned pieces
self.is_in_check, self.pins, self.checks = self.check_for_pins_and_checks(king_pos)
# If we are in check we can only take the piece, move the king, or put own piece in the way
if self.is_in_check:
if len(self.checks) == 1: # Single check
moves = self.get_all_possible_moves()
check = self.checks[0]
checking_piece_pos = check[0]
piece_checking = self.board[check[0]] # Enemy piece that is causing the check
valid_squares = [] # Valid squares the piece can move to
if piece_checking[1] == 'N': # Knight check, must capture knight or move king
valid_squares = [checking_piece_pos]
else:
for i in range(1, 8):
valid_square = (king_pos + check[1] * i) # Look in the direction of checking piece
valid_squares.append(valid_square)
if valid_square == checking_piece_pos: # If finding the checking piece, look no further
break
# Filter to only keep moves that are valid during check
moves = list(filter(lambda x: x[0] == king_pos or x[1] in valid_squares or
(self.board[x[0]][1] == 'p' and x[1] == self.enpassant_square and piece_checking[1] == 'p'), moves))
else: # Double check, only king can move
moves = []
self.get_king_moves(king_pos, moves, False)
# If not in check, we find all moves (with respect to pins)
else:
moves = self.get_all_possible_moves()
return moves
# Checks if there are any pinned pieces or current checks
def check_for_pins_and_checks(self, square):
pins, checks = [], []
is_in_check = False
enemy_color, friendly_color = ('b', 'w') if self.is_white_turn else ('w', 'b')
# Check out from all directions from the king
for i in range(8):
d = s.directions[i]
possible_pin = False
for j in range(8): # Check the entire row/column in that direction
end_square = square + d*j
piece_color, piece_type = self.board[end_square][0], self.board[end_square][1]
if is_on_board(end_square):
if piece_color == friendly_color and piece_type != 'K':
if not possible_pin: # First own piece, we found a possible pin
possible_pin = (end_square, d)
else: # 2nd friendly piece, it wasn't a pin
break
elif piece_color == enemy_color:
# 5 different cases as before:
if (0 <= i <= 3 and piece_type == 'R') or \
(4 <= i <= 7 and piece_type == 'B') or \
(j == 1 and piece_type == 'p' and ((enemy_color == 'w' and 6 <= i <= 7) or (enemy_color == 'b' and 4 <= i <= 5))) or \
(piece_type == 'Q') or \
(j == 1 and piece_type == 'K'):
if not possible_pin: # No friendly piece is blocking -> is check
is_in_check = True
checks.append((end_square, d))
break
else: # Friendly piece is blocking -> we found a pinned piece
pins.append(possible_pin)
break
else: # Enemy piece that is not applying check or pin
break
else: # i, j is off board
break
# Check for knight checks
for d in s.knight_moves:
end_square = square + d
end_piece = self.board[end_square]
if is_on_board(end_square):
if end_piece[0] == enemy_color and end_piece[1] == 'N': # Enemy knight attacking king
is_in_check = True
checks.append((end_square, d))
return is_in_check, pins, checks
所以现在我们需要将我们固定的信息应用到我们的生成移动函数中。我将再次以女王为例。
我们唯一需要做的就是找到棋子是否被固定（第一个额外的代码块），然后在我们附加移动之前我们需要检查该棋子没有被固定或者固定方向允许我们移动棋子在那里（例如将女王移向或远离国王）。
def get_queen_moves(square):
# Loop through our pins and see if our piece is pinned. Remove it from our pinned piece list since we don't need the information any more.
pin_direction = ()
for i in range(len(self.pins)-1, -1, -1):
if self.pins[i][0] == square:
piece_pinned = True
pin_direction = (self.pins[i][1])
self.pins.remove(self.pins[i])
break
# Up, left, down, right, up/left, up/right, down/left, down/right
for d in [-10, -1, 10, 1, -11, -9, 9, 11]:
for i in range(1, 8): # At most 7 squares in each direction
end_square = square + d*i
end_piece = self.board[end_square]
# If square is enemy piece or empty square, append move
if end_piece in [enemy_pieces, empty_square]:
# Here we check if piece is pinned or if the direction allows us to add the piece anyway.
if not piece_pinned or pin_direction in (d, -d):
moves.append(square, end_square)
# If enemy piece, then break the direction since we can't go further here
if end_piece in enemy_pieces:
break
# Found own piece, can't move here so move on to next direction
else:
break
应该就这些了，有什么问题请追问:)
这是我第一个答案的合并（和部分验证）代码。我到处都将 (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])
这些状态必须保存在与当前板关联的某个地方。这可能证明为董事会创建 class 而不是使用简单的列表列表是合理的。如果您发现创建 class 太过分了
，则该信息也可以保存在面板列表的第 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
move,promote = input(),"?"
if move == "resign": return opponent
if move == "draw":
if input(f"Does {opponent} accept a draw? ")=="y": return "DRAW"
else: continue
try:
move = tuple(divmod(p,10) for p in map(int,move.split("-")))
if move in legalMoves: break
except: pass
print("Not a valid move, try again")
print("Legal Moves:",*(f"{fc}{fr}-{tc}{tr}"
for (fc,fr),(tc,tr) in sorted(legalMoves)))
board = playMove(board,*move,promote)
player,opponent = opponent,player
运行游戏...
stats = {"black":0, "white":0, "DRAW":0}
while True:
print("Specify moves as cr-cr e.g. 04-06 to move from (0,4) to (0,6)")
outcome = playChess(computer="black")
stats[outcome] += 1
print(*(f"{p}: {c} " for p,c in stats.items()))
print()
if input("continue (y/n)?:")=="n":break
我目前正在研究国际象棋引擎，该引擎目前正在运行，但需要很长时间才能生成动作。检查检测花费的时间最长，因为必须生成许多移动。
我尝试了很多东西后卡住了，无法真正弄清楚如何提高效率。这是我的做法：
要检查移动是否 allowed/legal，我检查移动的一方是否在之后检查：
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
这是迄今为止我的引擎中最昂贵的操作，我想知道我是否可以以某种方式简化它。伪合法移动是使用此文件计算的，供任何感兴趣的人使用。为完成所有移动，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
我希望我把我的 problem/code 的一切都说清楚了。感谢任何帮助。
使用预先计算的数据结构还有很多工作要做。例如，您可以为每种棋子类型和方向准备一个字典，其中包含来自任何位置的可能目的地。这样，您就不需要复杂的代码来检查可用的移动。
[请参阅我对合并和调整后的代码的第二个答案]
您还可以使用它来执行第一次验证以进行检查！。如果它是另一块棋子，您可以通过检查国王可以到达的位置来做到这一点。例如，如果您在车可以从国王的位置移动的位置找到车，那么就有可能进行检查！。对每种棋子类型执行此操作将使您知道是否有必要评估实际移动。
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])
如果 none 为真，则白王没有威胁。如果 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”，但大部分代码应该更简单（并且可能更快）。
看起来你在移动生成和检查检测中使事情变得复杂，这使得它真的很慢。
更好的检查检测方法
现在你说给对方生成所有的合法走法，看对方能不能擒王。这是非常慢的，更好的方法是从你自己的国王的角度来看，看看在你移动后任何方向是否有任何敌人的棋子，它可能看起来像这样（广场是你的国王广场）：
def is_in_check(square):
enemy_color, friendly_color = ('b', 'w') if self.is_white_turn else ('w', 'b')
# Check out from all directions from the king
for i, d in enumerate(s.directions):
for j in range(1, 8): # Check the entire row/column in that direction
end_square = square + d*j
piece_color, piece_type = self.board[end_square][0], self.board[end_square][1]
if is_on_board(end_square ):
if piece_color == friendly_color and piece_type != 'K':
break
elif piece_color == enemy_color:
# 5 different cases:
# 1. Orthogonally from king and piece is a rook
# 2. Diagonally from king and piece is a bishop
# 3. 1 square away diagonally from king and piece is a pawn
# 4. Any direction and piece is a queen
# 5. Any direction 1 square away and piece is a king
if (0 <= i <= 3 and piece_type == 'R') or \
(4 <= i <= 7 and piece_type == 'B') or \
(j == 1 and piece_type == 'p' and ((enemy_color == 'w' and 6 <= i <= 7) or (enemy_color == 'b' and 4 <= i <= 5))) or \
(piece_type == 'Q') or \
(j == 1 and piece_type == 'K'):
return True
else: # Enemy piece that is not applying check or pin
break
else: # i, j is off board
break
# Check for knight checks
for d in s.knight_moves:
end_piece = self.board[square + d]
if is_on_board(end_square):
if end_piece[1] == 'N' and end_piece[0] == enemy_color: # Enemy knight attacking king
return True
return False
如果代码不清楚，请在评论中提问，我从我的早期引擎中复制了大部分内容，因此它可能与您的表示不完全一样。这个想法是从国王的各个方向看。如果您找到自己的棋子或不在棋盘上，请休息并继续下一个方向。如果你找到敌方棋子，那么代码中有 5 种情况：如果你斜向看，敌方棋子是主教等。这个查找非常快，因为如果国王在棋盘中间，你最多需要查看 27 个位置没有块阻塞，但通常要少得多。
移动一代
我花了很多时间试图使我的 Python 引擎尽可能快，并开始像你一样使用 2D 阵列板表示。它可以工作，但是一维板表示更快（虽然有点难以理解）。
但是对于您的 2D 表示，我认为有 2 种方法：
- 生成伪合法移动，然后在搜索时测试它们是否合法。
- 生成所有固定的棋子，然后只生成合法的移动。
1。稍后通过合法检查生成伪合法移动
看起来你有一个可行的方法。我发现通过可能的方向循环而不是将它放在 4 个单独的循环中更好一点，例如对于女王来说是这样的（很抱歉展示我的一维方法，但它对你来说是相似的，只是其他方向）：
def get_queen_moves(square):
# Up, left, down, right, up/left, up/right, down/left, down/right
for d in [-10, -1, 10, 1, -11, -9, 9, 11]:
for i in range(1, 8): # At most 7 squares in each direction
end_square = square + d*i
end_piece = self.board[end_square]
# If square is enemy piece or empty square, append move
if end_piece in [enemy_pieces, empty_square]:
moves.append(square, end_square)
# If enemy piece, then break the direction since we can't go further here
if end_piece in enemy_pieces:
break
# Found own piece, can't move here so move on to next direction
else:
break
在你的 minimax（在我的例子中是 negamax，无论如何都是相同的方法）搜索你会做这样的事情：
def negamax(depth, alpha, beta):
# Depth = 0, return value from the quiescence search
if depth == 0:
return self.quiescence(alpha, beta)
# Get pseudo legal moves
children = gen_moves(self.gamestate)
# Negamax recursive loop
for child in children:
# If move is legal, make it. Otherwise move on to the next candidate.
# In my make_move function I return 1 if I am not left in check, otherwise I unmake the move there and return 0.
if self.gamestate.make_move(child):
# Do a normal search
score = -self.negamax(depth - 1, -beta, -alpha, True)
# Take back move
self.gamestate.unmake_move()
如果您实施移动顺序和 alpha/beta 等，您很可能会节省很多时间，而不是检查所有移动的合法性，而只检查您正在考虑的移动。我希望我在这里说清楚。
2。生成大头针和仅合法移动
我喜欢先生成图钉，然后只生成合法的移动。它有点复杂，所以请询问我的代码是否有任何不清楚的地方。这个想法是像以前一样从国王四面八方去。如果我们在例如对角线方向我们继续走更多次，看看我们是否在那个方向找到敌方主教或女王。如果我们这样做，我们的主教就被固定了。我们保存棋子以及它被发现的方向（如果像这种情况下它是主教，固定的棋子仍然可以移动，朝向和远离国王）。
这里是生成合法走法以及查找图钉和支票的代码：
# Get all moves considering checks and pins
def get_valid_moves(self):
king_pos = self.white_king_location if self.is_white_turn else self.black_king_location
# Find if is in check and all the possible pinned pieces
self.is_in_check, self.pins, self.checks = self.check_for_pins_and_checks(king_pos)
# If we are in check we can only take the piece, move the king, or put own piece in the way
if self.is_in_check:
if len(self.checks) == 1: # Single check
moves = self.get_all_possible_moves()
check = self.checks[0]
checking_piece_pos = check[0]
piece_checking = self.board[check[0]] # Enemy piece that is causing the check
valid_squares = [] # Valid squares the piece can move to
if piece_checking[1] == 'N': # Knight check, must capture knight or move king
valid_squares = [checking_piece_pos]
else:
for i in range(1, 8):
valid_square = (king_pos + check[1] * i) # Look in the direction of checking piece
valid_squares.append(valid_square)
if valid_square == checking_piece_pos: # If finding the checking piece, look no further
break
# Filter to only keep moves that are valid during check
moves = list(filter(lambda x: x[0] == king_pos or x[1] in valid_squares or
(self.board[x[0]][1] == 'p' and x[1] == self.enpassant_square and piece_checking[1] == 'p'), moves))
else: # Double check, only king can move
moves = []
self.get_king_moves(king_pos, moves, False)
# If not in check, we find all moves (with respect to pins)
else:
moves = self.get_all_possible_moves()
return moves
# Checks if there are any pinned pieces or current checks
def check_for_pins_and_checks(self, square):
pins, checks = [], []
is_in_check = False
enemy_color, friendly_color = ('b', 'w') if self.is_white_turn else ('w', 'b')
# Check out from all directions from the king
for i in range(8):
d = s.directions[i]
possible_pin = False
for j in range(8): # Check the entire row/column in that direction
end_square = square + d*j
piece_color, piece_type = self.board[end_square][0], self.board[end_square][1]
if is_on_board(end_square):
if piece_color == friendly_color and piece_type != 'K':
if not possible_pin: # First own piece, we found a possible pin
possible_pin = (end_square, d)
else: # 2nd friendly piece, it wasn't a pin
break
elif piece_color == enemy_color:
# 5 different cases as before:
if (0 <= i <= 3 and piece_type == 'R') or \
(4 <= i <= 7 and piece_type == 'B') or \
(j == 1 and piece_type == 'p' and ((enemy_color == 'w' and 6 <= i <= 7) or (enemy_color == 'b' and 4 <= i <= 5))) or \
(piece_type == 'Q') or \
(j == 1 and piece_type == 'K'):
if not possible_pin: # No friendly piece is blocking -> is check
is_in_check = True
checks.append((end_square, d))
break
else: # Friendly piece is blocking -> we found a pinned piece
pins.append(possible_pin)
break
else: # Enemy piece that is not applying check or pin
break
else: # i, j is off board
break
# Check for knight checks
for d in s.knight_moves:
end_square = square + d
end_piece = self.board[end_square]
if is_on_board(end_square):
if end_piece[0] == enemy_color and end_piece[1] == 'N': # Enemy knight attacking king
is_in_check = True
checks.append((end_square, d))
return is_in_check, pins, checks
所以现在我们需要将我们固定的信息应用到我们的生成移动函数中。我将再次以女王为例。 我们唯一需要做的就是找到棋子是否被固定（第一个额外的代码块），然后在我们附加移动之前我们需要检查该棋子没有被固定或者固定方向允许我们移动棋子在那里（例如将女王移向或远离国王）。
def get_queen_moves(square):
# Loop through our pins and see if our piece is pinned. Remove it from our pinned piece list since we don't need the information any more.
pin_direction = ()
for i in range(len(self.pins)-1, -1, -1):
if self.pins[i][0] == square:
piece_pinned = True
pin_direction = (self.pins[i][1])
self.pins.remove(self.pins[i])
break
# Up, left, down, right, up/left, up/right, down/left, down/right
for d in [-10, -1, 10, 1, -11, -9, 9, 11]:
for i in range(1, 8): # At most 7 squares in each direction
end_square = square + d*i
end_piece = self.board[end_square]
# If square is enemy piece or empty square, append move
if end_piece in [enemy_pieces, empty_square]:
# Here we check if piece is pinned or if the direction allows us to add the piece anyway.
if not piece_pinned or pin_direction in (d, -d):
moves.append(square, end_square)
# If enemy piece, then break the direction since we can't go further here
if end_piece in enemy_pieces:
break
# Found own piece, can't move here so move on to next direction
else:
break
应该就这些了，有什么问题请追问:)
这是我第一个答案的合并（和部分验证）代码。我到处都将 (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])
这些状态必须保存在与当前板关联的某个地方。这可能证明为董事会创建 class 而不是使用简单的列表列表是合理的。如果您发现创建 class 太过分了
，则该信息也可以保存在面板列表的第 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
move,promote = input(),"?"
if move == "resign": return opponent
if move == "draw":
if input(f"Does {opponent} accept a draw? ")=="y": return "DRAW"
else: continue
try:
move = tuple(divmod(p,10) for p in map(int,move.split("-")))
if move in legalMoves: break
except: pass
print("Not a valid move, try again")
print("Legal Moves:",*(f"{fc}{fr}-{tc}{tr}"
for (fc,fr),(tc,tr) in sorted(legalMoves)))
board = playMove(board,*move,promote)
player,opponent = opponent,player
运行游戏...
stats = {"black":0, "white":0, "DRAW":0}
while True:
print("Specify moves as cr-cr e.g. 04-06 to move from (0,4) to (0,6)")
outcome = playChess(computer="black")
stats[outcome] += 1
print(*(f"{p}: {c} " for p,c in stats.items()))
print()
if input("continue (y/n)?:")=="n":break