Aarhus University Seal / Aarhus Universitets segl

On Range of Skill

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
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 languageEnglish
Title of host publicationProceedings of the Twenty-Third AAAI Conference on Artificial Intelligence : Constraints, Satisfiability, and Search
Number of pages6
PublisherAAAI Press
Publication year2008
Pages277-282
ISBN (print)978-1-57735-368-3
Publication statusPublished - 2008
EventAAAI Conference on Artificial Intelligence - Chicago, Illinois, United States
Duration: 13 Jul 200817 Jul 2008
Conference number: 23

Conference

ConferenceAAAI Conference on Artificial Intelligence
Nummer23
LandUnited States
ByChicago, Illinois
Periode13/07/200817/07/2008

    Research areas

  • Game Playing, Computational Complexity

See relations at Aarhus University Citationformats

ID: 11264483