I think I’m missing out something about minimax algorithm.
I found the exercices about it in the training section very easy, but when I try to implement it for bot battle, I always get stuck by the computation time.
I managed to implement it for a few games, my bot easily passes the first leagues so I feel like my algorithm work, but I never managed to go beyond depth 2 or 3 without running into a timeout.
I feel like a minimax algorithm with depth 2 or 3 is still pretty dumb, and indeed, my handcrafted algorithmic solution always beats my minimax ( For example in dot&boxes, my minimax was 108th when my basic algorithmic solution is 14th ). So I think I’m doing something wrong, but when I lookup some research, it seems that this algorithm is supposed to take time.
I use alpha beta running and memoization but it’s clearly not enough
So my questions are :
- Is it normal, and minimax algorithm is not optimised for Codingame bots battle ?
- Is there other algorithms I should know about to reduce the branching factor ?
- Am I suppose to compute the game tree before starting the game so my minimax can be more efficient ? I feel like there’s not enough space nor time for that either but I haven’t tried yet
In general, do you have some reading recommendation about game theory algorithms and when/how to use them in real life example that go beyond what can be found on Wikipedia or equivalent ?