Slow chess bot, need to go faster

I have created a chess bot using minimax and alpha beta pruning, along it I have also created a GUI. But my bot can't go very deep before becoming extremely slow. Already in depth 4 it can take up to 40-50 seconds to find a move.

The algorithm looks like this:

def minimax(depth,board, alpha, beta, is_max):
    if depth == 0:
        return evaluation(board)
    leg_moves = board.legal_moves
    if is_max:
        value = -9999
        for i_move in leg_moves:
            move = chess.Move.from_uci(str(i_move))
            board.push(move)
            value = max(value, minimax(depth - 1, board, alpha, beta, False))
            board.pop()
            alpha = max(alpha, value)
            if beta <= alpha:
                return value
        return value
    else:
        value = 9999
        for i_move in leg_moves:
            move = chess.Move.from_uci(str(i_move))
            board.push(move)
            value = min(value, minimax(depth - 1, board, alpha, beta, True))
            board.pop()
            beta = min(beta, value)
            if(beta <= alpha):
                return value
        return value

To summarize, how do I make it faster?

Implementing a Negamax function instead of Minimax will make future efficiency implementations much easier as a start, it will also make the code look cleaner:

def negamax(depth, board, alpha, beta, color):
    if depth == 0:
        return evaluation(board)
    leg_moves = board.legal_moves
    for i_move in leg_moves:
        move = chess.Move.from_uci(str(i_move))
        board.push(move)
        value = -negamax(depth - 1, board, -beta, -alpha, -color)
        board.pop()
        alpha = max(alpha, value)
        if beta <= alpha:
            return value
     return value

Then you might want to look into concepts such as sorting the moves before going into the recursive function, since you will get a beta cutoff much faster that way and not having to look through as many moves. Then you can also implement for example a transposition table (with iterative deepening), null moves and late move reduction.

You probably also want to look at your move generation and see if you can make it any faster. For example, what board representation do you use?

I have made a chess engine in Python which is not at all top notch. It goes to depth 6 in about 15 seconds and you can find the code here for inspiration: Affinity Chess. It uses a 1D board representation, but a bitboard representation would be even faster.

I would also highly recommend looking at www.chessprogramming.org, there is lots of really nice information there.