ICCA Journal

Vol. 22, No. 4 - December 1999

Table of Contents

Table of Contents193
The Last Issue (H.J. van den Herik)193
KQQKQQ and the Kasparov-World Game (E.V. Nalimov, C. Wirth, and G.Mc.C.Haworth) 193
Rotated Bitmaps, a New Twist on an Old Idea (R.M. Hyatt) 213
Learning Piece-square Values using Temporal Diffences (D.F. Beal and M. Smith) 223
Notes:
The Kasparov-World Match (P. Marko and G.McC.Haworth) 236
Two Strategic Shortcomings in Chess Programs (J. van Reek, J.W.H.M. Uiterwijk, and H.J. van den Herik) 239

Review:

Hands off Hans! (D. Hartmann) 241
Information for Contributors244
News, Information, Tournaments, and Reports:
Advanced Shuffle Chess with Technical Improvements (I. Althöfer) 245
Report on the 19th Open Dutch Computer-Chess Championship (Th. van der Storm) 252
Calendar of Computer-Games Events in 1999 and 2000 254
Report on the First Meeting of the Special Issue Group on Games Informatics (H. Iida, H. Matsubara, and A. Yoshikawa)255
ICCA Journal Referees in 1999 (The Editorial Board) 257
The Swedish Rating List (T. Karlsson) 258
Brains of the Earth (J. Nunn and F. Friedel) 259
Make Sure the ICGA Journal Reaches You 264

 

THE LAST ISSUE

This last issue of the ICCA Journal coincides with the end of the century, in which the computer-chess programmers have achieved their aim of beating the human World Champion. The researchers are now looking for the next challenge. For some, it is solving the game. Although this is considered to be practically impossible, persistent computer-chess researchers have already made the first step in this direction by digging up new knowledge from databases or by postulating and showing some empirical evidence that the game is a win for White.

For other researchers, the next century must show the applicability of the computer-chess techniques in other games. Since the ICCA will serve both groups, it was decided (see Vol. 22, No. 3) that after January 1, 2000 the ICCA Journal will continue under the name ICGA Journal, meaning the International Computer Games Association Journal. The official transformation of ICCA into ICGA will take place at the next Triennial Meeting in 2002. For the moment, readers will be a member of the ICCA and will receive the ICGA Journal.

The Editorial Board will be broadened and in the spirit of the IJCAI-97 Workshop (Nagoya, 1997), the CG’98 Conference (Tsukuba, 1998) and the ACG9 Conference (Paderborn, 1999) the pages will be open to research results from other games, such as Go, Shogi, Backgammon, Bridge, Poker, Sokoban, Scrabble and Crosswords. We stress that the ICGA Journal focuses on computer games and/or the use of computers in games. In this respect we are complementary to the Mathematical Games Section of Theoretical Computer Science, where the emphasis is laid on the mathematical and computational analysis of games.

The transformation of the ICCA Journal into the ICGA Journal will open the door to breakthroughs in a plethora of games, some of them still to be invented. Knowing the perseverance of many researchers the following question posed more than ten years ago at the Second Computer Olympiad will soon become more prominent: Which Games Will Survive? Will it be Go, Shogi or Chess? Or will it be a new popular game, for instance comparable with Rubik’s Cube? To your Editor, such questions also will be a guideline for his publication policy, i.e., he will support contributions on how humans play games in comparison with computers, on cognitive research, on social aspects of game-playing programs, on philosophical issues, etc.

Together with this invitation for contributions, I would like to stress that the ICGA Journal will maintain the standards of the ICCA Journal as achieved over the years. It is a scientific Journal and as such recognised by the ISI (Institute for Scientific Information). The usual procedures with peer refereeing etc. will be continued. All in all, the ICGA Journal constitutes a new challenge for Editors and contributors alike.

