Chess Simulation

Question

Part of the program I wrote simulates a Chess game choosing random moves for each player until it's a draw or win for either player. It takes 3 seconds to complete 1 simulation and since it trains this way it will be much too slow to get real progress in chess because of the insane branching factor.

I tried dividing the most lengthy function in to multiple processes. This made it much slower because the function actually isn't that complicated and starting the processes takes longer than to just run it in one process. Is there any other way to speed this up?

For anyone who might be interested in seeing all the code and running it for themselves (it is fully functioning): GitHub

This function belongs to class Node, which as the name suggests is a node on the game tree that this program explores and trains on.

Simulation function:

# Random simulation
def roll_out(self):
    self.visits += 1
    settings.path.append(int(self.index))
    board = copy.deepcopy(self.state)             # starting state of board
    player = Player(self.state, self.color)
    opponent = Player(board, self.opp)
    if checkmate(board, self.color):              # is the starting state already checkmate?
        value, self.win = 20, True
        settings.value[self.color] = value
        return
    if opponent.draw:                             # is the starting state already a draw?
        value, self.draw = 5, True
        settings.value[self.color] = value
        return
    for i in range(1000):
        self.random_move(opponent, board)         # moves a random piece
        player.set_moves(board)                   # update our legal moves
        if player.draw:
            value = 5
            settings.value[self.color] = value
            return
        if opponent.won:
            value = 0
            settings.value[self.color] = value
            return
        if len(opponent.pieces) == 1 and len(player.pieces) == 1:
            value = 5
            settings.value[self.color] = value
            return
        self.random_move(player, board)           # moves a random piece
        opponent.set_moves(board)                 # update opponents legal moves
        if opponent.draw:
            value = 5
            settings.value[self.color] = value
            return
        if player.won:
            value = 20
            settings.value[self.color] = value
            return
        if len(player.pieces) == 1 and len(opponent.pieces) == 1:
            value = 5
            settings.value[self.color] = value
            return

Move function located in Player class:

# Places chosen piece to chosen location on board
def move(self, c_pos, t_pos, board):
    if self.side == 'black':
        me, end_row = 'b', 7
    else:
        me, end_row = 'w', 0
    c_row, c_column = c_pos[0], c_pos[1]
    t_row, t_column = t_pos[0], t_pos[1]
    piece = board[c_row][c_column]
    board[c_row][c_column] = 1
    if 'P' in piece and t_row == end_row:
        self.pawn_queens += 1
        piece = me + 'Q' + str(self.pawn_queens)
    board[t_row][t_column] = piece
    if 'bK' in piece:
        self.bk_moved = True
    if 'bR1' in piece:
        self.br1_moved = True
    if 'bR2' in piece:
        self.br2_moved = True
    if 'wK' in piece:
        self.wk_moved = True
    if 'wR1' in piece:
        self.wr1_moved = True
    if 'wR2' in piece:
        self.wr2_moved = True
    if 'K' in str(piece) and t_column == c_column - 3:
        rook = board[c_row][0]
        board[c_row][2], board[c_row][0] = rook, 1
    if 'K' in str(piece) and t_column == c_column + 2:
        rook = board[c_row][7]
        board[c_row][5], board[c_row][7] = rook, 1
    if self.checkmate(board):
        self.won = True
    self.available_moves_reset()

And then what I would think is the time consuming function, I left out the code for the queens moves since it's basically the code from the rook and bishop combined and would be I think too long to post here.

Pawn moves:

def get_pawn_moves(board, color):
    for row in board:
        for square in row:
            if color[0] + 'P' in str(square):
                key = square.replace(color[0], '')
                pawn_moves[key] = []
    if color == 'b':
        opp = 'w'
        p_start, start_row = 1, 0
    else:
        opp = 'b'
        p_start, start_row = 6, 7
    row = 0
    for i in board:
        col = 0
        for j in i:
            if color[0] + 'P' in str(j):
                key = j.replace(color[0], '')
                if color[0] == 'b':
                    one_step = row + 1
                    two_steps = row + 2
                else:
                    one_step = row - 1
                    two_steps = row - 2

                p_capture_left = col - 1
                p_capture_right = col + 1

                if one_step in range(8):
                    if color[0] and opp not in str(board[one_step][col]):
                        pawn_moves[key].append([one_step, col])
                        if row == p_start:
                            if opp and color[0] not in str(board[two_steps][col]):
                                pawn_moves[key].append([two_steps, col])

                    if p_capture_left != -1 and opp in str(board[one_step][p_capture_left]):
                        pawn_moves[key].append([one_step, p_capture_left])

                    if p_capture_right != 8 and opp in str(board[one_step][p_capture_right]):
                        pawn_moves[key].append([one_step, p_capture_right])
            col += 1
        row += 1

