ICGA Journal

Vol. 24, No. 2 - June 2001

Table of Contents

Table of Contents65
Ken (G.McC. Haworth and E.A. Heinz)65
Ken, Unix and Games (D. Ritchie) abstract67
Ken Thompson's Influence on Computer Games Research (J. Schaeffer) 71
The Bell Captain (H.J. van den Herik)73
Self-play, Deep Search and Diminishing Returns (E.A. Heinz) 75
Ken Thompson and DEEP BLUE (F.-H. Hsu) intro80
Ken Thompson's 6-Man Tables (J. Tamplin and G.McC. Haworth) abstract 83
Retrograde Analysis: Software Architecture (L.B. Stiller) 86
Endgame Tables and Endgame Study Composition (H.M.J.F. van der Heijden) abstract 88
Endgame Tables and Chess Composition (N.D. Elkies) 93
Computer Discoveries in Losing Chess (J.D. Beasley) abstract 102
King and Two Generalised Knights against King (V. Kotešovec) abstract 105
Information for Contributors108
News, Information, Tournaments, and Reports:109
Report on the 11th CSA Computer-Shogi Championship (R. Grimbergen) 109
Report on the First International CSVN Tournament (Th. van der Storm) 115
Report on the First Italian Computer-Chess Championship (G. Masciulli) 118
The CMG Sixth Computer Olympiad (Maastricht, 2001) 120
The CMG Computer-Games Workshop (Maastricht, 2001) 122
ICCA Treasurers' Report for 2000 (D.N. Levy and D. Beal) 123
Calendar of Computer-Games Events in 2001-2002 124
The First Jenazon Cup (I. Althöfer) 124
The Swedish Rating List (T. Karlsson)125
Obituary:126
Claude E. Shannon (1916-2001) (B. Mittman) intro126
How the ICGA Journal Reaches You128

 

Ken

From the beginning, the world of game-playing by machine has been fortunate in attracting contributions from the leading names of computer science. Charles Babbage, Konrad Zuse, Claude Shannon, Alan Turing, John von Neumann, John McCarthy, Alan Newell, Herb Simon and Ken Thompson all come to mind, and each reader will wish to add to this list. Recently, the Journal has saluted both Claude Shannon and Herb Simon.

Ken's retirement from Lucent Technologies' Bell Labs to the start-up Entrisphere is also a good moment for reflection. He is principally known as the father of UNIX and has been the recipient of some six prestigious awards including two IEEE awards, the ACM Turing Award and the National Medal of Technology of the USA. He was also awarded the first Fredkin prize in 1983 when BELLE, ACM and World CC Champion, won the title of U.S. Chess Master. The endgame CDs earned an ICCA Award, and here, the ICCA thanks Ken for his significant and enduring contributions to our community by revisiting some of the themes he developed.

UNIX and C developed in symbiosis and Dennis Ritchie, father of C, leads off by giving us his view from the next desk at Bell. He recreates the special culture of the research community there, simultaneously both liberal and productive, illustrating the sometimes surprising connections between Ken's games-related and other work. Jonathan Schaeffer reviews Ken's three principal contributions to computer game-playing, and Jaap Van den Herik mentions other activities and achievements: ICCA administration, event participation and success, opening-book preparation, intelligent computer vision and player-rating systems.

Ernst Heinz surveys the research inspired by and/or closely related to Ken's pioneering self-play experiments. He announces the results of his own most comprehensive investigation. It appears that statements about the decreasing returns of increasing search may soon be made with high levels of statistical confidence.

Feng-Hsiung Hsu's personal memories relive the innovative history that began with Joe Condon and Ken's BELLE, the first deployment of chess-specific hardware and parallelism, and developed through CHIPTEST, DEEP THOUGHT I and II, DEEP BLUE I and the deeper, match-winning DEEP BLUE II.