Looking back into the century behind us, I would like to thank many persons with whom I have worked quite closely to give the Journal its present status and prestige. You all did a superb job and I am sure that the ICCA Journal was instrumental in achieving the goal of defeating Garry Kasparov. Next to the editorial staff, I would like to name two persons who did a fantastic job in bringing the Journal up to the level of being recognised world-wide as a leader in the field, by contributing themselves and by encouraging many other (young) researchers. They are the late Professor Bob Herschberg of the Delft University of Technology and Professor Jonathan Schaeffer of the University of Alberta. Thank you, gentlemen!

This last issue contains a somewhat paradoxical issue. Since 1997 the computer-chess community is proud that the Deep Blue researchers (Feng-hsiung Hsu, Murray Campbell, C.J. Tan, Joseph Hoane, Jerry Brody and Joel Benjamin) defeated Garry Kasparov. However, in this issue the same community admits, even in two contributions, that their findings did not provide sufficient support for the World Team in their contest with Garry Kasparov. The human World Champion has taken revenge for his 1997 defeat by beating the World Team (a combination of computers, computer-chess researchers, grandmasters including the FIDE World Champion Khalifman, etc.) convincingly in an exciting game. Quite a top performance! We offer Garry Kasparov our congratulations, and hope to report soon on his participation in a world-championship match with computers involved.

In the foreseeable future we look forward to three such matches, viz. the Advanced Chess World Championship, the Shuffle Chess World Championship and the "normal" World Chess Championship. In the past we have reported on Othello and Checkers matches in which the World Champion was involved. Now we envisage (1) reporting on analogous matches in many other games in our news section which will be maintained, and (2) putting on record the underlying scientific and technological breakthroughs in scientific contributions.

Finally, the very last issue of this last issue is money. We encourage all our members to renew their membership for themselves and to offer their game-playing partners a membership for 2000 to become familiar with many distinct computer games. Meanwhile we will strengthen our ties with the Mind Sports Olympiad, during which we will be organising the World PC-based Chess Championship (previously WMCC). For the next century we have diversities of games and contributions, but the same spirit: finding the ultimate truth in whatever game.

Jaap van den Herik


KQQKQQ AND THE KASPAROV-WORLD GAME

E.V. Nalimov1, C. Wirth2 and G.McC. Haworth3

USA, Switzerland and the UK

ABSTRACT


The 1999 Kasparov-World game for the first time enabled anyone to join a team playing against a World Chess Champion via the web. It included a surprise in the opening, complex middle-game strategy and a deep ending. As the game headed for its mysterious finale, the World Team requested a KQQKQQ endgame table and was provided with two by the authors. This paper describes their work, compares the methods used, examines the issues raised and summarises the concepts involved for the benefit of future workers in the endgame field. It also notes the contribution of this endgame to chess itself.


1 Microsoft Corporation, One Microsoft Way, Redmond, WA 98052-6399, USA: eugenen@microsoft.com
2 ETH Zürich, Institute für Theoretische Informatik, CH-8092 Zürich, Switzerland: christoph.wirth@inf.ethz.ch
3 ICL, Sutton's Park Avenue, Sutton's Park, Reading, Berkshire, RG6 1AZ, UK: guy.haworth@icl.com

ROTATED BITMAPS, A NEW TWIST ON AN OLD IDEA

Robert M. Hyatt1

Birmingham, USA

ABSTRACT


This paper describes some developments related to using bitmaps (64-bit integers using one bit for each square of the chessboard). In late 1994, after the ACM computer-chess event in Cape May, New Jersey, I decided to embark on a complete replacement chess program for CRAY BLITZ. I was interested in using the bitmap approach mentioned by Slate and Atkin in CHESS 4.x to determine for myself whether this approach was suitable for chess or not. In developing this new program, the concept of rotated bitmaps was developed, and this turned out to be what was needed to make this type of data structure produce reasonable performance.


1 Computer and Information Sciences, University of Alabama at Birmingham, 115A Campbell Hall, UAB Station, Birmingham, AL 35294-1170. Email: hyatt@cis.uab.edu.

