6 ms·

How Checkers Was Solved

158 points by panic 9y ago

kevinwang 9y ago
That was one of the greatest stories I've ever heard
- viblo 9y ago
  If you like this story I suggest you take a look at the book "One Jump Ahead" by Schaeffer for a lot more in depth view!
  - RJIb8RBYxzAMX9u 9y ago
    There's also Blondie24[0], which's got a pretty humorous backstory to its namesake. [0] https://www.amazon.com/dp/1558607838/ https://www.amazon.com/dp/1558607838/
    - mholmes680 9y ago
      can second this recommendation. good, quick reading.
- lmm 9y ago
  You might like The Master of Go - humans, but a similar arc of the master in fading health facing an opponent for whom the game means something quite different.
WalterGR 9y ago
I had no idea that there was once a real-life incident reminiscent of the film War Games! [Solving chess] took Schaeffer harnessing computers all over the world, drawing on and expanding his expertise in parallel computing. He conscripted machines everywhere from Switzerland to Lawrence Livermore National Laboratory, a major Department of Energy facility that often deals with nuclear weapons. “There was somebody else there [running a program] called BOMB and I was running checkers programs,” Schaeffer told me. “It was a very strange situation. Security should have been concerned.” And they were. They paid him a visit after discovering gigabytes of data flowing out of a national lab to Edmonton, Alberta. (edit: add the remainder of the second paragraph.)
trm42 9y ago
Awesome story and well written.
jpeanuts 9y ago
A truly fascinating story. I recall reading another version with an additional detail: after Checkers was solved Schaeffer evaluated every recorded game Tinsley had played in his life - and determined that there were only a handful of moves that he ever made in competition that were not perfect (in the sense of perfect play). The vast majority of the time, if you were playing Tinsley, you literally could not possibly win.
blahedo 9y ago
It's good, really, that this article focussed on Tinsley. I saw a talk by Schaeffer about ten years ago, just as he was finishing up solving checkers, and it was an astonishingly depressing talk. He invested his whole life—decades—as I recall his marriage failed partially as a result of his obsession with this—on what, in the end, was a lookup table. There was a lot of neat engineering he had to do along the way (storage, parallel work) but that's not what he cared about: he cared that he had solved checkers. Were there any insights about patterns that could be induced, maybe to teach humans how to do analysis or to learn some interesting mathematical fact about the graph structure of the board? No—you just see what the board state is, and look it up in the database to tell you the next move. I can't even tell you how demotivational this speech was.
- Pulcinella 9y ago
  Sometimes I fear that this will be the end result of brain research. A vast table that says: when these neurons are activated in this pattern, it means happiness. When these neurons are activated in this pattern, it means the brain is perceiving a tree. We will understand the brain and consciousness and it will be completely unenlightening... :(
  - degenerate 9y ago
    There's no way to map "what is the meaning of life?" to a table, so you'll never have that problem. As long as our universe and existence isn't 100% solved, the human brain will never be solved!
    - fiblye 9y ago
      It's been a few years, but I recall there being research into 100% mapping out crab or ant behavior and it was getting to a point of being quite accurate. Mammal brains have a few extra layers of complexity, but none of those layers involve magic. If ever we get around to "solving" one animal's brain, it shows that others can be as well.
      - 9y ago
dargopolis 9y ago
Having read Jonathan Schaeffer’s great book One Jump Ahead, I couldn’t help feeling that this article was a (well-written) book report which just barely mentions its primary source. Nice summary, but read the original. I haven’t read the second edition which apparently includes the follow-up story of solving the game, but I found the first edition very compelling. I wonder if the reporter was following the recent Deepmind/U of Alberta news and then came across the checkers story. Disclaimer: I was in Jonathan’s compiler course 30 years ago, prior to Chinook.
joshvm 9y ago
A great recent documentary on Checkers is King Me (trailer here; https://www.youtube.com/watch?v=Eh8wyKabQiY https://www.youtube.com/watch?v=Eh8wyKabQiY). I say that as someone who is terrible at the game and doesn't enjoy playing it. One of the players it features is Ron King, who is currently one of the strongest Checkers players. He holds the record for playing (and beating) 385 people simultaneously, though I believe he was beaten by Tinsley. Also his trash talking is fantastic.
Houshalter 9y ago
There is a fantastic story on the first checkers AI here: http://relprime.com/chinook/ http://relprime.com/chinook/

158 points by panic 9y ago

kevinwang 9y ago

That was one of the greatest stories I've ever heard

viblo 9y ago
If you like this story I suggest you take a look at the book "One Jump Ahead" by Schaeffer for a lot more in depth view!
- RJIb8RBYxzAMX9u 9y ago
  There's also Blondie24[0], which's got a pretty humorous backstory to its namesake. [0] https://www.amazon.com/dp/1558607838/ https://www.amazon.com/dp/1558607838/
  - mholmes680 9y ago
    can second this recommendation. good, quick reading.
lmm 9y ago
You might like The Master of Go - humans, but a similar arc of the master in fading health facing an opponent for whom the game means something quite different.

WalterGR 9y ago

I had no idea that there was once a real-life incident reminiscent of the film War Games! [Solving chess] took Schaeffer harnessing computers all over the world, drawing on and expanding his expertise in parallel computing. He conscripted machines everywhere from Switzerland to Lawrence Livermore National Laboratory, a major Department of Energy facility that often deals with nuclear weapons. “There was somebody else there [running a program] called BOMB and I was running checkers programs,” Schaeffer told me. “It was a very strange situation. Security should have been concerned.” And they were. They paid him a visit after discovering gigabytes of data flowing out of a national lab to Edmonton, Alberta. (edit: add the remainder of the second paragraph.)

trm42 9y ago

Awesome story and well written.

jpeanuts 9y ago

A truly fascinating story. I recall reading another version with an additional detail: after Checkers was solved Schaeffer evaluated every recorded game Tinsley had played in his life - and determined that there were only a handful of moves that he ever made in competition that were not perfect (in the sense of perfect play). The vast majority of the time, if you were playing Tinsley, you literally could not possibly win.

blahedo 9y ago

It's good, really, that this article focussed on Tinsley. I saw a talk by Schaeffer about ten years ago, just as he was finishing up solving checkers, and it was an astonishingly depressing talk. He invested his whole life—decades—as I recall his marriage failed partially as a result of his obsession with this—on what, in the end, was a lookup table. There was a lot of neat engineering he had to do along the way (storage, parallel work) but that's not what he cared about: he cared that he had solved checkers. Were there any insights about patterns that could be induced, maybe to teach humans how to do analysis or to learn some interesting mathematical fact about the graph structure of the board? No—you just see what the board state is, and look it up in the database to tell you the next move. I can't even tell you how demotivational this speech was.

Pulcinella 9y ago
Sometimes I fear that this will be the end result of brain research. A vast table that says: when these neurons are activated in this pattern, it means happiness. When these neurons are activated in this pattern, it means the brain is perceiving a tree. We will understand the brain and consciousness and it will be completely unenlightening... :(
- degenerate 9y ago
  There's no way to map "what is the meaning of life?" to a table, so you'll never have that problem. As long as our universe and existence isn't 100% solved, the human brain will never be solved!
  - fiblye 9y ago
    It's been a few years, but I recall there being research into 100% mapping out crab or ant behavior and it was getting to a point of being quite accurate. Mammal brains have a few extra layers of complexity, but none of those layers involve magic. If ever we get around to "solving" one animal's brain, it shows that others can be as well.
    - 9y ago

dargopolis 9y ago

Having read Jonathan Schaeffer’s great book One Jump Ahead, I couldn’t help feeling that this article was a (well-written) book report which just barely mentions its primary source. Nice summary, but read the original. I haven’t read the second edition which apparently includes the follow-up story of solving the game, but I found the first edition very compelling. I wonder if the reporter was following the recent Deepmind/U of Alberta news and then came across the checkers story. Disclaimer: I was in Jonathan’s compiler course 30 years ago, prior to Chinook.

joshvm 9y ago

A great recent documentary on Checkers is King Me (trailer here; https://www.youtube.com/watch?v=Eh8wyKabQiY https://www.youtube.com/watch?v=Eh8wyKabQiY). I say that as someone who is terrible at the game and doesn't enjoy playing it. One of the players it features is Ron King, who is currently one of the strongest Checkers players. He holds the record for playing (and beating) 385 people simultaneously, though I believe he was beaten by Tinsley. Also his trash talking is fantastic.

Houshalter 9y ago

There is a fantastic story on the first checkers AI here: http://relprime.com/chinook/ http://relprime.com/chinook/