ICGA Journal

Vol. 25, No. 2 - June 2002

Table of Contents

Table of Contents 65
Science and News (H.J. van den Herik) 65
Domineering: Solving Large Combinatorial Search Spaces (N. Bullock) abstract 67
An FPGA Move Generator for the Game of Chess (M. Boulé and Z. Zilic) abstract 85
Note: 95
Secrets of Pawnless Endings (G.McC. Haworth) 95

Reviews:

97
Computers and Games (D. Hartmann) 97
Machines that Learn to Play Games (D. Hartmann) 99
Articles Published Elsewhere 101
Information for Contributors 104
News, Information, Tournaments, and Reports: 105
Computers and Octi: Report from the 2001 Tournament (C. Sutton) abstract 105
Report on the IWEC-2002 Man-Machine Othello Match (M. Buro) 113
The 5th Advanced Chess Match (The Editor) 115
Report on the 12th CSA World Computer-Shogi Championship (R. Grimbergen) 116
Report on the First International Workshop on Entertainment Computing (H. Iida) 122
Clobber – A New Game with Very Simple Rules (I. Althöfer) rules 123
Results of the 2nd International CSVN Tournament (Th. van der Storm) 125
The Massy 2002 Chess Programs Tournament (The Editor) 126
Calendar of Computer-Games Events in 2002-2003 126
The Swedish Rating List (T. Karlsson) 127
How the ICGA Journal Reaches You 128

 

SCIENCE AND NEWS

The scientist and the journalist agree: the border region between science and news is as large as the difference between man and woman. In his book Science and Hypothesis, Poincaré stated: "Science is built up of facts, as a house is built of stones but an accumulation of facts is no more a science than a heap of stones is a house." News is usually characterized by 'what recently happened', but in relation to science we are inclined to think of news as a new fact. In our games world, this could be a new game, although the usual meaning of news such as recent tournament results more frequently applies. Closely related to the introduction of a new game, which we regard as news, we sometimes deal with a new strategy, which we regard as science. Hence, the difference between science and news may not be as large as the scientist and the journalist thought when they agreed on the border region.

Usually the news sinks in properly, while science faces hard times as it is difficult to understand and to internalise. The power of the ICGA Journal is that is serves two groups: the scientists and the group of interested news readers. Although right from the start we have divided our Journal into two parts: the scientific section and the news section, the Editorial Board understands that both sections are fully interwoven.

Let us start with the big news from the scientific section. In the first contribution of this issue Nathan Bullock informs us that he has solved the game of 10x10 Domineering. That is quite a performance. Moreover, he provides a clear description on how an adequate combination of knowledge from the domineering area can help the search process to solve many other open questions. The results are impressive and tabulated in an updated chart of these boards for which the game theoretic values are currently known.

Not every scientific breakthrough results in a problem being fully solved. Mostly it is the reverse as science is a collection of small building blocks. Therefore we are proud to publish the first article on the use of FPGAs (Field Programmable Gate Arrays) in chess programs. It is written by Marc Boulé and Zeljko Zilic. However, they are not the first researchers who implemented the FPGA technique as successor to the IC (Integrated Circuit) and ASIC (Application Specific Integrated Circuit) techniques in a chess-playing program. The experimental priority claim comes from the programming team Brutus, headed by Dr. Chrilly Donninger. In their program, the authors successfully incorporated the new technique, but since they work commercially with ChessBase they have not published anything on the matter so far. Obviously, Brutus’ third place in the World Championship in Maastricht was a telling announcement of the new technique.

Crossing the border area between science and news we arrive at the scientific releases of the news section. Here we find the descriptions of two new games, viz. Octi and Clobber. Octi is well described by Charles Sutton and Clobber by Ingo Althöfer. The latter game has little-brother games which have already been solved. Moreover, the programs developed so far for the standard games of Octi and Clobber are said to play on expert level and above.

In a sense the report on Entertainment Computing by Hiroyuki Iida is a breakthrough too. It enlarges the scope of our games world and paves the way for further research in the application domain of computer games entertaining human beings. Clearly, we are now on a borderline of the news section and we should not inadvertently pass by the real news of Gekisashi’s World Championship in the game of shogi. It is given its due by Reijer Grimbergen and the Western world cannot but agree that shogi is quickly approaching the tournament record of the computer-chess world. Experts have told me that over the next ten years the playing strength of shogi programs will increase to a level comparable to that of the best chess programs of 2002. That is big news, especially if it comes true. It would mean that within ten years this news will be in the science section.

