0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Commented Nov 4, 2020 at 16:16

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.