General self-motivation and strategy identification: Case studies based on Sokoban and Pac-Man

Tom Anthony, D. Polani, C.L. Nehaniv

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)
145 Downloads (Pure)


In this paper, we use empowerment, a recently introduced biologically inspired measure, to allow an AI player to assign utility values to potential future states within a previously unencountered game without requiring explicit specification of goal states. We further introduce strategic affinity, a method of grouping action sequences together to form "strategies," by examining the overlap in the sets of potential future states following each such action sequence. We also demonstrate an information-theoretic method of predicting future utility. Combining these methods, we extend empowerment to soft-horizon empowerment which enables the player to select a repertoire of action sequences that aim to maintain anticipated utility. We show how this method provides a proto-heuristic for nonterminal states prior to specifying concrete game goals, and propose it as a principled candidate model for "intuitive" strategy selection, in line with other recent work on "self-motivated agent behavior." We demonstrate that the technique, despite being generically defined independently of scenario, performs quite well in relatively disparate scenarios, such as a Sokoban-inspired box-pushing scenario and in a Pac-Man-inspired predator game, suggesting novel and principle-based candidate routes toward more general game-playing algorithms.

Original languageEnglish
Article number6687219
Pages (from-to)1-17
Number of pages17
JournalIEEE Transactions on Computational Intelligence and AI in Games
Issue number1
Publication statusPublished - 18 Dec 2013


  • Artificial intelligence (AI)
  • games
  • information theory


Dive into the research topics of 'General self-motivation and strategy identification: Case studies based on Sokoban and Pac-Man'. Together they form a unique fingerprint.

Cite this