pursuit-evasion games

Pursuit-evasion games model a predator chasing prey, a missile chasing an aircraft, or the like. Unlike most other games discussed here, the players may have to make continuous decisions, for example deciding on a real-valued turn angle at every moment in time. So these games call for different techniques than more familiar ones.

Cliff and Miller

CoEvolution of Neural Networks for Control of Pursuit and Evasion (PDF)
Work by Dave Cliff and Geoffrey Miller on using genetic algorithms to learn a pursuit-evasion game. They have animated movies of some of the learned strategies in action. Some papers mentioned are online.

- Co-evolution of pursuit and evasion I: Biological and game-theoretic foundations (1994, arXiv), by Miller and Cliff. Nice overviews of animal pursuit and evasion, game theory, and related work.
- Co-evolution of pursuit and evasion II: Simulation and model results (1996 PDF), by Cliff and Miller, with their own results.
- Tracking the Red Queen: Measurements of adaptive progress in co-evolutionary simulations (1995 PDF), by Cliff and Miller. How to tell whether you're making progress when you have no external standard.

papers

Advantage updating applied to a differential game (1994, 10 pages)
Mance Harmon, Leemon Baird and A. Harry Klopf
Postscript, from here. Also available as a web page. The residual-gradient form of advantage updating is applied to a missile-aircraft game, and compared to Q-learning.

Reinforcement learning applied to a differential game (1995, 28 pages)
Mance Harmon, Leemon Baird and A. Harry Klopf
Postscript, from here. Also available as a web page. Similar to the above paper, with more details.

Residual advantage learning applied to a differential game (1996, 6 pages)
Mance Harmon, Leemon Baird and A. Harry Klopf
Postscript, from here. Also available as a web page. Similar to the above paper.

Multi-player residual advantage learning with general function approximation (1996, 12 pages)
Mance Harmon and Leemon Baird
Postscript, from here. Proposes advantage learning, an improvement over advantage updating.

Competition, coevolution and the game of tag (1994, 11 pages)
Craig W. Reynolds
Web page with abstract and links to the full paper. Simple simulated vehicles learn to play tag by genetic programming.

Combining genetic algorithms and memory based reasoning in pursuit games (1995, 8 pages)
John W. Sheppard and Steven L. Salzberg
Postscript. Using a genetic algorithm to jumpstart a nearest-neighbor algorithm.

Memory based learning of pursuit games (1995, 29 pages)
John W. Sheppard and Steven L. Salzberg
Postscript. Similar to the above paper. Also considers Q-learning.

A teaching strategy for memory-based control (1995, 28 pages)
John W. Sheppard and Steven L. Salzberg
Postscript. A journal version of the above paper. I found it the clearest of the three Sheppard-Salzberg papers.