Rook moves:

def get_rook_moves(board, color):
    for i in board:
        for j in i:
            if color[0] + 'R' in str(j):
                key = j.replace(color[0], '')
                rook_moves[key] = []
    opp = 'w' if color[0] == 'b' else 'b'
    row = 0
    for i in board:
        col = 0
        for j in i:
            if color[0] + 'R' in str(j):
                key = j.replace(color[0], '')
                for i in range(row, -1, -1):
                    if i != row:
                        if color[0] not in str(board[i][col]):
                            rook_moves[key].append([i, col])
                            if opp in str(board[i][col]):
                                break
                        else:
                            break
                for i in range(row, 8):
                    if i != row:
                        if color[0] not in str(board[i][col]):
                            rook_moves[key].append([i, col])
                            if opp in str(board[i][col]):
                                break
                        else:
                            break
                for i in range(col, -1, -1):
                    if i != col:
                        if color[0] not in str(board[row][i]):
                            rook_moves[key].append([row, i])
                            if opp in str(board[row][i]):
                                break
                        else:
                            break
                for i in range(col, 8):
                    if i != col:
                        if color[0] not in str(board[row][i]):
                            rook_moves[key].append([row, i])
                            if opp in str(board[row][i]):
                                break
                        else:
                            break
            col += 1
        row += 1

Knight moves:

def get_knight_moves(board, color):
    for i in board:
        for j in i:
            if color[0] + 'N' in str(j):
                key = j.replace(color[0], '')
                knight_moves[key] = []
    row = 0
    for i in board:
        col = 0
        for j in i:
            if color[0] + 'N' in str(j):
                key = j.replace(color[0], '')
                if row - 2 >= 0 and col + 1 <= 7:
                    if color[0] not in str(board[row - 2][col + 1]):
                        knight_moves[key].append([row - 2, col + 1])
                if row - 2 >= 0 and col - 1 >= 0:
                    if color[0] not in str(board[row - 2][col - 1]):
                        knight_moves[key].append([row - 2, col - 1])
                if row - 1 >= 0 and col + 2 <= 7:
                    if color[0] not in str(board[row - 1][col + 2]):
                        knight_moves[key].append([row - 1, col + 2])
                if row - 1 >= 0 and col - 2 >= 0:
                    if color[0] not in str(board[row - 1][col - 2]):
                        knight_moves[key].append([row - 1, col - 2])
                if row + 1 <= 7 and col + 2 <= 7:
                    if color[0] not in str(board[row + 1][col + 2]):
                        knight_moves[key].append([row + 1, col + 2])
                if row + 1 <= 7 and col - 2 >= 0:
                    if color[0] not in str(board[row + 1][col - 2]):
                        knight_moves[key].append([row + 1, col - 2])
                if row + 2 <= 7 and col + 1 <= 7:
                    if color[0] not in str(board[row + 2][col + 1]):
                        knight_moves[key].append([row + 2, col + 1])
                if row + 2 <= 7 and col - 1 >= 0:
                    if color[0] not in str(board[row + 2][col - 1]):
                        knight_moves[key].append([row + 2, col - 1])
            col += 1
        row += 1

Bishop moves:

