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

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

21129: <p><strong>Problem</strong></p>
<p>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:</p>
<ul>
<li>Depth 1: 0.01 s</li>
<li>Depth 2: 0.07 s</li>
<li>Depth 3: 0.76 s</li>
<li>Depth 4: 19.8 s</li>
</ul>
<p>I have timed each function and here are the worst performing functions, time is per move at depth 4:</p>
<ul>
<li>get_valid_moves (10 s)</li>
<li>deepcopy (8 s)</li>
<li>get_all_possible_moves (8 s)</li>
</ul>
<p><strong>What I have tried</strong></p>
<p>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.</p>
<p><strong>What I need feedback on</strong></p>
<p>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:</p>
<ul>
<li>Looping through 8 directions from the king location to find if I am in check and what pieces are pinned (8x8 loop)</li>
<li>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)</li>
<li>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)</li>
</ul>
<p><strong>Here is an example of how I calculate possible moves for a piece, bishop in this case:</strong></p>
<pre><code>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 &lt;= x &lt;= 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
</code></pre>
<p><strong>Board 2D respresentation:</strong></p>
<pre><code>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']])
</code></pre>
<p><strong>Final questions</strong></p>
<p>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... :)</p>
 -1: <p>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?</p>
<p>On the chance that you do:</p>
<p>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.</p>
<p>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.</p>
<p>And so on.</p>
<p>Bitboards can be more efficient, but as you explicitly said to exclude those, ...</p>
