2

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

eligolf
  • 252
  • 2
  • 10
  • 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. – David Oct 15 '20 at 10:14
  • Sorry, I thought this was a site to get help with programming as well, I will try another place! :) – eligolf Oct 15 '20 at 10:17
  • 4
    @David: chess programming questions are explicitly on topic. – RemcoGerlich Oct 15 '20 at 10:50
  • 2
    First things first: have you used a [perft function](https://www.chessprogramming.org/Perft) 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. – emdio Oct 15 '20 at 11:04
  • @emdio, I have just played it myself human vs human and tried all possible things of weird scenarios and it seems bug free. With an evaluation function of just going through the pieces on the board, assigning a value to the score, and sum it up gives me the above times for each depth – eligolf Oct 15 '20 at 11:12
  • 1
    @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. – emdio Oct 15 '20 at 11:18
  • @emdio, Thank you for the advice, I will do this! – eligolf Oct 15 '20 at 11:25
  • @RemcoGerlich I'm not asking for the question to be removed. They are allowed by the rules, I'm just pointing out that this may not be the best place to get an answer. – David Oct 15 '20 at 11:31
  • Since you're using python maybe you want to take a look at this engine: https://github.com/thomasahle/sunfish Also, for hard programming chess engine questions, the place to go would be http://talkchess.com – emdio Oct 15 '20 at 15:21
  • 1
    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. – Cort Ammon Oct 15 '20 at 18:44
  • Cheers everyone! – eligolf Oct 16 '20 at 05:47
  • If your engine has an expensive evaluation (e.g. neural net) Python is fine, but in circumstances where you want high node throughput Python is not the best choice for performance... something like C++ is much better – bcdan Nov 16 '20 at 06:33

1 Answers1

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

  • 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! – eligolf Oct 16 '20 at 11:20