LEARNING PIECE-SQUARE VALUES USING TEMPORAL DIFFERENCES

D.F. Beal and M.C. Smith1

London, England

ABSTRACT


This paper reports on the results obtained from using improved temporal difference learning methods to learn piece-square weight sets for use in a chess program. The learning takes place solely from self-play, starting from zero values. A comparison is made between values learnt from piece weights only, and piece weights plus positional weights. The weight sets obtained, when displayed as grey-scale diagrams matching chessboards, can be visually seen to correspond to various items of simple chess knowledge of the type found in elementary chess books, and regarded as basic information for beginning chess players. The paper also considers the effect of the squashing function used to map evaluations into probabilities-to-win.


1 Department of Computer Science, Queen Mary and Westfield College, University of London, Mile End Road, London E1 4NS, England. Email: Don.Beal@dcs.qmw.ac.uk

NOTES

THE KASPAROV-WORLD MATCH

P. Marko1 and G.McC. Haworth2

Canada and UK


The Kasparov-World match was initiated by Microsoft with sponsorship from the bank First USA. The concept was that Garry Kasparov as White would play the rest of the world on the Web: one ply would be played per day and the World Team was to vote for its move. On June 21st, 1999, the game duly began with the Team headed by moderator Danny King and four leading young players as coaches, each independently recommending a next move.

With an appropriate emphasis on youth and the future, the coaches were GM Etienne Bacrot (France, 16), FM Florin Felecan (USA, 19), Irina Krush (USA, 15) and WIM Elisabeth Pähtz (Germany, 14). The World Team members not only voted but gradually came together as an effective group around a bulletin board, with a few individuals emerging to fulfil key roles. The unofficial team’s strength can be judged in the context of current FIDE listings from the following selection of members, given in illustration with aliases in italics and apologies for omissions: Alvarez, Amann, Ansell, Bacik, Bauma, Beer, Bennett, Calhoun, Cardoso, Casual Observer, Chernoff, Epishin, Ethelontis, Fleming, Gagne, Gavriel, Georghiou, Gurevich, ter Haar, Henley, Hodges, Kacheishvili, Karayiannis, Karrer, Kastner, Khalifman, Knopfler, Koval, McCarthy, Mikkelsen, Mobley, Morris, Nesis, (Georgi and Vassily) Orlov, Pihlajasalo, Plaskett, (Ken and Natasha) Regan, Rihaczek, Sakaev, Sims, Solozhenkin, Speelman, Spiegel, Spiriev, Spy49, Suttles, Svidler, Ulf, Vaingorten and Wilczek.


1 SpaceBridge Networks Corporation, 115 Champlain St., Hull, Quebec, J8X 3R1, Canada. Email: pmarko@spacebridge.com.
2 ICL, Sutton’s Park Avenue, Sutton’s Park, Reading, Berkshire, RG6 1AZ, UK. Email: guy.haworth@icl.com

TWO STRATEGIC SHORTCOMINGS IN CHESS PROGRAMS

J. van Reek1 , J.W.H.M. Uiterwijk , and H.J. van den Herik2

Margraten, The Netherlands / Maastricht, The Netherlands


Chess programs have great difficulty in finding the correct moves for the strategic concepts consolidation and positional sacrifice. We suggest the application of two evaluation criteria as a solution, viz. the strengths of a blockade and the control over one’s own territory.


1 De Erk 8, 6269 BJ Margraten, The Netherlands.
2 Universiteit Maastricht, Department of Computer Science, Faculty of General Sciences, P.O. Box 616, 6200 MD Maastricht, The Netherlands. Email: {uiterwijk, herik}@cs.unimaas.nl

REVIEW

HANDS OFF HANS!

The System
by Hans Berliner

Gambit Publications Ltd.
ISBN 1901983102
£14.99; $24.95

Reviewed by Dap Hartmann1 