def get_bishop_moves(board, color):
    for n in board:
        for j in n:
            if color[0] + 'B' in str(j):
                key = j.replace(color[0], '')
                bishop_moves[key] = []
    opp = 'w' if color[0] == 'b' else 'b'
    row = 0
    for i in board:
        col = 0
        for j in i:
            if color[0] + 'B' in str(j):
                no_color = j.replace(color[0], '')
                ul_stop, dl_stop = False, False
                ur_stop, dr_stop = False, False
                count = 0
                for n in range(col, 8):
                    if col != n:
                        count += 1
                        u_row, d_row = row - count, row + count
                        if u_row >= 0:
                            if not ur_stop and color[0] not in str(board[u_row][n]):
                                bishop_moves[no_color].append([u_row, n])
                                if opp in str(board[u_row][n]):
                                    ur_stop = True
                            if color[0] in str(board[u_row][n]):
                                ur_stop = True
                        if d_row <= 7:
                            if not dr_stop and color[0] not in str(board[d_row][n]):
                                bishop_moves[no_color].append([d_row, n])
                                if opp in str(board[d_row][n]):
                                    dr_stop = True
                            if color[0] in str(board[d_row][n]):
                                dr_stop = True
                count = 0
                for n in range(col, -1, -1):
                    if col != n:
                        count += 1
                        u_row, d_row = row - count, row + count
                        if u_row >= 0:
                            if not ul_stop and color[0] not in str(board[u_row][n]):
                                bishop_moves[no_color].append([u_row, n])
                                if opp in str(board[u_row][n]):
                                    ul_stop = True
                            if color[0] in str(board[u_row][n]):
                                ul_stop = True
                        if d_row <= 7:
                            if not dl_stop and color[0] not in str(board[d_row][n]):
                                bishop_moves[no_color].append([d_row, n])
                                if opp in str(board[d_row][n]):
                                    dl_stop = True
                            if color[0] in str(board[d_row][n]):
                                dl_stop = True
            col += 1
        row += 1

King moves:

def get_king_moves(board, color, kmoved=False, r1moved=False, r2moved=False):
    for n in board:
        for j in n:
            if color[0] + 'K' in str(j):
                key = j.replace(color[0], '')
                king_moves[key] = []
    start_row = 0 if color[0] == 'b' else 7
    row = 0
    for i in board:
        col = 0
        for j in i:
            if color[0] + 'K' in str(j):
                key = j.replace(color[0], '')
                k_moves = []
                if row + 1 <= 7 and col + 1 <= 7:
                    if color[0] not in str(board[row + 1][col + 1]):
                        k_moves.append([row + 1, col + 1])
                    if color[0] not in str(board[row][col + 1]):
                        k_moves.append([row, col + 1])
                    if color[0] not in str(board[row + 1][col]):
                        k_moves.append([row + 1, col])
                elif row + 1 <= 7:
                    if color[0] not in str(board[row + 1][col]):
                        k_moves.append([row + 1, col])
                elif col + 1 <= 7:
                    if color[0] not in str(board[row][col + 1]):
                        k_moves.append([row, col + 1])
                if not kmoved and not r1moved:
                    if str(board[start_row][1]) and str(board[start_row][2]) and str(board[start_row][3]) == '1':
                        k_moves.append([start_row, 1])
                if not kmoved and not r2moved:
                    if str(board[start_row][5]) and str(board[start_row][6]) == '1':
                        k_moves.append([start_row, 6])
                if row - 1 >= 0 and col - 1 >= 0:
                    if color[0] not in str(board[row - 1][col - 1]):
                        k_moves.append([row - 1, col - 1])
                    if color[0] not in str(board[row - 1][col]):
                        k_moves.append([row - 1, col])
                    if color[0] not in str(board[row][col - 1]):
                        k_moves.append([row, col - 1])
                elif row - 1 >= 0:
                    if color[0] not in str(board[row - 1][col]):
                        k_moves.append([row - 1, col])
                elif col - 1 >= 0:
                    if color[0] not in str(board[row][col - 1]):
                        k_moves.append([row, col - 1])
                if row + 1 <= 7 and col - 1 >= 0 and color[0] not in str(board[row + 1][col - 1]):
                    k_moves.append([row + 1, col - 1])
                if row - 1 >= 0 and col + 1 <= 7 and color[0] not in str(board[row - 1][col + 1]):
                    k_moves.append([row - 1, col + 1])
                for i in k_moves:
                    king_moves[key].append(i)
            col += 1
        row += 1

Combine all moves in one dict:

