Krdytkyu

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): https://github.com/basvdvelden/ChessAI/tree/master

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

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.