How to deal with huge branching factors in real-time?

Question

Some time ago playing chess was challenging for algorithms, then Go game which is vastly more complex than compared to chess.

How about playing RTS game which have enormous branching factors limited by its time and space (like deciding what to do next)? What are the successful approaches to such problems?

Answer 1

As you mentioned in the question, you cannot solve all problems with decision trees. Decision trees usually works well in a turn-based game with a good heuristic function, but in RTS games takes a different approach.

In the case of a very complex RTS game, one could implemented a rule-based AI. For example

• given it is the early game use all units to scout for resources
• if a certain criteria is met build the base a certain way
• if another criteria is met build an army
• if the army is big enough, attack
• if being attacked by the enemy, bring the units back to the base to defend

Each of these rules could implement various other AI technique, for example use A-star to find the optimal path between a unit's current location and destination.

Further optimization could be done by "grouping" similar units to act like one unit. e.g. calculate the path for the entire group instead of each individual unit.

You could also add finer grained rules, like if enemy is a certain distance from a unit, move closer and attack or retreat to the base (depending on health, ammo, abilities, etc).

The benefit of this approach is that a rule-based system executes very fast as no training or decision trees are necessary and this frees up a lot of system resources for visuals like physics and graphics.

The disadvantage is that if the rule system is not complex enough, the player will easily recognize the pattern and the game will become predictable and boring. You will also notice that the more different units you add to the game, the exponentially more complex the rule system becomes as you have to cater and test interaction between each type of unit in the game otherwise players might find a weakness in the game design and exploit to complete missions in ways it was not designed to be completed.

One of the reasons why multi-player games are so popular is that you do not play against set rules, but against creative people who have the ability to comes up with new strategies you had never seen before.