|
|
|
|
— |
speed_of_ai_transition:range_of_human_performance:time_for_ai_to_cross_the_human_range_in_english_draughts [2022/09/21 07:37] (current)
|
| | ====== Time for AI to cross the human range in English draughts ====== |
| | |
| | // Published 26 October, 2020; last updated 08 March, 2021 // |
| | |
| | |
| | |
| | <HTML> |
| | <p>AI progress in English draughts performance crossed the following ranges in the following times:</p> |
| | </HTML> |
| | |
| | |
| | <HTML> |
| | <figure class="wp-block-table"> |
| | <table> |
| | <tbody> |
| | <tr> |
| | <td><strong>Range</strong></td> |
| | <td><strong>Start</strong></td> |
| | <td><strong>End</strong></td> |
| | <td><strong>Duration (years)</strong></td> |
| | </tr> |
| | <tr> |
| | <td>First attempt to beginner level</td> |
| | <td>1951</td> |
| | <td>~1956, <1961</td> |
| | <td>~4, <10</td> |
| | </tr> |
| | <tr> |
| | <td>Beginner to superhuman</td> |
| | <td>~1956, <1961</td> |
| | <td>1994</td> |
| | <td>~38, >33</td> |
| | </tr> |
| | <tr> |
| | <td>Above superhuman</td> |
| | <td>1994</td> |
| | <td>2007*</td> |
| | <td>13*</td> |
| | </tr> |
| | </tbody> |
| | </table> |
| | <figcaption> |
| | * treating perfect play as the end of progress, though progress could potentially be made in performing better against imperfect play. |
| | </figcaption> |
| | </figure> |
| | </HTML> |
| | |
| | |
| | |
| | ===== Details ===== |
| | |
| | |
| | ==== Metric ==== |
| | |
| | |
| | <HTML> |
| | <p>‘English Draughts’ is a popular variety of draughts, or checkers.</p> |
| | </HTML> |
| | |
| | |
| | <HTML> |
| | <p>Here we look at direct success of AI in beating human players, rather than measuring humans and AI on a separate metric of strength.</p> |
| | </HTML> |
| | |
| | |
| | ==== Data ==== |
| | |
| | |
| | <HTML> |
| | <p>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.</p> |
| | </HTML> |
| | |
| | |
| | ==== AI achievement of human milestones ==== |
| | |
| | |
| | === Earliest attempt === |
| | |
| | |
| | <HTML> |
| | <p>According to Wikipedia, the first checkers program was run in 1951.<span class="easy-footnote-margin-adjust" id="easy-footnote-1-2704"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-1-2704" title='&#8220;The first English draughts&nbsp;<a href="https://en.wikipedia.org/wiki/Computer_program">computer program</a>&nbsp;was written by&nbsp;<a href="https://en.wikipedia.org/wiki/Christopher_Strachey">Christopher Strachey</a>, M.A. at the&nbsp;<a href="https://en.wikipedia.org/wiki/National_Physical_Laboratory_(United_Kingdom)">National Physical Laboratory</a>, London.<sup><a href="https://en.wikipedia.org/wiki/English_draughts#cite_note-5">[5]</a></sup>&nbsp;Strachey finished the programme, written in his spare time, in February 1951. It ran for the first time on NPL&#8217;s&nbsp;<a href="https://en.wikipedia.org/wiki/Pilot_ACE">Pilot ACE</a>&nbsp;on 30 July 1951. He soon modified the programme to run on the&nbsp;<a href="https://en.wikipedia.org/wiki/Manchester_Mark_1">Manchester Mark 1</a>.&#8221;</p> <p>“English Draughts.” In <em>Wikipedia</em>, October 8, 2020. <a href="https://en.wikipedia.org/w/index.php?title=English_draughts&amp;oldid=982525532">https://en.wikipedia.org/w/index.php?title=English_draughts&amp;oldid=982525532</a>.'><sup>1</sup></a></span></p> |
| | </HTML> |
| | |
| | |
| | === Beginner level === |
| | |
| | |
| | <HTML> |
| | <p>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. <span class="easy-footnote-margin-adjust" id="easy-footnote-2-2704"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-2-2704" title='&#8220;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.&#8221;</p> <p>Schaeffer, Jonathan. <em>One Jump Ahead: Challenging Human Supremacy in Checkers</em>. 1st Edition. New York: Springer, 1997.</p> <p>quoted in:</p> <p>“Legacy &#8211; Chinook &#8211; World Man-Machine Checkers Champion.” Accessed October 26, 2020. <a href="http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html">http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html</a>.'><sup>2</sup></a></span> 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.</p> |
| | </HTML> |
| | |
| | |
| | <HTML> |
| | <p>In 1962 Samuel’s program apparently beat an ambiguously skilled player who would by four-years later become a state champion in Connecticut.<span class="easy-footnote-margin-adjust" id="easy-footnote-3-2704"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-3-2704" title='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<em>&nbsp;Research News</em>&nbsp;claimed that Nealey was “a former Connecticut checkers champion, and one of the nation’s foremost players.”</p> <p>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 championship, 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.&#8221;</p> <p>Schaeffer, Jonathan. <em>One Jump Ahead: Challenging Human Supremacy in Checkers</em>. 1st Edition. New York: Springer, 1997.</p> <p>quoted in: </p> <p>“Legacy &#8211; Chinook &#8211; World Man-Machine Checkers Champion.” Accessed October 26, 2020. <a href="http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html">http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html</a>.'><sup>3</sup></a></span> Thus progress was definitely beyond beginner level by 1962.</p> |
| | </HTML> |
| | |
| | |
| | === Superhuman level === |
| | |
| | |
| | <HTML> |
| | <p>In 1994, computer program Chinook drew six times against world champion Marius Tinsley, before Tinsley withdrew due to pancreatic cancer and Chinook officially won.<span class="easy-footnote-margin-adjust" id="easy-footnote-4-2704"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-4-2704" title='&#8220;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&#8217;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.<sup><a href="https://en.wikipedia.org/wiki/Chinook_(computer_program)#cite_note-1">[1]</a></sup>&#8220;</p> <p>“Chinook (Computer Program).” In <em>Wikipedia</em>, August 24, 2020. <a href="https://en.wikipedia.org/w/index.php?title=Chinook_(computer_program)&amp;oldid=974711515">https://en.wikipedia.org/w/index.php?title=Chinook_(computer_program)&amp;oldid=974711515</a>.'><sup>4</sup></a></span> Thus Chinook appears to have been close to as good as the best player in 1994.</p> |
| | </HTML> |
| | |
| | |
| | === End of progress === |
| | |
| | |
| | <HTML> |
| | <p>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 state<span class="easy-footnote-margin-adjust" id="easy-footnote-5-2704"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-5-2704" title='&#8220;English draughts was&nbsp;<a href="https://en.wikipedia.org/wiki/Solved_game">weakly solved</a>&nbsp;in 2007 by the team of Canadian computer scientist&nbsp;<a href="https://en.wikipedia.org/wiki/Jonathan_Schaeffer">Jonathan Schaeffer</a>. From the standard starting position, both players can guarantee a draw with&nbsp;<a href="https://en.wikipedia.org/wiki/Perfect_play">perfect play</a>.&#8221;</p> <p>“Draughts.” In <em>Wikipedia</em>, October 25, 2020. <a href="https://en.wikipedia.org/w/index.php?title=Draughts&amp;oldid=985336948">https://en.wikipedia.org/w/index.php?title=Draughts&amp;oldid=985336948</a>.'><sup>5</sup></a></span> (this does not imply that if someone plays imperfectly, perfect moves following this are known).<span class="easy-footnote-margin-adjust" id="easy-footnote-6-2704"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-6-2704" title='&#8220;A&nbsp;<a href="https://en.wikipedia.org/wiki/Two-player_game">two-player game</a>&nbsp;can be solved on several levels:<sup><a href="https://en.wikipedia.org/wiki/Solved_game#cite_note-Allis-1">[1]</a><a href="https://en.wikipedia.org/wiki/Solved_game#cite_note-2">[2]</a></sup>&#8230;<br><strong>Weak</strong> <br>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.&#8221;</p> <p>“Solved Game.” In <em>Wikipedia</em>, September 11, 2020. <a href="https://en.wikipedia.org/w/index.php?title=Solved_game&amp;oldid=977794097">https://en.wikipedia.org/w/index.php?title=Solved_game&amp;oldid=977794097</a>.'><sup>6</sup></a></span> This is not the best possible performance by all measures, since further progress could presumably be made on reliably beating worse players.</p> |
| | </HTML> |
| | |
| | |
| | ==== Times for AI to cross human-relative ranges ==== |
| | |
| | |
| | <HTML> |
| | <p>Given the above dates, we have:</p> |
| | </HTML> |
| | |
| | |
| | <HTML> |
| | <figure class="wp-block-table"> |
| | <table> |
| | <tbody> |
| | <tr> |
| | <td><strong>Range</strong></td> |
| | <td><strong>Start</strong></td> |
| | <td><strong>End</strong></td> |
| | <td><strong>Duration (years)</strong></td> |
| | </tr> |
| | <tr> |
| | <td>First attempt to beginner level</td> |
| | <td>1951</td> |
| | <td>~1956, <1961</td> |
| | <td>~4, <10</td> |
| | </tr> |
| | <tr> |
| | <td>Beginner to superhuman</td> |
| | <td>~1956, <1961</td> |
| | <td>1994</td> |
| | <td>~38, >33</td> |
| | </tr> |
| | <tr> |
| | <td>Above superhuman</td> |
| | <td>1994</td> |
| | <td>2007*</td> |
| | <td>13*</td> |
| | </tr> |
| | </tbody> |
| | </table> |
| | <figcaption> |
| | * treating perfect play as the end of progress, though progress could potentially be made in performing better against imperfect play. |
| | </figcaption> |
| | </figure> |
| | </HTML> |
| | |
| | |
| | <HTML> |
| | <p><em><em>Primary author: Katja Grace</em></em></p> |
| | </HTML> |
| | |
| | |
| | ===== Notes ===== |
| | |
| | |
| | <HTML> |
| | <ol class="easy-footnotes-wrapper"> |
| | <li><div class="li"> |
| | <span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-1-2704"></span>“The first English draughts <a href="https://en.wikipedia.org/wiki/Computer_program">computer program</a> was written by <a href="https://en.wikipedia.org/wiki/Christopher_Strachey">Christopher Strachey</a>, M.A. at the <a href="https://en.wikipedia.org/wiki/National_Physical_Laboratory_(United_Kingdom)">National Physical Laboratory</a>, London.<sup><a href="https://en.wikipedia.org/wiki/English_draughts#cite_note-5">[5]</a></sup> Strachey finished the programme, written in his spare time, in February 1951. It ran for the first time on NPL’s <a href="https://en.wikipedia.org/wiki/Pilot_ACE">Pilot ACE</a> on 30 July 1951. He soon modified the programme to run on the <a href="https://en.wikipedia.org/wiki/Manchester_Mark_1">Manchester Mark 1</a>.” |
| | <p>“English Draughts.” In <em>Wikipedia</em>, October 8, 2020. <a href="https://en.wikipedia.org/w/index.php?title=English_draughts&oldid=982525532">https://en.wikipedia.org/w/index.php?title=English_draughts&oldid=982525532</a>.<a class="easy-footnote-to-top" href="#easy-footnote-1-2704"></a></p> |
| | </div></li> |
| | <li><div class="li"> |
| | <span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-2-2704"></span>“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.” |
| | <p>Schaeffer, Jonathan. <em>One Jump Ahead: Challenging Human Supremacy in Checkers</em>. 1st Edition. New York: Springer, 1997.</p> |
| | <p>quoted in:</p> |
| | <p>“Legacy – Chinook – World Man-Machine Checkers Champion.” Accessed October 26, 2020. <a href="http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html">http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html</a>.<a class="easy-footnote-to-top" href="#easy-footnote-2-2704"></a></p> |
| | </div></li> |
| | <li><div class="li"> |
| | <span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-3-2704"></span>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<em> Research News</em> claimed that Nealey was “a former Connecticut checkers champion, and one of the nation’s foremost players.” |
| | <p>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 championship, 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.”</p> |
| | <p>Schaeffer, Jonathan. <em>One Jump Ahead: Challenging Human Supremacy in Checkers</em>. 1st Edition. New York: Springer, 1997.</p> |
| | <p>quoted in:</p> |
| | <p>“Legacy – Chinook – World Man-Machine Checkers Champion.” Accessed October 26, 2020. <a href="http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html">http://webdocs.cs.ualberta.ca/~chinook/project/legacy.html</a>.<a class="easy-footnote-to-top" href="#easy-footnote-3-2704"></a></p> |
| | </div></li> |
| | <li><div class="li"> |
| | <span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-4-2704"></span>“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.<sup><a href="https://en.wikipedia.org/wiki/Chinook_(computer_program)#cite_note-1">[1]</a></sup>“ |
| | <p>“Chinook (Computer Program).” In <em>Wikipedia</em>, August 24, 2020. <a href="https://en.wikipedia.org/w/index.php?title=Chinook_(computer_program)&oldid=974711515">https://en.wikipedia.org/w/index.php?title=Chinook_(computer_program)&oldid=974711515</a>.<a class="easy-footnote-to-top" href="#easy-footnote-4-2704"></a></p> |
| | </div></li> |
| | <li><div class="li"> |
| | <span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-5-2704"></span>“English draughts was <a href="https://en.wikipedia.org/wiki/Solved_game">weakly solved</a> in 2007 by the team of Canadian computer scientist <a href="https://en.wikipedia.org/wiki/Jonathan_Schaeffer">Jonathan Schaeffer</a>. From the standard starting position, both players can guarantee a draw with <a href="https://en.wikipedia.org/wiki/Perfect_play">perfect play</a>.” |
| | <p>“Draughts.” In <em>Wikipedia</em>, October 25, 2020. <a href="https://en.wikipedia.org/w/index.php?title=Draughts&oldid=985336948">https://en.wikipedia.org/w/index.php?title=Draughts&oldid=985336948</a>.<a class="easy-footnote-to-top" href="#easy-footnote-5-2704"></a></p> |
| | </div></li> |
| | <li><div class="li"> |
| | <span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-6-2704"></span>“A <a href="https://en.wikipedia.org/wiki/Two-player_game">two-player game</a> can be solved on several levels:<sup><a href="https://en.wikipedia.org/wiki/Solved_game#cite_note-Allis-1">[1]</a><a href="https://en.wikipedia.org/wiki/Solved_game#cite_note-2">[2]</a></sup>…<br/> |
| | <strong>Weak</strong><br/> |
| | 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.” |
| | <p>“Solved Game.” In <em>Wikipedia</em>, September 11, 2020. <a href="https://en.wikipedia.org/w/index.php?title=Solved_game&oldid=977794097">https://en.wikipedia.org/w/index.php?title=Solved_game&oldid=977794097</a>.<a class="easy-footnote-to-top" href="#easy-footnote-6-2704"></a></p> |
| | </div></li> |
| | </ol> |
| | </HTML> |
| | |
| | |
| |
