Open source game-theoretic poker player

https://github.com/adamsmith/game-theory-poker

by adamsmith • 14 years ago

74 41 14 years ago

unreal372• 14 years ago

OK now that Chess and Jeopardy have been conquered.

I wonder if no-limit texas hold'em poker is something that massive computing power can consistently conquer as well. Imagine if you had 10,000's of instances of EC2 churning at playing one hand of poker against the world's best opponents...

Is it possible?

alanctgardner2• 14 years ago

The thing about poker (versus chess), is the notion of complete versus incomplete information. In chess, you know the location of every piece. This means you can compute possible positions (theoretically) until every possible game ends. Even better, you can play the algorithm against itself, since it can see everything either player knows. This makes chess computationally expensive - there are many positions, and you can do fairly meaningful analysis on every possible move. The best chess algorithms know how to aggressively cull paths which won't work well early on.

In Texas Hold'em, you only know ( initially ) your pocket cards, then as the rest come up you gain a bit more information. But compare this to the number of cards you can't see as a player. Those overlays they show on TV are effectively the best you can do; there's just no more data to work with. It's not like chess where throwing more computing power at it helps anything.

dminor2• 14 years ago

That's silly. You have an opponent whose previous actions you can analyze with an eye to the possible cards to come and the moves you can make. Add more players and the calculations are more complex. There's plenty of data for a computer to crunch on.

jib• 14 years ago

If you played just one hand that would be true.

Poker strategy is based on large sample sizes - you're not trying to figure out the optimal strategy for a single hand, you're trying to figure out an overall strategy for groups of hands against groups of boards.

Winning strategy for limit poker is essentially making sure you're game theory optimal, so that there isn't a strategy someone can apply against you that will in the long run be profitable. You can't apply a simple greedy algorithm hand per hand, you need to be aware of the ranges of hands you could have and what strategies your opponent could be applying against those hands.

That is the not losing part, the winning more part is figuring out where your opponents arent playing GTO and figuring out if you can afford making your strategy exploitable to in turn exploit your opponents (because if you try to be always GTO you may not beat rake etc).

Looking at poker hand by hand is like looking at chess move by move.

btilly2• 14 years ago

In a group setting, computers can beat humans. They just keep track of more stuff.

And if you get 2 computers communicating, sitting at the same table, well, HUGE advantage.

Dn_Ab5• 14 years ago

It is very hard to make a bot that doesn't do stupid things. > 90% will fail and > 95% will fail to beat rake. Plus the top online poker players are basically half machine.

They use stuff like Hold'em manager and various sites to analyze a large amount of statistics against their opponents. Ranging from performance, games they tend to play and win, as well as storing a local database of all their hand histories, positions etc. they encounter. They also use the software to go over their own play to look for weaknesses with the computer giving suggestions. The bots would be going against something that is not fully human and similar to advanced chess results, they would stand little chance.

dminor2• 14 years ago

There's a group at the University of Alberta that does research in poker strategy. They have a program that plays heads-up poker (2 players) as well as the best in the world. Adding more players into the mix significantly complicates things though, so it will be a little while yet.

There are people that run bots on online poker sites, to varying degrees of success.

wilfra2• 14 years ago

Those bots have gotten significantly better the last few years. I would say the best bots today are beating nearly all of the recreational players and even the lower rungs of professional players - but the very best players can still beat them, should they be paying attention to their tendencies. The bots have a big advantage over them though in that they are robots: they don't get tired or hungry and their judgment never gets clouded on runs of bad luck.

PokerStars and FullTilt have worked hard to rid their sites of bots but many other networks have turned a blind eye to them, some even explicitly allowing them - since the bots pay rake like any other player. Every so often the players will revolt and the sites will crack down but the bots always find their way back again.

Dn_Ab5• 14 years ago

Note that the person you are replying to specified No-Limit, which is much harder. It's been a while but last I looked the Alberta Group could only do Limit Poker.

mbell• 14 years ago

Interesting, how much did you try to optimize this code? Some of it is a bit fishy.

moccajoghurt2• 14 years ago

There is actually a business behind bot-poker-player.

I have played about 20k tables Texas Hold'em Double or Nothing and stopped playing after 6 months with a profit of 1000$.

I have met quite a few bots and an experienced player will most likely recognize such bots. However it took a while to realize it and I had to look up the stats in order to see it.