def pseudo_legal(board, color, kmoved=False, r1moved=False, r2moved=False):
    all_moves = {}

    get_pawn_moves(board, color)
    get_rook_moves(board, color)
    get_knight_moves(board, color)
    get_bishop_moves(board, color)
    get_queen_moves(board, color)
    get_king_moves(board, color, kmoved=kmoved, r1moved=r1moved, r2moved=r2moved)

    all_moves.update(pawn_moves)
    all_moves.update(rook_moves)
    all_moves.update(knight_moves)
    all_moves.update(bishop_moves)
    all_moves.update(queen_moves)
    all_moves.update(king_moves)
    return all_moves

Check if moves are legal:

def get_moves(board, color, kmoved=False, r1moved=False, r2moved=False, opp_kmoved=False, opp_r1moved=False, opp_r2moved=False):
    if color == 'w':
        me, opp = 'w', 'b'
    else:
        me, opp = 'b', 'w'
    if not kmoved and not r1moved and not r2moved:
        moves, pieces = pseudo_legal(board, me), get_pieces(board, me)
    elif kmoved:
        moves, pieces = pseudo_legal(board, me, kmoved=True), get_pieces(board, me)
    elif r1moved:
        moves, pieces = pseudo_legal(board, me, r1moved=True), get_pieces(board, me)
    elif r2moved:
        moves, pieces = pseudo_legal(board, me, r2moved=True), get_pieces(board, me)
    legal_moves = {}
    for key in moves:
        count = 0
        piece = me + key
        for move in moves[key]:
            t_row, t_col = move[0], move[1]
            c_row, c_col = pieces[key][0], pieces[key][1]
            sim_board = copy.deepcopy(board)
            sim_board[t_row][t_col] = piece
            sim_board[c_row][c_col] = 1
            king = [t_row, t_col] if key == 'K' else pieces['K']
            if not opp_kmoved and not opp_r1moved and not opp_r2moved:
                opp_moves = pseudo_legal(board, opp)
            elif opp_kmoved:
                opp_moves = pseudo_legal(board, color, kmoved=True)
            elif opp_r1moved:
                opp_moves = pseudo_legal(board, color, r1moved=True)
            elif opp_r2moved:
                opp_moves = pseudo_legal(board, color, r2moved=True)
            legal = True
            for opp_key in opp_moves:
                for opp_move in opp_moves[opp_key]:
                    if king == opp_move:
                        legal = False
            if legal:
                if count == 0:
                    legal_moves[key] = []
                    count += 1
                legal_moves[key].append(move)
    if not legal_moves:
        return False
    return legal_moves

Answer 1

Looking over the github, one thing that's probably impacting your performance a good bit is memory thrash. Some of your big, complex functions spend a lot of time creating and assembling new data structures: for example your pseudo_legal() function (in chess_functions.py) is creating a new dictionary object every time its called. Along the way it calls range() quite a few times in order to loop over possibilities -- in Python 2, anyway, each of those range() calls is creating a new list. These short lived objects take time to create and also to destroy when they are no longer needed. That's a big part of your cost structure.

On a related note, I think you're also paying extra for the way the board is represented. You're storing the board as an array-of-arrays, which means more objects to be updating and also two lookups for every access. Your method for scanning involves checking all of the board squares (including the empty squares) to find the string string identifiers for the pieces, and then you parse the display names like 'wN' or 'bBp' before you start collecting possible moves. Taken together all that means every time you want to update the board, you have to do this for a lot of squares:

1. make a dictionary of possible moves
2. get the row list from the board
3. get the column entry from the row
4. get the string name of the piece there
5. parse the string to get the piece type (creating a new lookup string as part of the parsing -- another new object creation)
6. (usually) create a list to hold possible moves
7. do the logic to calculate possible moves add them to the list
8. ... which involves more double lookups...
9. copy the moves from the list to the dictionary

Between the lookups, the string creation, and the use of temporary lists you're moving a lot of memory around and also creating a lot of disposable objects which will need to be garbage collected.

If you want to speed things up, it might be a good idea to tackle these in a couple of ways.

sparse board

There are 64 spaces on the board, but only 32 pieces at max (and fewer as the games goes on). So you can avoid checking a lot of empty air by representng the board sparsely. A dictionary whose keys are (x,y) tuples does a nice job of representing the placement of the pieces. Moving a piece just means doing

 board[new_x, new_y] = board[old_x, old_y]
 del (board[old_x, old_y])

