# The most efficient valid move generation for minimax

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... :)

• Welcome to our site! Unfortuantely this is focused on chess so don't expect folks over here to understand what you're talking about. A site dedicated to Math, machine learning or game theory is probably more suitable for this kind of question. Commented Oct 15, 2020 at 10:14
• @David: chess programming questions are explicitly on topic. Commented Oct 15, 2020 at 10:50
• First things first: have you used a perft function to ensure your move generator is bug free? This is quite a hard task when writing a chess engine. After you're sure you have a bug free move generator, then measure how long it takes to make it to depth 4, 5, 6... with no search function. If those values are huge, then there's something wrong with the design of the move generator itself. Commented Oct 15, 2020 at 11:04
• @eligolf just paying isn't enough; you must properly test it with a perft function. Besides, the thing is you could have a bug in the search function. So to be sure and give a step each time, I'd insist in building a perft function and check how fast it is. If the move generator takes "too much" time to make it to low plies, then the issue is in the move generator design. Commented Oct 15, 2020 at 11:18
• Also, its worth looking at bit boards, which can replace some of the for loops with single logic operations, which can be dozens of times faster. Commented Oct 15, 2020 at 18:44

You should not stop after figuring out where the bottlenecks are, you should go on to identify them. For example, do you invoke the get_xxxx_moves() every time around?

On the chance that you do:

Instead of listing all moves each time, you may be able to reduce the work needed by only updating the piece move lists that are affected by a move. The other pieces (status and valid move lists) are unaffected, and don't need recalculation.

Thus, the opening move e2-e4 only affects pieces that cover/attack the start square e2 (wQ, wK, wBf1 and wNg1), so those are the only recalculations needed. Nothing covers/attacks e4, so no more work to do right now.

And so on.

Bitboards can be more efficient, but as you explicitly said to exclude those, ...

• That might be an idea, I still have to figure out what pieces are affected by a move which would be an entirely new function though. Maybe it could be worth it, I will have to try! Commented Oct 16, 2020 at 11:20