Kotok-McCarthy#Match with ITEP

Between 1959 and 1962, classmates Elwyn Berlekamp, Alan Kotok, Michael Lieberman, Charles Niessen and Robert A. Wagner wrote the program while students of John McCarthy at the Massachusetts Institute of Technology.

Building on Alex Bernstein's landmark 1957 programMastering the Game: A History of Computer Chess, {{cite web | author=Computer History Museum | author-link=Computer History Museum | title=Opening Moves: Origins of Computer Chess | date=September 2005 | url=http://www.computerhistory.org/chess/main.php?sec=thm-42b86c2029762&sel=thm-42b86c4252f72 | access-date=2006-12-17}} created at IBM and on IBM 704 routines by McCarthy and Paul W. Abrahams, they added alpha-beta pruning to minmax at McCarthy's suggestion to improve the plausible move generator. They wrote in Fortran and FAP on scavenged computer time. After MIT received a 7090 from IBM, a single move took five to twenty minutes. By 1962 when they graduated, the program had completed fragments of four games at a level "comparable to an amateur with about 100 games experience".{{cite web | last=Kotok | first=Alan | title=MIT Artificial Intelligence Memo 41 | date=3 December 2004 | url=http://www.kotok.org/AI_Memo_41.html | access-date=2006-12-08}} Kotok, at about age 20, published their work in MIT Artificial Intelligence Memo 41 and his bachelor's thesis.

In 1965, McCarthy, by then at Stanford University, visited the Soviet Union. A group using the [http://www.computer-museum.ru/english/m2.htm M-2] computer at Alexander Kronrod’s laboratory at the Moscow Institute for Theoretical and Experimental Physics (ITEP) challenged him to a match.{{cite video | people=McCarthy, John | url = http://video.google.com/videoplay?docid=-1583888480148765375 | title = The History of Computer Chess: An AI Perspective | date = 8 September 2005 | medium = Google Video | location=Mountain View, CA, USA | publisher=Computer History Museum | access-date=2006-12-08}}. McCarthy begins at 0:43:48. Kronrod considered Kotok-McCarthy to be the best program in the United States at the time.E.M. Landis, I.M. Yaglom, Remembering A.S. Kronrod, English translation by Viola Brudno. [http://www.cs.purdue.edu/homes/wxg/ W. Gautschi] (ed.) [written for Uspekhi Matematicheskikh Nauk, English publication Math. Intelligencer (2002), 22-30], available at Stanford University School of Engineering [http://sccm.stanford.edu/pub/sccm/sccm00-01.ps.gz SCCM-00-01] {{webarchive|url=https://web.archive.org/web/20070613172132/http://sccm.stanford.edu/pub/sccm/sccm00-01.ps.gz |date=2007-06-13 }} (PostScript). Retrieved on 19 December 2006 Although some of its faults were known in 1965{{cite journal | author=Greenblatt, Richard D. | title=Oral History of Richard Greenblatt | publisher=Computer History Museum | date=12 January 2005 | url=http://archive.computerhistory.org/projects/chess/related_materials/oral-history/kotok.oral_history.2005.102630478/kotok.oral_history_transcript.2005.102630478.pdf | access-date=2006-07-01 | author-link=Richard Greenblatt (programmer) | archive-url=https://web.archive.org/web/20110927121611/http://archive.computerhistory.org/projects/chess/related_materials/oral-history/kotok.oral_history.2005.102630478/kotok.oral_history_transcript.2005.102630478.pdf | archive-date=27 September 2011 | url-status=dead }} and were corrected in the Greenblatt program at MIT Project MAC, Kotok-McCarthy was no longer in development and was three years out of date.

Georgy Adelson-Velsky, Vladimir Arlazarov, Bitman, Anatoly Uskov and Alexander Zhivotovsky won the correspondence match played by telegraph over nine months in 1966-1967. The Kotok-McCarthy program lost the match by a score of three to one and the first two games were played with a weak version.{{cite journal | author=Brudno, Michael| title=Competitions, Controversies, and Computer Chess | date=May 2000 | url=http://www.cs.toronto.edu/~brudno/essays/cchess.pdf | access-date=2006-12-09}} The ITEP group was advised by Russian chess master{{Citation needed|date=February 2007}} Alexander R. Bitman and three-time world champion Mikhail Botvinnik.{{cite web | title=International Grandmaster and World Champion Mikhail Botvinnik in Moscow | publisher=Computer History Museum accession number 102645357| year=1980 | url=http://www.computerhistory.org/chess/full_record.php?iid=stl-430b9bbdb9817 | access-date=2006-12-24}} According to the Computer History Museum, McCarthy "used an improved version"Photo: John McCarthy, artificial intelligence pioneer, playing chess at Stanford's IBM 7090, {{cite web | title=Computer History Museum accession number L062302006 | author=Unknown photographer. Courtesy of Stanford University. | year=1967 | url=http://www.computerhistory.org/chess/full_record.php?iid=stl-431e1a07ca980 | access-date=2006-12-22}} in 1967 but what improvements were made is unknown.

In 1967 Mac Hack VI{{Cite FTP | author=Greenblatt, Richard D., Eastlake, Donald E. III, and Crocker, Stephen D. | title=The Greenblatt Chess Program | year=1969 | url=ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-174.pdf | url-status=dead | server=Massachusetts Institute of Technology | access-date=2006-07-01}} by Richard Greenblatt with Donald E. Eastlake III became an honorary member of the United States Chess Federation{{Citation needed|date=February 2007}} when a person lost to it in tournament play in Massachusetts. Kronrod lost his directorship at ITEP and his professorship because of complaints from physics users that ITEP mathematics resources were being used for gaming. Mikhail Donskoy, Arlazarov and Uskov developed the ITEP program into Kaissa{{Citation needed|date=February 2007}} at the [https://web.archive.org/web/20070206092603/http://www.ipu.ru/engl/index.htm Institute of Control Sciences] and in 1974, it became the world computer chess champion.Photo: Arlazarov, Uskov, and Donskoy in Moscow, {{cite web | title=Computer History Museum accession number 102645411 | author=Unknown photographer. Gift of M.M. Newborn. | year=1980 | url=http://www.computerhistory.org/chess/full_record.php?iid=stl-431f4cc15a4a7 | access-date=2006-12-18}} Debate continued{{cite journal | author=Newborn, Monty| title=Oral History of Monty Newborn | publisher=Computer History Museum | date=28 February 2005 | url=http://archive.computerhistory.org/projects/chess/related_materials/oral-history/newborn.oral_history.2005.102630783/newborn.oral_history_transcript.2005.102630783.pdf | access-date=2006-12-17}} some forty years after the first test, about whether the Shannon{{cite journal|author=Shannon, Claude E. |title=Programming a Computer for Playing Chess |journal=Philosophical Magazine |series=7th Series |volume=41 |issue=314 |date=March 1950 |url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf |access-date=2006-07-01 |url-status=dead |archive-url=https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf |archive-date=2010-07-06 }} Type A brute force approach, used by ITEP, is superior to the Type B selective strategy, used by Kotok-McCarthy. The success of programs such as Northwestern University's Chess 4.5, which used the Type A strategy,{{Cite journal|last=Korf|first=Richard E.|author-link=Richard E. Korf|year=1985|title=Depth-first iterative deepening|url=https://cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf|language=en|publication-date=1985}}{{cite news | url=https://archive.org/stream/byte-magazine-1978-10/1978_10_BYTE_03-10_Chess_for_the_Microcomputer#page/n181/mode/2up | title=Creating a Chess Player / An Essay on Human and Computer Chess Skill | work=BYTE | date=October 1978 | access-date=17 October 2013 |author1=Frey, Peter W |author2=Atkin, Larry R | pages=182}} however, led to the Type A strategy being favored, at least for projects where playing strength, and not insight into human thought processes, was the goal.{{cite journal|author=Heath, David and Allum, Derek |title=The Historical Development of Computer Chess and its Impact on Artificial Intelligence |date=April 1997 |url=https://www.aaai.org/Papers/Workshops/1997/WS-97-04/WS97-04-013.pdf |access-date=2018-11-24 }} Recently, however, chess programs which make use of neural networks to evaluate positions, such as Giraffe, Alpha Chess Zero and Leela Chess Zero, make use of Monte Carlo Tree Search in order to allow a deeper search by not evaluating every position.

{{portal|Chess}}

• Georgy Adelson-Velsky
• Mikhail Botvinnik
• Computer chess

{{Reflist}}

• {{cite thesis | last=Kotok | first=Alan | title=A chess playing program for the IBM 7090 | publisher=Massachusetts Institute of Technology. Dept. of Electrical Engineering | date=June 1962 | hdl=1721.1/17406| type=Thesis }}
• {{cite web

| title=A Chess Playing Program (AIM-41)

| author=MIT Computer Science and Artificial Intelligence Laboratory (CSAIL)

| publisher=Massachusetts Institute of Technology, CSAIL Digital Archive - Artificial Intelligence Laboratory Series

| date=n.d.

| url=http://www.ai.mit.edu/research/publications/browse/0000browse.shtml

| access-date=2006-12-24

| archive-url=https://web.archive.org/web/20060913001624/http://www.ai.mit.edu/research/publications/browse/0000browse.shtml

| archive-date=2006-09-13

| url-status=dead

}}

:* AIM-41 [ftp://publications.ai.mit.edu/ai-publications/0-499/AIM-041.ps PostScript]. Retrieved on 24 December 2006.

:* AIM-41 [https://web.archive.org/web/20170706114810/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-041.pdf PDF]. Retrieved on 24 December 2006.

• {{cite web

| title=LCS/AI Lab Timeline

| author=MIT Computer Science and Artificial Intelligence Laboratory (CSAIL)

| date=n.d.

| url=http://www.csail.mit.edu/timeline/timeline.php/timeline.php?query=event&id=26

}}

• {{cite web | title=Computer Chess History by Bill Wall | year=2006 | url=http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm | access-date=2006-12-09|archive-url=https://web.archive.org/web/20060410130407/http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm|archive-date=2006-04-10}}

Category:Chess software

Category:History of chess