On Range of Skill

Thomas Dueholm Hansen; Peter Bro Miltersen; Troels Bjerre Sørensen

On Range of Skill

Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

2 Citations (Scopus)

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 algorithm 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 estimating 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 exponential 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.

Original language	English
Title of host publication	Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence : Constraints, Satisfiability, and Search
Number of pages	6
Publisher	AAAI Press
Publication date	2008
Pages	277-282
ISBN (Print)	978-1-57735-368-3
Publication status	Published - 2008
Event	AAAI Conference on Artificial Intelligence - Chicago, Illinois, United States Duration: 13 Jul 2008 → 17 Jul 2008 Conference number: 23

Conference

Conference	AAAI Conference on Artificial Intelligence
Number	23
Country/Territory	United States
City	Chicago, Illinois
Period	13/07/2008 → 17/07/2008

Keywords

Game Playing
Computational Complexity

Cite this

@inproceedings{e5fb95401ced11ddbe51000ea68e967b,

title = "On Range of Skill",

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 algorithm 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 estimating 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 exponential 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.",

keywords = "Game Playing, Computational Complexity",

author = "Hansen, {Thomas Dueholm} and Miltersen, {Peter Bro} and S{\o}rensen, {Troels Bjerre}",

year = "2008",

language = "English",

isbn = "978-1-57735-368-3",

pages = "277--282",

booktitle = "Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

note = "AAAI Conference on Artificial Intelligence ; Conference date: 13-07-2008 Through 17-07-2008",

}

TY - GEN

T1 - On Range of Skill

AU - Hansen, Thomas Dueholm

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

N1 - Conference code: 23

PY - 2008

Y1 - 2008

N2 - 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 algorithm 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 estimating 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 exponential 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.

AB - 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 algorithm 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 estimating 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 exponential 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.

KW - Game Playing

KW - Computational Complexity

M3 - Article in proceedings

SN - 978-1-57735-368-3

SP - 277

EP - 282

BT - Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence

PB - AAAI Press

T2 - AAAI Conference on Artificial Intelligence

Y2 - 13 July 2008 through 17 July 2008

ER -

On Range of Skill

Abstract

Conference

Keywords

Fingerprint

Cite this