John Tamplin and Guy Haworth summarise the headline data on Ken's most recent retrograde analysis of 6-man chess endgames. This work incidentally includes and underwrites without exception the 1990s 6-man work of Lewis Stiller, who, in turn, throws some light on the measures needed to produce those results. The contributions by Harold van der Heijden and Noam Elkies demonstrate how the considerable tranche of perfect endgame knowledge created by Ken and others has contributed and will contribute to the world of chess composition, not only in technical but also in artistic terms.

John Beasley introduces us to the strange, upside-down Lewis Carroll world of Qui Perde Gagne or Losing Chess – same men, modified rules, different objective. He illustrates how retrograde analysis can highlight remarkable phenomena in a domain where human experience and intuition is relatively undeveloped. Václav Kotešovec in contrast retains the rules and objective of conventional chess while modifying men and board for a thorough examination of the power of two 'Generalised Knights' or Leapers.

The contributions in this issue only partly demonstrate how Ken has quietly encouraged and helped many people behind the scenes across a wide range of topics, usually with his signature lowercase emails pared to the bone. The anecdotes which have reached the editorial desk attest to this as well as to a sense of enjoying life to the full – the many competitions, the demonstration games, the CD-ROMs, the flights to and fro across America, the landings, and the MiG-29 adventure in Russia.

Ken now enjoys new challenges at Entrisphere and the freedom of the skies as a full-time flying-instructor. May he continue to inspire us and his colleagues in our respective fields.

Guy Haworth and Ernst Heinz


 

KEN, UNIX AND GAMES

D. Ritchie1

USA
 

ABSTRACT

Ken Thompson's work on chess and on Unix are his best-known contributions, but all this work was intertwined with other game and recreational activities. This note describes some of the synergies.


1 Bell Labs, Lucent Technologies, 600 Mountain Av., Murray Hill, NJ 07974-0636 USA. Email: dmr@plan9.bell-labs.com

 

KEN THOMPSON'S INFLUENCE ON COMPUTER GAMES RESEARCH

J. Schaeffer1

Alberta, Canada


Most computer people would be hard pressed to name the inventor of the UNIX operating system. Of those who know of Ken Thompson's pivotal role in computer science history, few could name any of his other major scientific accomplishments. Having one major scientific triumph in a career is something that most people would envy. However, UNIX is just the best-known of Ken's long list of achievements. Brian Kernighan, a long-time colleague of Ken, once told me that Ken was at the heart of many of the important computing-related contributions that came out of Bell Labs (and now Lucent Technologies) over the past three decades.

So, why isn't the name Ken Thompson better known? In my opinion, it is because of his reluctance to write. Ken let other people write papers; he preferred to write code. Hence, his publication record is relatively small. However, the list of acknowledgments he received in papers authored by other people would be substantially longer. That was just the way Ken operated. He eschewed the limelight, preferring to work on what interested him, offering valuable advice to whoever needed it.

Today, it is easy to overlook the major contributions of Ken Thompson to the game-playing community. We all take for granted that faster machines result in deeper searches and (therefore) stronger game-playing programs. When we think of a high-performance special-purpose game-playing machine, DEEP BLUE comes to mind. Endgame databases are a way of life for many games, including chess, checkers, and awari. However, a quick literature search will show that Ken Thompson was in large part responsible for all three of these major insights into computer games. For almost 20 years, these three results have driven many of the research directions in computer chess (and computer games), culminating in the 1997 DEEP BLUE victory over Garry Kasparov.

Ken's innocuous paper (Thompson, 1982) on computer self-play games (a mere two pages in length) had a profound impact on the mentality of the game-programming community. He showed that a single ply of search was worth roughly 200 rating points, an impressive number of points for a relatively modest improvement in performance (roughly a factor of five, something easily achieved at least every four years due to Moore's Law). This paper gave a recipe for success: all one had to do was build a faster chess search engine. The race was now on for better algorithms, more efficient implementations, parallel searching, and, of course, special-purpose hardware. More importantly, Ken's paper tantalized us: by equating performance with speed, one could extrapolate the results to approximate when a chess machine would be comparable in strength to the human world chess champion. Ken's experiments have been repeated many times for chess and other game-playing domains, e.g., by Hyatt and Newborn (1997) and Heinz (2000).

