# How to tell if a minimax search tree is computationally feasible using parallel computing

I am trying to apply the minimax algorithm to a game of Pokemon. This is a problem where the search tree is usually around 20 levels deep (number of turns) and each level has 9 or less branches (number of choices per turn). What I am wondering is if this is a computationally feasible problem using parallel computing? My idea for how to tackle it is to fork a new thread for the first n number of levels to break up the work.

If my math is correct this means that there will be 9^20 operations that need to be split up (technically it will be less since the number of choices per turn decrease as the game gets closer to the end). I was wondering if there is some sort of constant or general rule of thumb I can use to quickly estimate if this problem is computationally possible and worth pursuing or not?

The most ideal outcome would be if the computation can run in 2 minutes or less, but it isn't a requirement.

• Just out of curiosity, are you assuming the adversary's pokémon, moves and stats are known? (In which case I suppose the 9 choices are 4 possible moves + 5 possible pokémon swaps). Otherwise there are vastly many more than 9 possible choices to consider for the adversary as it is not a perfect information game. For example, before seing all 4 moves of one of his pokémon he might go for any possible move theoretically available to this pokémon for all you know. Nov 4 '20 at 16:16

Plainly, evaluating $$10^{19}$$ positions is not going to be feasible in 7200 seconds. But if you use alpha-beta to prune the search tree and have perfect move ordering you can get that down to around $$10^{10}$$, a number that looks much more reasonable given that chess engines on PC hardware can do a couple million nodes per second easily. Since alpha-beta is a serial algorithm, you'll have to do more than just naively divide the search tree among processors to reap its benefits, but there has been a great deal of research in this area: start here.
It's a straightforward Fermi estimate: if you spend one microsecond of CPU time on each node of the tree, and if you visit $$9^{20}$$ nodes of the tree, then the computation will take about $$9^{20} \times 10^{-6}$$ CPU-seconds. If you have 10 CPUs, divide by 10 to get the elapsed time. I'll let you plug that into a calculator and formulate the appropriate conclusion.