Question about minimax

General
#1

Hi,

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 ?

3 Likes
#2

Hi,

The biggest optimization I’ve found for tree like searches is to store only a move in a Node, not the whole game state and performing the simulations from initial turn state with moves from all parents and grandparents all the way to the root. This way the copying/passing of game states is eliminated and only the simulation time is increased slightly.

You could read about Monte Carlo Tree Search, MCTS, it builds the tree asymmetrically and works well with big branching factor.

No matter what algorithm is used, reducing the branching factor is always a good idea, some moves may be better from others in general. Of course all moves have potential for future outcomes, but for competitive programming you could risk that potential.

Another big optimization is to precompute things as much as possible. As you mention it’s good idea to precompute the game tree, but for games bigger than Tic-Tac-Toe it’s not very possible. But you could precompute all kind of things, like terminal test for state, outcome of a given move…

Profile your code, you’ll be surprised where you have bottlenecks.

The reading resources I’m using are the technical papers, they have really good experiments and guidelines. Also every (general) book/course for algorithms could help.

2 Likes
#3

A half way measure to building the whole tree is to instantiate a bunch of nodes that you store in a pool. Whenever you need one, take it from the pool. And return those that have become useless at the end of each turn (or not, depending on how memory efficient you want to be).
Essentially it allows you to frontload the cost of allocation during the first turn, which often has a generous timer, and avoid it during the next turns that have a stricter timer.

3 Likes
#4

Minimax is widely used on CG bots.
Use C++, or maybe C#/Java. Other languages aren’t fast enough for 50ms. On C#/Java try to create all objects at turn 0 (you have 1000ms on turn 0), then use some lists to keep track of assigned/free objects per class… Avoid creating objects on turns as much as possible, to avoid Garbage Collection.

Turn time starts just after you read the first input for the turn, try to get an accurate timer.

For C++ put these pragmas at the start of the code:

#pragma GCC optimize(“O3”,“unroll-loops”,“omit-frame-pointer”,“inline”)
#pragma GCC option(“arch=native”,“tune=native”)
#pragma GCC target(“sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2”)

It enables optimizations. You won’t get debug info but you don’t need it on submits.

Minimax have different versions, some of them prune most than others. It’s about testing them.