Predicting remaining runtime for minimax algorithm with alpha-beta-pruning

Question

Problem

I am trying to solve a perfekt information zero-sum game (like tick-tack-toe or chess) using a negamax algorithm with alpha-beta-pruning. The goal is to proof wheter one player can force a win or draw. This means that there is no depth-limit but the algorithm always evaluates the gametree until there is a win/draw.

I spent multiple weeks optimizing my code to my specific game and got it down to a runtime of several days I would say. But there lies the problem:

Because of the alpha-beta-pruning the runtime of the minimax-algorithm is highly unpredictable. I can't tell wheter it will be done in the next 5 minutes or run for 5 more weeks until I actually simulated it. I would love to be able to predict the remaining runtime and not be off by several orders of magnitude.

What I tried so far

I am recording the results of all sub- and subsub-branches up to 5*sub-branches and the time it took my machine to simulate them. Then I just assume that positions on the same level take the same time to evaluate and call it a day. These predictions are sometimes off by a factor of 10 or more.

I also looked at recorded data to see wheter my assumtion holds. The time needed to evaluate a 5*sub-branch varied between 0.01s to as much as 180s. Thats why my predictions where off. Who would have gessed.

My Question

As I imagine this would apply to all implementations of minimax:

1. Are there more sophisticated algorithm out there to accuratly predict the remaining runtime of a minimax-algorithm with alpha-beta-pruning? Or is minimax just unpredictable by design?

2. If so how do they work?

Answer 1

I have spent a lot of time with Negamax algorithms which I highly suggest that you switch over to. It will give the same results as Minimax, but is much easier to debug and optimize further since it is just half the code.

I have no clue about the game you are trying to solve, but if it is even the slightliest complicated I assume it won't be possible without a super computer. To answer your questions though:

1. Minimax with alpha-beta pruning relies highly on the order of which you try your moves (to use board game terms). You want to try the best moves first, this is done in chess by ordering the possible moves function with e.g. capture moves higher up than castling.

   You can also optimize the algorithm much much more with different techniques depending on what you are trying to solve. For example transposition tables if the same position can occur in another branch.

2. We need to know more about the game you are trying to solve to know what algorithm can work best.

Final words: If you want to get an idea of how long it will take to solve and how far you have gotten after some time, I suggest you use iterative deepending. This will also speed up your search, since you can try the best guesses from the previous iterations first and hence get faster beta cut offs in the next iteration:

for depth in range(1, inf):
    score = minimax(alpha, beta, depth....)
    time = elapsed_time()

Now you can print the elapsed time for each depth and see how far it gets in a certain period of time. This is also good to measuer if your optimizations are giving any results. Since the Minimax tree is getting exponentially larger for each depth you can get an idea on how much time the next depth will take you.

So if you know around how many moves it will take for a win/draw/loss you can pretty easily estimate whether it will be possible or not through this technique.

Hope I make myself clear, English is not my native language :) Feel free ask in the comments if something is not clear.