"Arrogance is knowing that less than 1% of the signals out there are worth paying attention to;
and humility is realizing that it is impossible to recognize in real time which signals these are."

Hans Berliner

It is quite unusual to garnish a book review with a quote from the author of that book and, furthermore, a quote that is not even taken from the book. But it fits the review of an unusual book by an unusual man. The source of this statement is the response that you got, several years ago, when you 'fingered' Berliner's computer account at Carnegy Mellon University. It stuck to me like glue and ever since, I have seen it confirmed over and over again. At first glance, one might appreciate it as a worthy motto for the SETI (Search for Extra Terrestrial Intelligence) institute. But then the truth hits you like a wet blanket, and you realize that it applies to everyday life more than you would wish.

The System is another way to look at chess; another way to consider the choice of move; another way to develop your pieces in the opening; another approach, another attitude towards the game. "I will have to await the judgement of time on this matter", is the final sentence in this book. It refers to whether or not Berliner's System [his boldface] may rank among the innovative ideas and notions in the history of chess, developed by chess greats such as Steinitz, Capablanca, Nimzowitsch, and Alekhine. Note that Berliner speaks of "the judgement of time", and not of the judgement of contemporary chess reviewers, many of whom proved to be largely incapable of reading.

Most of the reviews I have seen revolve around two themes: (1) Berliner is very arrogant; (2) Berliner claims to refute certain openings but does not deliver. I will try to address both issues as objectively as I can. First, is Hans Berliner arrogant? He won the 5th correspondence chess world championship by the unprecedented margin of 3 points (previous championships had been decided by either ½ or 1 point). His correspondence chess record is +94 =10 –1, that is 94%. IM Jeremy Silman writes in his review that "[correspondence chess players] never […] realize that their understanding of chess as a whole [is] so far below any over-the-board World Champion's […]". Actually, on p.165, Berliner says that "I have found that during my career in the 1960s, the top correspondence players were, with certain notable exceptions, not among the class of OTB [over the board] IMs or GMs. These players […] lacked a little in positional understanding, and in overall understanding of opening play." I think it is fair to say that Berliner himself should be regarded as one of these notable exceptions: In 1957, he finished fifth in the US Invitational Championship, behind Fischer, Reshevsky, Lombardy, and Sherwin. The year before, he won the Eastern States open, ahead of Rossolimo, Lombardy, and Fischer. Clearly he has proven himself a highly skilled OTB player, and it is very unlikely that he suddenly lost his talent when he took up correspondence chess. Still, Silman insists that "[correspondence chess players] play the openings exceedingly well (though far below super GM level, of course)". Perhaps IM Silman should explain where lies this gap between "exceedingly well" and "super GM level".

Silman provides the perfect bridge to the second theme by stating: "Having an ego is one thing (all good players have one), but to claim that you have refuted several popular openings is quite another." Most reviewers blatantly ignore what Berliner writes in the very first paragraph of the Foreword: "[This book] is not a compendium of opening variations. You will not be able to look up your favourite lines here!" Clear enough, I would think. At least, I noticed the use of the word 'not', twice. Nevertheless, in his review, National Master Randy Bauer writes that there is "no mention of the lines mentioned in Nunn's Chess Openings". Well, Master Randy, what part of "You will not be able to look up your favourite lines here!" did you not understand? Not only have you ignored Dr. Berliner's heed in the first paragraph of his book, you also seem to be totally unaware of how much time elapses between the submission of a manuscript, and the moment when it appears on the shelves of your local bookstore. In plain English: Nunn's book was not out when Berliner was working on his. Young Randy, and most other reviewers for that matter, appear to be particularly intrigued by the latest developments in the Grünfeld Defense. I will not descend into the perilous details of providing variations here, but 12. … Qa3! seems to be the crucial move that The System fails to address. How is it that all these reviewers point this out? Is it so incredibly obvious, or have they simply read each others reviews? Taylor Kingston remarks that Qa3 "goes back at least to Brown-Kudrin, Philadelphia Open 1992, and was given considerable notoriety by Kamsky-Anand, Las Palmas 1995". Considering that writing a book takes several years, and that The System is not a compendium of the latest developments of opening theory, it is a ridiculous criticism. Berliner has developed his ideas of System play over the course of 50 years. He had a newspaper column in the Washington Post in the late 1960s, in which he first described some of the System play ideas. In fact, there are sections in the book that date back to this period.