In summary, we conclude that science and news can be clearly distinguished by the laymen, but are less clear cut to the experts. They are fascinated by the many interconnections that turn news and science into one smooth and exciting research area.

Jaap van den Herik


DOMINEERING: SOLVING LARGE COMBINATORIAL SEARCH SPACES

Nathan Bullock1

Edmonton, Alberta, Canada

ABSTRACT


Domineering, also known as crosscram, is a perfect-information, two-player game. We have created a search program which is able to prove who wins on many different sizes of boards. Some of the board sizes no one else has ever been able to solve. The main improvement is our evaluation function which can determine statically a winner at a shallower point in the search tree than was previously possible by other evaluation functions. It allows us to eliminate large portions of the search space. Along with a few other improvements, the evaluation function enabled us to solve board positions with just a fraction of the number of nodes which previous solvers needed.
1 Dep. of Computing Science, University of Alberta, Canada. Email: bullock@cs.ualberta.ca.

AN FPGA MOVE GENERATOR FOR THE GAME OF CHESS

Marc Boulé and Zeljko Zilic1

Montreal, Canada

ABSTRACT


This article details the use of an FPGA (Field Programmable Gate Array) to increase the playing strength of the chess-playing program MBChess. The FPGA is a user-reconfigurable logic device well suited to the development of complex digital circuits. In this application, the FPGA is used to perform hardware move generation with implicit move ordering, a time-consuming operation when performed in software. A simpler inter-square connection protocol reduces the number of wires between chess squares, when compared to the Deep Blue design. The design also has the capability of generating checking moves separately, as well as indicating discovered checks: an important feature for good move ordering. Integration to the software's transposition table and killer heuristic is demonstrated as well. The device is mounted on a card and inserted in the host computer where it is used as a coprocessor.


1 McGill University, Department of Electrical Engineering, McConnell Engineering Building Room 633, 3480 University Street, Montreal, Quebec, Canada, H3A 2A7. Email: {mboul,zeljko}@macs.ece.mcgill.ca

NOTE

SECRETS OF PAWNLESS ENDINGS

G.McC. Haworth1

Reading, UK


It is now 32 years since Ströhlein's pioneering computation of KRKN and ten years since the publication of Nunn's Secrets of Rook Endings. This book defined a new genre under his authorship and editorship (Nunn, 1992, 1994, 1995; Müller and Lamprecht, 1999, 2001) and has merited a second edition.

Now comes the second edition of Secrets of Pawnless Endings, in which we not only get a modest refresh of existing chapters on some 15 4/5-man endings but also a generous and ambitious 62 pages on a wide range of deeper and more challenging 6-man endings. An opening table gives some 85 maximal mutual zugzwangs and wins plus Nunn's verdict - seeing beyond the nominal statistics - as to whether the endgame is a general win or draw. Here, his broad conclusions agree with Beasley (2002).

The established recipe, first applied to KQKR and KRKB/N, still seems to be effective: a base of perfect information, a judicious choice of games, positions and moves, and a readable commentary when the significance of the moves can be elicited. The endgame still exhibits understandable themes and principles of play even if it increasingly resembles a combinatorial maze, more navigable by computer than by human, but it.

A technical achievement, easily overlooked, is that Nunn has been manually assigning a '!' where the move is apparently the only way to win, ignoring time-wasting moves that allow a forced return to the current position. Few errors have come to light so far, evidence of remarkable accuracy on Nunn's part.

The changes to the first 13 chapters are essentially cosmetic and the position numbers of the first edition are usefully unchanged. The new 6-man chapter lists all the Thompson results (2001; Tamplin & Haworth, 2001) and focuses on 18 of the 64 endings he computed, namely KRmKmm2 , KRRKRm, KRmmKQ, KQmKRR, KQRKQm and KQMKQM. Of these, KQQKQQ occurred in analysis during the remarkable Kasparov-World game (Nalimov, Wirth and Haworth, 1999) but in the absence of KRmKRm, KRRKRN seems to occur most often over the board. Each longest win is included, exhibiting the outermost reaches of endgame space. While the complete sets of mutual zugzwangs (Tamplin, 2002) are not analysed here as a whole, occasional often pivotal mzugs are highlighted. Nunn usefully follows Thompson in subdividing multiple-Bishop endgames into their distinct parts by Bishop-pattern.

