Rolling Horizon Coevolutionary Planning for Two-Player Video Games
This work addresses the problem of real-time decision-making for AI in two-player video games, representing an incremental extension of single-player methods.
The paper tackles decision-making in two-player real-time video games by extending rolling horizon evolutionary planning to handle multiple players, using co-evolution of action sequences for each player. It shows promising results in comparisons with other general video game AI algorithms on a two-player space battle game.
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.