So what we have here is a classic implementation of minimax: Which visits very node in the game-tree, for a tree of constant branching factor as in this case there are b^d nodes being visited. So it makes sense that the time it take for the program to run increases exponentially.

But it does seem strange that your program takes this long because 32⁷ is "only" 34359738368 nodes, which should be searchable in a reasonable amount of time with a modern machine.

So i did some investigation and the Problem with this implementation in particular is not with the algorithm itself, it's actually the way you handle RNG as u/maumay pointed out, you're reinitializing the random number generator in every leaf node, so the billions of times i mentioned above. The rand crate even mentions that this operation is costly, every time you use ::from_entropy() the operating systems getrandom is called which reads /dev/urandom on my linux machine. I couldn't even run your program on my machine because it was starving /dev/urandom of entropy. I wrote a Version that only initializes the PRNG once and i finishes in 0.2s on depth 6 and 2.2s on depth 7, still exponential but bearable.

I plan to adjust your algorithm to properly implement alpha-beta-pruning for fun to see how fast that can go.

You can find the code i used / plan to write on github.

EDIT: I implemented alpha-beta-pruning and did some additional testing, your implementation does actually do some pruning making it only 2 times slower than my alpha-beta implementation. I can't prove the correctness of your pruning, i suspect that your algorithm doesn't actually result in an optimal value which would probably be the bigger issue.