One has to sympathise with those whose endgame play is increasingly caught in the harsh spotlight of infallibility and understand why participants in the Dutch Open of 2000 did not wish to play FRITZ backed by Nalimov's 5-man data (Hartmann, 2000). Although the theoretical result is achieved in two-thirds of the games chosen, depth of win is often unwittingly conceded on a large scale by both attacker and defender.

 

JN327: Nunn (1994). JN118: Rinck (1917). JN395: Dobrescu (1979). JN510: from a longest win.

Although only one 6-man study has been added to the book, enthusiasts of composed positions will now be able to examine over 1300 6-man examples (Van der Heijden, 2001) in the context of both Thompson's data and Nunn's analysis. The composer Rinck and the theme of domination (Kasparyan, 1980) are both well to the fore. Some studies will now be found to be faulty, i.e. cooked, and others to have alternative wins or duals. Readers may care to progress the increasingly difficult positions given. White is to move and win except for JN395 which is a remarkably deep wtm draw: the continuations below are based on Nunn's analysis.

We should not forget that the pursuit of knowledge and intelligence starts with the acquisition of facts. The computer has revealed unsuspected opportunities for both attack and defence. KQKR is harder to win than anticipated; KBBKN (Roycroft, 1984), KQKBB, KQBKRR and KRBKBN with opposite-colour Bishops are now seen as wins. The one computer-computer game in the book suggests that human instinct might triumph over a computer without perfect information, but that a computer could well even turn draws into wins if it could back a human opponent into 'hard to defend' territory. The more common, partitionable, 6-man P-endgames will soon become computable on a large scale so we may well see even more remarkable table-driven computer finales in the future. Nunn even anticipates further changes to established theory.

According to Frederic Friedel, Gary Kasparov acknowledges that "these databases show me things", words which indicate that there is still much to learn about both the endgame and the potential of the chessmen in combination. The verification and discovery of whatever higher-order knowledge there is about chess endgames remain two key AI computer challenges. For the foreseeable future, Nunn's trilogy offers the best opportunity to gain more understanding of the endings covered, and one that practical players also may now increasingly value given the modes of continuous and faster play now in use.

REFERENCES

Beasley, J. (2002). A revised survey of six-man pawnless endings. BESN, Special Number 27 (2nd Edition). ISSN 1363-0318.

Hartmann, D. (2000). Championship on the Fritz. ICGA Journal, Vol. 23, No. 2, pp. 101-108.

Heijden, H.M.J.F. van der (2001). Collection of endgame studies. Chessbase. 

Kasparyan, G.M. (1980). Domination in 2,545 Endgame Studies. Progress Publishers.

Müller, K. and Lamprecht, F. (1999). Secrets of Pawn Endings. Everyman. ISBN 1-8574-4255-5.

Müller, K. and Lamprecht, F. (2001). Fundamental Chess Endings. Gambit. ISBN 1-9019-8353-6.

Nalimov, E.V., Wirth, C., and Haworth, G.McC. (1999). KQQKQQ and the Kasparov-World Game. ICCA Journal, Vol. 22, No. 4, pp. 195-212.

Nunn, J. (1992). Secrets of Rook Endings. B.T. Batsford, London. ISBN 0-7134-7164-6. 2nd edition (1999). Gambit. ISBN 1-9019-8318-8.

Nunn, J. (1994). Secrets of Pawnless Endings. B.T. Batsford, London. ISBN 0-7134-7508-0. 2nd Edition (2002). Gambit. ISBN 1-9019-8365-X.

Nunn, J. (1995). Secrets of Minor-Piece Endings. B.T. Batsford, London. ISBN 0-7134-7727-X.

Roycroft, A.J. (1984). Two Bishops against Knight. EG, Vol. 5, No. 75, pp. 249-252. ISSN 0012-7671.

Tamplin (2002) chess.jaet.org/endings/ Chess endgame-server and reference site.

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

Thompson, K. (2001). cm.bell-labs.com/cm/cs/who/ken/chesseg.html. 6-man EGTs, maximal positions, maximal mutual zugzwangs and endgame statistics.

 