The premise of The System, namely that White’s first-move advantage is real and can be maintained throughout the game, makes it vulnerable to attacks such as mentioned above. But there is no other way to illustrate the ideas behind System play than to give examples. Even though the principles of The System are uniformly applicable throughout the entire game, all the way into the far endgame, the claim that the first-move advantage can be maintained demands proof. The careful reader will notice that Berliner describes at various places his enormous difficulties in coming up with the right answer. And there are cases where he frankly admits that he does not know the answer (yet). In that same highly-criticized line in the Grünfeld mentioned above, Berliner openly admits his doubts and insecurities. For a long time in his career, he believed that 10. h4 was the correct move to play. But "I played it three times in the 5th World Correspondence Championship […] and was lucky to get two points out of three games." When he realizes, after many years of active play and post-mortem analyses, that 10. Rc1 is much better, he writes: "The System and winning move is 10. Rc1." That, clearly, was the 'release the hounds' signal. Suddenly, National and International Masters are all over him, throwing the latest instances of "super GM level" play at this mere "postal champion of the world". And, according to Jeremy Silman, postal players are "a bit out of touch with the realities of chess understanding". But fortunately he candidly admits that he is prejudiced.

The correct way to appreciate The System is as follows. It is a proven fact that more games are won by White than by Black. Clearly that must point to some implicit advantage for having the first move. The White player has the initiative in the opening, and as such is able first to make the moves that, according to whatever principles you want to adhere to, give him an advantage. In The System the advantages one should strive for are both well-known principles (Piece Location, Development, and Board Control) as well as new (or at least relatively-unknown) principles such as Options, Response Pairs, and Transpositions (all of which are clearly explained in the book). However, the very first principle is: Tactics Rules. No matter how beautiful your piece placement, you should not have to sacrifice more than a Pawn to attain that. According to the principles of The System, the ideal first three moves for White are: 1. d4 2. c4 3. Nc3. Accomplishing that gives White a clear dominance in the center. Very important throughout the entire discussion of The System is the control over the square e4. The Knight on c3 does an excellent job there, and in many variations the kingside Bishop will move to d3, after which the kingside Knight will move to e2, either preparing f4, or moving to g3. I found that there are two highly-original ideas as a natural consequence of applying the System principles to the move selection. One is that castling is not always a logical move. The other is that the move f3 can be applied frequently with stunning effectiveness. It occurred to me that two principles ('castling is frequently a very sound move', and 'f3 is generally a weak move') that were deeply rooted in my play were suddenly being questioned by The System.

And there we have arrived at the crux of the entire book: it makes you think. It makes you re-evaluate the principles that you have become so attached to. The System does not provide you with a move-by-move strategy of winning every game you play with the White pieces. What is does do, is make you re-appraise many of the standard moves in the opening. I think that Berliner makes a very convincing case that after 1. d4, the most natural move (read: The System move) is 2. c4, and not 2. Nf3. Certainly, you are not lost after Nf3, but you do block the f-Pawn, and you will have a harder time controlling e4. Admittedly, his way of presenting The System is a bit unorthodox. But a first reading (and in the case of some of the critics clearly a mere casual reading) does not measure up to 50 years of thinking about it. Over the years, Berliner has become convinced that The System is real, and that the moves are 'merely' to be discovered. He gets heavily criticized when he compares The System to the theory of gravitation and the theory of evolution, which Kingston rejects as "presumptiousness [sic] that […] ventures into arrogance". The point Berliner tries to make is that both these laws of nature were 'out there' all along, until Newton, Einstein, and Darwin unveiled them. It is being used as a metaphor, but if you are convinced that Berliner is presumptuous, arrogant, name-dropping, patronizing, egoistic (and I could pluck a few more adjectives from the various reviews), then it is easy to be deluded into thinking he expects to be mentioned right along with those greats in the history of science. Malicious thoughts obviously corrupt reason. Why is it so hard to just read what is written, as opposed to transforming vile prejudices into 'facts'? "Even to aspire to be among these greats may seem to many to be a vainglorious dream", Berliner admits in the Epilogue. But these greats are the men of chess who have developed new ideas or devised other Systems pertaining to the game of chess.

