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?