Ajedrez informático: el experimento más largo en ciencia informática

por ChessBase
05/06/2020 – El 31 de agosto de 1970, se inició un importante experimiento que sigue estando en marcha hasta el día de hoy. En aquel entonces, se disputó el primer torneo de ajedrez informático, dentro del marco de la conferencia "ACM’s National Conference" (ACM - Assosiation for Computing Machinery). El interés que creado por el proyecto estaba tremendo. ACM terminó siendo patrocinador un torneo que se disputaba a ritmo hasta el año 1994. El Profesor Jonathan Schaeffer ha escrito un informe sobre sus experiencias con este proyecto pionero que iba a convertirse en uno que llegó a durar 50 años. La idea: crear un programa informático de ajedrez que fuese capaz de competir con los jugdores más fuertes humanos. El experimento continuará también en el futuro. Artículo en inglés por Jonathan Schaeffer (Universidad de Alberta).

Fritz 17 Incluye el módulo FAT FRITZ Fritz 17 Incluye el módulo FAT FRITZ

Fritz 17 es la nueva edición de aquel mismo programa de ajedrez Fritz que ha fascinado al mundo del ajedrez desde hace unos 25 años (¡!): las victorias de Garry Kasparov y de Vladimir Kramnik; los métodos innovadores y modernos de entrenamiento para jugadores aficionados y profesionales; ajedrez cibernético en el servidor de Fritz, etc. Fritz es “el programa de ajedrez más popular de Alemania” (Der Spiegel) y ofrece todo lo que necesita el ajedrecista. La novedad más espectacular: Fritz 17 incluye el módulo basado en una red neuronal de inteligencia artificial, "Fat Fritz".

Más...

By Jonathan Schaeffer, University of Alberta

Abstract

Chess competitions continue to this day, allowing for 50 years of data on the growth of artificial intelligence capabilities in this domain. During this period, program ratings have soared from roughly 1400 in 1970 to almost 4000 today. The 1970 event was the first continuous competition in computer science history, and it represents the longest ongoing experiment in computer science history. This special issue of the ICGA Journal is devoted to documenting the historic 1970 tournament. (1)

Introduction

Creating a program capable of competing with the human world chess champion was one of the first “grand challenge” problems of the fledgling research area of artificial intelligence. The importance of computer chess at the dawn of the computer age is reflected in the many computer science luminaries that contributed to the early advances in the field. This includes Claude Shannon (father of information theory), Alan Turing (creator of the Turing Machine and the Turing Test), Herbert Simon (Nobel Laureate and winner of the prestigious Turing Award), Alan Newell (Turing Award winner), and John McCarthy (Turing Award winner).

In the 1950s and the 1960s, progress in developing chess programs was slow. However a breakthrough occurred with the development of MACHACK VI by Massachusetts Institute of Technology student Richard Greenblatt. In 1967 the program defeated a 1500 rated player and even won the Class D prize at a local tournament. This represented a huge increase in performance, to the level of that of a local club player.

MACHACK’s tournament career was short. Greenblatt summarized it by writing that (Van den Herik and Greenblatt, 1992),

MACHACK went on to play in about half a dozen human chess tournaments. Its best results were drawing an 1880 player and beating a 1720 player. Its best performance rating in a tournament was 1820 and I believe its official USCF rating was 1523.

In recognition of the program’s trailblazing success, it was made an honorary member of the United States Chess Federation (USCF).

Tony Marsland, a graduate student at the University of Washington, enjoyed playing chess and this interest motivated him to write a chess program. After graduating in 1967, he spent one year as an Assistant Professor before going to work for Bell Telephone Labs in New Jersey where he continued tinkering with his program in his spare time. In 1970, he came up with an idea for helping to popularize computer chess research at the upcoming Association for Computing Machinery (ACM) conference (Marsland, 2007):

... I wrote to Monty Newborn, who was working at Columbia University in Manhattan and was an organizer for the upcoming ACM...Computer Conference, suggesting that we provide some kind of a Computer Chess Exhibit. I had in mind a demonstration of computer vs. human play. Instead, Monty came up with a better idea of a computer chess tournament and we met with Keith Gorlen and David Slate (Northwestern University)... and hammered out a proposal that Monty took to the ACM for their blessing...

