ICGA Journal

Vol. 26, No. 3 - September 2003

Table of Contents

Table of Contents145
The Epic Conflict (H.J. van den Herik) 145
Endgame Play in Scrabble (B. Sheppard) abstract 147
Two Learning Algorithms for Forward Pruning (L. Kocsis, H.J. van den Herik, and J.W.H.M. Uiterwijk) abstract 165
Notes:182
Five Visualisations of the k-best Mode (I. Althöfer et al.) abstract 182
A Program for Playing Tarok (M. Luštrek, M. Gams, and I. Bratko) abstract 190
Review:198
The Blue Monty (D. Hartmann) 198
Information for Contributors200
News, Information, Tournaments, and Reports:201
The 7th ACBL's World Computer-Bridge Championship (A. Levy) 201
The Gifu Challenge 2003 World Computer-Go Championship (N. Sasaki) 205
Grandmasters Brutalised in Lippstadt (F. Friedel) 207
Shredder Wins in South America (ChessBase) 210
The 2nd Polish Computer-Chess Championship (M. Szmit) 211
Garry Kasparov vs. X3D Fritz (The Board of ICGA) 213
 The World Computer-Chess Champions (The Board of ICGA) 214
Calendar of Computer-Games Events in 2003 214
The Swedish Rating List (T. Karlsson)215
How the ICGA Journal Reaches You 216

 

THE EPIC CONFLICT

A prediction is a statement of what happens in the future. It may be right or wrong. The most interesting predictions are challenging the human mind to the extreme, up to the point that they are not accepted as an actual forecast. However, as time comes by, research findings often have changed the human opinion. What once seemed impossible is then expected to take place within months instead of decades. Overdoing is a typical human activity. As a case in point, we would like to consider the sportive activities in the month of November 2003. Is Fritz dethroning Kasparov once and for all? Are the best-five programs of the 11th WCCC in Graz, Austria all playing above the human World-Champion level? These questions are often asked by not only specialists but the public.

Stretching the spectrum of predictions somewhat more, George Bernard Shaw1 (1917) remarked: "All great truths begin as blasphemies." Indeed, in the 1950s many people, even researchers, could not imagine that computers would ever outplay human beings in the game of chess. For them, the complexity of the game was as the Holy Grail which should be hidden for always. Now, the Grail has arguably been dug up and is almost in our hands. New York and Graz will show us where we stand and what the prospects are.

The epic conflict is between man and machine, between believers and disbelievers, between scientists and chess players. At this place, I would like to single out one person in particular: Garry Kasparov. He shows time and again that he is prepared to test his skill against the latest scientific progress. So far, Kasparov has played three serious matches (1996, 1997, and 2003) with a fourth coming up in November 2003 (see p. 213 of this issue). The venue will be New York. No other chess players have staked their reputation so many times.

Moreover, Kasparov himself believes that silicon thinking will eventually surpass his own. In future events he expects that in Man vs. Machine matches the human grandmasters may be proud when they score 0.5 point out of six games. However, Kasparov does not indicate any time frame. So far, for the real progress.

The next stage is the virtual progress. The X3D company has given FRITZ a brand new outlook, namely "a play in the third dimension". Kasparov, playing with 3-D glasses, will see a virtual chess-board floating between him and the screen. Nobody knows what impact this will have on his play. Yet, the experience is very interesting and Kasparov is seriously preparing himself for the match.

Immediately afterwards, Fritz will play in the 11th World Computer-Chess Championship in Graz, Austria. There may be outsiders, but it is expected that the tough fight for the ICGA World Computer-Chess Champion title will have five serious contenders: Junior, Shredder, Fritz, Brutus, and Diep. Many believe that after New York and Graz the public opinion will be definitely altered: laymen and scientists will then be convinced of the fact that computers no longer play at the level of the human World Champion but that the best five outperform this World Champion by a large margin.

This forecast brings us back to other games and the scientific discourse. Alongside the 11th WCCC there will be the 8th Computer Olympiad and the 10th Advances in Computer Games Conference, all in Graz. Many games will be played in the Olympiad ranging from Dots and Boxes to the ultimately challenging game of Go. The Conference will pay attention to a similar variety of Games. There are 24 contributions, of which six are on Chess and six on Go; the remaining twelve cover games such as Checkers and Lines of Action as well as Oshi-Zumo and Wythoff games. A complete program can be found at www.cs.unimaas.nl/icga/acg10/.

