Abstract | ||
---|---|---|
In normal scenarios, computer scientists often consider the number of states in a game to capture the difficulty of learning an equilibrium. However, players do not see games in the same light: most consider Go or Chess to be more complex than Monopoly. In this paper, we discuss a new measure of game complexity that links existing state-of-the-art algorithms for computing approximate equilibria to a more human measure. In particular, we consider the range of skill in a game, i.e. how many different skill levels exist. We then modify existing techniques to design a new algorithm to compute approximate equilibria whose performance can be captured by this new measure. We use it to develop the first near Nash equilibrium for a four round abstraction of poker, and show that it would have been able to win handily the bankroll competition from last year's AAAI poker competition. |
Year | Venue | Keywords |
---|---|---|
2007 | AAAI | last year,aaai poker competition,new measure,nash equilibrium,game complexity,massive zero-sum game,different skill level,new algorithm,computer scientist,human measure,approximate equilibrium,state space,zero sum game |
Field | DocType | Citations |
Correlated equilibrium,Computer science,Best response,Algorithm,Equilibrium selection,Repeated game,Game theory,Normal-form game,Sequential game,Extensive-form game | Conference | 27 |
PageRank | References | Authors |
2.89 | 7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Zinkevich | 1 | 1893 | 160.99 |
Michael H. Bowling | 2 | 2460 | 205.07 |
Neil Burch | 3 | 373 | 29.51 |