News for hackers. Stuff that matters.
Re:The Steely, Headless King of Texas Hold ’Em by Someone on Thursday September 05, 2013 @11:06AM (#6334611)
Is it actually possible to mathematically solve those games? Suppose player Alice bets $100; how does player Bob judge that bet? As a strong hand or as a bluff? Any software program will have to model what's inside the head of its opponent, and we know way too little of that to do that.

Moreover, if we could, the opponent may choose a different strategy. It may be like a game with nontransitive dice: if you figure out which dice I use, you can beat me, but if I figure out that you figured that out, I can pick different dice and beat you (http://en.wikipedia.org/wiki/Nontransitive_dice)

I think it is possible to write software that statistically beats any opponent, but proving that it does is way harder.

Re:The Steely, Headless King of Texas Hold ’Em by jib on Thursday September 05, 2013 @12:00PM (#6334941)
Yes it is possible to mathematically solve limit poker (as well as no-limit poker, but no-limit poker is orders of magnitude more difficult - they are effectively different games).

The definition of solvable is "Does there exist a strategy that, regardless of opponents play, is not a losing strategy" though (because the game is symmetrical). It is not possible to solve for "Does there exist a strategy that, regardless of opponents play, guarantees maximum profits". You can solve it for not losing money, but you cant solve it for making the max amount of money.

Trivially it's not possible to write software that beats any opponent (because what would it do playing against itself?) . Less trivially, any game that has a finite amount of decisions (and limit hold-em does) has at least one Nash equilibrium, so there exists a strategy that will at least have you break even.

The way to solve the game is to calculate your odds of winning based on previous actions and ensure that you take actions that make any future decision of the opponent have the same outcome (to reach a Nash equilibrium).

That strategy hasnt been calculated yet, but the best limit players are most likely playing very close to it, at least if you compare to the best no-limit players playing no-limit (the variable amounts possible to bid in no-limit multiplies the possible strategies massively).

Re:The Steely, Headless King of Texas Hold ’Em by Strilanc on Thursday September 05, 2013 @12:38PM (#6335140)
Yes, you can solve them mathematically. The main difference is that instead of a strategy picking a move for each possible state of the game, it picks a probability distribution over moves for each possible state of the game (including history).

Given two strategies, you can determine which one is expected to win and by how much. That allows you to find the strategy that's hardest to take advantage of. In the case of non-transitive dice, the hardest strategy to take advantage of is likely to be "pick each die with equal chance".

That being said, solving these games is extremely expensive. Super-exponential in the size of the game, if I remember correctly. Way worse than games like chess. See this paper: http://www.sciencedirect.com/science/article/pii/00220000849...

Re:The Steely, Headless King of Texas Hold ’Em by iopq on Thursday September 05, 2013 @02:09PM (#6335788)
Yes, this is called the Nash equilibrium strategy.

Let's say for all the possible hand/board combinations and betting patterns you evaluate all of them (with current computing power this is not possible) then you can take the line that maximizes your value assuming your opponent maximizes his. Then you both end up close to even over a long period of play.

But it's even more simple than that: Nash equilibrium strategy says that you have to bluff 1/3 of the time on the river in a certain spot and have a highly valued hand 2/3 of the time.

It doesn't matter whether your opponent calls you or not. If he calls you too much, your value hands get paid off more often. If he doesn't call you enough, he loses too much to your bluffs. If the bet is the size of the pot, then he has to call one half of the time as part of his Nash equilibrium strategy to not get exploited. If he deviates, he will lose to the bot in the long term.

And since this is limit it's actually very simple. Bet sizes in regards to the pot are tiny (1/5 to 1/10 of the pot) and there is no having to choose the bet size or allowing for players to overbet the pot (make a bet larger than the pot)

No limit is a much bigger challenge than limit for computers, because a small edge in limit is too hard to exploit since you'll get tired of exploiting a computer for pennies per hand

Re:The Steely, Headless King of Texas Hold ’Em by lazyant on Thursday September 05, 2013 @12:23PM (#6335059)
The example is not very good because solving or beating the game is always defined "in the long run" ie over a large sample of hands, not one particular hand (ex: if Alice bets $100 all the time she is bluffing a lot since good cards are hard to get)
Re:The Steely, Headless King of Texas Hold ’Em by ianstallings on Thursday September 05, 2013 @11:21AM (#6334707)
Yeah I think that's the main hurdle actually, the information-sparsity problem. We never really know what the opponent holds, unlike chess where nothing can be hidden. Also there is the case of non-optimal play from an opponent and modeling that would be incredibly challenging.