Implementing Iterative Deepening with minimax algorithm with alpha beta pruning PYTHON

Question

I have implemented a NegaMax algorithm (which is just a shorter version of minimax algorithm) with alpha beta pruning . Now I want to implement Iterative Deepening so that I can find a best move for every depth and then reorder the the nodes under the tree based on the scores of the previous layers so that my alphabeta pruning works more efficiently.

Here's what I have done so far:

InitialDEPTH = 1

def findBestMove(gs, validMoves):
    global nextMove
    global InitialDEPTH 
    nextMove = None
    
    for d in range(2):
        CurrentDEPTH = InitialDEPTH + d
        findMoveNegaMaxAlphaBeta(gs, validMoves, CurrentDEPTH, -CHECKMATE, CHECKMATE, 1 if gs.whiteToMove else -1)
    
    return nextMove

Here gs is the gamestate that changes with everymove and contains all the information about the game at t hat point like if castling is possible or whether there is a enpassant move possible. My negamax algorithm looks like this :

def findMoveNegaMaxAlphaBeta(gs, validMoves, depth, alpha, beta, turnMultiplier):
    global nextMove
    if depth == 0 :
       return turnMultiplier * scoreBoard(gs)    

    maxScore = -CHECKMATE

    # I have a felling i need to add some code here to make it work
    for move in validMoves :
        gs.makeMove(move)
        nextMoves = gs.getValidMoves()
        score = -findMoveNegaMaxAlphaBeta(gs, nextMoves, depth - 1 , -beta, -alpha, -turnMultiplier)
        if score > maxScore:
            maxScore = score
            if depth == DEPTH :
                nextMove = move
        gs.undoMove() 
        if maxScore > alpha:   # This is were pruning happens
            alpha = maxScore
        if alpha >= beta :
            break    

    return maxScore

How can I add the time constraint function to this code so that it only returns the best move when the the mentioned time gets over and not before that.

Also how can I reorder the nodes after each depth for efficient pruning in the next depth. I have written some sort of function for that , but I do not know how to implement this. The function that I wrote :

def sorting(move):
    gs.makeMove(move)
    score = scoreBoard(gs)
    gs.undoMove()

    return turnMultiplier * score
validMoves.sort(key = sorting)

user_12053079 · Answer

As I see it you have 2 questions which I will try to answer:

How can I add the time constraint function to this code so that it only returns the best move when the the mentioned time gets over and not before that.

So you want to search for a certain number of seconds each move instead of searching for a specific depth? This is very easy to implement, all you have to do is make the iterative deepening go to some large depth and then compare the current time with the search start time each x number of nodes. Something like this:

import time

start_time = time.time()
move_time = 5  # 5 seconds per move
for depth in range(100):
    ...
    score, move = negamax()
    
    # Only save move if you haven't aborted the search at current depth due to time out.
    if move:
        best_score, best_move = score, move

def negamax():
    if time.time() - start_time > move_time:
        return None, None


    ....
    return score, move

Also how can I reorder the nodes after each depth for efficient pruning in the next depth.

I have no idea what you are trying to do with your current sorting. Here is what the negamax framework usually looks like:

def negamax():
    if depth = 0:
        return evaluation()

    valid_moves = gs.get_valid_moves()

    # Here you sort the moves
    sorted_valid_moves = sort(valid_moves)

    for move in sorted_valid_moves():
        gs.make_move()
        score = -negamax(...)
        gs.unmake_move()

You can sort the moves based on several criterias, you can read more about how to implement each of them here.

Implementing Iterative Deepening with minimax algorithm with alpha beta pruning PYTHON

1 Answers