Stanford-ITEP Match

From Chessprogramming wiki
Jump to: navigation, search

Home * Tournaments * Stanford-ITEP Match

Stanford-ITEP Match,
a four game correspondence match over nine months between the Kotok-McCarthy-Program and the ITEP Chess Program starting on November 22, 1966.

The Challenge

In 1965, John McCarthy, by then at Stanford University, visited the Soviet Union. A group using the M-2 [1] computer at Alexander Kronrod’s laboratory at the Moscow Institute of Theoretical and Experimental Physics (ITEP) challenged him to a match. Kronrod considered the Kotok-McCarthy-Program to be the best program in the United States at the time [2].

The Match

JohnMcCarthy.jpg
versus
Adelson-Velsky-G.Moscow-1980.jpg

At the end of 1966 a four game correspondence match began between the Kotok-McCarthy-Program, running on a IBM 7090 computer, and a program developed at the ITEP, written by Georgy Adelson-Velsky, Vladimir Arlazarov, Anatoly Uskov, Alexander Zhivotovsky, and advised by Russian chess master Alexander Bitman and three-time world champion Mikhail Botvinnik [3].

The match played over nine months was won 3-1 by the ITEP program. Despite playing on weaker hardware, it was the better program. Based on Shannon Type A, it could took advantage on the tactical oversights of the Kotok-McCarthy-Program, caused by it flaws of the Shannon Type B plausible move generator.

Quotes

Cold War on an 8x8 Board

Excerpt from Competitions, Controversies, and Computer Chess [4]:

Round 1: In between 1950, when Shannon’s paper was first published, and 1966 only three chess programs were developed. By 1970 six programs (none from the initial three) participated in the first US Computer Chess Championship. The first World Championship in 1974 had 13 participants. This remarkable growth was largely spurred by a well publicized match between the Kotok/McCarthy program developed at MIT and Stanford University and a program developed at the Institute for Theoretical and Experimental Physics (ITEP) in Moscow. This match was a “first” in many ways: it was the first match between two computer programs.  
It was the first match where a type A strategy faced a type B strategy. But most importantly it was a challenge in the Cold War scientific race. Just as putting a man into space, it was of no practical value, but it had similar psychological implications.
Alan Kotok developed his program while an undergraduate at MIT in collaboration with several other students and under the direction of John McCarthy. His program implemented a type B strategy, considering 4 moves at the first ply, 3 moves on second, 2 on levels three and four and 1 on five through eight. The payoff function considered such elements as material (the main component), development, control of the center, and pawn structure. It also did not use several of the latest algorithmic improvements made between its initial creation (1962) and the match, most notably alpha-beta and the killer heuristic. It had a weak plausible move generator, causing Botvinnik to remark that “the rule for rejecting moves was so constituted that the machine threw out the baby with the bath water.” [Botvinnik 1967]
The Soviet program was implemented by Georgiy Adelson-Velskiy, Vladimir Arlazarov, Alexander Bitman, Anatoly Uskov, and Alexander Zhivotovsky, working in Alexander Kronrod’s Laboratory. It implemented Shannon’s type A strategy, with the search depth set as a parameter. In games 1 and 2 the machine looked ahead 3 ply, while in games 3 and 4 a depth of 5 ply was used. The payoff function was similar to the one in the Kotok/McCarthy program, but an emphasis was placed on gaining a spatial advantage.
The match was played by telegraph, starting on November 22, 1966 and continuing for a year. All games were agreed drawn if no mate was delivered or announced in 40 moves, as both programs showed complete incompetence in the endgame. In games one and two, against the weaker version of the ITEP program Kotok/McCarthy drew twice through the 40 move rule, although it was slightly worse in one of the games and much worse in the other. It was thoroughly beaten in both of the games against the stronger version, losing game three in 19 moves and game four in 41. In all of the matches the ITEP program was playing slightly better positional chess: because of the emphasis on space advantage the ITEP program was better at pushing pawns forward. It won, however, not because of any superiority in positional play, but by taking advantage of blunders on the part of the American program. [Newborn 1975] Because there were possible moves that were much better then the moves the Kotok/McCarthy program actually made, it was clear that the program failed to consider them at all, indicating a weakness in the plausible move generator. Thus the first round was won by the Russians and by the type A approach, and although the Soviet dominance in Computer chess was short-lived, the dominance of type A approaches continues today. This match has a very sad postscript: Alexander Kronrod, the head of the Computational lab at ITEP, was a highly principled person who, among with many other mathematicians, signed a letter in defense of Esenin-Volpin, a mathematician who was placed in an insane asylum for anti-Communist views. For his signature of the letter Kronrod was reprimanded by the Communist Party. The physicists at ITEP, who were irritated because computer time was “wasted” on game playing instead of their problems used the reprimand as an excuse to oust Kronrod from his position. At the same time Kronrod was fired from his professorship at the Moscow Pedagogical Institute. These actions effectively ended the career of this brilliant mathematician. 

