Computer Programmers solve checkers.

[Phanekim]

Checkers solved


In high school, I solved tic tac toe in my 50 minute US history class.

Checkers is not a complex game I figure it is solvable as well.

Same with heads up poker. An argument can be made that in human versus human...the human poker pro would be able to extract more from the newbie human than a computer though. This is due to exploitative strategy.

Of course, in a multi way game there's no way a computer would win due its inability to predict wierd implicit alliances.

[Gullanian]

I think you're getting a bit mixed up.

The reason checkers is so easily solvable is because it's a complete information game, with basic rules. The total permutations of the game is huge though, so most of the problem was having access to the computational power to solve the problem.

Tic tac toe is much more solvable because from any state the total permutations are relatively small.

Poker is incomplete information, this means you can't apply the same algorithms to solve the game such as you can apply in tic tac toe, or checkers.

The algorithm they used to solve checkers was probably the min-max algorithm or some deviation of it, and if you look at how the algorithm works you will soon understand why poker is a completely different problem area.

[Phanekim]

[ QUOTE ]
I think you're getting a bit mixed up.

The reason checkers is so easily solvable is because it's a complete information game, with basic rules. The total permutations of the game is huge though, so most of the problem was having access to the computational power to solve the problem.

Tic tac toe is much more solvable because from any state the total permutations are relatively small.

Poker is incomplete information, this means you can't apply the same algorithms to solve the game such as you can apply in tic tac toe, or checkers.

The algorithm they used to solve checkers was probably the min-max algorithm or some deviation of it, and if you look at how the algorithm works you will soon understand why poker is a completely different problem area.

[/ QUOTE ]

I am not getting mixed up. I do know the difference between perfect information and imperfect information games. Despite the fact that poker is an imperfect information game, heads up poker is quite solvable as shown by mathematics of poker. Maybe its not solvable in the sense that it is 100% winner but it deinfately sets you up to be inexploitable.

[rainonacongadrum]

So what's the likelihood of poker ever being solved?

It seems that a computer programmer might be able to at least program a computer so the computer plays "ideal" poker. The program could also take information from software like Poker Tracker and be even better.

[jogsxyz]

Checkers is a deterministic game. Poker is not.
A computer playing perfect checkers cannot be beaten.
Poker can be 'solved' in the sense that the computer
always makes the best EV play. Still the computer
will not always beat a donk. There's often no best
play that can beat every possible suck-out.

[rainonacongadrum]

Well if a program could be made to make the best EV play all the time given whatever is going on in a game wouldn't that be a huge moneymaker in any game?

[mvdgaag]

I think even an optimal strategy (in a game theoretical sense) for poker will have couter strategies that beat the optimal strategy.

Any strategy to be called a single strategy should be fixed. It can be 'raise 30%/fold 70% at random against a 20/15 opponent given this and that' so it is allowed to differentiate between a lot of variables that any person or computer could access. But within this information the strategy should be fixed.

In that case I think by definition the optimal strategy will be one that is least exploitable/most profitable against the entire range of possible strategies. But in that range are a few (probably themselves very exploitable strategies) that will beat an optimal strategy.

[chrisyt]

Just my take on the programming bit
I think there would be vast problems bringing AI (Artificial Intellegence) into a poker program and the 'Intellegence' is would be working out would constantly change. i.e. the players, no two are the same.
the best (in my opinion) would be basing decisions on probability by calculating the odds.
hence making the correct odds decision each time.
thats where the programs win. by not making daft mistakes us humans do.
but then it would be easier for us humans to control the computer as we would know how it then would react.
I'm new to this poker stuff thing, and it seems weather its legal or not some people use programs to play, i think there would be a flaw in it somewhere that would be exploitable.
just my take
(ex programmer java MSc and all that stuff)

[Gullanian]

I made a computer opponent that did the EV+ play every time and it sucked. Easily exploitable.

[MarkGritter]

[ QUOTE ]
I think even an optimal strategy (in a game theoretical sense) for poker will have couter strategies that beat the optimal strategy.

Any strategy to be called a single strategy should be fixed. It can be 'raise 30%/fold 70% at random against a 20/15 opponent given this and that' so it is allowed to differentiate between a lot of variables that any person or computer could access. But within this information the strategy should be fixed.

In that case I think by definition the optimal strategy will be one that is least exploitable/most profitable against the entire range of possible strategies. But in that range are a few (probably themselves very exploitable strategies) that will beat an optimal strategy.

[/ QUOTE ]

No, the game-theoretic strategy is, by definition, nonexploitable. A game-theoretic optimal strategy exists for poker, just as one does for checkers... we just don't know what it is.

The game-theoretic strategy might not be the "best" to play because it does not exploit your opponent's mistakes to the fullest.

Heads-up poker is a two person game with finitely many strategies for each player. The payoffs of these strategies are random but their expected value can be calculated. So in principle poker can be solved, just like checkers. (The difference is that the optimal strategy for checkers is pure--- no random decisions--- while the optimal strategy for poker is likely to be a mix.)

It is fairly easy today to solve real poker games for a single street. A long-term research effort like that applied to checkers should be able to solve some multi-street games within 20 years. (I think single-draw A-5 lowball is a real game that is within reach.)