0

I am creating a chess engine and have some trouble getting it to stop calculating from its recursive negamax (minimax) framework. I want it to return best move so far when a given time limit is up. Here is how my code is structured:

# Initial call
move = ai_make_move()

# AI function with iterative deepending
def ai_make_move():
    best_move_so_far = []

    # Here I init the time
    start_time = time.time()

    # Iterative deepening to go deeper and deeper into tree
    for depth in range(1, max_depth):
        move = negamax(alpha, beta, depth...)
        best_move_so_far.append(move)

# Negamax function
def negamax(alpha, beta, depth....):
    
    # Here I want to make the time check...
    if time.time() - start_time >= time_limit:
        # Return None to ai_make_move() or return best_move_so_far[-1] to initial call
    
    for move in possible moves:
        make_move()
        negamax(-beta, -alpha)
        unmake_move()

    # ...

The problem I have is to stop when time is up in the negamax function and return None to ai_make_move() function to be able to do something like if not move: return best_move_so_far[-1]. Or to return that immediately to the initial call.

Is it possible to stop a recursive call like this? Right now if I return something it will just return to the previous call of negamax and so on, which will give an error.

Eli
  • 156
  • 8
  • You can take different approaches, one would be to run the function as a separate thread or process and have it communicate results as its going and killing it after a set amount of time has expired. However, a simpler solution would probably be to check for expiration at the start of each iteration and simply return from the function once it's expired. – Grismar Jan 05 '21 at 07:20
  • The 2nd approach is how I am currently doing it, to return from the ai_make_move function when time is up. The issue is that it can start calculating when time is almost up, and then it takes double time to get next move. This due to the exponential nature of the code. I want to return exactly at say 5 seconds of thinking time. – Eli Jan 05 '21 at 07:24
  • Does this answer your question? [Timeout on a function call](https://stackoverflow.com/questions/492519/timeout-on-a-function-call) – Grismar Jan 05 '21 at 07:27
  • @Eli the issue isn't clear; isn't the return working inside the time check condition? – Abhinav Mathur Jan 05 '21 at 10:54
  • @AbhinavMathur, the function is recursive, hence it will not return to the initial function call, but to the previous negamax call until it finishes the recursive loop. I want to break it at exactly that time instead. – Eli Jan 05 '21 at 10:58

2 Answers2

0

You should add a timeout to your function, which is pretty well explained here: Timeout on a function call

Frederik Bode
  • 2,632
  • 1
  • 10
  • 17
  • Maybe, but I am not smart enough to find out how to place these things in my functions. I am running on Windows btw, so I guess I need to use the multiprocessing thing. I just can't wrap my head around how to place these things. Could you be very kind and update your answer with how it would look in this case? – Eli Jan 05 '21 at 08:35
0

You should be able to just return the score of the current board, just like the game ended.

if time.time() - start_time >= time_limit:
    return evaluation(board)

Obivously this dosen't stop the function immediately since the values have to go back the tree, but it shhould be pretty fast. Also why would you need a max_depth and a time_limit?

Honn
  • 737
  • 2
  • 18
  • If I want to search for max 2 deep then I will set max_depth to 2 and it will return after that. Basically to be able to control how deep it searches. And the time limit is to stop at a certain time so it doesn't go on forever if max_depth is set to something large. Unfortunately that statement doesn't work and it seems to be returning an arbitrary move that it played at that point in time. However, it stops at the correct time which is always something :) – Eli Jan 09 '21 at 15:00