Time for AI to cross the human range in English draughts

Updated 26 Oct 2020

AI progress in English draughts performance crossed the following ranges in the following times:

RangeStartEndDuration (years)
First attempt to beginner level1951~1956, <1961~4, <10
Beginner to superhuman~1956, <19611994~38, >33
Above superhuman19942007*13*
* treating perfect play as the end of progress, though progress could potentially be made in performing better against imperfect play.

Details

Metric

‘English Draughts’ is a popular variety of draughts, or checkers.

Here we look at direct success of AI in beating human players, rather than measuring humans and AI on a separate metric of strength.

Data

Data here comes mostly from Wikipedia. We found several discrepancies in Wikipedia’s accounts of these events, so consider the remaining data to be somewhat unreliable.

AI achievement of human milestones

Earliest attempt

According to Wikipedia, the first checkers program was run in 1951.1

Beginner level

There seems to be some ambiguity around the timing and performance of Arthur Samuel’s early draughts programs, but it appears that he worked on them from around 1952. In 1956, he demonstrated a program on television. 2 It is unclear how good the program’s play was, but it is said to have resulted in a fifteen-point rise in the stock price of IBM when demonstrated to IBM shareholders, seemingly at around that time. This weakly suggests that the program played at at least beginner level.

In 1962 Samuel’s program apparently beat an ambiguously skilled player who would by four-years later become a state champion in Connecticut.3 Thus progress was definitely beyond beginner level by 1962.

Superhuman level

In 1994, computer program Chinook drew six times against world champion Marius Tinsley, before Tinsley withdrew due to pancreatic cancer and Chinook officially won.4 Thus Chinook appears to have been close to as good as the best player in 1994.

End of progress

In 2007 checkers was ‘weakly solved’, which is to say that perfect play guaranteeing a draw for both sides from the start of the game is known, from the starting state5 (this does not imply that if someone plays imperfectly, perfect moves following this are known).6 This is not the best possible performance by all measures, since further progress could presumably be made on reliably beating worse players.

Times for AI to cross human-relative ranges 

Given the above dates, we have:

RangeStartEndDuration (years)
First attempt to beginner level1951~1956, <1961~4, <10
Beginner to superhuman~1956, <19611994~38, >33
Above superhuman19942007*13*
* treating perfect play as the end of progress, though progress could potentially be made in performing better against imperfect play.

Notes

  1. “The first English draughts computer program was written by Christopher Strachey, M.A. at the National Physical Laboratory, London.[5] Strachey finished the programme, written in his spare time, in February 1951. It ran for the first time on NPL’s Pilot ACE on 30 July 1951. He soon modified the programme to run on the Manchester Mark 1.”

    “English Draughts.” In Wikipedia, October 8, 2020. https://en.wikipedia.org/w/index.php?title=English_draughts&oldid=982525532.

  2. “It didn’t take long before Samuel had a program that played a respectable game of checkers, capable of easily defeating novice players. It was first publicly demonstrated on television on February 24, 1956. Thomas Watson, President of IBM, arranged for the program to be exhibited to shareholders. He predicted that it would result in a fifteen-point rise in the IBM stock price. It did.”

    Schaeffer, Jonathan. One Jump Ahead: Challenging Human Supremacy in Checkers. 1st Edition. New York: Springer, 1997.

    quoted in:

    “Legacy – Chinook – World Man-Machine Checkers Champion.” Accessed October 26, 2020. http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html.

  3. The historical record is fuzzy, but for some reason he chose to have his program debut against Robert Nealey a blind checkers champion from Stamford, Connecticut. IBM’s Research News claimed that Nealey was “a former Connecticut checkers champion, and one of the nation’s foremost players.”

    Although a self-proclaimed master, Nealey’s tournament results never justified such a claim. At the time of the game, he was not a former Connecticut state champion, although he did win the title in 1966, four years after the game with Samuel’s program. In the history of the state champi­onship, no recognized master had won the event. Nealey didn’t play in any of the premier checkers events, such as the U.S. championship, and apparently acquired his reputation by beating local players.”

    Schaeffer, Jonathan. One Jump Ahead: Challenging Human Supremacy in Checkers. 1st Edition. New York: Springer, 1997.

    quoted in:

    “Legacy – Chinook – World Man-Machine Checkers Champion.” Accessed October 26, 2020. http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html.

  4. “In a rematch, Chinook was declared the Man-Machine World Champion in checkers in 1994 in a match against Marion Tinsley after six drawn games, and Tinsley’s withdrawal due to pancreatic cancer. While Chinook became the world champion, it never defeated the best checkers player of all time, Tinsley, who was significantly superior to even his closest peer.[1]

    “Chinook (Computer Program).” In Wikipedia, August 24, 2020. https://en.wikipedia.org/w/index.php?title=Chinook_(computer_program)&oldid=974711515.

  5. “English draughts was weakly solved in 2007 by the team of Canadian computer scientist Jonathan Schaeffer. From the standard starting position, both players can guarantee a draw with perfect play.”

    “Draughts.” In Wikipedia, October 25, 2020. https://en.wikipedia.org/w/index.php?title=Draughts&oldid=985336948.

  6. “A two-player game can be solved on several levels:[1][2]
    Weak
    Provide an algorithm that secures a win for one player, or a draw for either, against any possible moves by the opponent, from the beginning of the game. That is, produce at least one complete ideal game (all moves start to end) with proof that each move is optimal for the player making it. It does not necessarily mean a computer program using the solution will play optimally against an imperfect opponent.”

    “Solved Game.” In Wikipedia, September 11, 2020. https://en.wikipedia.org/w/index.php?title=Solved_game&oldid=977794097.


We welcome suggestions for this page or anything on the site via our feedback box, though will not address all of them.