And so was born the United States Computer Chess Championship. This event was meant to generate publicity for computer chess, help foster and support research in this area, facilitate the exchange of ideas, and benchmark the progress of developing strong chess-playing programs. Monty Newborn and Kenneth King, both from Columbia University, organized the event. Jacques Dutka, a former chess master, was the tournament director. (2)

The 1st United States Computer Chess Championship

The tournament attracted six entrants. Of interest in the lineup was Hans Berliner, then a Ph.D. student at Carnegie Mellon University. He was a strong over-the-board chess master, and was the World Correspondence Chess Champion from 1965-1968. In 1956 he won the Eastern States Open, ahead of a promising junior player named Bobby Fischer. Berliner was the first strong chess player to write a chess program — in this case J. BIIT (Just Because It Is There) was the first program he had ever written!

MACHACK was noticeably and regrettably absent from the lineup. Greenblatt explains why his program did not participate (Van den Herik and Greenblatt, 1992):

Basically I was not particularly excited by the idea of computer-vs-computer chess. That plus the fact that I was busy at that time I think are the two reasons. I felt then and I still feel now to a great extent that it is better for the field if anybody can go to the local tournament and play any time when ready. The whole thing, where there is an event once a year, and you come in and play 4 or 5 games, is not a particularly positive situation. But on the other hand I also understand that from the point of view of sponsorship and people’s interest and so forth, maybe that helps promote the game and promote computer chess.

1st U.S. Computer Chess Championship Rules. (Computer History Museum, 1970)

Participants, as listed in the ACM conference program (Computer History Museum, 1970). Note the program authors differ slightly from those listed in the final results of the event.

Five entries were from various places in the United States: CHESS 3.0, COKO III, DALY CP, J. BITT, and SCHACH. From Canada, there was the MARSLAND CP. Most of these machines were located far away from New York City (Berliner, 1970):

Three of the computers were directly connected by telephone lines to input/output terminals in the New York Hilton Hotel. Here the operators of the programs typed in the moves made by the opponent computer, and in due time the computer would type back its reply. Two other computers were connected by voice telephone so that the operator at the computer site merely had to say the move made by the computer into the telephone for it to be actually played in New York. The sixth competitor was a mini- computer, so called because of its size and cost. This computer was located at the tournament site and had a television-type display on which the current position was shown. When the computer made a move the display changed. When its opponent made a move, this was communicated to the computer by means of a “light pen” with which the operator touched the piece that is moving and then the square to which it is going.

Chris Daly running the DALY CP installed on the IDIOM mini-computer. (Note the use of a light pen — in 1970!)

The first game to finish achieved one of the tournament’s goals immediately — publicity. Programming errors resulted in the MARSLAND CP quickly succumbing to J. BIIT (Marsland, 2007):

The first ACM ...Computer Chess Championship took place in New York. Meanwhile I was busy driving across the continent (probably I was in North Dakota when the first round started). However, I had arranged with my local sponsors [to have someone operate the program for me]. I am sure he would have had a happier time had [the MARSLAND CP] performed better, but at least we recognized the value to the advertising world of a New York Times headline like “Computer Loses in King-sized Blunder”! (3) Any mention of computer chess in the [New York Times] was better than none, I guess.

The participants quickly realized another goal: the exchange of ideas. David Levy, who started in 1971 to be the guest commentator at the ACM events, observed this first hand (Levy, 2005):

And one of the things that was very noticeable to me very quickly was the friendly atmosphere at the tournaments, in which the programmers would chat to each other while the games were in progress and between rounds. And they would get ideas from each other. So that after each tournament, the programmers would go away not only with more knowledge about their own programs, but with knowledge about how other people were doing things. And this, in my view, was the main factor in increasing the strength of programs steadily year on year. It was just an acquisition of important knowledge by most of the people in the field. So I think the importance of these tournaments cannot be underestimated in the whole history of the progress of computer chess.

CHESS 3.0 - COKO III. (Devlin, 1970) Left to right: Jacques Dutka, unknown, Keith Gorlen (CHESS 3.0), Monty Newborn, Steven M. Bellovin (4), unknown.

The tournament was won by CHESS 3.0, developed by a team of students at Northwestern University. The program’s win was decisive, not only by winning all three of its games but, more importantly, the quality of its play was noticeably above that of the other entries.

1970 U.S. Computer Chess Championship Result.

