Detecting checks more efficiently (Chess)
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 squareself.(colour).kingis the current position of the kingmoveis 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.