The NYT has a very interesting article today on AI and poker. A group of researchers in Alberta are using game theory to create automated ‘bots that can take on and beat most players. Now this was a little worrying for me; two months ago, I wrote a couple of rather confident posts suggesting that game theory wasn’t very helpful in solving complex and open-ended games like poker. Indeed, as Chad Orzel notes, human beings sometimes have difficulty in dealing with this sort of stuff too.
As it turns out though, the research project in Alberta reveals as much about the limits as the merits of game theory. The researchers have to make some radical simplifications in order for game theory to be useful at all, as they reveal in this report of their findings. First, they have to lop most of the branches of the “game tree” - the map of possible moves, responses and outcomes - in order to make the game tractable at all. They assume that all possible hands can be classified as falling into one of six or seven “buckets” of broadly equivalent hands. What’s more, their program doesn’t even start to try to analyse the play pattern of their opponent; instead, it assumes that the opposing player is also playing as if she was a computer program - i.e. that she’s employing optimal strategies. This means that their program isn’t going to be able to exploit patterns in its opponent’s game, although it will tend to win in the long run against players who follow “strictly dominated” strategies (i.e., who make really bone-headed mistakes). The authors ran the program against an expert poker player, who seems to have started to win consistently as soon as he stopped trying to exploit the program’s (non-existent) human weaknesses.
The researchers have made an interesting contribution - poker is a tough problem compared to, say, chess (which is much more rigid and deterministic, and therefore much more amenable to modelling). As they say, it’s a real achievement to have created a game theoretic poker player that isn’t completely outclassed by its human opponents. But there are good reasons to suspect that this line of research won’t go that much further - poker is too complex, and too dependent on subtle social interactions that are nearly impossible to model properly. The ‘bots don’t pose too much of a threat to you yet (as long as you remember not to draw to inside straights).
Hrrrmmmmm … I’d be more impressed if it was bridge.
I know little about game theory; does the fact that they have created this program based on a simplified game tree have any bearing on the possibility of creating a program that would work without the simplifications? — That is, would the same process be involved in building such a program, just a bit more painstaking; or is it a totally different problem?
This is a pretty narrow result. It applies to one variety of poker, and takes advantage of a game-tree reduction strategy whose broader applicability is difficult to ascertain, and the result is, in their words “not totally outclassed by the best human players.”
Do note carefully sections 5.2 and 5.3. It suggests to me that a major factor in their program’s success is its unorthodox playing style and inability to care how big the pot is. Given enough time, their grand master player was able to beat the computer, and they suggest that given enough time a really good player might always be able to do so. Of course, in the real world, the few thousand games you might need to work it out will probably leave you broke.
It suggests to me that the human factors still dominate poker, and that their code is taking unique advantage of that, not that they are genuinely modelling anything like an optimal strategy.
Jeremy
as far as I understand it, there are two basic simplifications here. One is simplifying the game tree - frankly I’m not really qualified to comment, but I’m not confident that the simplifications work. Second is the assumption that the computer plays against another opponent that tries to optimize strategies. This is rather problematic - and probably cripples the real life application of the approach to games with serious players. Like Scott, I have my doubts as to whether this approach can do a good job, but it’s like Johnson’s dog; it’s a wonder that it’s being done at all.
On-line poker is a fairly big business these days. There have been reports (though AFAIK no proof) that some people have built programs which can log into these on-line games and play. The theoretical goal is to have a ‘bot’ whose strategy will have a positive return, however small. Unlike a real player, a bot’s time is very cheap, and even if the bot nets only a dollar an hour, a few dozen bots playing 24 hours a day could generate a nice income.
Back in the days of IRC poker popularity, there were a fair number of bots that had been developed, many of which were quite profitable. While IRC poker wasn’t played for money, it certainly had much better play there than Yahoo or the free online rooms do these days, because the only people who knew about it / played on it were pretty serious about being good players.
I would be very surprised if there weren’t bots that played on online rooms.
À Gauche
Jeremy Alder
Amaravati
Anggarrgoon
Audhumlan Conspiracy
H.E. Baber
Philip Blosser
Paul Broderick
Matt Brown
Diana Buccafurni
Brandon Butler
Keith Burgess-Jackson
Certain Doubts
David Chalmers
Noam Chomsky
The Conservative Philosopher
Desert Landscapes
Denis Dutton
David Efird
Karl Elliott
David Estlund
Experimental Philosophy
Fake Barn County
Kai von Fintel
Russell Arben Fox
Garden of Forking Paths
Roger Gathman
Michael Green
Scott Hagaman
Helen Habermann
David Hildebrand
John Holbo
Christopher Grau
Jonathan Ichikawa
Tom Irish
Michelle Jenkins
Adam Kotsko
Barry Lam
Language Hat
Language Log
Christian Lee
Brian Leiter
Stephen Lenhart
Clayton Littlejohn
Roderick T. Long
Joshua Macy
Mad Grad
Jonathan Martin
Matthew McGrattan
Marc Moffett
Geoffrey Nunberg
Orange Philosophy
Philosophy Carnival
Philosophy, et cetera
Philosophy of Art
Douglas Portmore
Philosophy from the 617 (moribund)
Jeremy Pierce
Punishment Theory
Geoff Pynn
Timothy Quigley (moribund?)
Conor Roddy
Sappho's Breathing
Anders Schoubye
Wolfgang Schwartz
Scribo
Michael Sevel
Tom Stoneham (moribund)
Adam Swenson
Peter Suber
Eddie Thomas
Joe Ulatowski
Bruce Umbaugh
What is the name ...
Matt Weiner
Will Wilkinson
Jessica Wilson
Young Hegelian
Richard Zach
Psychology
Donyell Coleman
Deborah Frisch
Milt Rosenberg
Tom Stafford
Law
Ann Althouse
Stephen Bainbridge
Jack Balkin
Douglass A. Berman
Francesca Bignami
BlunkettWatch
Jack Bogdanski
Paul L. Caron
Conglomerate
Jeff Cooper
Disability Law
Displacement of Concepts
Wayne Eastman
Eric Fink
Victor Fleischer (on hiatus)
Peter Friedman
Michael Froomkin
Bernard Hibbitts
Walter Hutchens
InstaPundit
Andis Kaulins
Lawmeme
Edward Lee
Karl-Friedrich Lenz
Larry Lessig
Mirror of Justice
Eric Muller
Nathan Oman
Opinio Juris
John Palfrey
Ken Parish
Punishment Theory
Larry Ribstein
The Right Coast
D. Gordon Smith
Lawrence Solum
Peter Tillers
Transatlantic Assembly
Lawrence Velvel
David Wagner
Kim Weatherall
Yale Constitution Society
Tun Yin
History
Blogenspiel
Timothy Burke
Rebunk
Naomi Chana
Chapati Mystery
Cliopatria
Juan Cole
Cranky Professor
Greg Daly
James Davila
Sherman Dorn
Michael Drout
Frog in a Well
Frogs and Ravens
Early Modern Notes
Evan Garcia
George Mason History bloggers
Ghost in the Machine
Rebecca Goetz
Invisible Adjunct (inactive)
Jason Kuznicki
Konrad Mitchell Lawson
Danny Loss
Liberty and Power
Danny Loss
Ether MacAllum Stewart
Pam Mack
Heather Mathews
James Meadway
Medieval Studies
H.D. Miller
Caleb McDaniel
Marc Mulholland
Received Ideas
Renaissance Weblog
Nathaniel Robinson
Jacob Remes (moribund?)
Christopher Sheil
Red Ted
Time Travelling Is Easy
Brian Ulrich
Shana Worthen
Computers/media/communication
Lauren Andreacchi (moribund)
Eric Behrens
Joseph Bosco
Danah Boyd
David Brake
Collin Brooke
Maximilian Dornseif (moribund)
Jeff Erickson
Ed Felten
Lance Fortnow
Louise Ferguson
Anne Galloway
Jason Gallo
Josh Greenberg
Alex Halavais
Sariel Har-Peled
Tracy Kennedy
Tim Lambert
Liz Lawley
Michael O'Foghlu
Jose Luis Orihuela (moribund)
Alex Pang
Sebastian Paquet
Fernando Pereira
Pink Bunny of Battle
Ranting Professors
Jay Rosen
Ken Rufo
Douglas Rushkoff
Vika Safrin
Rob Schaap (Blogorrhoea)
Frank Schaap
Robert A. Stewart
Suresh Venkatasubramanian
Ray Trygstad
Jill Walker
Phil Windley
Siva Vaidahyanathan
Anthropology
Kerim Friedman
Alex Golub
Martijn de Koning
Nicholas Packwood
Geography
Stentor Danielson
Benjamin Heumann
Scott Whitlock
Education
Edward Bilodeau
Jenny D.
Richard Kahn
Progressive Teachers
Kelvin Thompson (defunct?)
Mark Byron
Business administration
Michael Watkins (moribund)
Literature, language, culture
Mike Arnzen
Brandon Barr
Michael Berube
The Blogora
Colin Brayton
John Bruce
Miriam Burstein
Chris Cagle
Jean Chu
Hans Coppens
Tyler Curtain
Cultural Revolution
Terry Dean
Joseph Duemer
Flaschenpost
Kathleen Fitzpatrick
Jonathan Goodwin
Rachael Groner
Alison Hale
Household Opera
Dennis Jerz
Jason Jones
Miriam Jones
Matthew Kirschenbaum
Steven Krause
Lilliputian Lilith
Catherine Liu
John Lovas
Gerald Lucas
Making Contact
Barry Mauer
Erin O'Connor
Print Culture
Clancy Ratcliff
Matthias Rip
A.G. Rud
Amardeep Singh
Steve Shaviro
Thanks ... Zombie
Vera Tobin
Chuck Tryon
University Diaries
Classics
Michael Hendry
David Meadows
Religion
AKM Adam
Ryan Overbey
Telford Work (moribund)
Library Science
Norma Bruce
Music
Kyle Gann
ionarts
Tim Rutherford-Johnson
Greg Sandow
Scott Spiegelberg
Biology/Medicine
Pradeep Atluri
Bloviator
Anthony Cox
Susan Ferrari (moribund)
Amy Greenwood
La Di Da
John M. Lynch
Charles Murtaugh (moribund)
Paul Z. Myers
Respectful of Otters
Josh Rosenau
Universal Acid
Amity Wilczek (moribund)
Theodore Wong (moribund)
Physics/Applied Physics
Trish Amuntrud
Sean Carroll
Jacques Distler
Stephen Hsu
Irascible Professor
Andrew Jaffe
Michael Nielsen
Chad Orzel
String Coffee Table
Math/Statistics
Dead Parrots
Andrew Gelman
Christopher Genovese
Moment, Linger on
Jason Rosenhouse
Vlorbik
Peter Woit
Complex Systems
Petter Holme
Luis Rocha
Cosma Shalizi
Bill Tozier
Chemistry
"Keneth Miles"
Engineering
Zack Amjal
Chris Hall
University Administration
Frank Admissions (moribund?)
Architecture/Urban development
City Comforts (urban planning)
Unfolio
Panchromatica
Earth Sciences
Our Take
Who Knows?
Bitch Ph.D.
Just Tenured
Playing School
Professor Goose
This Academic Life
Other sources of information
Arts and Letters Daily
Boston Review
Imprints
Political Theory Daily Review
Science and Technology Daily Review