pmariglia
commented
3 years ago Definitely not a bug.
I think it's safe to say that using the minimax algorithm, a search depth of 2 is the most you're going to get when using this bot unless you have an insane supercomputer - the engine is just too slow. The exponential growth hurts much more than you may realize.
Just to give an idea of the amount of operations required for each search depth. Let's assume 4 moves and 5 switches per player, 9 decisions total. This means 81 "transpositions" to calculate (alpha-beta pruning exists and reduces this - but lets just use this as an example) Let's also assume each transposition takes 0.0001s to calculate each.
| Search Depth | Number of Transpositions | Total Time (seconds) |
|---|---|---|
| 1 | 81^1 = 81 | 81 * 0.0001 = 0.0081 |
| 2 | 81^2 = 6561 | 6561 * 0.0001 = 0.6561 |
| 3 | 81^3 = 531441 | 531441 * 0.0001 = 53.1441 |
As for this:
If not, perhaps the bot could detect when the timer is close to running out and reduce search depth at that point?
To use minimax properly, the entire calculation from 2 -> 3 needs to be done. So it could calculate for up to say ~10 seconds, but it wouldn't have enough information to make a better decision that if it just stopped at search depth=2. A monte-carlo-tree-search style algorithm would benefit from calculating in this way.
Regardless, I have good reason to believe that adding an additional search depth would not seriously improve the performance of the minimax bot. I ran the minimax bots head-to-head, one searching to a depth of 2, the other searching to a depth of 3 for about 500 gen8randombattle games. It took a very long time, and in the end they were roughly equal in the number of wins.
I think to make a better Pokemon bot, a different algorithm entirely must be used.
rahidz
Not sure why, but the bot runs pretty much instantaneously at a search depth of 2, but when I change it to 3 in config.py, it bogs down to the point where within a few turns, it loses on time. I might be wrong, but this feels like a bug to me, even if the increase in time is exponential per search depth, going from 0-2 seconds per move to 100+ seconds seems excessive. If not, perhaps the bot could detect when the timer is close to running out and reduce search depth at that point?
This occurs regardless of battle_bot mode, and regardless of whether I run locally or on Docker.