Strangely enough, the reviews that most ferociously attack Berliner’s book also contain elaborate back-peddling paragraphs: "There is the possibility that Berliner is entirely right […]" (Kingston), "[…] he’s either poorly informed, deluded, or the greatest genius chess has ever seen" (Silman). Why not become a Catholic, on the off-chance that there is a heaven, eh? The most ridiculous is this one: "[…] his name-dropping and obvious […] egocentric ravings only proves [sic] how little he really knows (or how much, if he proves to be correct!)", also barfed up by Silman. Sure, and all brontosauruses are thin at one end, much much thicker in the middle, and then thin again at the far end (Anne Elk).

There are few chess books that provoke the reader into slowing down the pace of playing the opening moves of the game. Let's face it, modern opening theory has evolved so much that few people will pause after 1. d4 Nf6 2. c4 e6 3. Nc3 d5 and ask themselves the question: What is the correct 4th move? Yet, The System does just that. It spends considerable effort to argue that 4. cxd5 is The System move, while 4. Bg5 is not. It is easy to see how the majority of the reviewers was misguided by Berliner's somewhat authoritative style of writing: "White's 4th move is a System move; therefor, 7. … Bf5 must be an error […]". But that is how scientific writing is done! You do not put forward a theory, and then continue to argue that 'suppose that perhaps my theory is right, it might then follow that …'. No, you first present your theory, and then continue to analyze all its implications. Sure enough, in the conclusions, you re-evaluate the situation, and ponder the consequences should the theory be flawed after all. Hans Berliner is a scientist and a chess player. Naturally, his style of writing is an amalgam of the two disciplines. Chess players may feel he presents his ideas with too much authority, while scientists will argue that he has entered a highly-speculative domain where no rigorous theory may exist. When chaos theory was first presented, orthodox mathematicians felt that the whole premise was just a farce, whereas the people dealing with chaos in the real world thought it was too presumptuous to think one could formalize such events. Personally, I do not believe in a universal theory of chess, and I am happy to say that I do not regard The System as an attempt to be that. How can reviewers ignore frank statements such as "I wish it were possible to say that the good ship System is now safely berthed in some friendly harbour. Unfortunately, that is not the case, and even though I hope to spend another 10 years on this endeavour, it is not realistic to assume it will be completed by then." Does that sound like someone who arrogantly proclaims that he has discovered the undisputed theory of chess? Hans Berliner is an unusual man with a very direct approach. The title of the 5th collection of Dilbert cartoons could easily be his credo. Just replace "Always postpone meetings with" by "Life's too short to deal with". If you find that rude or offensive, you may choose to dislike the man, but you should be fair in judging his book. Fischer is one of the most outspoken anti-Semites since Hitler. Yet one of them wrote a masterpiece.

I warmly recommend The System to anyone who appreciates chess as a battle for ideas, a quest for beauty, and a source of inspiration. I was so absorbed in it, one late night when I was riding home on the bus, that I didn’t notice I was in the wrong bus until 20 minutes later. It was a very long walk back home.


1 Radioastronomisches Institut, Universität Bonn, Auf dem Hügel 71, 53121 Bonn, Germany. Email: dap@astro.uni-bonn.de