So I’m struggling with applying search algorithms with challenges that involve controlling more than one unit.
Most search algorithms I know are variations of the following:
Start with a root node representing the current game state.
Generate a list of all possible “moves”. (Moves in the context of a game like Code of Ice and Fire would be the combination of actions made in one turn).
Choose one of the possible moves - randomly or using some other heuristic.
Apply the move to the current node’s state and create a child node.
Loop steps 2 to 4 until some termination condition is reached, going up and down the game tree.
The problem I run into is with step 2. In a game like Code of Ice and Fire, the number of possible actions on any given turn is huge. On a typical turn you could build different structures on any number of different locations, train any number of different units on any number of different locations, move each of your units in 4 cardinal directions etc… AND you can do all that those actions in different order combinations. The number of possible “moves” is astronomical. Given the 50ms per turn time constraint, I sometimes can’t even generate the possible moves for a single node, never mind several branches. Is there a good way to deal with this problem?
When I read some post mortems by top players, they seem to manage to incorporate search algorithms into their strategy even for games like these but I haven’t gleaned enough information from them to understand how to deal with this problem. Any ideas?
Have you heard about Monte Carlo Tree Search (MCTS). This algorithm is known to work well with big branching factor.
Also it is always a good strategy to reduce the count of all possible moves from a given game state, very often not all moves are necessary.
One thing I’m doing very often is to store only the move in the tree Node, not the whole game state and when I need the state I simulate it(from the initial state) after gathering the moves from the root Node to the current one. This way a lot of memory is saved and the copying of the state is eliminated. It’s a bit more tedious to manage, but wherever I’ve used this strategy the performance gains are big.
I actually had MCTS in mind when I wrote the OP. I know it quite well.
So let’s talk and expand on your second suggestion:
I can see how this could help, in theory, but I have a hard time seeing how this could be applied correctly in practice. Could you give me a concrete example?
I have found that MCTS can do quite well, given CGs time constraints, with a branching factor in the low hundreds or under. But in some games the branching factor is in the thousands, if not tens of thousands, how do you get that down to a manageable level?
One idea that I have had and I think could work with MCTS is to simply always generate a random move during exploration, instead of generating all legal moves and then picking one at random.
It’s very game specific, you have to experiment a lot. Of course the more algorithms you implement, the better you estimate the important moves.
For example in Coders Strike Back you control two pods and for each pod you have to output target coordinates (x, y) and a thrust power between 0 and 200.
If you deicide to use the points on the map, for x you have 16 000 possibilities [0, 16 000), for y 9000 possibilities [0, 9 000), for the thrust 201 [0, 200], that’s per pod. This gives us 57888000000 branching factor/moves (if my math is correct (not to mention that x and y could be outside the map))
But a lot of those moves are redundant, since the pod may change its angle with maximum +/-18 degrees (a lot of moves will turn the pods with their maximum angle change). Using the angle sounds more optimistic. For the angle change you have 37 possibilities [-18, 18](output target point in the direction of the angle), for the thrust 201 [0, 200], that’s per pod. This gives us 14 874 branching factor/moves (if my math is correct)
A lot better, but still quite big factor. After many experiments, observing other players’ games, reading the forum… it turns out that small changes in the angle and the thrust are not very important. The most significant moves are when the pod doesn’t turn at all, turns +18 degrees or turns -18 degrees, that’re 3 possibilities for the angle [-18, 0, +18]. For the thrust it’s also most important when the pod doesn’t accelerates, uses half the maximum acceleration or the maximum acceleration, that’re 3 possibilities for the thrust [0, 100, 200], again that’s per pod. This gives us 18 branching factor/moves (if my math is correct) with which you could work normally.