In 1968 undergraduate students Larry Atkin and Keith Gorlen wrote a chess program. Physics graduate student and 2050 USCF rated player David Slate heard of this initiative and wrote his own program. In 1969, the two teams joined forces with the resulting effort named CHESS 2.0. In 1970 Gorlen left Northwestern University and the CHESS team (although he stayed in touch and occasionally made contributions). Atkin’s and Slate’s version CHESS 3.0 entered the ACM event.

The Northwestern University program, often called CHESS X.Y to avoid having to remember their numbering scheme, was to dominate the first decade of computer chess tournaments. It is remarkable how consistently well their program played over the first 10 ACM championships (1970-1979). Given the small number of games in each event, the closeness of the competition in terms of playing strength, the presence of programming bugs, and unreliability of computing hardware, their dominance is a testament to Atkin’s and Slate’s innovative ideas, careful programming, and attention to detail. Slate and Atkin (1977) succinctly capture the frustration they felt in developing their programs in the 1970s: “The lack of programming tools has plagued the whole field of computer chess. With the proper tool one might accomplish in a day a job that had been put off for years.” The truth is that over 40 years later, their comment is still valid!

CHESS 3.0 wins the 1st U.S. Computer Chess Championship, 1970. Left to right: Monroe Newborn (Columbia), Larry Matsa (ACM), David Slate (CHESS 3.0), Larry Atkin (CHESS 3.0), and Ben Mittman (CHESS 3.0). Courtesy of Monroe Newborn.

Environment

Monty Newborn, who co-organized the event, described the tournament environment (Newborn, 1975):

At 5:30 each evening the games were scheduled to begin, but more typically they began around 6 P.M. It was a rare event throughout the tournament when all three games were simultaneously in progress. Almost always at least one computer was having difficulties. However, in general, the better programs were more reliable, and in turn the better games had fewer interruptions. Each evening there were several hundred spectators in attendance, including computer specialists and chess experts. The most notable chess experts were [Grandmaster] Pal Benko one of the top players int the United States, who seemed somewhat unsure of the future potential of computers in the chess world, and [International Master] Al Horowitz former chess editor of the New York Times, a long- time skeptic regarding their potential.

Throughout the tournament there was a most casual and informal atmosphere... Good moves were met with cheers from the audience; bad moves were hissed. The programmers discussed moves they expected their computers to make, reporters interviewed the participants, and Berliner ate his sandwiches. Berliner, an old pro of the human chess tournament circuit, came well stocked with food each evening.

Part of the lure of the event was the entertainment value. The programs played at a weak level and had numerous idiosyncrasies that surprised and delighted the audience. Ben Mittman described a 3rd round encounter where COKO III “finally managed to eke out a draw against J. BIIT while the audience howled in laughter as the final blunders...were played on the display board” (Mittman, 1976).

As a historical footnote, as pointed out in The New York Times (Devlin, 1970):

By chance the tournament fell on the 200th anniversary of the appearance of the world's first chess automaton, called the TURK. Introduced in the Royal Palace in Vienna by its inventor, Baron Wolfgang von Kempelen, it defeated almost all comers — including Napoleon — and baffled some of the best minds in Europe. The automaton was the figure of a Turk seated at a cabinet on which was a chess board. Actually the TURK was operated by a man hidden by an ingenious set of false panels.

Now, finally, after two centuries, the mechanical TURK had been superseded by an electrical one.

Aftermath

The championship attracted important media attention, including coverage in The Times (London), The New York Times, and the Washington Post. All this helped convince ACM that the event was a success and worthy of being repeated. Thus began a 25-year relationship between computer chess and ACM.

The championship was a novelty for that time and was reported in numerous technical venues. ACM’s SIGART, the Special Interest Group for ARTificial intelligence, gave a trivial summary of the event. However, over time SIGART devoted numerous articles to the increased interest in computer chess that the tournament generated. Further, several of the competitors turned their research into computer chess into academic publications. Each article helped raise the profile of chess as a worthy application for AI research.

First AI Publication on the 1970 Tournament in SIGART. (Bledsoe, 1970). The significance of the event is understated.

Hans Berliner was particularly prolific in writing popular and technical articles related to the event. He wrote an insightful article for Chess Life magazine. It reached all members of the United States Chess Federation, several tens of thousands of chess players.

“1st U.S. Computer Championship” by Hans Berliner. (Berliner, 1970 – click to enlarge)

