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.
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.