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?

[6471849653]

[ QUOTE ]
I do know the difference between perfect information and imperfect information games.

[/ QUOTE ]

Games like chess are games of incomplete information and the trees are many more and huge than they are at poker that's a game of complete information as the trees are only up to the showdown and there's only a couple of different simple moves to think about every street; it takes a second to compute the best line up to the showdown in a poker game while one does never get there in a chess game at this time.

What one sees with the eyes is not complete information; and what one doesn't see with the eyes is not incomplete information. When both sides see as much it's a game of complete or non-complete information depending if it can be calculated up to the end and say the line that was taken was the best all the way to the end.

P.S. If the computer wins or draws the heads up limit holdem match vs. the two pros on Monday/Tuesday (next week; http://campustechnology.com/articles/49023/ ), it could be because their software graphics are so bad that it's hard to play one's best game. I know from experience, though I have never played against a bot I couldn't beat huge both heads up and shorthanded.

[6471849653]

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


[/ QUOTE ]

The more players there are the less the bots lose.