Conference Proceedings Or Journal
 

Adversarial Policy Switching with Application to RTS Games

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/conference_proceedings_or_journals/n870zs129

Descriptions

Attribute NameValues
Alternative Title
Creator
Abstract
  • Complex games such as RTS games are naturally formalized as Markov games. Given a Markov game, it is often possible to hand-code or learn a set of policies that capture the diversity of possible strategies. It is also often possible to hand-code or learn an abstract simulator of the game that can estimate the outcome of playing two strategies against one another from any state. We consider how to use such policy sets and simulators to make decisions in large Markov games. Prior work has considered the problem using an approach we call minimax policy switching. At each decision epoch, all policy pairs are simulated against each other from the current state, and the minimax policy is chosen and used to select actions until the next decision epoch. While intuitively appealing, we show that this switching policy can have arbitrarily poor worst case performance. In response, we describe a modified algorithm, monotone policy switching, whose worst case performance, under certain conditions, is provably no worse than the minimax fixed policy in the set. We evaluate these switching policies in both a simulated RTS game and the real game Wargus. The results show the effectiveness of policy switching when the simulator is accurate, and also highlight challenges in the face of inaccurate simulations.
  • This is an author's manuscript version. The published article is copyrighted by The AAAI Press.The published version is available at http://www.aaai.org/ocs/index.php/AIIDE/AIIDE12/paper/view/5540.
  • KEYWORDS: Adversarial strategy, Real-Time Strategy (RTS) games, Game strategies, Minimax policy switching, Computer games, Markov games
Resource Type
Date Available
Date Issued
Citation
  • King, B. Fern, A. & J. Hostetler (2012). "Adversarial policy switching with application to RTS games". AAAI Conference. on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2012) Workshop on Artificial Intelligence in Adversarial Real-time Games. AAAI Technical Report WS-12-15.
Conference Name
Academic Affiliation
Series
Rights Statement
Funding Statement (additional comments about funding)
  • This work was funded in part by NSF grant IIS-0905678 and by ARO grant W911NF-08-1-0242. Jesse Hostetler was supported in part by a scholarship from the ARCS Foundation of Portland, Oregon.
Publisher
Peer Reviewed
Language
Replaces

Relationships

Parents:

This work has no parents.

Items