|
Alberta (Canada) – Canadian researchers have created an invincible Checkers program that can beat any human. Jonathan Schaeffer from the University of Alberta began working on his “Chinook” program 18 years ago and now claims to have mathematically solved the game.
Schaeffer published his results in the journal Science and documents how he had dozens of computers compute through billions possible moves. Chinook now has a database of possible moves and countermoves which, according to Schaeffer, can only allow a human to draw under the best possible circumstances.
Unconvinced? You can now test your skills against Chinook because Schaeffer has put the program online here . Of course there isn’t much fun to a playing Checkers when you know you are about to lose, so the scientist has turned his computers onto a much more lofty goal … beating humans at Poker.
Source: http://www.tgdaily.com/content/view/33003/98/
Play (scroll down): http://www.cs.ualberta.ca/~chinook/play/index.html
|
Korea (South)11577 Posts
|
|
|
poker? rofl thats impossible lol
|
wow, what a waste of 18 years. -_-
|
Checkers has far fewer possible outcomes compared to games like Chess or Go, so it's not surprising that they could develop an unbeatable AI.
|
have one computer play white. have the other play black in another window. you know what i'm getting at...
|
|
|
On July 21 2007 14:24 Jyvblamo wrote:
Checkers has far fewer possible outcomes compared to games like Chess or Go, so it's not surprising that they could develop an unbeatable AI.
There are very good AI's for Chess, but not even a mediocre one for Go (afaik).
|
Cayman Islands24199 Posts
open 2 games with this comp, one in which you go first, one in which comp goes first, then mirror.
omfg?!
|
I saw something about this on Sirlin.net
http://www.sirlin.net/archive/checkers-solved/#comments
Too bad poker has way too many variables and cannot be mathematically solved.
Also Chess "I heard somewhere (lost the source, sorry) that if every particle in the universe could somehow be used to compute one operation per second and that all the particles in the universe were used in a massively parallel computer that analyzed all possible positions in Chess, it would take longer than the current estimated age of the universe to finish. So yeah, pretty long."
|
If 2 of these comps play each other, they will just draw. For some games it matters who go first, but not checkers apparently.
|
On July 21 2007 14:30 Pika Chu wrote:Show nested quote +On July 21 2007 14:24 Jyvblamo wrote:
Checkers has far fewer possible outcomes compared to games like Chess or Go, so it's not surprising that they could develop an unbeatable AI. There are very good AI's for Chess, but not even a mediocre one for Go (afaik).
I know that, the point is both those games have incredibly greater numbers of possible moves/outcomes compared to Checkers. I didn't say Chess was comparable to Go in terms of possible games (it's not).
|
On July 21 2007 14:18 sushiman wrote:
wow, what a waste of 18 years. -_-
to publish a paper in science that's worth it
guaranteed professorship for the rest of his life
|
Most of us have been playing Starcraft for 9-10 years. Its not that much a difference.
Wow, also on that site it lists other games that have been solved. My Gf thinks shes the shit at connect 4, I'll rape her every time now.
http://homepages.cwi.nl/~tromp/c4/c4.html
|
Wtf How did I lose?
It wouldn't let me move any more pieces.
|
Calgary25979 Posts
This has been solved for awhile, no?
|
Canada7170 Posts
Haha I live in Calgary and this was on all the news channels at night.
HUGE breakthrough. *cough*
I'd think that next on the list is Monopoly; a "best of" set to offset luck issues. Odds and implied odds are very important. Also, a computer could easily understand the exact values of a proposed trade in the long term better than any human.
|
|
|
On July 21 2007 15:07 CharlieMurphy wrote:Wtf How did I lose? It wouldn't let me move any more pieces.
captures are forced in checkers=/ you only have 1 option, capture the white piece, at which point he will counter-capture 3 of yours and it spirals down from there
|
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad.
|
On July 21 2007 14:24 IIICodeIIIIIII wrote:
have one computer play white. have the other play black in another window. you know what i'm getting at...
They draw, afaik there is always a possibility for draw and the computer will find it. So only a human, who makes mistakes, can lose ... and there is no human player who makes no mistakes.
|
On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad.
What?
|
On July 21 2007 18:36 Maenander wrote:Show nested quote +On July 21 2007 14:24 IIICodeIIIIIII wrote:
have one computer play white. have the other play black in another window. you know what i'm getting at... They draw, afaik there is always a possibility for draw and the computer will find it. So only a human, who makes mistakes, can lose ... and there is no human player who makes no mistakes.
It should be easy to draw with the computer since you just have to memorize a drawing game and then play it since the computer will always play the same (best) moves in response to yours.
|
AI Checkers vs Cheat Code(s)
|
On July 21 2007 18:37 mahnini wrote:Show nested quote +On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What?
brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise)
So in a nut-shell, a dumb but working method.
|
IIRC Go would eat any computer that was competent at Chess/Checkers alive, or is my memory poor?
|
|
|
i made my first move then it made some bullshit up about me making multiple moves...
program noob dodger
|
On July 21 2007 16:02 JeeJee wrote:Show nested quote +On July 21 2007 15:07 CharlieMurphy wrote:Wtf How did I lose? It wouldn't let me move any more pieces. captures are forced in checkers=/ you only have 1 option, capture the white piece, at which point he will counter-capture 3 of yours and it spirals down from there
Triple jump to the face. King me.
|
On July 22 2007 01:13 haduken wrote:Show nested quote +On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method.
Brute force means trying every possible combination. This means that every move in every possible game has been stored in a database, the trick is just to follow the path leading to the best outcome.
Similarly, there is an algorithm for Tic Tac Toe which will always lead to a draw (or a win if your opponent makes a mistake).
|
I believe chess can also be solved, but there are too much possilbe positions, I think the number was smth like 10^40
|
Germany2896 Posts
And they only solved the simple version of checkers where the queen (or whatever it is called in english) can only move one step. but o/c checkers<chess<go in fields of ai programming. For solving chess and go completely you probably need a quantum computer. But unlinke someone above stated it is not necessary to calculate every move. There are some tricks which allow you to leave large parts of the tree out, without missing any chances to win/draw.
|
|
|
On July 22 2007 01:24 HaXxorIzed wrote:
IIRC Go would eat any computer that was competent at Chess/Checkers alive, or is my memory poor?
A computer that's competent at Go is a pretty rare thing, there's so many possibilities they have trouble comprehending it. And yes, Chess is "solvable" the same way Checkers is, there's just a hell of a lot more permutations (in the order of 10^40 or even more, as said). Go on the other hand, while still "solvable", you're looking at 10^600 or even more iirc.
|
Bill307
Canada9103 Posts
On July 22 2007 13:24 Jathin wrote:Devising algorithms that leave portions of the tree out aren't actively used I don't think. I think I read somewhere that it's easier/more fool-proof/just as efficient to do brute-force (or a modification of the such, like brute force after a certain point) http://en.wikipedia.org/wiki/Chess_computers
You heard wrong. Heuristics are crucially important to chess-playing programs.
Edit: I read parts of the article and I think what they're saying is, it's a bad idea to try to prune branches from the tree without at least searching part-way down those branches first. But after searching part-way they may see that one branch is (almost) definitely going to lead to a worse position than another, and so they don't need to analyse the rest of that branch. That's basically the effect of doing alpha-beta pruning. Chess programs employ other heuristics, too, but I am not familiar with them.
On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad.
It wasn't completely brute-force. Chinook first figured out that of the 5 * 10^20 possible positions in checkers, only 10^14 needed to be analysed. Then it brute-forced those 10^14 positions.
(It didn't need to analyse every move because many moves lead to losing positions, and so there's no point in analysing them when Chinook will never play those moves.)
|
On July 21 2007 23:14 gravity wrote:Show nested quote +On July 21 2007 18:36 Maenander wrote:On July 21 2007 14:24 IIICodeIIIIIII wrote:
have one computer play white. have the other play black in another window. you know what i'm getting at... They draw, afaik there is always a possibility for draw and the computer will find it. So only a human, who makes mistakes, can lose ... and there is no human player who makes no mistakes. It should be easy to draw with the computer since you just have to memorize a drawing game and then play it since the computer will always play the same (best) moves in response to yours.
Yeah and it is just as easy to let the program vary its moves by some kind of random number generator. I think it is likely there are different ways to reach a non-losable position for the program in most situations ^^
|
Bill307
Canada9103 Posts
On July 21 2007 23:14 gravity wrote:Show nested quote +On July 21 2007 18:36 Maenander wrote:On July 21 2007 14:24 IIICodeIIIIIII wrote:
have one computer play white. have the other play black in another window. you know what i'm getting at... They draw, afaik there is always a possibility for draw and the computer will find it. So only a human, who makes mistakes, can lose ... and there is no human player who makes no mistakes. It should be easy to draw with the computer since you just have to memorize a drawing game and then play it since the computer will always play the same (best) moves in response to yours.
True but, apparently in professional tournaments the first 3 moves are selected at random, so you would have to memorize a draw for each possible starting position.
Furthermore, what if the computer can take more than one move that leads to a draw? Then it might pick one at random.
|
Bill307
Canada9103 Posts
What I find more amazing than this achievement, is the story of Marion Tinsley, the former world checkers champion and an unimaginably strong checkers player.
Referring to a match between Tinsley and Chinook in 1994 (at which time Chinook had opening and ending databases but had not solved the mid-game of checkers), I found the following quote:
Also present in the room is a mild-looking retired professor of mathematics. He wears a light blue suit and tie-pin with "Jesus" written on it in colored rhinestones. He doesn't look like the sort of man to acquire a nickname like "The Terrible Tinsley." But Marion Tinsley's benign exterior cloaks a formidable intellect. At age 27, he was the best checkers player in the world, and by all accounts his game has only improved during the forty intervening years. His record is unparalleled in checkers, chess, or any other game of skill.
To get an idea of the embarrassingly wide margin by which Tinsley surpasses his nearest competition, consider his defense of the world title in 1989 against the challenger Paul Davis. Tinsley drew 23 games, won 9, and lost 0. During his forty-year reign, and over the course of over a thousand games of tournament play, Tinsley has lost exactly nine games. It's hard to come up with anyone who has so thoroughly dominated a field of human endeavor for such a long stretch of time.
http://www.math.wisc.edu/~propp/chinook.html
Just to reiterate that, his last human challenger lost 9 games out of 32 against Tinsley, whereas Tinsley has lost 9 games out of one thousand throughout his entire career.
I also liked this post on Slashdot:
Show nested quote +Hasn't it always been fairly easy for a computer to beat a human at checkers? I don't recall it making the news the first time deep blue beat the world grand master at checkers. No. Schaeffer has a book out ("One Jump Ahead") about writing Chinook. He thought the same when he started, but the project got rapidly far harder than he thought. It helped that the existing human champion (Marion Tinsley) was literally as close to perfection as any human has ever been at any game- they exhaustively studied every professional game he ever played and found something like a grand total of 10 actual mistakes in a 40 year career. It's a very sad book in many ways- there was a lot of tension between certain members of the team and you realized that professional checkers was dying rapidly. Tinsley and Schaffer set up a world championship rematch between them (Tinsely won the first one) and Tinsely pulled out after six games saying he felt ill. He checked himself into the hospital, was diagnosed with some aggressive form of cancer and died a few months later. Schaeffer basically retired Chinook from human tournaments since nobody else was even remotely close to Tinsley. It didn't make many headlines because everyone knows checkers is easy. Except that they are wrong- it's not.
|
On July 22 2007 01:13 haduken wrote:Show nested quote +On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method.
I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it.
|
On July 21 2007 14:49 LeoTheLion wrote:to publish a paper in science that's worth it guaranteed professorship for the rest of his life
Science is probably the most respected journal in the scientific world/industry. another top one is Nature.
this paper might well be a stepping stone for this professor to obtain tenure at his institution, or to move to another institution that has better academic assets available for furthering research
it is by no means a "shame" or "waste" to publish in Science - if only i had that kind of opportunity in my research heh
|
Bill307
Canada9103 Posts
On July 22 2007 14:30 mahnini wrote:Show nested quote +On July 22 2007 01:13 haduken wrote:On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it.
Well, the alternative for "solving" checkers would be to come up with a mathematical proof that proves the outcome of the game is always a draw, given that both players always make the best possible move on each turn.
Here is a simple example of a proof that solves a game: suppose you have a non-random 2-player game where:
a) it is impossible to draw: the game always ends in a win or a loss; and
b) player 1 can choose to pass on his first move (and no other moves can be passed on).
Then it is easy to prove that player 1 always wins, given that both players always make the best move. Because it is impossible to draw and the game has no randomness, we know that either the first person to move will win, or the second person to move will win. Because player 1 can choose whether he plays first or second, he can just choose whichever case always leads to a win. Therefore player 1 always wins.
Of course, sometimes it must be veritably impossible to come up with a proof like this, and so the only realistic way to solve the game is to brute-force every position, or prove that only a subset of those positions need to be analysed and then brute-force said subset (which is what the Chinook team did).
|
On July 22 2007 14:42 Bill307 wrote:Show nested quote +On July 22 2007 14:30 mahnini wrote:On July 22 2007 01:13 haduken wrote:On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it. Well, the alternative for "solving" checkers would be to come up with a mathematical proof that proves the outcome of the game is always a draw, given that both players always make the best possible move on each turn. Here is a simple example of a proof that solves a game: suppose you have a non-random 2-player game where: a) it is impossible to draw: the game always ends in a win or a loss; and b) player 1 can choose to pass on his first move (and no other moves can be passed on). Then it is easy to prove that player 1 always wins, given that both players always make the best move. Because it is impossible to draw and the game has no randomness, we know that either the first person to move will win, or the second person to move will win. Because player 1 can choose whether he plays first or second, he can just choose whichever case always leads to a win. Therefore player 1 always wins. Of course, sometimes it must be veritably impossible to come up with a proof like this, and so the only realistic way to solve the game is to brute-force every position, or prove that only a subset of those positions need to be analysed and then brute-force said subset (which is what the Chinook team did).
I see what you are saying, but wouldn't you have to prove both a and b? How would you prove a and b without playing out every possible move?
|
A and B are the rules of the game
|
On July 22 2007 14:52 mahnini wrote:Show nested quote +On July 22 2007 14:42 Bill307 wrote:On July 22 2007 14:30 mahnini wrote:On July 22 2007 01:13 haduken wrote:On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it. Well, the alternative for "solving" checkers would be to come up with a mathematical proof that proves the outcome of the game is always a draw, given that both players always make the best possible move on each turn. Here is a simple example of a proof that solves a game: suppose you have a non-random 2-player game where: a) it is impossible to draw: the game always ends in a win or a loss; and b) player 1 can choose to pass on his first move (and no other moves can be passed on). Then it is easy to prove that player 1 always wins, given that both players always make the best move. Because it is impossible to draw and the game has no randomness, we know that either the first person to move will win, or the second person to move will win. Because player 1 can choose whether he plays first or second, he can just choose whichever case always leads to a win. Therefore player 1 always wins. Of course, sometimes it must be veritably impossible to come up with a proof like this, and so the only realistic way to solve the game is to brute-force every position, or prove that only a subset of those positions need to be analysed and then brute-force said subset (which is what the Chinook team did). I see what you are saying, but wouldn't you have to prove both a and b? How would you prove a and b without playing out every possible move?
Read this book, it will change the way you think about life, and stretch your mind!
http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/0073523402
|
testpat
United States565 Posts
Terminology is going to be bad here, hopefully the examples will be better.
Easiest: If in part of a tree, you evaluate one move to a win/loss, you don't need to search any other moves in that portion of the tree. This is a major source for pruning min max trees.
You can also do some pruning based on the knowing the states of the games. For example.
You can prune parts of trees without solving them if you can show that the subtree is suboptimal to another option. In chess, you can prune all trees that promote pawns into bishops & rooks because all future moves will be a subset of queen. However, you must analyze trees that promote into knights.
You can also prune paths that lead to solved states if the current path is a superset of a solved state. For example, if you know that a certain checkers position leads to a win for white with no kings, and you are evaluating a state that is the same except one of the white pieces is a king.
(However, this requires knowing/evaluating that the king cannot be forced into a move that regular piece couldn't make).
|
So this pretty much kills checkers, feels meaningless to play a game when you know theres an optimal strategy 
Luckily it's pretty much impossible to do for more advanced games, since the number of available strategies are enourmous compared to the ones in checkers.
iirc some math professor estimated the number of strategies in chess to 10^120
developing algorithmes for optimizing the play get's a lot more interesting in such games
|
MyLostTemple
United States2921 Posts
lets get a computer that can own at difficult game ;o
|
|
|
|
|
|
EPT![[image loading]](http://i8.tinypic.com/66lh1t3.jpg)
