Name
Abstract | ||
|---|---|---|
At AAAI'07, Zinkevich, Bowling and Burch introduced the Range of Skill measure of a two-player game and used it as a parameter in the analysis of the running time of an algo- rithm for finding approximate solutions to such games. They suggested that the Range of Skill of a typical natural game is a small number, but only gave heuristic arguments for this. In this paper, we provide the first methods for rigorously es- timating the Range of Skill of a given game. We provide some general, asymptotic bounds that imply that the Range of Skill of a perfectly balanced game tree is almost exponen- tial in its size (and doubly exponential in its depth). We also provide techniques that yield concrete bounds for unbalanced game trees and apply these to estimate the Range of Skill of Tic-Tac-Toe and Heads-Up Limit Texas Hold'em Poker. In particular, we show that the Range of Skill of Tic-Tac-Toe is more than 100,000. |
Year | Venue | Keywords |
|---|---|---|
2008 | AAAI | em poker,asymptotic bound,heads-up limit texas,unbalanced game tree,approximate solution,two-player game,typical natural game,balanced game tree,skill measure,concrete bound |
Field | DocType | Citations |
Small number,Mathematical optimization,Heuristic,Exponential function,Computer science,Artificial intelligence,Game tree,Machine learning | Conference | 2 |
PageRank | References | Authors |
0.36 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Dueholm Hansen | 1 | 161 | 13.77 |
| Peter Bro Miltersen | 2 | 1146 | 94.49 |
| Troels Bjerre Sørensen | 3 | 181 | 18.08 |