The algorithm the bot used was really simple. In poker terms you'd call the bot-player a rock. He bets when he has good cards and will always go all-in whatever happens after the flop.

You'd think that this algorithm is too simple to be succesful but that's wrong. There are two factors that make this strategy profitable:

1. If you play on low limits the players usually play incredibly aggressive and will nearly always lose a lot of money whenever your bot bets.

2. Even if you have a winrate of only 55% (which is necessary to not make a minus, because you never play for free, there is a fee for each table) you will make profit because of the cashback your online poker provider will give you after each month. This is also why you have to play a lot of tables. The bot played about 800 tables each day, which is insane. However it does increase the cashback and the more you play, the more money will get each month.

aneth4• 14 years ago

Seems like a rather easily detectable bot, playing 800 tables a day and playing predictably.

I thought all poker sites banned such bots. Is that just a lie?

moccajoghurt2• 14 years ago

Well I think that depends on the poker provider. Titan-Poker didn't.

relix• 14 years ago

Since there were bots the poker sites have started detecting bots. If a player played every day exactly 800 tables (or exactly e.g. 8 hours), it would be instantly banned for being a bot.

Bots have a lot of randomization now to make it appear human: sleep randomly to emulate "thinking", click on different parts of the button, randomly move the cursor around but still humanly, click next to the button, move the cursor on one button before moving it to another button to actually click, and so on...

robinwarren• 14 years ago

I pointed this out to a guy I used to work with when he was creating a bot. I correctly guessed he'd not allowed for the fact someone might spot a player with sub 1 sec response times who always clicked on the exact same pixel etc. He added some random waits in here and then, every now and then you'd hear a flushing sound from his computer as his bot 'went to the toilet'.

btilly2• 14 years ago

Sites try, but can fail.

My favorite story was someone playing 120 tables simultaneously, who was verified to be human. See http://news.ycombinator.com/item?id=1899310 for discussion on that one.

orensol• 14 years ago

Will be interesting to see how/if it can scale on cheap cloud based cpu oriented machines, such as Amazon High-CPU instances.

unreal372• 14 years ago

From what I have read today, the current poker bot programs do a lot of work in advance, and just follow decision trees when to raise, call and fold along that tree. They already know how they will bet with J10 suited before the flop when they are the first to act before the game starts.

The real challenge is the number of permutations of that, which raise memory requirements into the petabytes range. Not to mention multi-player games, and the no-limit version where betting gets more complex.

Not sure if having high-cpu instances at your disposal helps during game play.

martinced• 14 years ago

It's Limit Texas Hold'em. (of course)

Limit Texas Hold'em and No-Limit Texas Hold'em, are two entirely different game. They happen to share a few things in common but from a game theory they're two wholly different beast.

