|Table of Contents||201|
|From Cognition to Perception (H.J. van den Herik)||201|
|Lambda-Search in Game Trees – with Application to Go (T. Thomsen) abstract||203|
|Solving Kriegspiel-like Problems: Exploiting a Transposition Table (M. Sakuta and H. Iida) abstract||218|
|The Innovated Art of Chess Analysis (J. van Reek, J.W.H.M. Uiterwijk, and H.J. van den Herik) abstract||230|
|Information for Contributors||233|
|News, Information, Tournaments, and Reports:||234|
|Report on the 20th Open Dutch Computer-Chess Championship (Th. van der Storm)||234|
|Report on the 4th ACBL World Computer Bridge Championship (A. Levy)||237|
|Report on the 3rd Advanced Chess Match (The Editorial Board)||241|
|FRITZ and the Giants (F. Friedel)||242|
|JUNIOR in Dortmund (F. Friedel)||248|
|A One-sided Advanced Chess Match. Part 2: Comments (I. Althöfer)||254|
|Report on the IPSJ-SIG-GI Workshop in Hamamatsu (T. Tanaka)||257|
|Don Beal – A Steady Hand at the Till (D.N.L. Levy)||258|
|A Welcome to Hiroyuki Iida (D.N.L. Levy)||258|
|ICGA Journal Referees in 2000 (The Editorial Board)||259|
|Calendar of Computer-Games Events in 2001-2002||259|
|The Swedish Rating List (T. Karlsson)||260|
|Ricochet Robot (N. Wedd)||261|
|David Champernowne (1912-2000)||262|
|Sidney Samole (1935-2000)||263|
|Make Sure the ICGA Journal Reaches You||264|
This is the last issue of the twentieth century. It is an excellent viewpoint to analyse the past and to predict the future. Although a century has one hundred years we take a time span of sixty years on both sides, since it was only in the 1940s that researchers managed to build an actual computer. A debate on the scientific priority of who was the first to construct such a machine was concluded around 1970. Then it became apparent that John V. Atanasoff had invented the first electronic computer in 1939 and therefore should have the patent rights. In Europe, Konrad Zuse was the very first person to have developed a prototype computer with his Z3 machine of 1941. It was quite prophetic that Zuse considered the royal game of chess as one of the most challenging tasks to be performed by his machine.
Around 1950 the first commercial computers entered society. They were good at counting and calculating and one can only wonder what happened to them when they recently failed so obviously in Miami, Florida. After counting and computing partial differential equations, computers showed up in bookkeeping and other administrative business as well as in the world of intelligent actions, such as translation, theorem proving, and games. In particular, chess and checkers were chosen as the first domains in which computers were given a chance to excel. As we all know it took the playing programs half a century to arrive at the level of World Champion. A striking difference with the past is that the current superiority of a chess or checkers computer will never again be challenged by any human being, i.e., the checkers program CHINOOK now reigns supremely and the various chess programs belong to the world top. Still, for researchers there remains the ultimate question of the theoretical outcome of the game. For checkers, it is expected to be solved within the next ten years; for chess, it is far beyond any conceivable reach (a distributed program should run approximately one hundred centuries to establish the result).
After Kasparov's defeat by DEEP BLUE in 1997, the Editors of the former ICCA Journal preferred to broaden the scope of the research reported from chess to games. The transition was effected last year by modifying the name into ICGA Journal. If we now look back at the games dealt with in a scientific manner in the ICGA Journal (including the current issue) we see that the following games have been addressed: Awari, Chess, Go, Kalah, Kriegspiel, and RoShamBo as well as Planning seen as a game, and the topic of problem solving as in Tsume Shogi. Moreover, reports of competitions and descriptions of other games were published, such as on Amazons, Bridge, Hex, Lines of Action, Shogi, and Shuffle Chess. A respectable list. On the one hand it should be extended in the century to come, and on the other hand the length of the list should vary since persistent researchers will crack some games or solve them.
This issue also records changes in the Board of ICCA. Don Beal stepped down as a Secretary-Treasurer after many years of outstanding service. He is succeeded by Hiroyuki Iida, who is expected to realise an effective broadening of our scope. Besides Don's stepping down we saw the retirement of Ken Thompson. He left Bell Laboratories after more than a quarter of a century of research and will now spend his time on his hobby, teaching amateur pilots. We thank him for the outstanding contributions he made to the world of computer chess and will pay more attention to his many merits in a next (special) issue.
There are two obituaries: one of a renowned scientist, David Champernowne, and the other of an eminent entrepreneur, Sidney Samole. Together with Turing, Champernowne was (one of) the first who developed a computer-chess algorithm (around 1950). A quarter of a century later this algorithm formed the basis of Samole's commercial success: a chess-playing microcomputer available for all. Even the Pyrrhonistic sceptics had to concede that a silicon box could move the pieces according to the rules, which looked like playing chess. Grandmasters laughed at it, but the commercial advance was irresistible. Obviously, the process of cognition had settled an agreement with computer technology. However, we do not know where this agreement will lead us.
Meanwhile we are at the start of a new century, of which the computer buzzwords are: data mining, telecommunications, e-commerce, and mobile technology. We see soccer players at the scientific conferences and chess players opting for the Olympic Games. The time of autonomous agents has arrived and the scientific obstacles are shifting from cognition to perception. The questions Where is my King? and Is my King in danger? characterise the past century. The twenty-first century will stress the questions: Where is the ball? and What can I do with it? Around 2050 a computerized robot team will play an acceptable game of football. The process of perception will then be conceived by chips.
Returning to thinking games and thought processes a fundamental question of Artificial Intelligence might be answered in 2060: can human intuition be captured in a silicon box?
For many computer-games researchers this question is already a guideline for investigation. In the next years this Journal hopes to report on solutions of games, both old and new, and on the unravelling of the intricacies of cognition and perception in games.
Jaap van den Herik1
This paper proposes a new method for searching two-valued (binary) game trees in games like chess and Go. Lambda-search uses null moves together with different orders of threat sequences (so-called lambda-trees). Lambda-search focuses on threats and threat aversions, but still guarantees to find the minimax value. The guarantee presupposes that the game rules allow passing or that zugzwang is not a motive. Using negligible working memory in itself, the method seems able to offer a large relative reduction in search space over the standard alpha-beta method (comparable to the relative reduction in search space of alpha-beta over minimax). Among other things, the reduction depends upon how non-uniform the search tree is. Lambda-search is compared to other analogous approaches, such as null-move pruning and proof-number search. Moreover, it is explained how the concept and context of different orders of lambda-trees may ease and encourage the implementation of abstract game-specific knowledge. This is illustrated on open-space Go block tactics, by distinguishing between different orders of ladders. In close relation, some possibly fundamental work regarding an abstract formalization of the concept of relevancy zones (zones outside of which added stones of any colour cannot change the status of the given problem) is offered.
2 This article is a slightly adapted and improved version of a paper delivered under the same title on October 27, 2000 on the Second Computer and Games Conference (CG'2000) in Hamamatsu, Japan. The paper is published as Thomsen (2001). We kindly thank the Editors T.A. Marsland and I. Frank as well as Springer-Verlag for the preparedness to allow an (enriched) reproduction.
Makoto Sakuta and Hiroyuki Iida1
We recently proposed Uncertainty Paradigm Search (UPS), a novel deterministic approach for solving problems with uncertainty. One of its applications is in Tsuitate-Tsume-Shogi (mating problems in a Kriegspiel-like variant of Shogi). This approach relies on the use of metapositions. A metaposition is a hybrid complex of possible positions that are not distinguishable for the solver.
The previous implementation of the search for solving a problem was based on a simple depth-first, full-width search with iterative deepening, which did not use a transposition table.
In this contribution, we examine four methods for encoding a metaposition into some value with fewer bits in order to use a transposition table. Each encoding method is tested in a search process, using a benchmark test set of 102 problems. In this paper, we have examined several methods for encoding a metaposition and applied them for searching with a transposition table.
They show us that the efficiency of search by using a transposition table is improved by a factor of eight. The four encoding methods make use of (1) arithmetic sum, (2) exclusive-OR sum, (3) two cyclic redundancy check codes, and (4) a secure hash function. The method of exclusive-OR sum proves not to be acceptably resistant to type-1 errors in this domain; the others are.Though the execution time is roughly comparable among the other three methods, the arithmetic sum is slightly superior in our implementation.
J. van Reek1 , J.W.H.M. Uiterwijk2 , H J. van den Herik2
Margraten, The Netherlands / Maastricht, The Netherlands
The question whether computer-chess programs can correctly decide between different strategies is investigated by means of the adjourned game Botvinnik-Fischer (Varna, 1962). Two previously-published variations are checked by FRITZ 6 and HIARCS 7.32. The analysis focuses on three strategic concepts, viz. counterattack, consolidation, and restriction. FRITZ 6 computed a counterattack perfectly. Consolidation was not found by the applied programs. HIARCS 7.32 successfully used brute force and positional knowledge for the calculation of restriction.
Computer-chess programs have advanced the analysis of over-the-board games quite considerably. Famous combinations are recalculated and sometimes corrected. Moreover, features of positional play are nowadays recognised and key moves of strategic planning are often found (Van Reek, Uiterwijk, Van den Herik, 1998). The next question is: Can computer-chess programs correctly decide between different strategies?
The question will be investigated by means of the famous adjourned game Botvinnik-Fischer played in Varna in 1962 (see Diagram 1). The position has been analysed by three World Champions, Fischer (1972), Botvinnik (1985) and Kasparov in the days before the strong chess programs. Van Reek (1998) found a stronger sealed move than Fischer's. His first effort to test this move (and consequently his new idea on the strategy to follow) on a computer failed. So he waited two years for stronger programs and faster machines in order to investigate the position again.
We start with giving the moves actually played. Then we investigate two previously-published variations (by Fischer (1972) and Botvinnik (1985)) analysed by FRITZ 6 and HIARCS 7.32 on a Pentium III 500 MHz computer. HIARCS 7.32 used the Nalimov endgame table bases. The allotted time per ply was thirty minutes. Finally we examine an improvement of the sealed move.
2.1 The Moves Played
In the position of Diagram 1, Fischer had sealed 45. ... Rc5?! The game continued with 46. Rf7 Ra5 47. Rxh7! Geller proposed this move during the overnight analyses. "This defence was overlooked by Fischer" (Botvinnik, 1985). "This was the first defence I had considered!" (Fischer, 1972). 47. ... Rxa4 48. h4+! Kf5 49. Rf7+ Ke5 50. Rg7 Ra1 51. Kf3. Diagram 2 has been reached. After 51. ... b5? 52. h5! the game ended in a draw.
The remaining moves are: 52. … Ra3+ 53. Kg2 gxh5 54. Rg5+ Kd6 55. Rxb5 h4 56. f4 Kc6 57. Rb8! h3+ 58. Kh2 a5 59. f5 Kc7 60. Rb5 Kd6 61. f6 Ke6 62. Rb6+ Kf7 63. Ra6 Kg6 64. Rc6 a4 65. Ra6 Kf7 66. Rc6 Rd3 67. Ra6 a3 68. Kg1 draw.
|Diagram 1: Adjourned position of Botvinnik-Fischer, Varna 1962.||Diagram 2: Position after 51. Kf3.||Diagram 3: Analytical position after 53. Rb4.|
2.2 Analyses by Botvinnik and Fischer
From Diagram 2, the first important variation begins with 51. ... Kd4! Black sacrifices the g-Pawn in order to advance his passed Pawns. Botvinnik found a nice counterattack, a pawn rush followed by a series of checks: 52. Rxg6 b5 53. h5 b4 54. h6 b3 55. Rg4+ Kc5 56. Rg5+ Kc6 57. Rg6+ Kb7 58. Rg7+ Ka6 59. Rg6+ Ka5 60. Rg5+ Ka4 61. Rg4+ Ka3. At last the King has found a haven. 62. Rh4 b2 63. h7 b1Q 64. h8Q. Fischer tried to win the game at home with 64. ... Qb3+ 65. Ke2 Qd1+ 66. Ke3 Rb1 67. Qf8+ Ka2. Kremenetsky refuted this opinion by 68. Qc5 drawn (Botvinnik, 1985, p. 77). The thirteen-year-old Kasparov found the alternative 67. Rc4 (ibid). Again the black attack and white counterattack have an equal strength. Both programs checked all white moves and agreed with them. Moreover, the programs computed 54. Rg4+. Probably this move is a dual draw (54. ... Kc3 55. Rh4 Rg1 56. h6 Rg8 57. h7 Rh8 58. Ke2 b3 59. Kd1). Finally, HIARCS 7.32 found one additional deviating move, viz. 61. Rg7 which only loses time (61. ... a5 62. Rg4+). The computations confirmed all moves of the first variation (given in bold).
2.3 A New Idea
The second variation departs from the adjourned position (Diagram 1). According to Van Reek (1998), the winning variation starts with 45. ... h5!! A strategy of active consolidation begins. The first key move consolidates the King's side. 46. h4+ Kh6. A tactical justification of the variation is 47. a5 b5! 48. Rf6!? b4 49. a6!? b3 50. Rf3 b2 51. Rb3 Rc3+! 47. Rf4 Rc5! The second key move starts a consolidation of the Queen's side. 48. Rd4 Ra5. The flanks are now consolidated by Black, and he is ready for activity. The black moves were calculated by the computers. For instance, the programs investigated 45. ... Rc4? Botvinnik (1985) refuted this move by 46. a5 bxa5 47. Rf7 a6 48. h4+ Kh6 49. Rd7! In the evaluations by FRITZ 6, 45. ... h5 became choice nine from nineteen potential moves. Other moves calculated by FRITZ 6 were 47. ... Rc3+ 48. f3 a5? and 48. ... a5? HIARCS 7.32 computed 47. ... a5? and 48. ... b5? These moves weaken the b-Pawn, an essential asset of Black's position.
The second variation continues with 49. f4. White prevents ... g5. 49. ... Kg7. Black begins a strategy of restriction by moving his King to the central area. 50. Kf3 Kf6 51. Ke4 Ke6 52. Rc4 Rc5 53. Rb4. Both programs had no difficulty in finding the central movement by the black King. Diagram 3 has been reached. If White has to move, Black wins. Therefore Black plays 53. ... Ke7! The first key move: the black King begins a triangle manoeuvre 54. Kd3 Kf6 55. Ke4 Ke6. A move exchange has been completed. The programs computed 53. ... Rc6!? This move seems to be a dual win (54. a5 bxa5 55. Ra4 Rc5 56. Ra2 Rb5!). HIARCS 7.32 confirmed the other two moves by Black in the second variation. FRITZ 6 gave 54. ... Kf6 and 54. ... Kf7 as equal choices and calculated 55. ... Rc6?! 56. Rd4 a5! The second key move completes the zugzwang manoeuvre. 57. Ke3 Rc3+ 58. Ke4 Rb3 59. Rc4 Rb4 and wins. Both programs confirmed the last four moves by Black.
Three prophylactic strategies were applied in two variations of the endgame Botvinnik-Fischer (Varna, 1962): counterattack, consolidation and restriction.
A counterattack was carried out by White in the first variation. Many moves were forced. Some moves required accurate calculation. It posed little difficulty to FRITZ 6. Difficult analyses by three World Champions were confirmed with remarkable ease.
At the start of the second variation, Black had to choose between consolidation and attack. The right choice was to consolidate the flanks. Probably the programs had no clue, because centralisation is an important criterion. Generally, computer programs have great difficulty in finding consolidation (Van Reek, Uiterwijk, Van den Herik, 1999). Recent examples are the closed positions in the games Van Wely-FRITZ SSS* and Van der Wiel-FRITZ SSS*, Rotterdam 2000 (Hartmann, 2000). The Botvinnik-Fischer endgame demonstrates similar problems in an open position.
In the second part of the second variation, Black had to choose between restriction and attack. HIARCS 7.32 made the right choices. In one case, the program found an alternative win. The achievement of HIARCS 7.32 can be explained by its exquisite positional knowledge. Although it does not know the strategic concept of restriction, it recognizes the positional advantage of decreased mobility. Here brute force overcomes the lacking strategic knowledge with great success.
This article shows how useful chess programs can be for the analysis of historical games. Only the most difficult strategic problem remains unsolved: What are the basic rules for a proper decision between two (or three) distinct strategic concepts?
Botvinnik, M. (1985). Meine 25 interessantesten Endspiele. Walter de Gruyter, Berlin. ISBN 3-11-009539-4.
Fischer, B. (1972). My 60 Memorable Games. Faber and Faber, London. ISBN 0-571-09987-4.
Hartmann, D. (2000). Championship on the FRITZ. ICGA Journal, Vol. 23, No. 2, pp. 101-108.
Reek, J. van (1998). Michail Botwinnik. Schaakspelers als Eindspelkunstenaars. Deel 7. Stichting Eindspel, Margraten. ISBN 90-74827-37-3.
Reek, J. van, Uiterwijk, J.W.H.M., and Herik, H.J. van den (1998). Planning a Strategy in Chess. ICCA Journal, Vol. 21, No. 3, pp. 183-192.
Reek, J. van, Uiterwijk, J.W.H.M., and Herik, H.J. van den (1999). Two Strategic Shortcomings in Chess Programs. ICCA Journal, Vol. 22, No. 4, pp. 239-240.
In the last months of 2000 the Editor was informed on the passing away of two remarkable men, one renowned in science, the other in business. Both had a clear relation to computer chess. We therefore considered it appropriate to honour them by an obituary for which we relied on sources indicated in the footnotes. –Ed.
On August 19, 2000 the Cambridge economist David Champernowne passed away. He was a long-time friend of Alan Turing, a pioneer of computers and computer chess, from the time that they were undergraduates together at King's College, Cambridge. In 1948 the two men devised a chess-playing program which they called TUROCHAMP. It was one of the first such programs and although it was elementary and only ever beat one opponent, Champernowne's wife, who was a beginner, it incorporated important methods of evaluation.
They also devised a form of chess, called round-the-house chess, in which each player had to move before the other had run round the house – if you got back before your opponent had moved, you were entitled to another move. Fast running tended to prevent good thinking, they found, so the problem was to choose the right balance. More importantly, Champernowne was one of the first people with whom Turing discussed his idea of a Universal Machine (now called a Turing machine), and when Turing invented a machine for calculating the zeros of the zeta function, Champernowne lent a hand in grinding some of the wheels.
Changing to economics, Champernowne went on to do doctoral research into income distribution, and was elected in 1937 to a research fellowship. In more recent years, he returned, as he put it, to his old love, worrying at the problem of why the distribution of income and wealth tends to become less and less equal. All this came to fruition in Economic Inequality and Income Distribution, written with Frank Cowell and published by Cambridge University Press in 1998.
In 1936 Champernowne took an assistant lectureship at the London School of Economics where he worked closely with William Beveridge for two years. He became a university lecturer in statistics in Cambridge in 1938 and was drafted into the Prime Minister's Statistical Department two years later. In 1941 he was made Assistant Director of programmes in the Ministry of Aircraft production.
After the war Champernowne returned to his birthplace as director of the Oxford Institute of Statistics, with a fellowship at Nuffield College. He did not, however, find the Oxford intellectual and organisational environment as attractive as Cambridge, and although he was made professor of statistics in 1948, he was soon exploring the possibility of moving back to Cambridge. In 1959 he resigned his Oxford chair to become a reader in economics at Cambridge and a fellow of Trinity. In 1970 he was given a personal chair, as there were no vacancies, becoming a professor of economics and statistics. The most tangible result of Champernowne's first ten years back in Cambridge was his three-volume study Uncertainty and Estimation in Economics (1969). The appearance of this work prompted the British Academy to elect him a Fellow in 1970. The year after that he became an Editor of the Economic Journal, concentrating especially on theoretical and mathematical articles.
David Gawen Champernowne won a scholarship from Winchester to Cambridge in 1931, took a double first in mathematics in two years and then a first in Part II of the economics Tripos to top it off. He published his first papers while still an undergraduate – on the number 0.1234567 891011..., which is now known as Champernowne's constant – but all his life he remained something of a schoolboy, living in a rather fanciful and abstract world, and known to all as Champ. He is survived by his wife, Wilhelmina Dullaert, and their two sons.
David Champernowne, FBA, Professor of Economics and Statistics at Cambridge University, 1970-78, was born on July 9, 1912. He died on August 19, 2000, aged 88.
On July 30, 2000 Sidney Samole, the man behind the first series of microcomputers that played a reasonable game of chess, passed away. Probably many of you have forgotten or even did not know the name of this chess Prometheus who brought the game of chess in a silicon box to the world like Prometheus brought flame and fire to the earth. Sid Samole touched the lives of chess aficionados and computer-chess scientists alike. His characteristic proposal was: "How about a nice game of chess?"
Today it is hard to imagine the chess world without computers. And it is equally hard to imagine being able to appreciate fully American chess history without understanding the position of Sidney Samole. He was the man who dreamed, patented and produced the first commercial chess computer. Samole closely cooperated with Ron Nelson (his first protegee) and later with Dan and Kathe Spracklen. Together with them and through their computer programs he as the team captain holds many world and national titles. Here is a partial list of their championships.
Fidelity's creatures won the first four World Microcomputer Chess Championships (WMCCs): CHESS CHALLENGER won in London 1980, FIDELITY X in Travemünde 1981, ELITE A/S in Budapest 1983, and ELITE X in Glasgow 1984. Moreover, they won the first four US Computer Championships, all held in Mobile, Alabama, in 1985, 1986, 1987 and 1988. A remarkable performance is its first place (tied with DEEP THOUGHT) in the 1988 ACM Championship.
In 1976, Sid owned and operated Fidelity Electronics, a hearing-aid manufacturing firm he had built up with contracts from the Veterans' Administration. Among its other cutting-edge technology, his firm produced high-tech, bio-medical products, such as "myo-electric" hands, prostheses that could actually be controlled by the brain impulses of amputees.
After building three working models and four non-working models, Sid decided to promote his new brainchild at Chicago's Consumer Electronics Show in January 1977. It was clear that Sid's, and his chess computer's, time had come. Under his both imaginative and careful management, Fidelity prospered. Chess computers were hot, and Sid's keyboard-entry models held the field for a time. He went on to produce computerized bridge, checkers, and Othello. He designed and manufactured computerized gin and cribbage, as well as other card games. Fidelity manufactured all its games in the US. By 1989, a recession was in the wind, and Sid was sensitive to its warning breezes. He sold Fidelity Electronics at the top of its value to Hegener and Glaser, a German public firm.
For decades Sidney Samole supported chess. For instance, Fidelity sponsored many first prizes in various US Open Championships. In 1988 the US Chess Federation honoured Sid with its highest award for corporate sponsorship, the Gold Koltanowski Medal. On June 11, 1994, Excalibur sponsored the largest and most successful one-day chess promotion in history, the US Chessathon in New York City's Grand Central Station, where chess-playing children dominated the huge main room, decked with USCF banners. Approximately 400,000 people witnessed the event! His last act for chess constitutes probably the most thoughtfully planned chess endowment of all time, providing for the most impressive building dedicated to chess in the world. It is the new, official home for the World Chess Hall of Fame (yes, it has FIDE's official imprimatur and incorporates the US Chess Hall of Fame as well). The museum is located at 13701 SW 119 th Avenue in Miami, Florida.
In 1995 Samole was appointed a trustee of the US Chess Trust. In 1996 he was elected Vice-President of the US Chess Hall of Fame. In 1997 the US Chess Trust renamed the chess museum "The Hall of Fame and Sidney Samole Chess Museum."
Largely as a result of his role in the tale of the chess-playing microcomputer's Sid became a multi-millionaire entrepreneur. Throughout his life he remained straightforward and self-deprecating about his success. Sidney gave the computer-chess researchers much to ponder and he enjoyed doing it. He is missed in different ways by different people.