[HN Gopher] How A.I. Conquered Poker
___________________________________________________________________
How A.I. Conquered Poker
Author : jdkee
Score : 75 points
Date : 2022-01-18 18:00 UTC (4 hours ago)
(HTM) web link (www.nytimes.com)
(TXT) w3m dump (www.nytimes.com)
| bluecalm wrote:
| I am the solver programmer mentioned in the article. I think it
| came out pretty decently. Maybe not all the details are right (I
| was late answering fact checking email) but I think it's a decent
| read and the author has done a good job!
| michalsustr wrote:
| Congrats on putting this together, it's not easy! I'm curious,
| what papers have you used for your implementation? I know there
| are a couple of reimplementations of DeepStack out there.
|
| Disclaimer: I'm doing phd in this area, generalizing to harder
| games than poker.
| bluecalm wrote:
| The solver was purely based on our (mine and my partner's)
| ideas. We tried reading some papers to find ideas to improve
| our solver but we had found that they are not very helpful -
| written in opaque language, using wrong tree representation
| and not focusing on practical implementation aspect. Maybe
| things changed since then but I haven't found anything useful
| at all in published papers about poker with the exception of
| two page one by Oskari Tammelin describing CFR+ algorithm
| (which we haven't used in our software because of its
| significant memory requirements).
|
| We considered it very unlucky that the science paper was
| published as we thought more people will implement solvers
| then (ours was ready in mid 2014 and we released and a
| working solver with a GUI in early 2015, 3 months after the
| Limit Holdem paper). As it turned out though it didn't really
| matter much.
|
| I had an idea to code a poker solver around 2008.
| Unfortunately I was yet to learn to code back then. The
| biggest challenge was to overcome implementation issues. Once
| I got the crucial part to be fast enough I knew the solver is
| possible. I think not having much background in the field
| allowed me to come up with more natural (and better) tree
| representation and memory efficient (even if not the fastest)
| algorithm as I was thinking more as poker player than a
| computer scientist back then.
| michalsustr wrote:
| Interesting! We have very recently wrote a paper on the
| various tree representations [1]. Maybe it is the same
| distinction you found on your own? I judge this based on
| the screenshots on your website. Public state trees are
| amenable to nice factorization over the hands, and indeed
| most implementations use it, but formally they write they
| use the history tree notation.
|
| [1] https://arxiv.org/abs/2112.10890
| im3w1l wrote:
| How perfect is the play that piosolver calculates? Do you make
| any simplifying assumptions?
|
| I noticed in the article that piosolver can incorporate a mixed
| strategy with multiple bet sizes. Pretty neat, is that a recent
| feature? As I rememember it, a few years back people would
| discuss what the optimal bet size was in various situations
| with the implicit assumption that there is just one.
| bluecalm wrote:
| Adding multiple betsizes was one of the first features we
| added in 2015 - so not very recent, no. The one true correct
| bet size is a seducing idea but that just doesn't exist for
| most situations. You can try finding the best one with the
| assumption you can only use one but it's not the best idea in
| my opinion. Main reasons are that that's the sizing most
| people will be most ready to play against and EV difference
| between possible bet sizes is minimal.
|
| What happened in chess is now happening in poker: at first
| people were all about the best theoretical move and then
| gradual shift to "not necessary the best just sound enough
| but less likely to be analyzed by the opponents" started
| happening.
|
| As to the first part of your question: the solutions are
| pretty much perfect. The only assumption is about possible
| bet sizes. As to accuracy we measure it in theoretical
| exploitability (how much a perfect adversary who knows our
| strategy exactly could win against us). You can easily go so
| low that even a theoretical perfect adversary wouldn't get
| close to beating the rake vs the solution, even at high
| stakes.
| [deleted]
| ewhauser421 wrote:
| Congrats - PIOSolver is an amazing program. What are the future
| plans for it? It would be great if you didn't need a PhD to set
| it up though. I keep wondering if I'm actually training myself
| using the right solutions or not based on the setup :)
| bluecalm wrote:
| The plans are to start turning it into real company which
| hopefully means easier to use software, more learning
| material and better communication. Till now it was mostly two
| guys working from home and overwhelmed by it all.
| splonk wrote:
| (Former pro and high stakes player, occasional solver developer)
|
| This is actually one of the best poker articles I've ever seen in
| generalist media. Not too clickbaity, reasonable high level
| overview of game theory, a (very accurate IMO) quote from old pro
| Erik Seidel about the state of the game just 15 years ago, a
| discussion on variance vs. EV and results, and most importantly,
| an emphasis on math, randomization techniques and emotional
| control rather than the TV image of staring in someone's eyes and
| reading their soul. Probably the one biggest misconception people
| have is that pros have sick reading abilities since TV likes to
| emphasize staredowns, when the actual single biggest skill long
| term pros have is the ability to lose hand after hand for hours
| and still play their best game.
|
| Incidentally, the anecdote at the top of the article is pretty
| intuitive game theoretically. Basically on the river you need to
| bluff with some portion of your hands, or else nobody will ever
| call when you have a good hand. The natural portion of your hands
| to bluff with is the absolute worst ones - you don't want to
| bluff with your middling hands because you have some small chance
| of just winning a showdown when it checks around. On a board of
| Kc4c5c2d2c, 7d6d is quite likely the absolute worst hand you can
| hold given the action that's taken place, therefore it's the one
| you bluff with. (For some pot/stack sizes it's possible that you
| bluff so rarely that you have to choose between 7d6d/7h6h/7s6s,
| but that's getting into details.)
| smallerfish wrote:
| I think there's room for a "battlebots meets online poker"
| product. Imagine buying your bot a real money budget and setting
| it loose in a tournament to combat other bots.
| bloodyplonker22 wrote:
| Online poker has already been evolving in this direction. Any
| serious player who plays online will use player assistance
| tools (such as PIOsolver). Top level poker AI such as Pluribus
| has already proven that it can hold its own and beat the best
| online players such as linuslove. It is well known that online
| poker sites are full of poker bots now. There are programs to
| help users try to tell if they are playing against a bot by
| seeing how fast it reacts on each hand, for example if it
| always takes a fixed amount of time on each hand or if there is
| a pattern.
| smallerfish wrote:
| Yeah, that was the evolution of my thought process. Online
| poker is already full of bots, which will get more and more
| sophisticated over time and defeat bot detection hurdles --
| so why not embrace it and have bot-only zones? You could have
| entire tournaments play out in less than a minute if all
| participants were software.
| cortesoft wrote:
| I would expect bots to add random delays? They could even
| determine real player delay distributions and emulate that.
| conductr wrote:
| I'm actually working on this as a side project. I've been
| dragging my feet as I wasn't sure anyone would want to "code to
| play" and had no real marketing plan.
|
| It's a fun project though, especially trying to design in a way
| that proves I'm not manipulating the deck behind the scenes.
|
| Email in profile if anyone is up for being an alpha player.
| smallerfish wrote:
| I think the real money aspect would obviously get you some
| traction, but that's difficult to deal with (since you might
| run into online gambling laws, although you could very
| credibly argue that this isn't really any different from
| algorithmic trading). Maybe you could get in on the hype
| train and launch it as a crypto product?
| Nextgrid wrote:
| Isn't that just algorithmic trading?
| meetups323 wrote:
| Classic games tend to be more fun than New York horoscopes.
| For me at least, there's something fundamentally profound
| about solving a logical puzzle better than anyone in history,
| that just isn't there in guessing which way some lines are
| going to go.
| tromp wrote:
| I like how the article gives examples of the sort of entropy
| players draw on to make their random choices:
|
| > Koon will often randomly select which of the solver's tactics
| to employ in a given hand. He'll glance down at the second hand
| on his watch, or at a poker chip to note the orientation of the
| casino logo as if it were a clock face, in order to generate a
| percentage between 1 and 100.
| splonk wrote:
| The watch face is the classic one, the chip orientation is new
| to me. I like it, it's less obvious that you're randomizing
| something, and given how much poker players like to fidget with
| their chips the orientation is probably reasonably random.
|
| Another classic is to use the suit of your cards, but that has
| problems with being correlated with the state of the board. It
| works fine preflop.
| marcodiego wrote:
| Is there any remaining logic game which AI hasn't become
| superhuman? IIRC Monte Carlo tree search has done wonders in this
| area.
| splonk wrote:
| Here's a recent paper from DeepMind about their recent efforts
| towards generalized game solving (caveat: I haven't actually
| read it yet).
|
| https://arxiv.org/pdf/2112.03178.pdf
|
| Abstract:
|
| "Games have a long history of serving as a benchmark for
| progress in artificial intelligence. Recently, approaches using
| search and learning have shown strong performance across a set
| of perfect information games, and approaches using game-
| theoretic reasoning and learning have shown strong performance
| for specific imperfect information poker variants. We introduce
| Player of Games, a general-purpose algorithm that unifies
| previous approaches, combining guided search, self-play
| learning, and game-theoretic reasoning. Player of Games is the
| first algorithm to achieve strong empirical performance in
| large perfect and imperfect information games -- an important
| step towards truly general algorithms for arbitrary
| environments. We prove that Player of Games is sound,
| converging to perfect play as available computation time and
| approximation capacity increases. Player of Games reaches
| strong performance in chess and Go, beats the strongest openly
| available agent in heads-up no-limit Texas hold'em poker
| (Slumbot), and defeats the state-of-the-art agent in Scotland
| Yard, an imperfect information game that illustrates the value
| of guided search, learning, and game-theoretic reasoning"
| btheshoe wrote:
| Imperfect information games that require agents to cooperate
| with each other haven't been solved yet. (multiagent
| cooperation is still a hard problem) Hanabi is a big(ish)
| research area. Contract bridge has had some work done on it.
| HWR_14 wrote:
| I'm surprised that Hanabi is such a huge research area.
| Compared to bridge or poker, it seems like a far more simple
| game.
| ska wrote:
| > I'm surprised ... it seems like a far more simple game.
|
| This probably shouldn't surprise you. If you are
| researching how to attack a new/difficult class of
| problems, typically you look for the simplest versions of
| that class first.
| isaacg wrote:
| As far as I know, in Magic: the Gathering, the best bots are
| far worse than most players. Part of the difficulty is that the
| rules are so complicated that there are only a couple of
| complete rules implementations. Beyond that, it's an imperfect
| information game with far more actions per game than poker, so
| optimal-solver techniques haven't seen success.
| dwohnitmok wrote:
| I think this is purely a resource issue, e.g. if Google Brain
| decided to make an MtG bot I would be fairly confident it
| would be superhuman. Even real time strategy games like
| Starcraft are looking like they're on the cusp of superhuman
| bots (Alphastar was competitive as Protoss against elite
| players, but did not consistently beat them).
| jdmoreira wrote:
| The search tree is huge in mtg. It has to be the largest of
| any game. You can take actions all the time. There are
| triggers all the time, you can stack your actions on top of
| your opponent actions. Huge space really.
|
| And then of course it's also imperfect information both in
| the sense of your opponent hand but also his deck. The
| cardpool is also very large for some formats.
|
| I actually don't think it's solvable just by throwing MCTS
| at it with todays hardware but would love to know more
| about this, if someone else has more insight please reply.
|
| EDIT: Oh and there is also the meta-game / deck building
| aspect. If you are going to win a tournament you have to
| have favorable matchups against most players in the room.
| archontes wrote:
| I doubt very highly it would be able to sit at a game of
| commander. Four players with 100 card singleton decks would
| be an absolutely enormous space to operate in.
| golergka wrote:
| Have people tried using GPT-3 for this?
| cortesoft wrote:
| Wouldn't the fact that the game is constantly changing, with
| new cards being added and old ones being removed, also make
| it harder to solve?
| soferio wrote:
| What teaching or training tools are out there for a very average
| player at no limit Texas hold'em who just wants to get at bit
| better to a respectable level at a modest time commitment , and
| does not need to be a pro-level player?
| jstx1 wrote:
| Books (there's very few good ones)
|
| Training videos
|
| 1-on-1 coaching
|
| PioSolver (and other similar software)
|
| For any of these to stick, you need to spend some amount of
| time studying by yourself; just consuming learning material and
| playing isn't enough.
| Reflecticon wrote:
| Could you recommend a couple of books for a start?
| jstx1 wrote:
| The Mathematics of Poker, by Chen & Ankenman - this one
| doesn't age because it's really fundamental if you want to
| understand things from the ground up. But it won't seem
| that practical at first.
|
| Applications of No-Limit Hold 'em, by Matthew Janda - this
| one goes into specifics about how to think on each street,
| how to build a good strategy etc. Some of the details will
| be different from the latest theory because the book was
| released in 2013 but it's still a very solid read if you
| want to level up.
| treme wrote:
| www.runitonce.com 25$/mo essential membership will give you
| enough from beginner to semi pro easily.
| torginus wrote:
| Does this mean that online poker is effectively over?
| jstx1 wrote:
| It's kind of dead-ish because there aren't big edges and most
| people who play online are decent enough. Online poker has been
| deteriorating for years (with maybe a small uptick due to the
| pandemic). But this article could have been written a few years
| ago, there's nothing new in it.
| redisman wrote:
| Ever since the US outlawed it it's been dead-ish
| paxys wrote:
| Chess has been "solved" by computers for a long time now, yet
| the online Chess community is bigger than ever. I don't see why
| it would be any different for Poker.
| vanusa wrote:
| Unlike with chess, in the poker world there's a huge
| financial incentive to run bots (or provide bot assistance to
| live players).
| fdgsdfogijq wrote:
| Big difference with poker is that its all about money, the
| game doesnt work if people arent risking something. And if
| computers are superior, the game breaks down.
| robrenaud wrote:
| You are worried that people will cheat in online poker, or
| what?
|
| For poker, people can still play face to face, and it being
| a game of mixed strategies means it's probably a lot less
| important that poker bots are better than people than in
| chess. Top chess players use the computers to set up
| preparation bombs on their opponents, with rebuttals to
| moves for specific positions created by the computers. That
| doesn't work in a game of imperfect information and mixed
| strategies.
| JacobThreeThree wrote:
| >You are worried that people will cheat in online poker,
| or what?
|
| The norm for online chess is to not play for money,
| whereas the norm for online poker is to play for money,
| often for large sums.
|
| Of course the game with higher stakes is more likely to
| attract cheaters.
| paxys wrote:
| > whereas the norm for online poker is to play for money,
| often for large sums
|
| That is definitely not the norm. Most people are playing
| recreationally. Heck it is illegal to pay poker online
| with real money in 44/50 states in the US.
| cortesoft wrote:
| Yeah, but playing poker for not real money is a very
| different game. Players have no incentive to not take
| huge risks, so it is a completely different game.
| eurasiantiger wrote:
| And how do you suppose they enforce that?
| rainonmoon wrote:
| Poker is not really all about money. Plenty of games might
| only ask you to stake like $5 but the joy and aim of the
| game is really to outplay the table, not take home $25.
| JacobThreeThree wrote:
| For the purpose of AI "conquering" poker the money makes
| a huge difference.
|
| Would you play the same way if you were betting your life
| savings versus $5?
| throwaway287391 wrote:
| > Big difference with poker is that its all about money,
| the game doesnt work if people arent risking something.
|
| I don't see this, I used to really enjoy online poker
| tournaments for play-money. It's a fun and strategic game
| in and of itself with nothing more than minor bragging
| rights on the line, to me at least. I honestly don't see
| why it should be any different from chess in terms of
| purely recreational play. (You could say chess is a deeper
| game, and that's probably true in some ways, but that's not
| a positive feature for casuals like me with no desire to
| invest many hours/years into mastering the game.)
| [deleted]
| abaldwin99 wrote:
| The difference for poker is it takes a lot more play time to
| sort players by skill. There's no ELO to climb and thus you
| don't get to play against more challenging opponents.
|
| e.g. I'll lose 100% of my matches against a Chess GM but
| against the best poker player in the world I could go all in
| preflop every hand and still win the match ~20% of the time.
|
| Only way to counter this variance is to play lots and lots of
| hands (Law of large numbers) It could take weeks/months in a
| single matchup to determine the better poker player.
|
| In terms of playing for real money, in general you'll find
| more challenging competition at higher stakes. But then
| there's an incentive for bots.
| jstx1 wrote:
| But it hasn't conquered it! I kept searching the article for some
| new recent breakthrough that I've missed but it's not there. Yes,
| solvers like Pio have been around for years and limit holdem has
| been essentially solved for a while but nobody plays limit holdem
| anyway.
|
| The two most popular games (no-limit Texas holdem and pot-limit
| Omaha) are still unsolved.
| evrydayhustling wrote:
| There is still a lively academic community and major progress!
| Check out CMU's no limit results [1]. (I realize articles like
| this have to pick some angles to make it interesting, but it
| was weird to see only dated research mentioned.)
|
| But if you are rooting against the machines, don't worry: it is
| almost certainly impossible to calculate a full equilibrium
| policy for no limit multiplayer, so we will instead be debating
| over the virtues of various types of imperfection for a long
| time. And even if an Oracle gave us convenient access to
| equilibrium strategy, it would still not be the optimum at a
| table full of imperfect players. Your poker game is safe for a
| while!
|
| [1] https://www.nature.com/articles/d41586-019-02156-9
| protoax wrote:
| Hasn't Facebook's Pluribus come pretty close to "solving" no-
| limit holdem? I don't know a lot about poker so I can't really
| assess their claim's validity.
| noambrown wrote:
| Bots are superhuman in no-limit Texas hold'em. Libratus beat
| top humans in two-player in 2017 and Pluribus beat top humans
| in six-player in 2019:
| https://www.science.org/doi/abs/10.1126/science.aao1733
| https://www.science.org/doi/abs/10.1126/science.aay2400
|
| It's shocking that the reporter didn't mention these results or
| anything else more recent than 2015.
| bko wrote:
| The article was fascinating but honestly read like an ad for
| PioSolver
| lawrenceyan wrote:
| Noam is being too humble, but he's one of the primary
| creators of Libratus/Pluribus as an fyi.
| hashberry wrote:
| > he opened a computer program called PioSOLVER, one of a handful
| of artificial-intelligence-based tools
|
| So I checked out this tool, and the team describes themselves as
| "programmers interested in algorithms"[0] ... what is the
| difference between A.I. and algorithms?
|
| [0] https://www.piosolver.com/pages/about-us
| bluecalm wrote:
| It just sounded like a good description. We never got any
| funding and started the business as a side project so no need
| for big words :)
| stu2b50 wrote:
| Depends on whether you use the traditional or vernacular
| definition of AI. Traditionally it was more about the _how_ not
| the what. AI was an agent acting rationally in an environment.
| Pac-Man guided by Dijkstra? That 's AI, there's an agent, an
| environment, and said agent is acting "rationally".
|
| In modern vernacular it has become a synonym for machine
| learning or sometimes specifically neural networks.
| buscoquadnary wrote:
| The amount of VC funding you'll get.
| ModernMech wrote:
| Algorithms are provably correct. If you've got no proof of
| correctness, the best you have is a heuristic.
| HALtheWise wrote:
| The taxonomy I personally use is:
|
| * Every computer program has algorithms, it's an extremely
| general term for "the idea behind how the computer will solve
| the problem". Advanced algorithms are typically those that took
| a lot of human effort to come up with.
|
| * Machine Learning refers to a specific class of algorithms
| where the computer automatically figures out (part of) what it
| should do based on data.
|
| * Deep learning is the subset of ML that uses deep neural
| networks.
|
| * Artificial Intelligence is a marketing term, and is actually
| about the _problem_ being solved, not the technology being used
| to solve it. In particular, AI is any computer program that
| solves a problem people would previously expect can only be
| solved by a human applying creativity and/or intelligence, like
| playing a game, understanding natural language, or creating
| artwork. This definition is obviously a moving target as
| expectations change.
|
| Deep learning is currently the most powerful and general
| toolkit for solving AI problems, so the concepts tend to get
| mixed together pretty frequently, but I personally like using
| the definitions above to keep things straight.
| hammock wrote:
| Clearest and most useful descriptions I've seen by far.
| Thanks for sharing
| JacobThreeThree wrote:
| I like your framework.
|
| Would you put statistical analysis "algorithms" in the same
| category as "Machine Learning"?
| neonate wrote:
| https://archive.is/rNhub
| RivieraKid wrote:
| For some time I've been pondering about creating a multiplayer
| poker AI that would (1) play reasonably well but not at a
| superhuman level (2) not require expensive hardware.
|
| Frustratingly, this seems to be an unsolved problem. Pluribus is
| only 6-max, requires fixed starting stack sizes and requires a
| lot of hardware.
___________________________________________________________________
(page generated 2022-01-18 23:00 UTC)