Optimizing chess engine using minimax

Question

I have developed a chess engine in python using minimax algorithm and i have also used Alpha-Beta Pruning to optimize it further. Currently i am searching to a depth of 4 which isnt a lot but it still takes 10 - 60 s to think of a move.

The main thing that slows down the program is iterating again and again. I first generate all possible moves in a deque.collection() and then i iterate through it once to validate it. Now i iterate through it once again to evaluate the moves and then compare them to get the best possible move. I am using for loops throughout this and the format of all possible moves is a collection(mainmoves) of collections(moves)

What can i do to optimize this and reduce the time taken to generate a move.

def minimaxRoot(depth,isMaximizing):
    global board
    possibleMoves = gen(False)
    bestMove = -math.inf
    bestMoveFinal = None
    for move in possibleMoves:
        orig = normperform(move)
        value = max(bestMove, minimax(depth - 1,not isMaximizing,-math.inf,math.inf))
        undo(move,orig)
        if value > bestMove:
            bestMove = value
            bestMoveFinal = move
    return bestMoveFinal

def minimax(depth,ismax,alpha,beta):
    global board
    if depth == 0:
        return calcpoints()
    maxeval = -math.inf
    mineval = math.inf
    if ismax == True:
        mainmoves = gen(False)
        if mainmoves == 'mate':
            return 8000
        for move in mainmoves:
            orig = normperform(move)
            eval = minimax(depth-1,False,alpha,beta)
            undo(move,orig)
            maxeval=max(eval,maxeval)
            alpha = max(alpha,eval)
            if beta <= alpha:
                break
        return maxeval
    elif ismax == False:
        mainmoves2 = gen(True)
        if mainmoves2 == 'mate':
            return 8000
        for move2 in mainmoves2:
            orig2 = normperform(move2)
            eval2 = minimax(depth-1,True,alpha,beta)
            undo(move2,orig2)
            mineval = min(mineval,eval2)
            if eval2 < beta:
                beta = eval2
            if beta <= alpha:
                break
        return mineval

Answer 1

I was attempting to do the same thing with Python, and here's what I did to make my engine search a board with a depth of 5 under about 30s.

• Cache the move generation. Use functools.lru_cache so the library won't have to generate moves repeatedly. This was the step that enabled my engine to skip from a depth of 4 to a depth of 5. Note that lru_cache uses hash tables to cache keys, but chess.Board isn't hashable by default. This can be fixed by using chess.Board.__hash__ = chess.polyglot.zobrist_hash however. In this way, you can cache the ordered move list to further improve its speed.
• Use Move Ordering, as @Momo mentioned. He/she did great reasoning and explanation so I'm not going through it all over again.
• Use Python chess library. I'm not sure if you're using it, but it provides a chess board model with decent speed. It also works with functools.lru_cache with the method mentioned above.
• Use Openings data and Openings searcher. You can use data here to make your engine use openings, which takes no time to calculate, while also providing better results for the early game.

You're probably just making this in Python for fun and experimentations, so I do encourage you to try this in Python first. But if this was for serious usage, you may want to implement this in C or C++, or use engines like Stockfish.

Well, that's about all. Hope it helps. ;)

Answer 2

There are two main issues which lead to your chess engines low search depth:

1. Firstly, you have no Move Ordering implemented. The time it takes for the search to complete is heavily dependent on the nodes it visits. I'd recommend you to count the number of nodes visited by your engine in every search iteration. You ideally should not compute all moves at once, or at least search those moves which have a high potential of becoming the best move first (e.g captures). That way you can increase the chance of an early beta cutoff. Move Ordering is crucial for the search algorithm. You can read more about Move Ordering here.
2. Python is not the best language to implement a high performing chess engine with. You would be better off with a compiled language like C or C++. Although there is one engine in Python called Sunfish which plays at arround 2000 ELO strength I think.