Checkers solved

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Checkers solved

Post by sje » Thu Jul 19, 2007 6:38 pm

Jonathan Schaeffer and his group have solved checkers (draughts). The game is a draw with best play.

See: http://news.bbc.co.uk/2/hi/science/nature/6907018.stm

User avatar
George Tsavdaris
Posts: 1627
Joined: Thu Mar 09, 2006 11:35 am

Re: Checkers solved

Post by George Tsavdaris » Thu Jul 19, 2007 8:09 pm

sje wrote:Jonathan Schaeffer and his group have solved checkers (draughts). The game is a draw with best play.

See: http://news.bbc.co.uk/2/hi/science/nature/6907018.stm
Can they show us the proof? I doubt. :D

Personally i consider this as a valid proof although i haven't seen it and i will never see it in its entirety.

Really a great achievement!
I wonder about the details. Do you know any official statement from Schaeffer? I mean if you solve Checkers you should write a rather big paper or anyway present all the procedure with details. I would like to see all the details, for example how much disc space all these positions require, what exactly was the method etc.....
After his son's birth they've asked him:
"Is it a boy or girl?"
YES! He replied.....

IanO
Posts: 487
Joined: Wed Mar 08, 2006 8:45 pm
Location: Portland, OR
Contact:

Re: Checkers solved

Post by IanO » Thu Jul 19, 2007 8:12 pm

Outstanding!

Anyone know the technique used? From the BBC article, it could have been involved a Monte Carlo approach and/or pattern extraction from games.

I wonder what Dr. Schaeffer will work on for the next 20 years?

Ian

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Checkers solved

Post by wgarvin » Thu Jul 19, 2007 8:31 pm

I just saw this on Google News:
http://www.sciam.com/article.cfm?articl ... anID=sa007

It's fantastic. I had no idea they were so close to solving it. The last thing I read about it was they had solved one well known opening position ("White Doctor" I think).

I think they used a mixture of endgame databases, gigantic databases of middlegame positions with known GTVs, and a strategy-based "prover" that used both proof-number search and alpha-beta search to try and prove the GTV of specific positions.

Edit: I think this paper gives an overview of their approach: http://citeseer.ist.psu.edu/6903.html

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Checkers solved

Post by bob » Thu Jul 19, 2007 9:18 pm

IanO wrote:Outstanding!

Anyone know the technique used? From the BBC article, it could have been involved a Monte Carlo approach and/or pattern extraction from games.

I wonder what Dr. Schaeffer will work on for the next 20 years?

Ian
It was based on endgame databases + a deep opening search. They finally completed enough databases that they could get to it from the opening position for all possibilities.

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Checkers solved

Post by wgarvin » Thu Jul 19, 2007 9:29 pm

This IEEE spectrum article has a decent non-technical description of how they did it:
http://www.spectrum.ieee.org/jul07/5379

Mark
Posts: 216
Joined: Thu Mar 09, 2006 8:54 pm

Re: Checkers solved

Post by Mark » Thu Jul 19, 2007 10:50 pm

bob wrote:
IanO wrote:Outstanding!

Anyone know the technique used? From the BBC article, it could have been involved a Monte Carlo approach and/or pattern extraction from games.

I wonder what Dr. Schaeffer will work on for the next 20 years?

Ian
It was based on endgame databases + a deep opening search. They finally completed enough databases that they could get to it from the opening position for all possibilities.
Looks like when I reported checkers being solved in the General Topics forum in March I was just a few months early! At that time I must have stumbled onto their "beta website."

It was odd that Jonathan made such an effort to deny it back in March.

Regards,

Mark

Terry McCracken

Re: Checkers solved

Post by Terry McCracken » Thu Jul 19, 2007 11:43 pm

Mark wrote:
bob wrote:
IanO wrote:Outstanding!

Anyone know the technique used? From the BBC article, it could have been involved a Monte Carlo approach and/or pattern extraction from games.

I wonder what Dr. Schaeffer will work on for the next 20 years?

Ian
It was based on endgame databases + a deep opening search. They finally completed enough databases that they could get to it from the opening position for all possibilities.
Looks like when I reported checkers being solved in the General Topics forum in March I was just a few months early! At that time I must have stumbled onto their "beta website."

It was odd that Jonathan made such an effort to deny it back in March.

Regards,

Mark
It's not odd at all. I knew about it, but had to stay quiet. They had it solved but they had to run all kinds of proofs in case they were in error.
After it had been published could I mention it. But I didn't expect them to publish before next month. So you beat me to the punch.

Jonathan Schaeffer had 17+ years invested in this project, and it is his brainchild and announcing it too early could be very damaging.

I was requested not to mention it until it was published, not by Jonathan Schaeffer but by Martin Devenport, a friend of Jonathan's since they were kids.

Well, it's public knowledge now, and that site that was stumbled upon wasn't suppose to be up, and Jonathan told people it wasn't solved as that would really hurt him if it was spread around that it was when the final proofs weren't in and before publication.


Terry

Terry McCracken

Re: Checkers solved

Post by Terry McCracken » Thu Jul 19, 2007 11:52 pm

George Tsavdaris wrote:
sje wrote:Jonathan Schaeffer and his group have solved checkers (draughts). The game is a draw with best play.

See: http://news.bbc.co.uk/2/hi/science/nature/6907018.stm
Can they show us the proof? I doubt. :D

Personally i consider this as a valid proof although i haven't seen it and i will never see it in its entirety.

Really a great achievement!
I wonder about the details. Do you know any official statement from Schaeffer? I mean if you solve Checkers you should write a rather big paper or anyway present all the procedure with details. I would like to see all the details, for example how much disc space all these positions require, what exactly was the method etc.....
It's all been done. I was frustrated that I couldn't talk about it! Well requested by Jonathan Schaeffer's friend Martin Devenport. So I had to sit on my hands when I knew what was going on.

Keeping Secrets...
Terry

Mark
Posts: 216
Joined: Thu Mar 09, 2006 8:54 pm

Re: Checkers solved

Post by Mark » Fri Jul 20, 2007 12:20 am

Terry McCracken wrote:
Mark wrote:
bob wrote:
IanO wrote:Outstanding!

Anyone know the technique used? From the BBC article, it could have been involved a Monte Carlo approach and/or pattern extraction from games.

I wonder what Dr. Schaeffer will work on for the next 20 years?

Ian
It was based on endgame databases + a deep opening search. They finally completed enough databases that they could get to it from the opening position for all possibilities.
Looks like when I reported checkers being solved in the General Topics forum in March I was just a few months early! At that time I must have stumbled onto their "beta website."

It was odd that Jonathan made such an effort to deny it back in March.

Regards,

Mark
It's not odd at all. I knew about it, but had to stay quiet. They had it solved but they had to run all kinds of proofs in case they were in error.
After it had been published could I mention it. But I didn't expect them to publish before next month. So you beat me to the punch.

Jonathan Schaeffer had 17+ years invested in this project, and it is his brainchild and announcing it too early could be very damaging.

I was requested not to mention it until it was published, not by Jonathan Schaeffer but by Martin Devenport, a friend of Jonathan's since they were kids.

Well, it's public knowledge now, and that site that was stumbled upon wasn't suppose to be up, and Jonathan told people it wasn't solved as that would really hurt him if it was spread around that it was when the final proofs weren't in and before publication.


Terry
Actually, it was in June I posted my message, not March. Anyway, thanks for explaining this, Terry. That clears things up quite a bit.

To finish a 17+ year project to solve checkers is really an amazing accomplishment! Jonathan must be feeling pretty good now.

Regards,

Mark

Post Reply