327: 1. Bd4+ Kb1 (1. … R?d4 2. Kc2! Ra4 3. Kb3!; 1. ... Ka2 2. Kc2! Ra5 3.Bc3 Ra6 4. Bb4 Ka1 5. Rc3 Ka2 6. Rc5 Ra8 7. Rb5 Ra6 8. Rb8 Ra7 9. Bc3) 2. Rc1! Ka2 3. Kc3! Rb4 4.Rc2+! Kb1 5. Rh2 Rb7 6. Kd3 Rc7 7. Rb2+ Kc1 8. Ra2 Philidor's win.

118: 1. Qc7+! Ka8 2. Qa5+! Kb7 3. Nc5+! Kb8 4. Qb6+! Kc8 5. Qb7+! Kd8 6. Kd2! a Rinck mzug (p. 95) and win in 1.

395: 1. Rf3+! Ke5 2. Nc4+! Kd4 3. Ne3! Ke4 4. Rf2! Qh1+ 5. Ke2! Qh5+ 6. Kd2! Qa5+ 7. Ke2! Qa2+ 8. Ke1! Qa5+ 9. Ke2! Qa6+ 10. Kd2! Qd3+ 11. Ke1! Qc3+ 12. Kd1! Qd4+ 13. Rd2! Qa1+ 14. Ke2! Qa6+ 15. Kf2! Qf6+ 16. Ke2! Qf3+ 17. Ke1! Qg3+ reflecting position 12w after Black calls for 17 unique moves from White.

510: If you got close, you are probably a computer. 1. 1. Kh2! mzug Kb3 2. Qd3+ Kb4 3. Ne3! Rf2+ 4. Kg1 R2f7 5. Qc4+ Ka3 6. Qc3+ Ka4 7. Kh2 {countering Rg8+} Rf2+ 8. Kh1 R2f7 9. Qb2 Rf6 10. Qa2+ Kb5 11. Qc4+ Ka5 12. Qc5+ Ka4 13. Ng4 Rf5 14. Qb6 Rh8+ 15. Kg2 Rhf8. White has driven the bK to the edge but the wN is not in the attack yet. White wins ... on move 122.

1 33, Alexandra Rd., Reading, Berkshire, UK RG1 5PG. email: guy.haworth@laposte.net.
2 m denotes a minor piece, i.e. Bishop or Knight; M denotes a major piece, i.e. Queen or Rook.


REVIEWS

COMPUTERS AND GAMES

Proceedings of the Second International Conference, CG2000
held in Hamamatsu, Japan, October 2000

Edited by Tony Marsland and Ian Frank

(Lecture Notes in Computer Science 2063)
Springer-Verlag Berlin Heidelberg New York, 2001

ISBN 3-540-43080-6
ISSN 0302-9743
443 pages € 52

Reviewed by Dap Hartmann

The players started to gather around the ball
and kick it towards the opponent's goal

(somewhere in this book)


Filled to the brim with papers on a wide variety of subject, Computers and Games contains the proceedings of the second international conference on computers and games (CG2000) which was held in Japan in October 2000. There are 23 revised papers, carefully selected from a total of 44 papers submitted. In addition, there are five reviews and two invited talks, making a grand total of 30 contributions.

The field of computer games has broadened considerably over the years. I encountered the following games in this book: Amazons, Awari, Backgammon, Boggle, Bridge, Cellular Automata Games, Chess, Chinese Chess, Go, Graph Ramsey Games, Lines Of Action, Othello, Poker, Rock-Paper-Scissors, Scrabble, Shogi, Trivial Pursuit, Virus Games, War Games, and Wheel of Fortune. And the following puzzles: Correspondence Problem, Peg Solitaire Problems, Crosswords, plus a review on RoboCup (soccer for robots). The problem is, how to organize the 30 contributions? Should papers describing a specific game or puzzle be grouped together? Impossible. Some papers deal with several games, for example when discussing a specific search technique. There are two papers on Awari. One describes attempts at solving the game (Awari Retrograde Analysis), the other is titled Learning from Perfection. A Data Mining Approach to Evaluation Function Learning in Awari. Should these papers be kept together, or put in different chapters? (As it happens, the former paper is in Chapter 1, the latter in Chapter 2). There is another paper on retrograde analysis, but applied to Chinese Chess endgames. And Strategies for the Automatic Construction of Opening Books by Thomas Lincke deals with Othello and Awari. So, maybe the papers can be grouped according to specific search techniques. I encountered Abstract Proof Search, Alpha-Beta, B*, Conspiracy Number Search, Disproof-Number Search, MiniMax, NegaMax, Proof-Numbers Search, and Uncertainty Paradigm Search. I may have missed a game, a puzzle or a search technique, but it is immediately clear that there is no apparent way to group the 30 papers. With such a wide variety of games, search techniques, machine learning, and other aspects of computer games programming, it is a difficult task to create any systematic ordering. The editors wisely decided to make four thematic chapters. Each paper is included in the chapter that most closely fits its content.

