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

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

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.

Originalsprog	Engelsk
Titel	Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence : Constraints, Satisfiability, and Search
Antal sider	6
Forlag	AAAI Press
Publikationsdato	2008
Sider	277-282
ISBN (Trykt)	978-1-57735-368-3
Status	Udgivet - 2008
Begivenhed	AAAI Conference on Artificial Intelligence - Chicago, Illinois, USA Varighed: 13 jul. 2008 → 17 jul. 2008 Konferencens nummer: 23

Konference

Konference	AAAI Conference on Artificial Intelligence
Nummer	23
Land/Område	USA
By	Chicago, Illinois
Periode	13/07/2008 → 17/07/2008

Citationsformater

@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

Konference

Fingeraftryk

Citationsformater