which would also automatically 'capture' any piece in new_x, new_y if there was already something there.

don't indirect the move functions

Related to using a dictionary is what you put into it. You can save a lot of string splitting and if-checking by just storing the functions which generate a move set in the board itself. Something like:

def knight(x, y):
    yield (x - 1, y + 2)
    yield (x - 2, y + 1)
    yield (x - 1, y - 2)
    yield (x - 2, y - 1)
    yield (x + 1, y + 2)
    yield (x + 2, y + 1)
    yield (x + 1, y - 2)
    yield (x + 2, y - 1)


board[0,1] = ('w', knight)
board[0,6] = ('w', knight)
board[7,1] = ('b', knight)
#... etc

That way when you want to know what moves are available for the piece in a square you don't need an extra lookup:

get_moves_for(x, y):
   color, move_set = board[x,y]
   for move in move_set():
       # check legality here....

split the logic for the moves

I used a generator here in my 'knight' function. That allows me to spit out all of the move combinations for a knight one at a time without having to assemble them into a list. For any given piece, many of the possible moves will be invalid so we don't want to create a list and then trim it down -- instead we can pass along one possible move at a time and then validate it in isolation, keeping or discarding it as conditions permit.

A nice thing about splitting things up like this is that you can easily outsource pieces of the logic in bite-size pieces. For example all of our moves have to be limited to the range 0-7 in both x and y. Rather than copying that logic around, we can just add a filtering function that only passes along values that are in the right range:

 def clip(addr):
    x, y = addr
    return -1 < x < 8 and -1 < y < 8

For example, you can take the move set for a given piece and location and clip it against the board like this:

 color, moves = board[address]
 valid_moves = (m for m in moves() if clip(m))

which will filter out the impossible moves without any reference to what they are.

One thing that's a bit hard to tackle with a pure generator setup like that is the fact that chess moves are -- as you show in your code -- sequential for many kinds of pieces. A rook, for example, can slide along until it hits a friendly piece or captures an enemy piece. But it's hard for a purely one-step-at-a-time generator to evaluate thing sequentially. I tried it by making each successive run of moves start with the original home address, so one can make a new generator that resets it's idea of 'blocked-ness' when it runs into that home value again. I'm sure there are more elegant ways that could be done, this was just a quick way to get it working:

def slide(addresses, our_color):
    clipped = (m for m  in addresses if clip(m))
    stopped = False
    home = None
    for addr in clipped:
        if home is None:
            home = addr
        if addr == home:
            stopped = False
            continue
        if not stopped:
            next_square = board.get(addr)
            stopped = next_square is not None
            if not stopped or next_square[0] != our_color:
                yield addr

so now when you grab a piece and call slide() it will yield all the moves along its possible vectors, clipped to the limits of the board, and including possible captures (it does not however actually care those moves are captures -- it just says they're legal moves).

future work

I put a rough-and-ready approximation of a way it could be done into [this gist](https://gist.github.com/theodox/ea402db04aedcff607cd816843f3887d.

It's not nearly as fully-featured as yours and I think it's probably got a hidden logic flaw -- white wins by a very lopsided 8:1 margin or so However it does generate about 2,000 games a minute, averaging around 65 turns each, which suggests that even with a lot more careful attention to detail it should be possible to generate a lot of data without going to C++ code or compiled extensions.

There are several bits I didn't try to handle: the en-passant rule and castling, for example, and there's no algorithm for a draw. Those are all good places for tinkering. More importantly, I also brute-forced the calculations for checkmate by basically unioning all of the moves for each side after each turn. A more selective update of the different zones-of-death would probably double the throughput. The way I happened to try it is not really the point; it's mostly useful to show that you should be able to shave an order of magnitude or more off the times by paying close attention to limiting memory moves and object creation.

Answer 2

If you are mainly looking for performance while sticking with python, you should check out python-chess. It's board class has attributes like board.legal_moves and functions like board.is_game_over() which use bitboards for their low-level storage. It won't be as fast as C, but it will be a ton easier to use.