Checkers solved

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Terry McCracken

Re: Checkers solved

Post by Terry McCracken » Fri Jul 20, 2007 3:06 am

Mark wrote:
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
You stumbled upon it? Yes Martin knew in March..not me. I learned about it when you did. Or did you know in March as well? Then I talked to Martin, who talked to Jonathan, who talked to me again :lol:

Yes, I imagine Jonathan is on Cloud Nine today :D

Best,
Terry

P.S. I talked to Martin tonight...he's going to pick up Science tomorrow, and one for me, I hope :o :)

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

Re: Checkers solved

Post by Mark » Fri Jul 20, 2007 3:27 am

Terry McCracken wrote:
Mark wrote:
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
You stumbled upon it? Yes Martin knew in March..not me. I learned about it when you did. Or did you know in March as well? Then I talked to Martin, who talked to Jonathan, who talked to me again :lol:

Yes, I imagine Jonathan is on Cloud Nine today :D

Best,
Terry

P.S. I talked to Martin tonight...he's going to pick up Science tomorrow, and one for me, I hope :o :)
I was mistaken about the March date. Sounds like checkers was solved in late April and it was early June that I found out when I stumbled upon the "beta" website (from a link at Martin Fierz' Checkerboard website).

I'll try to pick up the July Science issue tomorrow.

Regards,

Mark

User avatar
Leto
Posts: 2028
Joined: Thu May 04, 2006 1:40 am
Location: Dune

Re: Checkers solved

Post by Leto » Fri Jul 20, 2007 3:51 am

Congrats to humankind, Chess is next.

User avatar
Leto
Posts: 2028
Joined: Thu May 04, 2006 1:40 am
Location: Dune

Re: Checkers solved

Post by Leto » Fri Jul 20, 2007 4:10 am

The proof is now online:
http://www.cs.ualberta.ca/~chinook/

SteveJ

Re: Checkers solved

Post by SteveJ » Fri Jul 20, 2007 5:05 am

The technique has been described in a paper that he and others published:

http://www.cs.ualberta.ca/~jonathan/Pap ... eckers.pdf

... an interesting read.

Next up for Dr. Schaeffer seems to be Poker. An interesting problem to solve. Unlike Checkers or Chess than are based on 'perfect information' (each player sees all the other pieces), poker has inperfect information. A new problem set!

http://www.cs.ualberta.ca/~games/poker/man-machine/

Steve

frankp
Posts: 216
Joined: Sun Mar 12, 2006 2:11 pm

Re: Checkers solved

Post by frankp » Fri Jul 20, 2007 9:15 am

Fantastic result for Schaeffer and his team.

Just to check I understand this: the secondary result 'black to move cannot win' is now also proved?

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

Re: Checkers solved

Post by wgarvin » Fri Jul 20, 2007 3:02 pm

frankp wrote:Just to check I understand this: the secondary result 'black to move cannot win' is now also proved?
From the initial position, and assuming perfect play by White, black can never win. They proved that the GTV of the initial position is a draw -- neither side can win unless the other side makes a mistake.

Note that since checkers is so drawish, high-level competitions use randomly-selected opening moves (where the first two moves by White and one move by Black are chosen at random, giving about 150? different "actual" starting positions for the game). The selected position is then played twice by the players, switching sides after the first game, to make it as fair as possible.

If I understand correctly, because of the randomly-selected moves there is still a slim possibility that players could defeat a perfect opponent, because one of those randomly-selected moves might be a non-GTV-conserving move (a forced mistake, allowing the player a chance to win). It would be interesting to see which of the random openings actually have non-drawn GTVs (my guess would be not very many?).

Post Reply