Checkers solved

[sje]

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

[George Tsavdaris]

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.

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.....

[IanO]

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]

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]

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]

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

[Mark]

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]

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]

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.

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]

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