In an earlier issue (March 2003, p. 61) we have outlined the programme of the Graz events. As a service to our readers we enclose a leaflet with relevant information on all these events. Obviously, we hope to see you all in Graz, the Cultural Capital of Europe 2003. May the city later on remember with pleasure and respect the heroic conflicts then played in the world of games.

Jaap van den Herik

1 G.B. Shaw (1856-1950). Annajanska (1917), p. 262.


 

ENDGAME PLAY IN SCRABBLE1

Brian Sheppard2

Concord, MA, USA
 

ABSTRACT

Although two-person Scrabble3 as a whole is a game with hidden information, once the bag of tiles is emptied it resolves to a game of perfect information. This phase of the game is called the endgame. The state space of Scrabble endgames is characterized by high branching factors (average 200) and shallow depth (less than 15 plies). Expert endgame play involves move generation and tactical search. The article describes several design alternatives for searching this domain, including one based on Berliner's (1979) B* algorithm. The most advanced implementation of this algorithm (implemented in MAVEN, a state-of-the-art computer player) achieves almost perfect play.


1 This is an adapted and updated version of Chapter 8 of Sheppard (2002).
2 Sheppard Company, Inc, Concord, MA, USA. E-mail:sheppardco@aol.com.
3 It is assumed that the readers are familiar with the rules of Scrabble. For the precise rules and the notation of moves we refer to www.scrabble.com.


 

TWO LEARNING ALGORITHMS FOR FORWARD PRUNING

Levente Kocsis, H.Jaap van den Herik, and Jos W.H.M. Uiterwijk1

Maastricht, The Netherlands
 

ABSTRACT

The article investigates two learning algorithms for forward pruning. The TS-FPV algorithm uses a tabu-search (TS) algorithm to explore the space of the forward-pruning vectors (FPVs). It focuses on critical FPVs. The RL-FPF algorithm is a reinforcement-learning (RL) algorithm for forward-pruning functions (FPFs). It uses a gradient-descent update rule. The two algorithms are tested using the chess program Crafty. The criteria used for evaluation are the size of the search tree and the quality of the move. The experimental results show that the two algorithms are able to tune a forward-pruning scheme that has a better overall performance than a comparable full-width search. The main result arrived at is that the FPFs obtained from RL-FPF outperform the best FPVs resulting from TS-FPV.


1 Department of Computer Science, Institute for Knowledge and Agent Technology (IKAT), Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands. Email: {l.kocsis,herik,uiterwijk}@cs.unimaas.nl

 

NOTES

FIVE VISUALISATIONS OF THE K-BEST MODE

I. Althöfer1, J. de Koning2, J. Lieberum3, S. Meyer-Kahlen1, T. Rolle1, and J. Sameith1

Jena, Germany
 

ABSTRACT

In k-best game-tree search the k best moves of a position are computed. In practice, k = 2 and k = 3 are frequently used settings. The note describes a k-best realisation of the alpha-beta algorithm and exhibits five different visualisations of the k-best candidates during the process of iterative deepening.


1 Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität Jena, 07740 Jena – Germany. Email: {althofer,falox}@minet.uni-jena.de, Stefan@meyer-kahlen.de, thomas.rolle@uni-jena.de.
2 Roland Holstlaan 581, 2624 HR Delft, The Netherlands. Email: k.ing@consunet.de.
3 Mathematisches Institut, Universität Basel, Rheinsprung 21, CH 4051 Basel, Switzerland. Email: lieberum@math-lab.unibas.ch.

 

A PROGRAM FOR PLAYING TAROK

Mitja Luštrek1 , Matjaž Gams1 and Ivan Bratko1

Ljubljana, Slovenia
 

ABSTRACT

A program for playing the three-player tarok card game is presented and the complexity of the game is analyzed. To deal with the unknown distributions of other players' cards, the program uses a sampling method that accomplishes hierarchical clustering to select representative sets of cards from a host of randomly generated sets. A game tree is searched with the alpha-beta algorithm using several common enhancements and a novel equivalence transposition table, which groups the positions by strategic similarity instead of storing single positions.