Biography AS Kronrod

Quote from Biography AS Kronrod by Alexander Yershov [5]

In 1958, Kronrod, Adelson-Velsky, and Landis selected "Snap" ("подкидного дурака") as the intellectual foundations for the development of the game heuristic programming. The program itself was a fiasco - but the basic principles (board games, search techniques and limited depth) were formulated. Further research laboratories in the field of game theory culminated in the first ever chess duel between the program of the Institute of Soviet and American best program developed at Stanford University under the direction of J. McCarthy. By telegraph match was played in four games ended 3-1 in favor of our institute. At the time, chess became a guinea pig for all programmers interested in artificial intelligence.

Games

Round 1

[Event "Stanford-ITEP Match"]
[Site "Stanford Moscow"]
[Date "1966.??.??"]
[Round "1"]
[White "ITEP Program"]
[Black "Kotok-McCarthy-Program"]
[Result "1/2-1/2"]

{3-ply per move} 1.e4 e5 2.Nc3 Nc6 3.Nf3 Bc5 4.Bc4 Nf6 5.O-O O-O 6.d3 d6 7.Be3 Bg4 8.h3 Bh5 9.Bd5
Bd4 10.g4 Bxc3 11.bxc3 Bg6 12.Bg5 Re8 13.Rb1 Rb8 14.Qe2 Kh8 15.d4 Kg8 16.Qc4 Na5
17.Bxf6 Qxf6 18.Qd3 c6 19.dxe5 dxe5 20.Bb3 Rbd8 21.Qe3 b6 22.Rfd1 Rd6 23.g5 Qe7 24.Rd3
Rxd3 25.cxd3 Rd8 26.Ra1 Qd6 27.d4 exd4 28.cxd4 Nxb3 29.axb3 a5 30.Ra4 Qe6 31.Ne5 Qe8
32.f4 Rd6 33.f5 Bh5 34.Nc4 Rd8 35.Nxb6 Rb8 36.Nc4 Bd1 37.Ra3 Bc2  {draw agrreed} 1/2-1/2

Round 2

[Event "Stanford-ITEP Match"]
[Site "Stanford Moscow"]
[Date "1967.??.??"]
[Round "2"]
[White "Kotok-McCarthy-Program"]
[Black "ITEP Program"]
[Result "1/2-1/2"]

{3-ply per move} 1.e4 Nf6 2.e5 Nd5 3.Nf3 e6 4.Bb5 a6 5.Ba4 b5 6.Bb3 Bb4 7.Nc3 Nf4 8.O-O Bb7 9.d4
Bxc3 10.bxc3 Nd5 11.Bxd5 Bxd5 12.Ba3 d6 13.exd6 cxd6 14.Re1 Nc6 15.Re3 O-O 16.Qe2
Bc4 17.Qe1 Qc7 18.Bb4 a5 19.Ba3 Kh8 20.Ng5 h6 21.Ne4 Rfd8 22.Nxd6 Rxd6 23.Bxd6 Qxd6
24.a3 Ne7 25.Re5 Nc6 26.Rc5 e5 27.Qe4 Ra6 28.Rd1 g6 29.Rd2 g5 30.Rd1 a4 31.Rd2 f6
32.Qe3 exd4 33.cxd4 Ne7 34.Qg3 Qxg3 35.hxg3 Nd5 36.Rc8+ Kh7 37.Rf8 b4 38.axb4 Nxb4
39.c3 Nd5 40.Rc8 {draw, as agreed before the start of the match, if one program reached move 40} 1/2-1/2

