Checkers solved

[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

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

Yes, I imagine Jonathan is on Cloud Nine today

Best,
Terry

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

[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

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

Yes, I imagine Jonathan is on Cloud Nine today

Best,
Terry

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

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

[Leto]

Congrats to humankind, Chess is next.

[Leto]

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

[SteveJ]

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]

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]

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