1 Department of Intelligent Systems, Jožef Stefan Institute, Ljubljana, Slovenia. E-mail: mitja.lustrek@ijs.si.


 

REVIEW

THE BLUE MONTY

Deep Blue. An Artificial Intelligence Milestone
by Monty Newborn

Springer-Verlag, 2003
ISBN 0-387-95461-9
$34.95

Reviewed by Dap Hartmann

I generally do not like books that are rushed to the printing press, just days after some important event. Such books often sacrifice accuracy and depth for the (financial) kick to be the first on sale. Garry Kasparov lost the final game of the rematch against Deep Blue on May 11, 1997. Before the month was over, David Goodman and Raymond Keene published Man versus Machine: Kasparov versus Deep Blue. In September 1997, A New Era: How Garry Kasparov Changed the World of Chess by Michael Khodarkovsky, Leonid Shamkovich, and Garry Kasparov was published, and Kasparov and Deep Blue by Bruce Pandolfini followed one month later. Then the storm settled. Until five years later, when the long-awaited inside story by Feng-hsiung Hsu was published. That was worth the wait. But what is the point of yet another book after that? Deep Blue. An Artificial Intelligence Milestone by Monty Newborn was published in December 2002. My copy of the book even has a copyright notice of 2003. Newborn's previous book, Kasparov versus Deep Blue, came out in January 1997, less than a year after the first match. Why did it take him almost six years this time? Everything in the current book was available shortly after the rematch, except the 'where are they now' and the 'how did IBM profit from this match' bits in Chapter 15. That does not justify the long wait; maybe Monty was just very, very busy.

Let me start by getting something of my chest that really annoyed me, and, frankly, greatly surprised me: the editing of this book is appalling. This pertains to the text as well as to the images. How can a book about the greatest intellectual accomplishment to date by a computer contain typos such as 'programmmed' (p.3), 'intellgence' (p.3) 'losng' (p.37), 'o-pening' (p.49), 'vise versa' (p.81), 'dircectly' (p.190), and reisgned (p.312). A simple computer spelling check would have found all of them, including the ones I undoubtedly missed. In addition, there are plenty grammatical errors ('were' instead of 'was', 'though' i.s.o. 'through', 'became' i.s.o. 'become'). And last but not least: blatant errors, the most embarrassing of which is undoubtedly the repeated misspelling of the name 'Charles Leiserson'. The title page proudly mentions 'Foreword by Charles Lieserson'. That same blunder is printed underneath his Foreword, and also on the back cover. Fortunately, Newborn thanks 'Charles Leiserson' in his Preface, mentions 'Charles Leiserson' on p.35, and has an entry in the Index for 'Charles Leiserson'. Names are difficult to get right, apparently. Klara, the mother of the three Polgar sisters, is 'Klara Polgar' on p.62, but 'Klara Polger' in the Index. How she managed to squeeze in between the entries 'Polgar, Judith' and 'Polgar, Zsofia' remains a mystery, as sorting is another thing computers are supposed to be good at. To make up for the 'ie' – 'ei' disaster in Leiserson's name, Newborn calls Norbert Wiener 'Norbert Weiner' on four occasions (p.7-8) in the text, and also in the Index. Yet, on p.14 his name is suddenly 'Wiener'. It is an intriguing mistake: a Google search on 'Norbert Wiener' yielded 16,500 hits, while a search on 'Norbert Weiner' scored 2,250 hits, including the MIT Press website, which advertises the collected papers of Norbert Wiener written by Norbert Weiner. The name is WIENER, believe me!

Why I am hammering home a few typos and some mistakes that could also be considered typos? Well, for one thing, this book was clearly no rush job, so that is out as an excuse. Secondly, the publisher (Springer-Verlag) is supposed to be a respectable publishing company, with high quality standards. And thirdly, I was not finished yet, the agony continues. The picture subscript on p.225 reads "Novag robot moved the pieces for David Kittinger's program Mchess". I don't know which program was inside this 'Novag Robot Adversary', but Mchess was written by Marty Hirsch, while Dave Kittinger wrote several programs, including one called Wchess. In a test match, Deep Blue won "3 of the 4 points against the National Chess Team of Denmark" (p.61). But the 'Summary of Matches' (p.67) lists one win and three draws. Maradonna once scored a goal using his hand, but Kasparov apparently got away with an illegal move. On p.142, Newborn tells us that "Kasparov had the first move. […] he brought out his knight to g3. The match was underway".