Round 3

[Event "Stanford-ITEP Match"]
[Site "Stanford Moscow"]
[Date "1967.??.??"]
[Round "3"]
[White "ITEP Program"]
[Black "Kotok-McCarthy-Program"]
[Result "1-0"]

{5-ply per move} 1.e4 e5 2.Nf3 Nc6 3.Nc3 Bc5 4.Nxe5 Nxe5 5.d4 Bd6 6.dxe5 Bxe5 7.f4 Bxc3+ 8.bxc3
Nf6 9.e5 Ne4 10.Qd3 Nc5 11.Qd5 Ne6 12.f5 Ng5 13.h4 f6 14.hxg5 fxg5 15.Rxh7 Rf8
16.Rxg7 c6 17.Qd6 Rxf5 18.Rg8+ Rf8 19. Qxf8# 1-0

Round 4

[Event "Stanford-ITEP Match"]
[Site "Stanford Moscow"]
[Date "1967.??.??"]
[Round "4"]
[White "Kotok-McCarthy-Program"]
[Black "ITEP Program"]
[Result "0-1"]

{5-ply per move} 1.e4 Nf6 2.e5 Nd5 3.Nf3 Nb4 4.Bb5 c6 5.Ba4 d6 6.d4 Qa5 7.c4 Nc2+ 8.Kf1 Nxa1
9.Nc3 Qb4 10.Qe2 dxe5 11.dxe5 Be6 12.Qd1 Bxc4+ 13.Ne2 b5 14.Bc2 Nxc2 15.Qxc2 Bxa2
16.Ned4 Qc4+ 17.Kg1 c5 18.Qd2 cxd4 19.Nxd4 e6 20.Nf3 Nc6 21.Qg5 Rd8 22.Bd2 Qc1+ 23.Be1
Qxb2 24.Qf4 Bd5 25.Qg3 Qe2 26.Bc3 b4 27.Be1 Bxf3 28.gxf3 Qxe1+ 29.Kg2 Qxe5 30.Qh4 a5
31.Rc1 Nd4 32.Rf1 Nxf3 33.Qh3 Rd3 34.Qg3 Ne1+ 35.Rxe1 Rxg3+ 36.Kf1 Qb5+ 37.Re2 Ra3
38.Ke1 Ra1+ 39.Kd2 Qd5+ 40.Ke3 Ra3+ 41.Kf4 Qf5#  0-1

See also

Publications

Chapter III. The Kotok-McCarthy Chess Program versus the ITEP Chess Program

External Links

References

  1. The Fast Universal Digital Computer M-2 from the Russian Virtual Computer Museum
  2. Evgenii Landis, Isaak Yaglom (1987). Remembering A.S. Kronrod. (2002). Translation by Viola Brudno, Edited by Walter Gautschi, ps
  3. International Grandmaster and World Champion Mikhail Botvinnik in Moscow, 1980, Gift of Monroe Newborn, "Botvinnik served as a consultant to Soviet computer chess developers who developed an early program at ITEP which won a correspondence chess match against a Stanford University chess program led by John McCarthy in 1967. Later he advised the team that created the chess program Kaissa at Moscow’s Institute for Control Science"
  4. Michael Brudno (2000). Competitions, Controversies, and Computer Chess, pdf
  5. Биография А.С. Кронрода, Biography AS Kronrod by Alexander Yershov (translated by Google Translate)

Up one Level