3 ms·

Checkers Is Solved: Perfect play by both sides leads to a draw

18 points by divia 19y ago

ivankirigin 19y ago
Now they just need to prove an algorithm for optimal style.
mynameishere 19y ago
They are still on book #79, "Mystery of the Sacred Stones", in the Choose Your Own Adventure series. Science marches on...
BrandonM 19y ago
Jonathan Schaeffer (the guy behind this project) gave a speech at this year's SIGCSE (computer science education) conference. The article says that artificial intelligence techniques were used to solve checkers, but it was really just brute force. He had a database of all possible 10-piece setups solved, and then he began iterating over all other positions. Of course, once a position reduced to one of the 10-piece positions, that particular game was solved. The guy actually seemed a bit nutty to me. The motivation for the whole endeavor was to demonstrate that his AI player (Chinook) was provably better than an amazing human checkers player by the name of Marion Tinsley. In a 45-year career, the man never lost a World Championship match, and he only ever lost 9 games (2 to Chinook). Do keep in mind that championship checkers matches are 39 games, meaning that he played thousands and thousands of games. Anyways, a PDF of his talk is available here: http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf . It was an interesting story, even if I thought the presenter was a bit strange.
- erik 19y ago
  I'm actually taking a class from Schaeffer at the moment. He is perhaps a bit odd, but so far he seems to be a decent professor.
  - BrandonM 19y ago
    Oh, he seemed like a great guy. He just seemed to be overzealous to accomplish a goal that really didn't seem (to me) to matter that much. When he said something along the lines of "Marion Tinsley is human, and humans make mistakes. Chinook will play perfectly after checkers is solved. Therefore, Chinook is better than Tinsley," I could almost hear "mad scientist" laughter. To me, a program that already knows the right answer and simply looks it up in a database is much less interesting than a human who arrives at a similar answer through reasoning and intuition, or even an AI program that uses heuristics and some kind of internal scoring mechanism. That's not even mentioning that I think a multi-year computation on something like solving checkers is really a (nearly) useless endeavor. Whose lives will be made better by this? Only in academia could such resources be directed at something with no tangible end value. I guess it's an accomplishment for Schaeffer, but to me it seems like anyone could throw a bunch of CPUs at a program that iterates over all possible checkers positions. I just can't imagine getting much satisfaction for such an accomplishment.

18 points by divia 19y ago

Now they just need to prove an algorithm for optimal style.

They are still on book #79, "Mystery of the Sacred Stones", in the Choose Your Own Adventure series. Science marches on...

BrandonM 19y ago

Jonathan Schaeffer (the guy behind this project) gave a speech at this year's SIGCSE (computer science education) conference. The article says that artificial intelligence techniques were used to solve checkers, but it was really just brute force. He had a database of all possible 10-piece setups solved, and then he began iterating over all other positions. Of course, once a position reduced to one of the 10-piece positions, that particular game was solved. The guy actually seemed a bit nutty to me. The motivation for the whole endeavor was to demonstrate that his AI player (Chinook) was provably better than an amazing human checkers player by the name of Marion Tinsley. In a 45-year career, the man never lost a World Championship match, and he only ever lost 9 games (2 to Chinook). Do keep in mind that championship checkers matches are 39 games, meaning that he played thousands and thousands of games. Anyways, a PDF of his talk is available here: http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf . It was an interesting story, even if I thought the presenter was a bit strange.

erik 19y ago
I'm actually taking a class from Schaeffer at the moment. He is perhaps a bit odd, but so far he seems to be a decent professor.
- BrandonM 19y ago
  Oh, he seemed like a great guy. He just seemed to be overzealous to accomplish a goal that really didn't seem (to me) to matter that much. When he said something along the lines of "Marion Tinsley is human, and humans make mistakes. Chinook will play perfectly after checkers is solved. Therefore, Chinook is better than Tinsley," I could almost hear "mad scientist" laughter. To me, a program that already knows the right answer and simply looks it up in a database is much less interesting than a human who arrives at a similar answer through reasoning and intuition, or even an AI program that uses heuristics and some kind of internal scoring mechanism. That's not even mentioning that I think a multi-year computation on something like solving checkers is really a (nearly) useless endeavor. Whose lives will be made better by this? Only in academia could such resources be directed at something with no tangible end value. I guess it's an accomplishment for Schaeffer, but to me it seems like anyone could throw a bunch of CPUs at a program that iterates over all possible checkers positions. I just can't imagine getting much satisfaction for such an accomplishment.