Some tables and photos appear on a different page than mentioned in the text. And speaking of photos, what happened there? The picture of David Levy (p.30) looks like a mug shot. The picture of Alan Turing (p.6) is horrible. Two images of the Thomas J. Watson Research Center (p.36 and 66), and the image of the IBM China Research Laboratory have extremely low resolution. And the picture of Carol Moore (head of the IBM Internet team) is a disgrace. In the preface, Newborn thanks her for providing that photo. Was it really as bad as we now see it in print? Somebody should have blown the quality-control whistle. Which brings us to the reproductions of cartoons in Chapter 16 'The Light Side of Deep Blue'. Some are of excellent quality, while others appear to be copies of faxes of 3rd generation copies of crumpled newspaper clippings. In the preface, Newborn promises that this chapter "will leave a smile on your face when you turn the final page of this book!". Maybe, if only he had resisted the temptation to explain all the cartoons to us. What was he thinking? Is it really necessary to explain to someone who has just finished a book on computer chess, a cartoon by Don Addis (p. 249) depicting a young girl carrying a box that reads 'Candy Land game', who knocks on the door of the 'Headquarters of Deep Blue'. It's a funny cartoon. But here comes Monty to explain it to us: "Don Addis depicts a young champion of Eleanor Abbott's game 'Candy Land' coming to see Deep Blue. She has heard of Deep Blue's success and is there to teach it a lesson or two. 'Deep Blue may be the chess champ, but not Candy Land champ,' she says to herself! It might be that she is coming to obtain advice from Deep Blue, rather than confronting it – one more person seeking help. Her facial expression conveys a combination of unhappiness, anxiety, and determination. The unhappiness and anxiety suggest she has come to learn, while the determination suggests battle. However, her strong knock on the door is the clincher, signaling it is battle she sought". Does that beat the fun out of it, or what?

Let me try to finish this review with a few kinder observations. First of all, I must admit that I am indebted to Monty Newborn for his 1975 book Computer Chess. In 1980, it was one of two books on computer chess in my university library. The other one, Botvinnik's Computers, Chess and Long-Range Planning, contained some interesting ideas, but no practical advice whatsoever. Monty's book got me started on writing a chess program, and I hereby thank him for awakening that inspiration. The present book does not explain anything about how computers play chess. That is probably a wise decision, because a writer who opens that can of worms is immediately faced with the problem of how detailed the explanations should be. There are excellent accounts available in the literature, so why include it in a book about the history of Deep Blue? Because that is basically what it is, a detailed account of everything that happened on the way to the New York rematch in which Kasparov was defeated. The story is much more complete than Hsu's book, and it contains all the relevant games in the appendices. The best part of the book is chapter 13, which is a move-by-move account of the final game of the rematch. It is delightfully detailed and takes the reader along for an exciting ride. In other chapters the details are sometimes quite irrelevant, such as that Kasparov arrived in New York on April 23, Monty checked in on April 28, Jerry Brody arrived on the 29th, and CJ Tan on the 30th. Or that Monty joined Kasparov's party for dinner (they had sushi), while on the next page he has dinner with the ACM group and bunch of other people (all of whom he mentions – but not the menu). At times, there is quite a lot of Monty in the story. The third paragraph of chapter 14 consists of seven sentences, each one featuring Monty: "[…] I prepared for the honor […] I began by introducing everyone […] I then thanked Mike Valvo […] I went to great pains to explain […] I then introduced the Deep Blue members […] I thanked a somber and disappointed human world champion […] I began to introduce his supporting team […] I sensed that he wanted to accept full responsibility". The book even features a picture of his cat Floyd, who was "terrific at the keyboard. He loved to perform the Random Paws Blues (in his coat and tails!)". Hardy har har!

Deep Blue is a useful account of the Deep Blue story that did not excite me at any point. The sloppy editing of the book is appalling. If it had come out just a few months after the rematch, time pressure might have been an excuse for both shortcomings. But after five years I accept nothing less than a great book on the events. This is not that book.