Search and Strategies contains seven papers, Learning and Pattern Acquisition has four papers. In the preface, these counts are erroneously swapped. Theory and Complexity Issues and Further Experiments with Games each have six papers. Additionally, there is a chapter with the two invited talks (Linguistic Geometry for Solving War Games by Boris Stilman, and Physics and Ecology of Rock-Paper-Scissors Game by Kei-ichi Tainaka), and five reviews (on Computer Language Games, Computer Go 1984–2000, Intelligent Agents for Computer Games, RoboCup through 2000, and Computer Shogi through 2000).

Each papers counts between 9 and 20 pages, with a mean of 15 pages, a median of 16 pages and a standard deviation of 4 pages. There is a 20 page contribution with only three references, while another (18 page) paper has 53 references. It goes beyond the scope of this review to describe every contribution, so I will only briefly mention three papers.

Michael Buro describes the connection between endgames in Amazons and Hamilton Circuits in Cubic Subgrid Graphs. I have some familiarity with the game of Amazons, but I have no idea what Hamilton circuits are, let alone Hamilton circuits in cubic subgrid graphs. Buro explains the rules of Amazons, but does not explain what Hamilton circuits are. There is, however, a definition of what a cubic subgrid graph is.

The ever productive Ernst Heinz (probably the most prolific contributor to the ICCA/ICGA Journal over the past five years) reports new results on the controversial topic of self-play in computer chess. The 24,000 (!!) self play games in his experiment did not suffice to quantify with good confidence the diminishing effect of the increase of playing strength at successive iteration depths. Nevertheless, Heinz reports a decrease in the increase of the playing strength from 169 ELO points (from 6 to 7 plies brute force), to 84 ELO points (from 11 to 12 plies brute force). More clearly than on the non-linear ELO scale, this trend is seen in the winning percentage, which drops from 73% to 62% over the same interval of iterative deepening.

How quickly progress is being made in some areas, is illustrated by Roel van der Goot's paper on the retrograde analysis of Awari (describing databases up to 35 pebbles), and the recent achievement of John Romein (Vrije Universiteit, Amsterdam), who strongly solved the game by creating all databases up to 48 pebbles. Romein presented his work at the third international conference on computers and games (CG2002), which was recently held in Edmonton.

The book is well edited, but there are some inaccuracies (p.202 twice misspells the letter ö in the name of Paul Erdös, as a superposition of an 'o' and a '}', and on p.395, every volume number in the references section has a boldface first digit). There is no uniformity in the reference sections of the papers. The frequently cited Artificial Intelligence paper on Proof-number search by Allis, Van der Meulen, & Van den Herik is found in three different flavors (p.18, p.37, p.441), while the author of Searching for Solutions in Games and Artificial Intelligence is variously listed as: Allis, L.V. (p.37), Louis Victor Allis (p.72), or L.V. Allis (p.86). Not really a big deal, but a little sloppy. As is the fact that not all references are in alphabetical order (p.95, 249, 296, 363, 395). However, I have a more serious point of criticism. In a book dealing with such a wide variety of games, search techniques and related issues, a good subject index is indispensable. Unfortunately, it is missing. Where in this book can you find something on Lines Of Action? (Answer: on p.177, in Learning Time Allocation Using Neural Networks, by Kocsis, Uiterwijk & van den Herik.) Hard to find without an index, when the name of the game is not part of the title of the paper. Even a mere keyword index (using just the keywords provided by the authors at the end of their abstract) would have been useful. Maybe the editors should consider giving a free copy of this book to a volunteer who is willing to create such an extensive subject index. That index can then be made available on the internet. Apart from these mostly minor glitches, Computers and Games provides a good overview of the state of the art in game-playing computers.


MACHINES THAT LEARN TO PLAY GAMES

Advances in Computation: Theory and Practice; Volume 8
Edited by Johannes Fürnkranz and Miroslav Kubat
Nova Science Publishers, Inc., New York, 2001

298 pages
ISBN 1-59033-021-8
US $89

Reviewed by Dap Hartmann

This book is about machine-learning algorithms for playing games
(from chapter 1)


