The most efficient valid move generation for minimax

Question

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

Answer 1

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, ...