  This paper describes a new algorithm for decision making in two-player
real-time video games. As with Monte Carlo Tree Search, the algorithm can be
used without heuristics and has been developed for use in general video game
AI. The approach is to extend recent work on rolling horizon evolutionary
planning, which has been shown to work well for single-player games, to two (or
in principle many) player games. To select an action the algorithm co-evolves
two (or in the general case N) populations, one for each player, where each
individual is a sequence of actions for the respective player. The fitness of
each individual is evaluated by playing it against a selection of
action-sequences from the opposing population. When choosing an action to take
in the game, the first action is chosen from the fittest member of the
population for that player. The new algorithm is compared with a number of
general video game AI algorithms on three variations of a two-player space
battle game, with promising results.
