The challenge of poker
Artificial IntelligencePublished 1 January 2002
Darse Billings, Aaron Davidson, Jonathan Schaeffer, Duane Szafron
Citations271
SJR quartileQ1
SJR score1.84
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The design considerations and architecture of the poker program Poki are described, which is a program capable of playing reasonably strong poker, but there remains considerable research to be done to play at world-class level.
Abstract
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect information, where multiple competing agents must deal with probabilistic knowledge, risk assessment, and possible deception, not unlike decisions made in the real world. Opponent modeling is another difficult problem in decision-making applications, and it is essential to achieving high performance in poker. This paper describes the design considerations and architecture of the poker program Poki. In addition to methods for hand evaluation and betting strategy, Poki uses learning techniques to construct statistical models of each opponent, and dynamically adapts to exploit observed patterns and tendencies. The result is a program capable of playing reasonably strong poker, but there remains considerable research to be done to play at a world-class level.
Keywords
PsychologyComputer ScienceEconomics, Econometrics and Finance
American Mathematical Society eBooksTheory of games and economic behavior
16,943 Citations2019Stephan Ramon Garcia, Steven J. Miller
Communications of the ACMTemporal difference learning and TD-Gammon
1,485 Citations1995Gerald Tesauro
The domain of complex board games such as Go, chess, checkers, Othello, and backgammon has been widely regarded as an ideal testing ground for exploring a variety of concepts and approaches in artificial intelligence and machine learning.
Elsevier eBooksUncertainty in Artificial Intelligence
1,434 Citations1992
Qualitative Probabilistic Reasoning and Cognitive models, Dempster-Shafer Theory in Knowledge Representation, and Possibility Theory: Semantics and Applications.
Machine intelligence and pattern recognitionUncertainty in Artificial Intelligence
423 Citations1990
Three ways are provided to settle the development of uncertainty, probability, fuzzy maths, gray theory and several ways about knowledge representation and treatment are summarized.
Machine intelligence and pattern recognitionSimulation Approaches to General Probabilistic Inference on Belief Networks
311 Citations1990Ross D. Shachter, Mark A. Peot
This paper investigates a family of “forward” Monte Carlo sampling techniques similar to Logic Sampling which appear to perform well even in some multiplyconnected networks with extreme conditional probabilities, and thus would be generally applicable.
Machine intelligence and pattern recognitionWeighing and Integrating Evidence for Stochastic Simulation in Bayesian Networks
273 Citations1990Robert Fung, Kuo‐Chu Chang
The evidence weighting mechanism, for augmenting the logic sampling stochastic simulation algorithm, and an enhancement to the basic algorithm which uses the evidential integration technique [Chin and Cooper, 1987].
International Joint Conference on Artificial IntelligenceFlexible learning of problem solving heuristics through adaptive search
206 Citations1983Stephen F. Smith
An operational prototype, constructed around a powerful adaptive search technique, is presented and applied to the problem of acquiring problem solving heuristics through experience, seeing that comparable levels of performance are achieved by the two systems, despite the latter's dependence on a considerable amount of domain specific knowledge for effective operation.
Artificial IntelligenceGeneralization learning techniques for automating the learning of heuristics
202 Citations1970D. A. Waterman
Procedures are developed which permit a problem-solving program employing heuristics in production rule form to learn to improve its performance by evaluating and modifying existingHeuristics and hypothesizing new ones, either during an explicit training process or during normal program operation.
Artificial IntelligenceThe B∗ tree search algorithm: A best-first proof procedure
188 Citations1979Hans Berliner
The algorithm, which is named B*, finds a proof that an arc at the root of a search tree is better than any other by attempting to find both the best arc atThe root and the simplest proof, in best-first fashion.
Artificial IntelligenceRepresentations and solutions for game-theoretic problems
184 Citations1997Daphne Koller, Avi Pfeffer
The Gala system is described, an implemented system that allows the specification and efficient solution of large imperfect information games and provides a new declarative language for compactly and naturally representing games by their rules.
Journal of Artificial Intelligence ResearchGIB: Imperfect Information in a Computationally Challenging Game
156 Citations2001Matthew L. Ginsberg
GIB, the program being described, involves five separate technical advances: partition search, the practical application of Monte Carlo techniques to realistic problems, a focus on achievable sets to solve problems inherent in the Monte Carlo approach, an extension of alpha-beta pruning from total orders to arbitrary distributive lattices, and the use of squeaky wheel optimization to find approximately optimal solutions to cardplay problems.
Artificial IntelligenceProgramming backgammon using self-teaching neural nets
155 Citations2002Gerald Tesauro
This paper views machine learning as a tool in a programmer's toolkit, and considers how it can be combined with other programming techniques to achieve and surpass world-class backgammon play.
Opponent modeling in poker
143 Citations1998Darse Billings, Denis Papp +2 more
Loki is described and evaluated, a poker program capable of observing its opponents, constructing opponent models and dynamically adapting its play to best exploit patterns in the opponents' play.
Artificial IntelligenceWorld-championship-caliber Scrabble☆☆SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the USA by Hasbro Inc., in Canada by Hasbro Canada Corporation, and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc.
124 Citations2002Brian Sheppard
MAVEN combines a selective move generator, simulations of likely game scenarios, and the B* algorithm to produce a world-championship-caliber Scrabble-playing program.
GIB: Steps Toward an Expert-Level Bridge-Playing Program
110 Citations1999Matthew L. Ginsberg
GIB, the first bridge-playing program to approach the level of a human expert, is described and the results of experiments comparing GIB to both human opponents and other programs are presented.
Incorporating opponent models into adversary search
73 Citations1996David Carmel, Shaul Markovitch
The M* algorithm is presented, a generalization of minimax that uses an arbitrary opponent model to simulate the opponent's search and the αβ* algorithm which returns the M* value of a tree while searching only necessary branches is presented.
Using probabilistic knowledge and simulation to play poker
69 Citations1999Darse Billings, Lourdes Peña‐Castillo +2 more
Progress is described in developing a high-performance pokerplaying program that introduces a new betting strategy that returns a probabilistic betting decision, a probability triple, that gives the likelihood of a fold, call or raise occurring in a given situation.
Communications of the ACMStudies in machine cognition using the game of poker
61 Citations1977Nicholas V. Findler
A progress report is presented of on-going research efforts concerning human decision making under uncertainty and risk and human problem solving and learning processes on the one hand, and machine learning, large scale programming systems, and novel programming techniques on the other.
Uncertainty in Artificial IntelligenceBayesian poker
52 Citations1999Kevin B. Korb, Ann E. Nicholson +1 more
This work describes the Bayesian Poker Program (BPP), which uses a Bayesian network to model the program's poker hand, the opponent's hand and the opponent’s playing behaviour conditioned upon the hand, and betting curves which govern play given a probability of winning.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)The B* tree search algorithm : a best-first proof procedure
51 Citations2018Berliner
National Conference on Artificial IntelligencePartition search
45 Citations1996Matthew L. Ginsberg
A new form of game search called partition search that incorporates dependency analysis, allowing substantial reductions in the portion of the tree that needs to be expanded, is introduced.
Lecture notes in computer scienceAbstraction Methods for Game Theoretic Poker
41 Citations2001Jiefu Shi, Michael L. Littman
This work examines several different medium-size poker variants and gives encouraging results for abstraction-based methods on these games, specifically variants of poker.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Using knowledge about the opponent in game-tree search
34 Citations1992Peter Jansen
This thesis investigates factors contributing to error both in the structure of game domains and in properties of the opponent's search strategy, and derives several interesting properties of random games, including difficulty-related characteristics.
Artificial IntelligenceMeasuring the performance potential of chess programs
34 Citations1990Hans Berliner, Gordon Goetsch +2 more
The data indicates that once a depth of “tactical sufficiency” is reached, a knowledgeable program can beat a significantly less knowledgeable one almost all of the time when both are searching to the same depth.
Dealing with imperfect information in poker
28 Citations1998Denis Papp
This thesis describes the implementation of a program that successfully handles all aspects of the game, and uses adaptive opponent modeling to improve performance.
Nova Science Publishers, Inc. eBooksLearning to play strong poker
24 Citations2001Darse Billings, Lourdes Peña‐Castillo +2 more
This chapter describes and evaluates the implicit and explicit learning in the poker program LOKI, a program capable of playing reasonably strong poker, but there remains considerable research to be done to play at a world-class level.
Using Selective-Sampling Simulations in Poker
19 Citations1999Darse Billings, Denis Papp +3 more
This paper describes work being done on developing a world-class poker-playing program and proposes selective sampling simulations as a general-purpose framework for building programs to achieve high performance in imperfect information games.
Operations ResearchComputation of Optimal Poker Strategies
9 Citations1977Norman Zadeh
Best strategies against perfect players (game-theoretic strategies) and against lesser players are presented and the percentage of time one should raise as a bluff before the draw is studied.