The most interesting and perhaps least known report on the 1970 tournament came from a relatively unknown author. The article, “The Program Was a Fish,” appeared in 1972. The author was a recent Northwestern University graduate who had a strong interest in computers and chess. He knew Atkin and Slate, which likely motivated his writing effort. Here is the start of the article:

Once upon a time there was a fish.

A most unusual fish, worth several million dollars. It lived in a one-story building with a grass-covered roof on the campus of Northwestern University. It had transistors instead of scales, tape reels instead of fins, and an electronic memory instead of gills. It preferred eating punch cards to eating fish food.

Most people would have called the fish a computer. To be precise, the would have called it a Control Data Corporation (CDC) 6400.

It was a CDC 6400, of course. But it was also a fish.

A fish, you see, is a chess player. A bad chess player. The title is awarded by other players when one of their peers exhibits a singular skill in losing chess games. Popular synonyms are “patzer” and “meatcake.”

And Northwestern’s CDC 6400 was a chess player. A bad one. A fish. During the years of tournament play, the machine earned the title not once, but several times. A whole legion of human opponents regularly blasted the machine off the board.

Then, one day during the summer of 1970, the fish became a champion.

It happened in New York City, during the twenty-fifth annual convention of the Association for Computing Machinery (ACM). Meeting at the New York Hilton Hotel, the ACM decided to enliven its proceedings with the world’s first all-computer chess tournament.

Six competitors swam to the surface for the three-round event, including programs from sites as distant as Texas and Alberta, Canada. Among the six was CHESS 3.0 – Northwestern’s electronic fish.

The author’s name was George R.R. Martin (1972). Perhaps you know one of his more recent works? Game of Thrones.

From George R.R. Martin’s “The Computer Was a Fish.” (Martin, 1972) Larry Atkin (left) and David Slate.

Conclusion

Thus began the 50-year project to build a chess program capable of competing with (and, eventually exceeding the abilities of) strong human players. And the experiment continues to this day and for the foreseeable future.

Starting in 1970, progress in computer chess program development accelerated. Monty Newborn (2005) succinctly summarizes the scientific aspects of the next quarter-century of progress, culminating in the 1997 DEEP BLUE match: (6)

There was a lot of sharing of ideas. There were several key ideas, of course. As the great experiment went along, the [idea of] minimax was shared by thousands. That’s the first perhaps big idea. The alpha beta algorithm became quickly spread around the community. The idea of using large hash tables, or transposition tables, got spread around in the late ‘60s and early ‘70s. The Greenblatt program was one of the early ones. The key ideas - minimax, alpha beta, the use of large hash tables – and that was then followed by [Northwestern University Professor] Peter Frey’s idea of using iterative deepening search rather than straight depth-first search. The introduction of iterative deepening depth-first search moved the programs up from playing about a weak class A to almost master level in about a one or two year period. Following iterative deepening, Ken Thompson’s BELLE came in with the special purpose hardware. As soon as Thompson came in ... others followed right along. Following the special purpose hardware, one looked into a search using many computers in parallel. All of these ideas were shared by others as one marched along. Furthermore, at our ACM conferences every year, we held panel discussions in which the ideas were pretty well shared... . There was a certain amount of material published in the major publications. In general, the community was a very close community. We had lots of fun together. Following the games, we generally went out to dinner and had a good time and talked. Early on, of course, there were the Russians involved. It was always exciting, getting together with the Russians and talking chess and politics. It was quite an exciting period.

The 1970 United States Computer Chess Championship was an historic milestone for chess, computer chess, artificial intelligence, and even computer science. It was the first computers- only competition. Of course, since then there has been an explosion of computer competitions, from racing autonomous vehicles (DARPA Grand Challenge) to improving conversational abilities (Loebner Prize) (6) to identifying user preferences (Netflix Prize), and so on. Indeed, there is nothing like an interesting competition (with appropriate rewards) to spur on research and development efforts.

The tournament was a success and became an annual event through to 1994. It was soon renamed as the North American Computer Chess Championship. Many of the people who competed in the ACM events went on to impressive careers, including in industry, academia, and government. One even won the Turing Award (Ken Thompson).

Today, to many in computer science, computer chess history stops in 1997 with the DEEP BLUE victory over Garry Kasparov. That is to be regretted, as it diminishes the credit that is due to the computer chess community for their impact on the field of artificial intelligence. Only recently has computer chess had an uptick in media and technical interest, the result of the ALPHAZERO project (Silver et al., 2018). The computer chess community — past and present — should be proud of our accomplishments.