Ken Thompson and Joe Condon shook the computer chess world and the artificial intelligence community with their chess machine BELLE (Condon and Thompson, 1982). Richard Greenblatt was the first to propose a chess machine (Greenblatt, Eastlake and Crocker, 1967) but he was never able demonstrate it to successfully. In many ways, much of DEEP BLUE's success can be attributed to BELLE chess hardware. In particular, Ken's design of the hardware move generator was a key component of the DEEP BLUE design (Hsu, 1999). Feng-Hsiung Hsu subsequently modified it to fit into a single chip, as well as several other enhancements, but the core design remained essentially the same (Hsu, 2002). The result was a chip capable of analysing over 2,000,000 chess positions per second (using 1997 technology!), and a victory over Garry Kasparov.

Although Ken was not the first to publish the idea of retrograde analysis (Ströhlein, 1970), he was the first to recognize its power (Thompson, 1986). Even the simple chess endgame of KQ versus KR proved an effective demonstration to chess grandmasters. Ken has computed chess endgame databases on-and-off for over 20 years, resulting in new insights into the secrets of endgame play, overturning many human pre-conceived ideas (e.g., showing that KBB versus KN is generally not a draw (Thompson, 1986)) and resulting in changes to the 50-move rule in chess.

Endgame databases were a major factor in the checkers program CHINOOK, the first program to win a human world championship (Schaeffer, 1997). Endgame databases were critical in solving Nine Men's Morris (Gasser, 1995) and will soon result in solving the African game of awari (Lincke and Marzetta, 2000, Van der Goot, 2001).

A subtle contribution by Ken, but one that was very important to our community, was his name and reputation. Ken actively participated in many computer-game events - tournaments and conferences - and his name added luster, prestige, and status to our community's efforts.

The computer-games community is deeply indebted to Ken. His scientific contributions have had a profound impact on the community, and continue to influence games-related research to this day. Few scientific publications in the fast-moving field of computing science have a life-span of more than a decade. Ken has several enduring papers, some little known outside the realm of computer-games programmers. But to our small community, these works stand the test of time and establish Ken Thompson as one of the pioneers in our field.


REFERENCES

Condon, J.H. and Thompson, K. (1982). Belle chess hardware. Advances in Computer Chess 3 (ed. M.R.B. Clarke), pp. 45-54. Pergamon Press, Oxford. ISBN 0-0802-6898-6.

Gasser, R. (1995). Harnessing Computational Resources for Efficient Exhaustive Search. PhD thesis, ETH, Swiss Federal Institute of Technology, Zürich.

Goot, R. van der (2001). Awari Retrograde Analysis. Second International Conference on Computers and Games, (eds. I. Frank and T.A. Marsland). To appear.

Greenblatt, R.D., Eastlake, D.E. and Crocker, S.D. (1967). The Greenblatt Chess Program. Fall Joint Computer Conference 31, pp. 801-810. 

Heinz, E.A. (2000). Scalable Search in Computer Chess. Vieweg Verlag, Wiesbaden. ISBN 3-5280-5732-7.

Hsu, F.-H. (1999). IBM's Deep Blue Chess Grandmaster Chips. IEEE Micro, Vol. 19, No. 2 (Mar-Apr), pp. 70-81. ISSN 0272-1732.

Hsu, F.-H. (2002). Behind Deep Blue. Princeton University Press. To appear.

Hyatt, R. and Newborn, M. (1997). Crafty Goes Deep. ICCA Journal, Vol. 20, No. 2, pp. 79-86. 

Lincke, T. and Marzetta (2000). A. Large Endgame Databases with Limited Memory Space. ICGA Journal, Vol. 23, No. 3, pp. 131-138.

Schaeffer, J. (1997). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer-Verlag, New York, N.Y. ISBN 0-3879-4930-5.

Ströhlein, T. (1970). Untersuchungen über kombinatorische Spiele. Ph.D. thesis, Fakultät für Allgemeine Wissenschaften der Technischen Hochschule München.