Machines That Learn To Play Games is Volume 8 in the series Advances in Computation: Theory and Practice. Earlier books in this series are on such diverse subjects as Weak Intelligence (Vol. 6) and Structured Matrices (Vol. 4). Volume 9 deals with Imaging and Vision Systems.

"Given the richness of existing literature, why bother putting together yet another book?", asks editor Miroslav Kubat in the introductory chapter Should Machines Learn How to Play Games? (10 pages). He proceeds to answer that question: "The secret behind human game-playing strengths is the ability to generalize from instruction and from past experience, to learn patterns that expedite decision making. With the continuing progress in machine learning, the number of scientists adopting this view and pursuing serious research along these lines has grown to the point that gives raison d'être to an entire book devoted to this theme". Kubat summarizes the book as follows: "The papers collected in this volume describe how to instill learning skills in game-playing machines. The reader is asked to keep in mind that this is not just about games – the possibility that the discussed techniques will be used in control systems and in decision support always looms in the background."

Co-editor, Johannes Fürnkranz, presents a 50-page survey of Machine Learning in Games. Starting with the work of Arthur Samuel on checkers, this chapter discusses Book Learning, Evaluation Function Tuning, Learning Patterns and Plans, and closes with a short overview of Opponent Modeling. The author's conclusion does not provide any deep insights: "If there is a conclusion to be drawn from this survey, then it should be that research in game playing poses serious and difficult problems which need to be solved with existing or yet-to-be-developed machine learning techniques."

In Human Learning in Game Playing (20 pages) Fernand Gobet and Herbert Simon give ample attention to 'chunking', a concept that Chase and Simon developed in the early 1970s. At the end of the paper, the authors briefly address two interesting questions ('How has human learning informed machine learning?' and 'What does machine learning tell us about human learning?'), but no great revelations follow.

Michael Buro has the shortest contribution (9 pages), Toward Opening Book Leaning, in which he presents an opening book framework for game-playing programs. Buro describes how to find reasonable alternatives to moves that have previously led to lost games. Several of the best Othello programs use this technique.

The learning abilities of the chess program KNIGHTCAP allowed it to improve from an ELO rating of 1650 to 2150 in just three days of play on Internet chess servers. In Reinforcement Learning and Chess (26 pages), Jonathan Baxter, Andrew Tridgell and Lex Weaver explain how this was accomplished with TDLeaf(λ), a variation on the TD(λ) algorithm developed by Richard Sutton and based on Arthur Samuel's Temporal Difference Learning. TDLeaf(?) was also applied to Backgammon, but it did not improve over standard TD(λ).

Gerald Tesauro presents a Comparison Training of Chess Evaluation Functions (14 pages). Tesauro has a PhD in theoretical physics from Princeton University, and is a research staff member at the IBM T.J. Watson Research Center. Rings a bell? It is, of course, home of DEEP BLUE. Tesauro describes how DEEP BLUE's evaluation function was trained. Remember that phenomenal move Be4 in game 2 of the rematch against Kasparov? The move that Kasparov could not believe a computer program capable of playing. It happened because of a tweak made to the king-safety weights after a post-mortem analysis of game one. With the original weights, DEEP BLUE would have played the material-greedy Qb6.

Feature Construction for Game Playing (22 pages) by Paul Utgoff discusses the problem of choosing informative features for evaluation functions, and describes a method that automates the process. "Constructing good features is the major developmental bottleneck in building a system that will make high quality decisions", says Utgoff. Some of the major problems are that knowledge is generally built up in several layers, and that individual features may be overlapping.

The introduction section of Learning to Play Expertly: A Tutorial on Hoyle (26 pages) by Susan Epstein begins as follows; "HOYLE is a program that plays board games. What is novel about HOYLE is that it learns to play a variety of games, learns to play them quickly, and learns to play them well". That settles it then – computer games researchers can now move on to do other things. Well, not so fast. HOYLE plays relatively simple games, such as tic-tac-toe and 5-men's Morris. But it learned how to play some of these games flawlessly from competing against a perfect player. Rather than a program which consists of separate modules, each of which plays a specific game, Epstein feels that "HOYLE resembles a person who already plays many games well, and then learns a new game".

