Using response functions to measure strategy strength
- Trevor Davis
- Neil Burch, Department of Computing Science, University of Alberta
- Michael Bowling, University of Alberta
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 Hold’em against opponents that use the UCT Monte Carlo tree search algorithm.
Citation
T. Davis, N. Burch, M. Bowling. "Using response functions to measure strategy strength". National Conference on Artificial Intelligence (AAAI), (ed: Carla E. Brodley, Peter Stone), pp 630-636, October 2014.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Davis+al:AAAI14,
author = {Trevor Davis and Neil Burch and Michael Bowling},
title = {Using response functions to measure strategy strength},
Editor = {Carla E. Brodley, Peter Stone},
Pages = {630-636},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2014,
}Last Updated: October 29, 2020Submitted by Sabina P
