Menu
I'm currently working on a chess engine, which is working so far but is taking forever to generate moves. The check detection takes by far the longest since many moves have to be generated.
I got stuck after trying many things and can't really figure out how to make it more efficient. Here is how I do it:
To check if a move is allowed/legal, I check, if the side making the move is in check afterwards:
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
To determine if a side is in check, i generate every move of the opponents side and check if they would be able to capture the king on their next move. (This is the bad part)
sq[1:] just determines the colour of the current square
self.(colour).king is the current position of the king
move is a tuple containing the coordinates of the end square of each 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
This is by far the most expensive operation in my engine and I'm wondering if I could simplify it somehow. The pseudo-legal-moves are calculated using this file, for anyone interested. To complete all moves, en-passant, casting, and promotion are generated separately. I also generate a list of possible, legal moves per side after each executed move, but since the check-detection uses a potential move, those lists cant be used.
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
I hope I made everything clear about my problem/code. Any help is appreciated.
202
In informal games most players still announce "check", however it is no longer required under the rules of chess and is not encouraged in formal games (Just & Burg 2003:28).
Normal rules apply, but you can also win (or lose!) a game by checking (or getting checked) 3 times in total. Games can still end in the traditional ways of checkmate, stalemate and time-out. The game can also end if a player checks their opponent's king three times.
Check is a situation in the game of Chess where a player's King is threatened directly by another player's piece. If at any point in the game a player's King is threatened directly by another player's piece so that in their next turn, they will be able to capture him - the other player has put the King in “Check”.
There is much to be done with pre-calculated data structures. For example, you could prepare a dictionary with the possible destinations from any positions for every piece type and orientation. With that, you wouldn't need complex code to check available moves.
[SEE MY SECOND ANSWER FOR CONSOLIDATED AND ADJUSTED CODE]
You could also use it to perform a first verification for check!. You would do that by checking the positions the king could reach if it were another piece. For example if you find a rook at a position where a rook could move from the king's position then there is a potential for check!. Doing this for each piece type will allow you to know if evaluating actual moves is necessary.
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)]
start with basic trajectories ...
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 }
then combine them for each piece type ...
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)] })
This will allow you to directly get the list of potential move positions for any piece anywhere on the board.
For example:
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)]
To know if there is a potential check on the white king at 5,4, you can perform a quick verification before going into move simulations:
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])
if none of those are True, then there is no threat to the white king. If checkByQueen, checkByRook or checkByBishop is True, then you'll need to verify occlusion by another piece in between but that would have already reduced the number of cases considerably.
You could also enhance the dictionary to give you the positons between two squares on the board using a position as key (instead of a string).
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]
This would allow you to easily check if there is a piece in between two positions. For example, if you find a queen at (5,0) you can check if the king is in line of sight using this:
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])
This can be combined into the above conditions to give a comprehensive verification:
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])
Using all this you would not need to simulate moves at all to detect a check!, you could do it in a single line:
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] )
Sample content:
for r,c in positions:
print("FROM",(r,c))
for piece in targets:
print(f" {piece:10}:",*targets[piece][r,c])
...
FROM (2, 4)
up : (3, 4) (4, 4) (5, 4) (6, 4) (7, 4)
down : (1, 4) (0, 4)
vertical : (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4)
left : (2, 3) (2, 2) (2, 1) (2, 0)
right : (2, 5) (2, 6) (2, 7)
horizontal: (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7)
upleft : (3, 3) (4, 2) (5, 1) (6, 0)
upright : (3, 5) (4, 6) (5, 7)
downleft : (1, 3) (0, 2)
downright : (1, 5) (0, 6)
diagUL : (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6)
diagDL : (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
king : (1, 4) (1, 5) (2, 3) (2, 5) (3, 3) (3, 4)
rook : (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7) (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4)
bishop : (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6) (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
queen : (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7) (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4) (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6) (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
wpawn : (3, 4)
bpawn : (1, 4)
wptake : (3, 5) (3, 3)
bptake : (1, 5) (1, 3)
knight : (4, 5) (4, 3) (3, 6) (3, 2) (0, 5) (0, 3) (1, 6) (1, 2)
...
[EDIT]
To leverage this for move generation, you still have to add some conditions but I believe the dictionary should make the logic simpler and faster:
# 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
... initialize move generation cycle
# 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")])
... for each piece on the board ...
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" )
There are more exceptions to be managed such as "castling" and "en passant" but most of the code should be simpler (and probably faster).
186
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
