In Practice
In practice, there is no one-size-fits-all solution for AI problems. Generally, some combination of techniques is required.
Starcraft
Starcraft is hard for AI because:
- adversarial
- long horizon
- partially observable (fog-of-war)
- realtime (i.e. 24fps, one action per frame)
- huge branching factor
- concurrent (i.e. players move simultaneously)
- resource-rich
There is no single algorithm (e.g. minimax) that will solve it off-the-shelf.
The Berkeley Overmind won AIIDE 2010 (a Starcraft AI competition). It used:
- search: for path planning for troops
- CSPs: for base layout (i.e. buildings/facilities)
- minimax: for targeting of opponent's troops and facilities
- reinforcement learning (potential fields): for micro control (i.e. troop control)
- inference: for tracking opponent's units
- scheduling: for managing/prioritizing resources
- hierarchical control: high-level to low-level plans
References