Using Response Functions to Measure Strategy Strength

Trevor Davis, Neil Burch, and Michael Bowling. Using Response Functions to Measure Strategy Strength. In Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI), pp. 630–636, 2014.




Extensive-form games are a powerful tool for representing complex multi-agent interactions. Nash equilibrium strategies are commonly used as a solution concept for extensive-form games, but many games are too large for the computation of Nash equilibria to be tractable. In these large games, exploitability has traditionally been used to measure deviation from Nash equilibrium, and thus strategies are aimed to achieve minimal exploitability. However, while exploitability measures a strategy's worst-case performance, it fails to capture how likely that worst-case is to be observed in practice. In fact, empirical evidence has shown that a less exploitable strategy can perform worse than a more exploitable strategy in one-on-one play against a variety of opponents. In this work, we propose a class of response functions that can be used to measure the strength of a strategy. We prove that standard no-regret algorithms can be used to learn optimal strategies for a scenario where the opponent uses one of these response functions. We demonstrate the effectiveness of this technique in Leduc poker against opponents that use the UCT Monte Carlo tree search algorithm.


  Title = "Using Response Functions to Measure Strategy Strength",
  Author = "Trevor Davis and Neil Burch and Michael Bowling",
  Booktitle = "Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI)",
  Pages = "630--636",
  Year = "2014",
  AcceptRate = "28\%",
  AcceptNumbers = "398 of 1406"

Generated by (written by Patrick Riley) on Fri Feb 13, 2015 15:54:26