Open source game-theoretic poker player
github.com
github.com
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.
I thought all poker sites banned such bots. Is that just a lie?
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...
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.
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?
There are people that run bots on online poker sites, to varying degrees of success.
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.
My point is that if you play low stakes, you get crushed by patient bots. If you play high stakes, you get crushed by cyborgs.
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.
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.
And if you get 2 computers communicating, sitting at the same table, well, HUGE advantage.
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.
The combination of stats, practice and experience is better than a bot or pure human. I know this because I have a close friend that does this stuff and makes close to a 100K a year and botting might have once been a hobby of mine.
There is no infinite computation, so brute force play is not possible - even in chess (PSPACE). The problem with bots is that they tend to have blindspots they are blind to since they can't very well model their understanding. Human Computer Combinations still win and will probably continue to do so until the day something comes alone that can beat us at the kind of higher order pattern recognition we are so good at. http://www.palantir.com/2010/03/friction-in-human-computer-s...
For poker, only the very small and IMO uninteresting subset of 2 player limit is effectively solved. The combination of human minds + machine computation will be the top intelligences for the foreseeable future.
Also, while I dont doubt your friend is good at poker, that does not mean he has an understanding of the algorithmic advances in game theory as they apply to stochastic games. Further, simply knowing him does not make you an expert, even if you had a background in poker botting. How do we know that a game needs to be perfectly solved in order for it to beat the best players? Would the best nlhe hu player in the world beat the best bot at 100bb stacks? Yes. Will this be the case for the foreseeable future? Probably not. My point is that you cannot speak conclusively about a field like this with so little knowledge of what is going on academically to advance it.
1: http://blog.chess.com/Clavius/most-impressive-computer-game-...
My friend? No he does not know about stochastic game trees or regret minimization or any of that fancy stuff. But that knowledge is not needed for top poker play any more than a Basketball player needs to know about differential equations to put a ball in the net.
And perfect play? I do not believe that perfect play is required to beat the best players, that is not even computationally tractable. Now, while it is true that computers may some day beat top players (in n-player NL), it is also true that we are very far away from that. I am confident that we will reach that point but it is hard to say when. Probably after Go. But already the top players, using computational aides, are not fully human. With those kind of tools they are able to regularly play the game at a level that is far higher than the old unaided standards, raising the stakes even higher for bots.
Little idea? I keep apace with current machine learning though not fully up to speed on poker specific stuff. Would need to spend a month or so to catch up.
Anyways to wrap this up, what I am saying is Human + Bots > Bots and I'm predicting right now that when Poker Bots surpass humans, they still will not be able to beat that combination.
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.
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.
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.
If only we had access to the backend histories of an online poker site!
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.