We here at 2+2 can solve poker!

There are (thanks to you 2+2ers for the source) 1.2 quintillion different routes a heads up game of limit holdem can go. It's been said that this is far to big a number to calculate all the possible outcomes...nope, it is, however, a big venture to pursue, but it is possible, and soon on top of that!

You guys remember Deep Blue from 1997? Well, it could calculate 200 million moves per second operating at only 12.5 gigaflops or so (not very fast by today’s supercomputer standards). How can I get a supercomputer? Well, all you have to do is hook up a bunch of off the shelf PCs, and whammo!...supercomputer. In fact, Virginia Tech did just that, and bought 1,100 PowerMac G5 Dual 2.0GHz units and made a system capably of 10 Teraflops of performance.

So, assuming a chess move is as complicated as what the system would have to do to go over poker moves, it could calculate all of the possible solutions, and come up with a Nash equilibrium in under 18 months!

I’m not sure how exponentially the game escalates as the number of players goes up, but it could easily be solved in ten years assuming processor speed continues to rise.

If none of us here are willing to donate money to this cause, would anyone volunteer their computer, ala distributed.net ? I certainly would.

I don’t know what solving the game would do to poker theory, as it may be too complicated to use readily, but I sure would like to find out.

Rick.

Hmm...interesting...I just found that the new Playstation 3 processor is quite powerful:

"Sony also laid out the technical specs of the device. The PlayStation 3 will feature the much-vaunted Cell processor, which will run at 3.2GHz, giving the whole system 2 teraflops of overall performance. It will sport 256MB XDR main RAM at 3.2GHz, and it will have 256MB of GDDR VRAM at 700MHz."

If that's the case, hell, I'll splurge on 20 of them, and solve poker all by myself. (I will have to get some programming/mathematics aficionado to assist however.)

After a little more looking, the overall performance is what they said, but the processor performance was 218 gigaflops, so in order to get the required 12.5 teraflops, I'd need 60 of them. A bit outta my budget, but something to save up for. /images/graemlins/grin.gif

[ QUOTE ]
I don’t know what solving the game would do to poker theory, as it may be too complicated to use readily, but I sure would like to find out.

[/ QUOTE ]
It would make bots far more viable than they are today.

It would do little for poker theory, that has already been worked out as far as humans are concerned. It may create a few more small edges, but I doubt it.

[Neil Stevens]

Poker can't be solved in the sense Chess can be solved because Poker is a game of incomplete information.

Plus, as Sklansky addresses in TOP, the optimal strategy (surely some huge mixed strategy) doesn't maximize your profit against weak opposition, so solving it won't even make you more money at low limits!

[ QUOTE ]
Poker can't be solved in the sense Chess can be solved because Poker is a game of incomplete information.

[/ QUOTE ]

If you mean that it's impossible to find the 'least exploitable' technique, then you are wrong.

If you mean that it's impossible to win every game then you are right.

[ QUOTE ]
Plus, as Sklansky addresses in TOP, the optimal strategy (surely some huge mixed strategy) doesn't maximize your profit against weak opposition, so solving it won't even make you more money at low limits!

[/ QUOTE ]

May not, rather than will not would be a better thing to say here. Of course, as has been indicated by others, a ideal play would be a fun thing to put in a bot.

Heads up limit poker is not within the realm of computability with todays techniques and computers. The computational complexity of solving poker is polynomial in the size of the state space -- roughly the square of the state space, and 2^88 is too big to crack.

The U Alberta folks split up the state space into something like 6 hand categories and used a limit of 3 bets per round, and used a sophisticated approach to the game theory to build one of the earlier generations of poki.

[ QUOTE ]
Heads up limit poker is not within the realm of computability with todays techniques and computers. The computational complexity of solving poker is polynomial in the size of the state space -- roughly the square of the state space, and 2^88 is too big to crack.

The U Alberta folks split up the state space into something like 6 hand categories and used a limit of 3 bets per round, and used a sophisticated approach to the game theory to build one of the earlier generations of poki.

[/ QUOTE ]

If you look at my starting post, you will see that it can easily be solved in under two years if all my information is accurate, and I'm pretty sure it is.

Rick.

[ QUOTE ]
If you look at my starting post, you will see that it can easily be solved in under two years if all my information is accurate, and I'm pretty sure it is.

[/ QUOTE ]

Let's say the search space has roughly 7,000,000,000,000 states. Then, in order to find an optimal startegy we need to do roughly 49,000,000,000,000,000,000,000,000 operations.
Now, let's assume, for a moment that each operation is one flop (in practice the operations are a bit larger but that's not important here.)
Let's say we have 1 terraflop = 1,000,000,000,000 operations per cpu per second, and 1000 cpu's.
Then the process will still take 49,000,000,000,000 seconds. That's roughly 1,500,000 years.

[AaronBrown]

Echoing rufus' point from another angle, the number of possible outcomes of one hand understates what you have to consider to solve Poker. Every player at the table can select any probability distribution of actions for any situation, and can change that for each hand.

For example, consider a much simpler game betting on how many heads we have between us. Each of us flips a coin and looks at it, but doesn't show it to the other. I say either zero or one. If I say one, you either say challenge or two. I win if I say zero and there are no heads between us, or if I say one and you challenge and there is at least one head between us, or if I say one, you say two and there are fewer than two heads between us. Otherwise, you win.

This game has four intitial states, HH, HT, TH and TT, and three possible sets of actions: zero, one/challenge and one/two. That's 12 possible combinations. But I can pick any p from 0 to 1 as the probability of saying zero with either H or T; that's two continuous numbers. Moreover, I can pick different p's for each hand, either independently or dependent on previous outcomes. Solving this 12 state game is not trivial. Multiply by 10^14 and you have a difficult problem even with a lot of computer power.

[ QUOTE ]
[ QUOTE ]
If you look at my starting post, you will see that it can easily be solved in under two years if all my information is accurate, and I'm pretty sure it is.

[/ QUOTE ]

Let's say the search space has roughly 7,000,000,000,000 states. Then, in order to find an optimal startegy we need to do roughly 49,000,000,000,000,000,000,000,000 operations.
Now, let's assume, for a moment that each operation is one flop (in practice the operations are a bit larger but that's not important here.)
Let's say we have 1 terraflop = 1,000,000,000,000 operations per cpu per second, and 1000 cpu's.
Then the process will still take 49,000,000,000,000 seconds. That's roughly 1,500,000 years.

[/ QUOTE ]

Well, I'm free for the next 78,000,000 Saturdays... /images/graemlins/tongue.gif

[Moozh]

I'm not sure if you've heard of Poki, but they're already working on solving heads up poker at the University of Alberta.

You can check it out (and play against it) here (http://www.cs.ualberta.ca/~games/poker/)

It might be possible to solve flop poker -- that is, solve hold-em that doesn't allow bets after the flop round.

I come up with about 3.1 million hands for each player. So roughly 58 million variables in a complete post-flop strategy -- that's small enough to fit into memory.

Optimizing that is still roughly order 2^45, but that's computable, if large. It's worth noting that if the vast majority of hands end up being terminal i.e. folded by one of the players, then this will be a good approximation of the optimal strategy.

[snoopdarr]

The OP had the right idea... distributed computing would be the way to go for any problem of this nature... set it up, and i'll let you have all my idle time!