Thompson, K. (1982). Computer Chess Strength. Advances in Computer Chess, 3. M.R.B. Clarke (ed.), pp. 55-56. Pergamon. ISBN 0-0802-6898-6.

Thompson, K. (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3, pp. 131-139.


1 Dept. of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8. email: jonathan@cs.ualberta.ca

 

THE BELL CAPTAIN

H.J. van den Herik1

Maastricht, The Netherlands


Here, in complementing other retrospectives in this issue of the ICGA Journal, we highlight further the multifaceted nature of Ken's contribution to the computer games community, and the 'Man and Technology' theme which has characterised his approach to life.

ICCA Secretary/Treasurer
In 1977, the ICCA was founded during the Second World Computer-Chess Championship in Toronto. The organisation was the brainchild of Barend Swets and many participants supported the idea, among them Ken Thompson who then tied for 4th place amongst 16 participants with his program BELLE. CHESS 4.6 won the title but Ken received credit for BELLE's KQKR endgame play against IGM Walter Browne (Fenner, 1979). Further, Ken agreed to serve as Secretary and Treasurer of the new organisation alongside Ben Mittman, the first ICCA President, and did so successfully and with much enthusiasm for six years.

His motive was to build a strong organisation so that computer chess could flourish and, at that time, he did everything he could to support this aim. Being a chess player of some capability himself, he was thrilled by the idea that a machine might play chess at a level that would be recognised by the chess world. To this end, and since acceptance is usually earned by actual results, he went with the continually improving BELLE from one weekend tournament to the next. Then he had the idea of moving much of its functionality to hardware (Condon and Thompson, 1982).

World Champion
In 1980, BELLE was the odds-on favourite of the 3rd World Computer-Chess Championship. However, it was not a walk-over: the 2nd-round game against NUCHESS ended in a draw and a play-off against CHAOS was needed before BELLE secured the title. Although so much was at stake, Ken was not at all nervous: together with Joe Condon, he had carefully prepared for the tournament and was convinced that they had done their utmost. Their attitude was that it should be sufficient or they would do better next time.

Opening Book Compiler
For Ken, building a chess machine was just one aspect of a large computer-chess project. Many other considerations had to be taken into account. For instance, chess players should be helped. Long before CHESSBASE and NICBASE started their activities, Ken had begun to collect Grandmaster, Master and computer games. First, the collection was meant only for retrieval but later Ken incorporated it in BELLE itself to provide it with an outstanding opening book. As a result many questions arose, for instance, "Is 1. … a6 a good move after 1. e4"? It scored 100 percent (1 out of 1), the sole example being the famous game Karpov-Miles played in Skara, 1980 (Matanovic et al., 1980). According to Ken, a move should feature in at least ten games before being considered seriously.

Chess Reader
Despite many great stories of halls of typing secretaries supporting US computer specialists to perform their tasks, Ken himself had to enter all the chosen games in BELLE's book. Of course, this was a thankless chore so Ken developed a program that could read the chess moves in all the relevant languages — English, Spanish, French, German, Dutch and so on. Since humans are fallible, the game scores were correctly assumed to be full of mistakes. Therefore, next to the optical-character-recognition program, Ken developed a program that analyzed the moves for consistency and made as many corrections as possible. It is one of his less-known achievements but fortunately, he later co-authored a commendable paper on this topic (Baird and Thompson, 1990). Other communities, wishing to capture their heritage electronically, could well emulate this feat of domain-intelligent character recognition.

Bell Captain
In 1982 Ken supported the participation of our program PION (Delft University of Technology) in the 12th ACM Championship in Dallas, Texas. He received the program by email, fixed some bugs, restructured the program and gave some advice. Our question on his opinion was answered by "it plays". In the hotel hall of the tournament site, there was one impressive place – obviously meant as the seat of the Chairman of the hotel's Board of Directors. Indeed, it was reserved for 'The Bell Captain' and Ken was duly photographed as such, standing behind the bell, by Tom Fürstenberg. Unfortunately, the picture has disappeared but 19 years later, the memories remain.

Inspiration and Author
In my role as Editor-in-Chief, I have had many talks with Ken, for instance on the publication of his results. He never cared to publish them but was always prepared to provide them for publication, especially in the ICCA Journal. So, it happened that the Editors (Herschberg and van den Herik) often phoned Ken at Bell Labs to receive the latest information to be included in the next issue of the Journal. Time and again he refused to be credited as an author and stated, "Do with it what you think is possible." In the circumstance, the best we could was to put his name in the title (cf. Herschberg and van den Herik, 1986; van den Herik and Herschberg, 1987; The Editors 1992, 1993); Tamplin and Haworth (2001) continue the tradition. We were therefore delighted when Ken eventually authored his own contributions to the Journal (Thompson, 1986, 1996).

Player Grader
Another of Ken's achievements was the development of an improved rating system. It was more sophisticated than but never replaced the Elo system (Elo, 1978). However, it re-addressed the principles of grading (q.v. Beasley, 1989; Glickman, 1995) and was adopted by the PCA, the Professional Chessplayer's Association.

Combining science, literature and art, I would say "Ken has initiated more scientifically than James Joyce would be able to report in his stream of consciousness. He is a hero of modern times of which Chaplin must have dreamed. Thank you, Ken, for your many and varied contributions."


REFERENCES

Baird, H.S. and Thompson, K. (1990). Reading chess. IEEE Trans. Analysis and Machine Intelligence, Vol. 12, No. 6, pp. 552-559.

Beasley, J.D. (1989). The Mathematics of Games, esp. Ch. 5. O.U.P, Oxford. ISBN 0-1928-6107-7.

Condon, J.H. and Thompson, K. (1982). Belle chess hardware. Advances in Computer Chess 3 (ed. M.R.B. Clarke), pp. 45-54. Pergamon Press, Oxford. ISBN 0-0802-6898-6.

Elo, A.E. (1978). The Rating of Chessplayers. Batsford, London. ISBN 0-7134-1860-5.

Fenner, C.J. (1979). Computer Chess, News about the North American Computer Chess Championship. British Chess Magazine, Vol. 99, No. 5, pp. 193-200. ISSN 0007-0440.

Glickman, M.E. (1995). Chess Rating Systems. American Chess Journal, Vol. 3, pp. 59-102. ISSN 1066-8292.

Herik, H.J. van den and Herschberg, I.S. (1987). The KBBKN Statistics: New Data from Ken Thompson. ICCA Journal, Vol. 9, No. 4, pp. 199. ISSN 1389-6911.

Herschberg, I.S. and Herik, H.J. van den (1986). Thompson's New Data-Base Results. ICCA Journal, Vol. 9, No. 1, pp. 45-49.

Matanovic, A. et al. (1980). Šahovsik Informator 29. Game 153. Centar za unapredivaje šaha. Beograd, Yugoslavia.

Tamplin, J. and Haworth, G.McC. (2001). Ken Thompson's 6-Man Tables. ICGA Journal, Vol. 24, No. 2, pp. 83-85.

The Editors (1992). Thompson: All about Five Men. ICCA Journal, Vol. 15, No. 3, pp.140-143.

The Editors (1993). Thompson: Quintets with Variations. ICCA Journal, Vol. 16, No. 2, pp. 86-90.

Thompson, K. (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, Vol. 9, No. 3, pp. 131-139.

Thompson, K. (1996). 6-Piece Endgames. ICCA Journal, Vol. 19, No. 4, pp. 215-226.


1 Department of Computer Science, Universiteit Maastricht, 6200 MD Maastricht, The Netherlands. E-mail: herik@cs.unimaas.nl.

 

KEN THOMPSON AND DEEP BLUE

Feng-Hsiung Hsu1

Palo Alto, USA


Ken Thompson had a great influence on the design of DEEP BLUE and on the people behind the machine. DEEP BLUE, the first machine to defeat the World Chess Champion in a regulation match, would not have been possible without his work on BELLE, the first chess machine to play at the national master level. For me personally, he was a teacher not just in technical matters but also in life itself.


1 Compaq Western Research Laboratory, 250 University Avenue, Palo Alto, CA 94301 USA. Email: fh_hsu@pacbell.net

 

KEN THOMPSON'S 6-MAN TABLES

J. Tamplin1 and G.McC. Haworth2

USA and UK
 

ABSTRACT

Ken Thompson recently communicated some results mined from his set of 64 6-man endgame tables. These list some positions of interest, namely, mutual zugzwangs and those of maximum depth. The results have been analysed by the authors and found to be identical or compatible with the available or published findings of Karrer, Nalimov, Stiller and Wirth.


1 4116, Manson Ave, Smyrna, GA, 30082-3723, USA. email: jat@jaet.org
2 33, Alexandra Rd., Reading, Berkshire, RG1 5PG, UK. email: guy.haworth@icl.com

 

ENDGAME TABLES AND ENDGAME STUDY COMPOSITION

H.M.J.F. van der Heijden1

The Netherlands
 

ABSTRACT

The endgame tables (EGTs) of Thompson and others have helped composers, tourney directors, judges and cook hunters check the correctness of endgame studies. Further, but only recently, EGTs have assisted the act of composition, for example, by being mined for their lists of mutual zugzwangs. This paper identifies further challenging opportunities for computers to contribute to study composition, even to the complete composition of a study indistinguishable in a 'Turing Test' from one originated by a composer.


1 Michel de Klerkstraat 28, 7425 DG Deventer, The Netherlands. email: harold_van_der_heijden@wxs.nl

 

COMPUTER DISCOVERIES IN LOSING CHESS

J.D. Beasley1

UK

ABSTRACT

The history of Losing Chess endgame analysis by computer is outlined, and some particularly striking discoveries are quoted.


1 7 St James Rd., Harpenden, Herts AL5 4NX, UK: johnbeasley@mail.com

 

KING AND TWO GENERALISED KNIGHTS AGAINST KING

Václav Kotešovec1

Czech Republic
 

ABSTRACT

A Knight jumps two squares in one direction and one square in the other. It can be generalised as a Leaper which jumps x squares in one direction and y squares in the other. At various times in its history, chess has featured other pieces of this kind, in particular, the mediaeval Firzan which moved one square in each direction. Calculations are described which examine the general outcome of the ending "King and two Leapers against King" on a square chessboard of any size. In particular, it is shown that all endings of this kind appear to be drawn on boards larger than 13X13, and that two identical Leapers cannot mate from a general position.


1 P. O. Box 43, 111 21 Praha 1, CZ (Czech Republic). Email: kotesovec@mbox.dkm.cz. English translation by John Beasley, 7 St James Rd., Harpenden, Herts. AL5 4NX UK: johnbeasley@mail.com.

 

OBITUARY

CLAUDE SHANNON (1916 – 2001): PERSONAL MEMORIES

Ben Mittman

Evanston, IL USA


Much has been written about Claude Shannon since his death in February, including the obituaries that Ken Thompson and Jaap van den Herik contributed to the last issue of the ICGA Journal. I would like to add a few personal memories of a simple, brilliant and unassuming man of science and fun. Dr. Shannon was invited by the Board of the ICCA in September of 1980 to be our special guest at the 3rd World Computer Chess Championship in Linz, Austria. The year was the 30th anniversary of his seminal paper: Programming a computer for playing chess. In Linz Shannon set the ground rules quickly: "I don't do windows or give talks". That was fine with us since his mere presence, along with his lovely wife Betty, gave us inspiration and pleasure.

Three things stand out in my mind as characteristic of this eclectic genius: juggling, Swiss Army knives and the Sacher torte. Shannon's contributions to the art and theory of juggling have been reported widely. In Linz, he kept several of us enthralled with his scholarly and pragmatic discussions of his efforts to instrument a juggler with wired gloves and electronics to capture raw data that would subsequently enter into his mathematical theory of juggling.