ICGA Journal

Vol. 25, No. 4 - December 2002

Table of Contents

Table of Contents 201
On Equal Footing (H.J. van den Herik) 201
The Way to Go (K. Chen) 202
Static Eye in "The Many Faces of Go" (D. Fotland) abstract 203
Semi-Empirical Quantitative Theory of Go. Part I : Estimation of the Influence of a Wall (Z. Chen) abstract 211
Position Evaluation in Computer Go (M. Müller) abstract 219
Review: 229
Chips Challenging Champions (D. Hartmann) 229
Information for Contributors 232
News, Information, Tournaments, and Reports: 233
The Clash of the Titans: Kramnik – FRITZ BAHRAIN (K. Müller) 233
The Match from FRITZ' View Point (M. Wüllenweber) 239
The 6th ACBL World Computer-Bridge Championship (A. Levy) 241
The 21st Century Championship Cup 2002 (B. Myers) 245
The 22nd Open Dutch Computer-Chess Championship (Th. van der Storm) 246
The 9th French Computer-Chess Championship (F. Louguet) 248
Report on the Symposium Man vs. Machine: the Experiment (O. D. Tabibi and N.S. Netanyahu) 250
Amazons Exhibition Games of Humans+Computer Teams (I. Althöfer and S. Wehmeier) 252
The Game of Bao (H.H.M.L. Donkers) 255
Backgammon at the 7th Computer Olympiad (F. Berger) 256
The Third International Conference on Computers and Games (L. Kocsis and E. van der Werf) 259
Open Dutch Student Championship Computer RoShamBo (H.H.M.L. Donkers) 260
Report on the Computer-Games Workshop (J.W.H.M. Uiterwijk) 262
Report on the Game Programming Workshop 2002 (S. Soeda) 264
Call for Papers: Advances in Computer Games Conference (H.J. van den Herik and H. Iida) 266
The ICGA on the web (G.McC. Haworth) 267
Calendar of Computer-Games Events in 2003 268
The Swedish Rating List (T. Karlsson) 269
Obituary: 270
Jan Louwman (1924-2003) (F. Morsch) 270
Correspondence: 271
Solving a Game is no Achievement, it is a Crime (C. Donninger) 271
Make Sure the ICGA Journal Reaches You 272

 

ON EQUAL FOOTING

Other days, other ways. Five years ago, in 1997, Deep Blue defeated World Champion Kasparov by 3.5 to 2.5. For a long time, it was believed that this event only would mark a single isolated point of success in the range of contests between human World Champions and computer programs. Within the human chess world there were many people who thought that this outcome was an exception, a small mistake made by the thinking process of the World Champion and a fortunate result for the computer. Insiders knew better. They were sure that the victory was only a milestone to be followed soon by other milestones. However, we had to wait five years before a new match of this calibre was played. In October 2002 it happened and in this issue of the Journal we report on a second milestone: Deep Fritz played in Bahrain (thus called Fritz Bahrain) on equal footing with the current World Champion Vladimir Kramnik. Our congratulations to ChessBase and in particular to Frans Morsch, Mathias Feist and Alexander Kure. Another milestone is the publication of three excellent contributions on Go, which make this issue a special issue. The Editor thanks Ken Chen for his effort to compose the scientific part of this issue and to tell us about "The Way to Go". We wish the go world much success with the progress in playing strength and hope to see them in the 8th Computer Olympiad and in the 10th Advances in Computer Games Conference in Graz, Austria in November 2002.

Jaap van den Herik


 

THE WAY TO GO

In the past three decades significant research and development efforts have been made on computer Go. Over a dozen of Ph.D. theses have been written on computer-Go topics. Over 50 Go programs have participated in computer-Go tournaments at one time or another. The Japanese government even included the development a Go program in their 5th generation project. Yet, the playing strength of the strongest Go programs today is only at an intermediate amateur level, far from a position rivalling top human players, which many other games have already achieved.

