Problem
I am creating a chess engine in Python using Minimax algorithm (with alpha/beta pruning) but I have some issues with performance. Currently the thinking time looks something like this for a mid game position:
- Depth 1: 0.01 s
- Depth 2: 0.07 s
- Depth 3: 0.76 s
- Depth 4: 19.8 s
I have timed each function and here are the worst performing functions, time is per move at depth 4:
- get_valid_moves (10 s)
- deepcopy (8 s)
- get_all_possible_moves (8 s)
What I have tried
I have tried to have the board represented as a 2D array (8x8) which is the easiest solution. With a 1D representation (10x12) I got a tiny bit better performance but not enough to increase depth.
What I need feedback on
Before I try to optimize my minimax function with transposition table lookups and such, I was hoping to have the most efficient way of calculating valid moves and all moves. Here is the process I currently use:
- Looping through 8 directions from the king location to find if I am in check and what pieces are pinned (8x8 loop)
- Get all possible (pseudo?) moves without considering checks or pins (8x8 loop to find all pieces on board and then add each pieces possible moves to a list)
- Get valid moves by seeing if I am in check or double check (removing moves from the all_possible_moves list if they are not legal)
Here is an example of how I calculate possible moves for a piece, bishop in this case:
def get_bishop_moves(self, row, col, moves):
piece_pinned = False
pin_direction = ()
for i in range(len(self.pins)-1, -1, -1):
if self.pins[i][0] == row and self.pins[i][1] == col:
piece_pinned = True
pin_direction = (self.pins[i][2], self.pins[i][3])
self.pins.remove(self.pins[i])
break
directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
enemy_color = 'b' if self.is_white_turn else 'w'
for d in directions:
for i in range(1, 8):
end_row, end_col = row + d[0] * i, col + d[1] * i
if all(0 <= x <= 7 for x in (end_row, end_col)):
if not piece_pinned or pin_direction == d or pin_direction == (-d[0], -d[1]):
end_piece = self.board[end_row][end_col]
if end_piece == '--':
moves.append((row, col), (end_row, end_col))
elif end_piece[0] == enemy_color:
moves.append((row, col), (end_row, end_col))
break
else:
break
else:
break
Board 2D respresentation:
start_board = np.array([
['bR', 'bN', 'bB', 'bQ', 'bK', 'bB', 'bN', 'bR'],
['bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp'],
['--', '--', '--', '--', '--', '--', '--', '--'],
['--', '--', '--', '--', '--', '--', '--', '--'],
['--', '--', '--', '--', '--', '--', '--', '--'],
['--', '--', '--', '--', '--', '--', '--', '--'],
['wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp'],
['wR', 'wN', 'wB', 'wQ', 'wK', 'wB', 'wN', 'wR']])
Final questions
Is there any way of doing the valid move generation differently (without using bitboards)? Am I overlooking something? It is not fun to work on the evaluation function when my engine doesn't reach more than depth 4... :)