About the author

Jonathan Schaeffer is a professor of computing science at the University of Alberta in Canada. In the 1980s he researched computer chess, and developed the program Phoenix that tied for first place in the 1986 World Computer Chess Championships. In the 1990s, he worked on checkers, winning the (human) world championship in 1994. In 2007 he announced that checkers was solved — perfect play leads to a draw. In the 2000s he worked on poker programs and was a member of the team that first demonstrated world-class poker play in 2003. In the 2010s he worked on university administration, a much more complicated game. No successes there to date!

Acknowledgements

Sarah Beth’s (2017) excellent blog posting “The First Computer Chess Championship in the USA” was a useful resource for this article.

References
  • Hans Berliner (1970). “1st U.S. Computer Chess Championship”, Chess Life, November, page 638.
  • Sarah Beth (2017). “The First Computer Chess Championship in the USA”, blog posting at HESS.COM/ARTICLE/VIEW/THE-FIRST-COMPUTER-CHESS-CHAMPINSHIP-IN-THE-USA.
  • David Levy (2005). “Oral History of David Levy,” Computer History Museum.
  • T. Anthony Marsland (2007).WEBDOCS.CS.UALBERTA.CA/~TONY/ICCA/WITA-HISTORY-README.TXT.
  • George R.R. Martin (1972). “The Computer was a Fish,” Analog Science Fiction – Science Fact, August, pages 61-74.
  • Benjamin Mittman (1977). “A Brief History of Computer Chess Tournaments: 1970-1975,” in Chess Skill in Man and Machine, Peter Frey (editor), Springer-Verlag.
  • Karsten Müller and Jonathan Schaeffer (2018). Man vs. Machine: Challenging Human Supremacy at Chess, Russell Enterprises, Inc.
  • Computer History Museum (1970). “Special Events for Association of Computing Machinery 25th National Conference”. COMPUTERHISTORY.ORG/CHESS/DOC-431614F6C8304.
  • Monroe Newborn (1975). Computer Chess, Academic Press.
  • Monroe Newborn (2005). Oral History of Monroe Newborn, Computer History Museum. COMPUTERHISTORY.ORG/CHESS/ORL-43343EF430C92.
  • David Silver et al. (2018). “A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go Through Self-play,” Science, vol. 362, no. 6419, pages 1140–1144.
  • David Slate and Lawrence Atkin (1977). “CHESS 4.5 – The Northwestern University Chess Program,” in Chess Skill in Man and Machine, Peter Frey (editor), Springer- Verlag.
  • John Devlin (1970). “Chess Computer Loses Game in a King-Size Blunder,” September 2. CHESSPROGRAMMING.ORG/ACM_1970#CITE_NOTE-5.
  • Jaap Van den Herik and Richard Greenblatt (1992). “An Interview with Richard D. Greenblatt,” International Computer Chess Association Journal, vol. 15, no. 4, pp. 200-207.
  • Woodrow Wilson (“Woody”) Bledsoe (1970). “First U.S. Computer Chess Tournament”, ACM SIGART Newsletter, October. DL.ACM.ORG/DOI/10.1145/1045151.1045152.
Notes

(1) Portions of the text have been taken from Man vs. Machine: Challenging Human Supremacy at Chess by Karsten Müller and Jonathan Schaeffer (2018).

(2) Dutka soon became famous for his 1971 paper in which he announced the calculation of the square root of 2 to one million digits. That may not sound like much of a computation today, but you have to recall he was using 1970-era computers.

(3) The actual title is “Chess Computer Loses Game in a King-Size Blunder” (Devlin, 1970).

(4) Steven Bellovin was an undergraduate student at Columbia University and helped out with the tournament. Today, he is the Percy K. and Vida L.W. Hudson Professor of Computer Science at Columbia University. He is credited with being one of the founders of Usenet (along with Tom Truscott, another computer chess pioneer). He is a member of the Cybersecurity Hall of Fame.

(5) The text was given verbally. Minor edits have been made to the wording.

(6) Of interest is that the 1997 and 2009 events were won by former ICGA President David Levy. Computer Go pioneer Bruce Wilcox won in 2010, 2011, 2014, and 2015. Clearly the competitive spirit of games transfers easily to other domains.


Pistas, tutoriales e indicaciones sobre nuestros productos, para sacarles todo el partido y más.