The most prominent intrinsic difficulty of computer Go is the machine's positional understanding. So far, no one has been able to develop a reasonably good evaluation function, static or dynamic, for complex Go positions. Strong human players can use visual perception, intuition, and experience to perform reliable positional reading (highly selective look-ahead). Until now, this has not been mimicked by a program and it is not likely to be so in the foreseeable future. If a good evaluation function is not available, how can one then write a strong Go program? Making things worse, the branching factor of a Go game is over 200 on the average. Hence, the computer-chess-type full-board look-ahead approach is powerless in Go. Several different paradigms have been used in building Go programs, including static analysis, try and evaluate, global selective search, and incentive/temperature approximation. Since no paradigm has emerged as "the way to Go", Computer Go is waiting for new ideas and new approaches to have a breakthrough.

This special issue marks a milestone – it is the first issue ever of any journal devoted solely to computer-Go articles. I thank the ICGA Journal Editorial Board, the anonymous referees, and the authors of three selected papers for making this milestone possible. (see the Editor's addition). It is my privilege to introduce the articles briefly below.

Life-and-death problems of Go groups are fundamental facets of a Go game. David Fotland's program, THE MANY FACES OF GO, is well known to have the best treatment of life-and-death issues in a tournament program. His contribution, Static Eye Analysis in "The Many Faces of Go", will definitely be beneficial for many current and future Go programs.

Zhixing Chen's program HANDTALK dominated the computer-Go world during 1995-1997. It won all major computer-Go world championships in those three years. His next generation program, GOEMATE, is a top Go program today. So far we have seen very little articles on the inside of HANDTALK and GOEMATE. Z. Chen's article, Semi-empirical Quantitative Theory of Go. Part I: Estimation of the Influence of a Wall, reveals his vigorous pursuit of quantified knowledge for his Go programs. He designed the influence functions to implement this quantified knowledge in HANDTALK and GOEMATE. His knowledge engineering work is outstanding in the computer-Go world. We hope we will soon be able to see part II, part III, etc. of his semi-empirical quantitative theory of Go.

Martin Müller's paper, Position Evaluation in Computer Go, gives readers some idea of the issues involved in the position evaluation in Go and how his new EXPLORER program deals with them.

I hope this special issue will cause more people to join in the research of computer Go - it is a very hard task but some breakthrough may not be far over the horizon. Finally, it is my pleasure to announce that more papers are underway, i.e., they are in or at the end of the refereeing process. They will be published in future issues of the ICGA Journal. It all means that Go has found its way to the ICGA.

Keh-Hsun Chen


Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA. Email: chen@uncc.edu.

 

STATIC EYE ANALYSIS IN "THE MANY FACES OF GO"

David Fotland1

San Jose, CA, USA
 

ABSTRACT

This article describes how the program THE MANY FACES OF GO statically evaluates eyes in the game of Go. Eyes are represented as a small game tree with upper and lower bounds on the values of the leaf nodes, along with a list of vital points.


1 Smart Games, 4863 Capistrano Ave, San Jose CA 95129, USA. E-mail: fotland@smart-games.com.

 

SEMI-EMPIRICAL QUANTITATIVE THEORY OF GO
PART I: ESTIMATION OF THE INFLUENCE OF A WALL

Zhixing Chen1

Guangzhou, China
 

ABSTRACT

This article examines the outward influence of a wall in the game of Go. It is concluded that there should be an increase of three mokus (points) for the increase of one line of the height. The related practice in some Go programs designed by the author is shown, and the results of the estimation of the influence of a wall in the programs are discussed.


1 Chemistry Department, Zhongshan University, Guangzhou, China. E-mail: cesczx@zsulink.zsu.edu.cn.

 

POSITION EVALUATION IN COMPUTER GO

Martin Muller1

Edmonton, Canada
 

ABSTRACT

Position evaluation is a critical component of Go programs. This article describes both the exact and the heuristic methods for position evaluation that are used in the Go program Explorer, and outlines some requirements for developing better Go evaluation functions in the future.


1 Department of Computing Science, University of Alberta, Edmonton, Canada T6G 2E8. Email: mmueller@cs.ualberta.ca

 

REVIEW

CHIPS CHALLENGING CHAMPIONS
GAMES, COMPUTERS AND ARTIFICIAL INTELLIGENCE

Edited by Jonathan Schaeffer and Jaap van den Herik

ISBN 0 444 50949 6
Elsevier, 2002; 362 pp.
$40; € 40

Reviewed by Dap Hartmann

"Computer games are the biggest AI success story to date", state the editors in the preface to this book. That innocent-looking statement actually reveals a lot about the tremendous struggle of artificial intelligence in the past five decades. Many promises were made, but only a few were fulfilled. All too often, the optimistic predictions by AI researchers proved incredibly difficult to realize. It must be frustrating to the followers of 'hard' AI that, despite their enormous efforts to equip robots with sophisticated computer vision and high-level decision-making software, today's most versatile robots have little of no pre-programmed 'intelligence'. In 1966, Marvin Minsky decided to solve once and for all the pesky problem of computer vision. He thought that it would probably take another ten years before a computer could play grandmaster-level chess; a stereotypical over-optimistic prediction. But not computer vision – how hard could that be in comparison? Even the dumbest person possesses that skill. Minsky employed a summer student to work on the problem. Today, 36 years later, a (sophisticated) personal computer can tie Vladimir Kramnik in a chess match. Elsewhere, AI researchers are still struggling to get computers to recognize where one object ends and another begins. Change the light, cast a different shadow, and it is back to the drawing board. Meanwhile, Minsky's summer student must be close to his retirement.

Computer achievements have been constantly depreciated through the pragmatic 'updating' of the definition of concepts such as 'brilliancy' and 'intelligence'. Each time a computer came close to the currently held belief of intelligent behaviour (albeit in a limited domain, such as game playing), the bar was raised sufficiently to preserve intelligence for humans only. This trend is best observed in domains where computers made the greatest progress. Even though they are now firmly established amongst the very best human chess players, some people still regard computers as stupid machines, which play chess 'only' by means of brute-force search. We still do not know how humans play chess, and thus the mystery of (human) intelligence remains. But we do know how computers play chess. In a desperate attempt to protect the human superiority, chess-playing computers are decreed to be unintelligent. 'We know how you operate, and we refuse to call that intelligent'. Is an electromagnet inferior to a natural magnet, because it is manmade and therefore less mysterious? While everyone readily accepts that machines outperform humans in almost every physical endeavour, it is apparently still impossible to accept that some of our great intellectual achievements can also be matched by computers. This stubborn denial and pragmatic paradigm shifting is most evident in, what I call, brilliancy inflation. When the 13-year old Bobby Fischer played 17. … Be6 in his game against Donald Byrne (New York, 1956), it was universally praised as an extremely brilliant move. Typewriters around the world were wearing out their exclamation mark key. Fischer himself is said to consider this his best game ever. But how brilliant is Be6, when Fritz 6.0 (running on a moderately fast PC) finds it in less than one tenth of a second? How many exclamation marks does the computer deserve for playing this move?

Admirable Achievements
Back to the preface of this book, where the editors mention "an outstanding series of computer triumphs", and state that "man has been humbled at backgammon, checkers, chess, Othello, and Scrabble. For many games, computer success is coming soon." I do not like these triumphant statements. They sound as if the goal of artificial intelligence is to trash humans in game playing. Admittedly, these triumphs are admirable achievements, not in the least because many people said that it could never be done. But what have we really learned about the games in which computers have now surpassed the level of the best humans? What more are they, but very strong sparring partners? Computers can play many chess endgames perfectly. Soon after Ken Thompson constructed the KBBKN database, the renowned endgame expert A.J. Roycroft tried to improve his skill in this endgame, by using the computer database as an oracle. He did not achieve very much (see: 'Expert against oracle', published in Machine Intelligence 11). Since then, little or no progress was made to extract knowledge from such omniscient databases, by neither man nor machine. Just how 'omniscient' are chess endgame databases? Could it be that they do not really contain any knowledge? Suppose that I memorize the outcome of every multiplication of all numbers up to four digits. My database then contains 100 million 'positions'. Given any two numbers of four digits or less, I can instantly produce the correct answer. Does my database contain any knowledge? Is my behaviour intelligent, or do I merely imitate intelligent behaviour by means of lookup? My 'act' is no more intelligent than looking up phone numbers in a telephone directory. How intelligent is the method by which we normally perform multiplications? In elementary school, we memorized the tables of multiplication up to 10. We use that small (100 elements) 'database' to speed up our multiplication algorithm. When multiplying large numbers, we constantly substitute small chunks in the calculation by results retrieved from our memorized tables. The reason why we regard this way of performing multiplications as intelligent, is that we can explain the method, and therefore we can teach others how to do it too. And if you cannot master this 'trick', you are clearly not very intelligent.

No implicit knowledge is contained in an endgame database. It is just a list of the number of moves to mate (or conversion) for every possible permutation of the chess pieces in that endgame. If such a list contains knowledge about the endgame, then a list of prime numbers must contain knowledge about number theory. An endgame database is a confined little universe, which you must meticulously observe to develop theories about that endgame. Roycroft made a first attempt, and John Nunn used databases to assist in the writing of his Secrets of Rook Endings. Two men exploring a few of the chess endgame universes. It will take more than a summer project to make a computer derive knowledge from the chess endgame telephone directories.

After this rather philosophical introduction, I will now turn to the actual review of the book. Chips Challenging Champions contains articles on computer game playing and puzzle solving, reprinted from the journal Artificial Intelligence. There are four sections: Puzzles, Two-Player Perfect-Information Games, Imperfect-Information and Stochastic Games, and Solved Games.

Puzzles
Three papers deal with puzzles. Richard Korf and Ariel Felner describe a technique for designing heuristic evaluation functions, based on pattern databases. Applied to the 15-Puzzle, and compared with the 'Manhattan distance' heuristic, it reduces the solving time by more than a factor of 2000. The intriguing Sokoban problems are the subject of a paper by Andreas Junghans and Jonathan Schaeffer. Unlike most puzzles (such as Rubik's Cube and the 15-Puzzle), Sokoban only exists in computer form. Anyone who has ever tried these 'deliver the stones' problems quickly discovers two things. First, the length of the solution for even the simplest problem is very long (97 moves; the average solution length is a stunning 260 moves, with an average branching factor of 12). Second, you quickly learn useful heuristics. Nobody has to tell you not to push a stone into a corner – you will soon find out that you cannot solve the puzzle if you do. The paper mentions only a few of these strategic principles, because "the full depth of Sokoban can only be appreciated by a more direct encounter with the game." Very true. The authors' program, ROLLING STONE, uses Iterative Deepening A* (IDA*) to solve Sokoban problems. It combines application-dependent and application-independent techniques to reduce the search effort. One figure illustrates the progress over time in the number of Sokoban problems solved. A problem is regarded 'solved' if the solution is found within 20 million nodes (requiring up to 3 hours of CPU time). After a slow initial start (12 problems solved in the first year), there followed a year of steady progress (28 more solved). In the final year reported here, only 17 additional problems were solved. At the writing of this paper, 57 of the 90 problems that make up the 'standard set' were solved. Some of the techniques developed for Sokoban have since been applied to other puzzles (15-Puzzle and Bricks).
The last chapter in this section is a 33-page contribution on solving crossword puzzles by Michael Littman, Greg Klein, and Noam Shazeer. Using a probabilistic approach, the master program, which consists of 30 independent subsystems (expert modules, written by Littman's students), averages a correctness of 95 percent in words and 98 percent, in letters. A remarkable achievement, considering that the program has no understanding of the semantics of the puzzles' clues.

Perfect Information
The 'Two-Player Perfect-Information Games' section opens with a paper on the Deep Blue system, written by Murray Campbell, Joseph Hoane, and Feng-hsiung Hsu. It is not quite the modern-day equivalent of the classic (25 years ago!) Slate and Atkin paper on Chess 4.5, but it does give some insights into what made Deep Blue tick. But don't look for more specific information than "Pawn structure: This table assesses various features of pawn structure not handled elsewhere" or "Rook behind passed: A bonus is awarded for a rook behind a passed pawn of the same color". We want more details!
Michael Buro surveys three tree-searching enhancements that he used in his Othello program Logistello: a generalized linear evaluation model, a selective search heuristic, and an opening book framework which improves upon previous play and explores new opening lines.
In 'A hierarchical approach to computer Hex', Vadim Anshelevich describes deduction rules which he implemented in Hexy, his world-class Hex-playing program. Complex Hex positions are evaluated recursively, starting from the simplest ones.
The current state of computer Shogi is reviewed by Hiroyuki Iida, Makoto Sakuta, and Jeff Rollason. Now that the human world champion has been defeated in checkers and chess, shogi is the next obvious challenge. The authors list four main challenges to achieve this: master-level opening, perfect endgame play, special-purpose hardware (Shogi chips), and the organization of a title match. They predict that a computer will be comparable in strength to the best human players by 2010. Good luck.
And after that hurdle has been taken, there remains the biggest challenge of all: Go. Go-expert Martin Müller presents an excellent review of the components of a typical Go program. He discusses knowledge representation, search methods, and techniques for solving subproblems. There is clearly a lot of work to be done: Müller lists no fewer than 14 items as "some of the research challenges". The appendix contains two games. The first game was played between two of the strongest Go programs. You need to be a fair Go player to notice the rather poor level of play, even though Müller is kind enough to call their performance "respectable". However, in the second game, the pitiful playing strength of computer-Go programs is clearly exposed. Müller (an impressive 6-dan amateur player) wipes the floor with one of the world's strongest Go programs, despite an incredible 29 stone handicap. For those eager to read more about computer Go, the reference section lists 104 papers.

Imperfect Information
The 'Imperfect-Information and Stochastic Games' section contains three papers. Gerald Tesauro describes TD-GAMMON, a neural network that learned how to play backgammon solely from playing against itself! And as if that is not surprising enough, the self-taught program is also amazingly strong. Just an additional shallow look-ahead is required to beat even the best human players.
The challenge of computer Poker is explained by Darse Billings, Aaron Davidson, Jonathan Schaeffer, and Duane Szafron, who created POKI. Poker programs must deal with multiple opponents (10 players), incomplete knowledge (the opponents' cards), risk management (betting real money), deception (bluffing), and opponent modelling. Despite a good overall performance, it will still be a while before POKI can provide its creators with a steady income.
Brian Sheppard, who recently wrote a delightful Ph.D. thesis on computer Scrabble, contributes a paper on MAVEN, his world-champion-calibre Scrabble program. MAVEN uses a selective move generator, the B* search algorithm, and Monte-Carlo simulations of likely game continuations. The appendix contains a game that is "in the author's opinion the best Scrabble game ever played in a tournament or match." After reading it, you are not likely to ever forget the word 'mouthpart'.

Solved games
The book closes with the very appropriate 'Games solved: Now and in the future', by Jaap van den Herik, Jos Uiterwijk, and Jack van Rijswijk. It is an review of all two-person zero-sum games with perfect information that have been solved to date, plus an outlook on which games will be next. There are brief descriptions of the methods developed for solving games, divided into brute-force methods and knowledge-based methods. The authors predict that by 2010, Awari, Othello, and Checkers will have been added to the list of solved games. Soon after this paper was published, John Romein and Henri Bal solved Awari. Another eight years, and two more games to go.

The Author Index appears to be hyper-modern: there are only six entries for Claude Shannon, four for John von Neumann, and not a single one for Alan Turing. The most frequently mentioned names are: Jonathan Schaeffer (52 entries), Jaap van den Herik (50), Hiroyuki Iida (42), and Jos Uiterwijk (40). There is no subject index.

It was an excellent idea to collect these articles from Artificial Intelligence into a separate book. All papers are highly readable – much more than the average AI article, which is usually so highly specialized and technical, that it is rather difficult to digest. At least for this reviewer. Chips Challenging Champions provides a thorough overview of the current state of computer game playing. It is good value for money, and well worth having.


 

CALL FOR PAPERS: ADVANCES IN COMPUTER GAMES 10 CONFERENCE

Graz, Austria
24-27 November, 2003

H.J. van den Herik and H.Iida

Maastricht, The Netherlands / Shizuoka, Japan

The tenth conference on Advances in Computer Games (ACG10) will be held in Graz, Austria, in the Casineum of the Casino in the centre of Graz. The conference commences on Monday November 24 at 8.30 h and will take place on four consecutive days, each day from 8.30 h till 11.30 h. The conference aims in the first place at providing an international forum for computer-games researchers presenting new results on ongoing work. The recent successes of the three International Conferences on Computers and Games have encouraged the organizers to widen their scope and therefore we also invite contributors on all aspects of research related to computers and games. Relevant topics include, but are not limited to: (1) the current state of game-playing programs, (2) new theoretical developments in game-related research, (3) general scientific contributions produced by the study of games. Also researchers on topics such as (4) social aspects of computer games, (5) cognitive research of how humans play games, and (6) issues related to networked games are invited to submit their contribution.

Important Dates

Paper Submission May 2, 2003
Acceptance Notification June 16, 2003
Camera-ready Papers August 1, 2003

Paper Submission Requirements

The proceedings of ACG10 will be published by Kluwer. Use the Kluwer style files found at: www.wkap.com/ifip/. The maximum length of papers in this format is 20 pages (10 pages are preferred). The preferred format for submission is PDF, but Postscript is also acceptable. The final version for the proceedings is to be submitted in LaTeX2e source form. Microsoft Word documents will be accepted but are not encouraged. All papers will be refereed. Accepted papers will be presented on the conference and printed in the proceedings. To submit a paper, please send an email to acg-paper@icga.org with the paper attached as a PDF or a Postscript file. Other requirements are:

Refereeing Process

All submissions will be refereed, and those accepted will be scheduled for presentation. Authors of accepted papers, or their representatives, are expected to present their papers at the conference.

Registration Fee Early Late
  (On or before September 1) (After September 1)
Participants Euro 150 Euro 180
Students Euro 100 Euro 120

Admission to the conference and a copy of conference proceedings are included in the conference registration fee.

Proceedings

The proceedings will be edited by H.J. van den Herik and H. Iida. They are expected to be published by Kluwer, in November 2003. During the conference participants can order (additional) copies.

The Programme Committee consists of: Jaap van den Herik (co-chair), Hiroyuki Iida (co-chair), Ken Chen, Chrilly Donninger, Aviezri Fraenkel, Kurt Jungwirth, Hans Kuijf, Ryohei Nakatsu, and Jonathan Schaeffer.

The Organising Committee consists of: Prof.dr. K. Jungwirth (chair), Johanna Hellemons, and Martine Tiessen.

More information: Prof.dr. H.J. van den Herik, Universiteit Maastricht, Dept. of Computer Science, P.O. Box 616, 6200 MD Maastricht, The Netherlands. Email: . Or Dr. H. Iida, University of Shizuoka, Dept. of Computer Science, Hamamatsu 432-8011, Japan. Email: .