They're as different that, basically, limit Texas Hold'em is a solved problem: good bots can rival with the best professional players (playing Limit Hold'em for money online is risky: you can be playing vs a bot or vs someone entering the moves of a bot).

But No-Limit Texas Hold'em? There are players who've won several major tournaments. The psychological element is very, very important.

And unless we make amazing AI discoveries, it's going to be very difficult to write bots able to beat good players at No-Limit Texas Hold'em.

But you can find bots online, even for NLHE, able to beat beginners and the rake at very low limits (called the nanostakes and the micro-stakes, but not above).

Another thing: there's so much money to be made (as in millions of $) by writing a bot able to beat mid-stakes and high-stakes online no-limit Texas Hold'em that the last thing someone who'd write such would do would be to publish it online.

Major sites like PokerStars do pro-actively look out for bots: the EULA states that they have the right to scan the entire memory of your computer and your entire hard disk. And you can't install such a software without giving the root/admin password of your system. And you cannot legally use a VPN: if they detect one you're out (you still technically can if you manage to fly 100% below the radar). And you can't use remote desktops. It's overall very restrictive.

They're regularly busting bot-rings and chinese-colluders rings and confiscating their money (and redistributing it to other players).

And if they suspect an account of multi-accounting, they'll do tricky things like moving and resizing all the poker tables at once, while simultaneously showing a captcha.

If you fail to enter it, you'll have a hard time convincing the site to not confiscate your money...

But back in the wild wild west days, it was amazing: some people had "war rooms" made of tens of PCs, all playing online poker and making very very big money. It was a big business.

But games got tougher, poker "black friday" hit the US hard, bot detection has vastly improved, etc.

So the "gold rush" is over for most botters.

icelancer• 14 years ago

As someone who worked for one of the online poker sites doing bot detection and collusion investigation, I find your optimism amusing. It is certainly not over.

DennisP• 14 years ago

If nothing else: air gap, computer vision, and a human player doing whatever the bot tells him to do.

IsaacL2• 14 years ago

I wrote a pokerbot for my university third year project: https://github.com/IsaacLewis/FYP. I haven't been able to spend any more time on that project since finishing it (though I wanted to), but I still find the space fascinating.

Unlike the linked bot, which is an "equilibrium" (or "game-theoretic") player, mine followed an "exploitative" strategy. What's the difference? Equilibrium strategies find (or attempt to find) a Nash equilibrium, and follow that. As the OP said, this minimises their losses, but also prevents them exploiting weaknesses in an opponent's playing style. Wheras an exploitative player adapts its strategy to take advantage of its opponent, but that leaves it open to being exploited itself.

The OP used RPS as an example - it's clear that the Nash equilibrium is picking each move with 1/3 probability. No matter what your opponent does, your expected value is 0. But what if your opponent decides that they will always pick rock? The EV of the equilibrium strategy is still 0, but you could switch to an exploitative strategy of always picking paper, in which case your EV is 1. For this reason, exploitative strategies will almost always win multiplayer RPS tournaments, because they can consistently beat the weaker players, whereas the equilibrium players will stay in the middle of the pack. It might seem like a surprising result that playing an exploitative strategy always leaves you open to exploitation yourself, but the maths works out.

If you an intuitive grasp of this idea, consider that to exploit your opponent's strategy, your play must be adapted based on observations of their play. But this means they can play with style X, leading you to play style X' which is dominant, before they catch you out by switching to style X'', which dominates X'. If you have experience playing poker with competent humans, they do the same thing.

In computer poker, AFAIK equilibrium players generally perform better. I think this is because poker is a more complicated game than RPS, so both humans and bots consistently make mistakes, so just playing solidly gives equilibrium bots the edge. But writing an exploitative bot is still pretty interesting, because it seems closer to human poker, which is more about bluffing and outthinking your opponents than mathematically optimising your play.

My bot wasn't especially interesting - it was based on an existing algorithm called Miximix, and I used Weka to try and machine learn a model of the opponent's strategy. Still, it could do interesting stuff - eg, if it played against an opponent that could be intimidated out of hands by large bets, it would realise that it could bet large without having good hands - ie, it successfully taught itself to bluff. What I thought would be really interesting was a bot with multiple-level opponent modelling - "what does my opponent think I have?" or "what does my opponent think I think he has?". Good human players think this way, and "recursively modelling other minds" seems integral to conscious thought, so it'd be cool to look into in more depth.

The other thing that would be cool to look into is "explanation-based learning". Normal machine learning approaches require large amounts of data to draw inferences, but human poker players seem capable of forming conclusions about their opponent based on very limited information. Explanation-based learning uses a domain model to help this.

Hmm, writing this comment has reignited my interest in this space - I really should dig out my old code and work on this again some time.

adamsmith• 14 years ago

With the advent of Deep Belief Nets, which can learn from lots of unlabeled data, it seems reasonable to believe you could duplicate or exceed the human ability to quickly understand a player's behavior based on past humans played.

If only we had access to the backend histories of an online poker site!

IsaacL2• 14 years ago

Oh, but you can... http://www.pokertableratings.com/buy-hand-histories

philh• 14 years ago

> But we can compute the optimal strategy for an abstract version of poker that, for example, during pre-flop betting treats pairs of aces the same way as pairs of kings.

Not a big deal, but the wording of this seems off. It doesn't sound like you're computing the optimal strategy for poker-prime, where poker-prime has the property that in pre-flop betting (but nowhere else?) pocket aces are no more valuable than pocket kings.

Rather it sounds like you're computing a sub-optimal strategy for poker, by taking an optimal strategy and making it computationally simpler at the expense of some correctness.

querulous2• 14 years ago

It's still optimal because your preflop play with KK is going to be exactly the same as with AA. Similarly, you are going to play 9s8c exactly the same as 9h8d.

andyakb8• 14 years ago

this is not true. suit simplifications can be made without any loss to the value of the solution, but saying AA=KK is not a lossless simplification

Open source game-theoretic poker player

Related Stories