In Acquisition of Go Knowledge from Game Records (25 pages) Takuya Kojima and Atsushi Yoshikawa describe two ways of extracting Go knowledge from recorded games between human experts. The Deductive Approach acquires strict knowledge (rules), while the Evolutionary Approach extracts heuristic knowledge. Although the authors claim that their algorithms for this latter approach can also extract heuristic knowledge from normal Go games, they have applied it here to tsume-go problems (life and death problems) for benchmarking purposes. The performance is said to be as good as 1 dan human players.

Fredrik Dahl also uses a database of expert-level Go games to train a computer program. In Honte, a Go-Playing Program using Neural Nets (19 pages), he explains how his Go program HONTE uses a combination of neural nets and more traditional AI techniques, such as alpha-beta search. More interesting than his general conclusion "Although HONTE has not yet reached the level of most popular commercial Go programs, results are promising", is Dahl's remark that "Our work highlights a problem associated with modeling based on human concepts, in that any misconception held by the programmer may be inherited and exaggerated by the program." That implies that programmers should not tell their programs what to learn specifically. Let them find out for themselves.

The final chapter in this book is Learning to Play Strong Poker (18 pages) by Billings, Peña, Schaeffer and Szafron. The challenge of programming a computer to play poker, is that it is a game of imperfect information, as the opponent's cards are not known. In the game of poker, deception, unreliable information, risk management, and opponent modeling outweigh the search component – the reliable solution to achieve strong performance in most perfect-knowledge games. The authors give a list of requirements for a world-class poker player, whether human or computer. Up to this point in time, "Our work has made some progress towards achieving a poker-playing program that can learn and adapt." The team is currently increasing efforts to improve opponent modeling, which offers the biggest potential performance gains.

Machines That Learn To Play Games is well edited and firmly bound. The figures are generally clear and clean, with the exception of Figures 10.2 and 11.1. There is a good person index and an excellent subject index (18 pages!). Future editors take heed! This subject index is a textbook example of how you should create one for your next book. A reader who wants to know about opponent modeling in Go, can find the proper place (page 57) under 'Go' subhead 'opponent modeling', and also under 'opponent modeling' subhead 'Go'. The entry 'Go' has 30 subheads, while chess has 36, ranging from 'grandmaster draws' to 'inductive logic programming'. 

The ghost of the late Bob Herschberg haunts through this book. The two references listed in the Person Index do not lead to his name in print. He is supposedly mentioned on page 56 and on page 236, but nothing there appears to refer to Herschberg. Maybe page reformatting messed up the proper page referencing and caused an offset by one page? Alas, his name does not appear on the previous or on the next page either. I finally solved this little mystery, and leave it as an exercise to the reader to find the solution.

If you are eager to learn about computers learning to play games, then Machines That Learn To Play Games is your book.


News, Information, Tournaments, and Reports

COMPUTERS AND OCTI: REPORT FROM THE 2001 TOURNAMENT

Charles Sutton1

Amherst, MA, USA

ABSTRACT


Computers are strong players of many strategy games, but in some games, namely Go, success has been more elusive. Thus, it may be fruitful to explore games with intermediate complexity. Octi is such a game.I describe the game of Octi, report results from the 2001 Computer Octi Tournament, and explain why Octi may be a useful domain for research in game AI.


1 Dep. of CS, University of Massachusetts, Amherst, MA, USA. Email: casutton@cs.umass.edu.

CLOBBER - A NEW GAME WITH VERY SIMPLE RULES

Ingo Althöfer1

Jena, Germany

The Rules of Clobber

Clobber is a board game for two players White (o) and Black (x). It is played on a rectangular grid of size m ? n. The players move in turn, with White to start. The last player to move is the winner. Draws are not possible. In the endgame a position typically splits into disjoint groups. So combinatorial game theory may be applied to simplify the computation of game-theoretic values considerably.

When a player is to move he has to jump orthogonally with one of his stones on a stone of the enemy which is placed on a directly neighbouring square. This piece of the enemy is deleted (it has been "clobbered" – hence the name "Clobber"). In the starting position the board is completely filled with stones, alternating white and black ones. So, for instance on the 6 ? 5 board white stones are on a1, a3, a5, b2, b4, c1, c3, c5, d2, d4, e1, e3, e5, f2, f4 and black stones on the remaining squares a2, a4, ... f5. In each move exactly one stone is clobbered. Hence, a game starting with the full m x n-board will last at most m x n - 1 moves.


1 Faculty of Mathematics and Computer Science, Friedrich-Schiller University Jena, 07740 Jena, Germany. Email: althofer@minet.uni-jena.de.