CHUD.com Community › Forums › CULTURE, HUMOR, & FREE FORM › Misc. Culture › Checkers Is Solved
New Posts  All Forums:Forum Nav:

Checkers Is Solved

post #1 of 13
9/14/07 at 12:21pm
Thread Starter 
On to Hi Ho! Cherry-O, science:

http://www.sciencemag.org/cgi/conten.../317/5844/1518

Quote:
The game of checkers has roughly 500 billion billion possible positions (5 x 10^20). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: Perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times as complex as Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as Deep Blue for chess. Solving a game takes this to the next level by replacing the heuristics with perfection.
Quote:
Conclusion. What is the scientific significance of this result? The early research was devoted to developing Chinook and demonstrating superhuman play in checkers, a milestone that predated the Deep Blue success in chess. The project has been a marriage of research in AI and parallel computing, with contributions made in both of these areas. This research has been used by a bioinformatics company; real-time access of very large data sets for use in parallel search is as relevant for solving a game as it is for biological computations.

The checkers computation pushes the boundary of what can be achieved by search-intensive algorithms. It provides compelling evidence of the power of limited-knowledge approaches to artificial intelligence. Deep search implicitly uncovers knowledge. Furthermore, search algorithms are well poised to take advantage of the increase in on-chip parallelism that multicore computing will soon offer. Search-intensive approaches to AI will play an increasingly important role in the evolution of the field.

With checkers finished, the obvious question is whether chess is solvable. Checkers has roughly the square root of the number of positions in chess (somewhere in the 10^40 to 10^50 range). Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology. The disk-flipping game of Othello is the next popular game that is likely to be solved, but it will require considerably more resources than were needed to solve checkers.
With this in my back pocket my nine-year-old niece is fucking toast. And so's her grampa, who, in a display of questionable ethics (and with some obvious coaching from said niece), took me 2 out of 3 last summer knowing I was several beers ahead.
Reply
post #2 of 13
9/14/07 at 12:39pm
A strange game. The only winning move is not to play.
Reply
post #3 of 13
9/14/07 at 12:43pm
Quote:
Originally Posted by Alan "Nordling" Cerny
A strange game. The only winning move is not to play.
Or, you could always go Kobayashi Maru on their ass and throw a checker piece into their mouth and watch as they choke. When their hand leaves the table you win.

You should have someone give them CPR after the win or it gets bumped up to manslaughter or 2nd degree homicide in some states.
Reply
post #4 of 13
9/14/07 at 12:43pm
I can't access the article, do you have an account or did you get to it another way?
Reply
post #5 of 13
9/14/07 at 12:57pm
Thread Starter 
Quote:
Originally Posted by englebert
I can't access the article, do you have an account or did you get to it another way?
Well, crap. Really? I'm a AAAS member, but I thought it was public access there... Lemme see.

Yeah, I'm an idiot. Science is only available online to members. Got a hundred bucks? Gets you 51 issues! The very curious can check out today's issue at a library, most likely a university one's your best bet.

Here's the authors' site, though: http://www.cs.ualberta.ca/~chinook/
Reply
post #6 of 13
9/14/07 at 1:19pm
ABC News has an article on it:

http://abcnews.go.com/Technology/sto...3394382&page=1
Reply
post #7 of 13
9/14/07 at 1:36pm
Quote:
Originally Posted by Trav McGee
Well, crap. Really? I'm a AAAS member, but I thought it was public access there... Lemme see.

Yeah, I'm an idiot. Science is only available online to members. Got a hundred bucks? Gets you 51 issues! The very curious can check out today's issue at a library, most likely a university one's your best bet.

Here's the authors' site, though: http://www.cs.ualberta.ca/~chinook/
He has the paper on his website, thanks. I wouldn't be surprised if I could access the article through Georgia Tech, but I'm too lazy to figure it out. Here is the link to the research article for any computer science nerds.
Reply
post #8 of 13
9/14/07 at 2:33pm
Quote:
This is the most challenging popular game to be solved to date, roughly one million times as complex as Connect Four.
Connect Four is for losers. Now back to removing the funny bone without touching the sides. Dammit!
Reply
post #9 of 13
9/14/07 at 5:26pm
While this is a cool thing, doesn't this seem like kind of a waste of resources? I mean, we got these super smart computers and they're solving Checkers?! Don't we have planets to go to and holodecks to make and diseases to cure?
Reply
post #10 of 13
9/14/07 at 5:29pm
Quote:
Originally Posted by Doc Happenin
While this is a cool thing, doesn't this seem like kind of a waste of resources? I mean, we got these super smart computers and they're solving Checkers?! Don't we have planets to go to and holodecks to make and diseases to cure?
It's all about developing more sophisticated AI techniques, which generally have more useful applications than you would expect. Games like Chess, Checkers, Othello are used to solve problems in developing decision making capability in software. They are played in very constrained environments, which allows the problem to be first solved in simpler terms until the techniques can be applied to real world environments that are practically infinite in their possibilities.
Reply
post #11 of 13
9/14/07 at 5:38pm
Thread Starter 
Quote:
Originally Posted by Doc Happenin
While this is a cool thing, doesn't this seem like kind of a waste of resources? I mean, we got these super smart computers and they're solving Checkers?! Don't we have planets to go to and holodecks to make and diseases to cure?
First two paragraphs of the article's Conclusion I posted up there fairly well sums it up.

The ABC story says they're also going for Poker. While that's definitely a skill game, and somehow programming AI to convincingly bluff (or call one) would be amazing, there's still a random element involved that games like Checkers, Chess, Othello etc. aren't saddled with. I wonder what their goal there is, other than a Turing Test kind of simulation of play.
Reply
post #12 of 13
9/14/07 at 5:44pm
Finally, after centuries of working at it we can all finally fucking stop playing. CHECKERS IS SOLVED, EVERYBODY!
Reply
post #13 of 13
9/14/07 at 5:49pm
I thought the idea of Checkers being solved meant that they were able to enumerate every possible configuration of moves, which is massive. Then they were able to evaluate the move tree to determine the best move possible in every turn. This is no easy feat in terms of computation or space requirements. So it still serves to further the field of AI. Research is almost always done with applications and further research in mind, so I doubt Checkers was their ultimate goal. I might read the paper later and find out what they think those might be.
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Misc. Culture
CHUD.com Community › Forums › CULTURE, HUMOR, & FREE FORM › Misc. Culture › Checkers Is Solved