TABLE OF CONTENTS

Table of Contents................................................................................................................................................................... 1

Computer Games in China (H.J. van den Herik) ............................................................................................................. 1

Move Generation with Perfect Hash Functions (Trevor Fenner and Mark Levene).................................................. 3

A Survey of NP-Complete Puzzles (Graham Kendall, Andrew J. Parkes, and Kristian Spoerer).......................... 13

Review: .................................................................................................................................................................................. 35

If Chess was like Pool, a Knight could be off by a Whisker (Dap Hartmann)......................................... 35

Information for Contributors............................................................................................................................................. 37

News, Information, Tournaments, and Reports: ........................................................................................................... 38

The 12^th Game Programming Workshop (Rémi Coulom)............................................................................. 38

Crazy Stone Wins the First UEC Cup (Rémi Coulom)........................................................................... 42

The 17^th International Paderborn Computer-Chess Championship (Tobias Tscheuschner).................. 45

The Complete Chess Match 2008 (Erwin l’Ami, Daniël Stellwagen, Jan van Reek and Jos Uiterwijk) 47

The 1^st Computer Stratego World Championship (Imer Satz)..................................................................... 50

The 16^th World Computer-Chess Championship (The Board of ICGA).................................................... 52

Rules for the 16^th World Computer-Chess Championship (The Board of ICGA).................................... 53

ICGA Triennial Meeting (The Board of ICGA).............................................................................................. 55

Call for Participation Computer Olympiad 2008........................................................................................... 58

ICGA Treasurer’s Report for 2007 (Hiroyuki Iida)........................................................................................ 59

The 2006 and 2007 ChessBase Best-Publication Award Recipients (The Editorial Board).................. 60

The 2007 Herschberg Best-annotation Award (The Editorial Board)........................................................ 61

Calendar of Computer-Games Events in 2008.............................................................................................. 61

The Swedish Rating List (T. Karlsson).............................................................................................................. 62

Correspondence: .................................................................................................................................................. 63

3-Hirn Grant for Jakob Erdmann (Ingo Althöfer).......................................................................... 63

Second 3-Hirn Grant (Ingo Althöfer)................................................................................................ 63

How the ICGA Journal Reaches You............................................................................................................................... 64

computer games in china

The larger the country, the more possibilities there are for creative computing. Chess, Games, and Science are quite attractive ingredients of the three ICGA events in Beijing, China in September/October 2008. The three events are: the 16^th World Computer-Chess Championship, the 13^th Computer Olympiad, and the Computer and Games Conference 2008.

The ICGA is proud to have two “big brothers”, viz. FIDE[1] and IOC[2], which paved the way for our events. In Turin 2006, we were “sequentially assembled” for the first time (IOC, FIDE, and ICGA). Now the ICGA is again following the IOC. Our three events are modest in comparison to the human Chess Olympiad and the Olympic Games for all sports, but the variety of thinking games is a challenge in itself. In this issue Graham Kendall, Andrew Parkes, and Kristian Spoerer show that the end of the list of one-person games (also called puzzles) is not yet in sight, let alone, that this will be the case for the many-person games. The established difficulty of many games guarantees a large research interest for many years. For China, the main ingredients for the Computer Olympiad are Chinese Chess, Go, Shogi, and Connect 6 (see the ICGA website).

The publicity for the Olympic Games as made by the Chinese organizers of the Olympic Games is also a stimulus for our participants. A brief investigation brought in the following four themes: (1) Forever Friends, (2) Everyone is No. 1, (3) I am a Star, and (4) Our Dreams. Each of them could have served as an appropriate title for this Editorial.

Of course, this Journal is scientific by its origin, its nature, and by the contributors. The two scientific articles show clear scientific progress by offering an excellent survey of NP-Complete Puzzles and by discussing Perfect Hash Functions. We are sure that many other proofs of concept will be experienced in Beijing during the events. They will lead to new breakthroughs as we have seen in the recent past with the emergence of Monte-Carlo Tree Search and the UCT algorithm. Our currently prevailing questions are: (1) how strong will be the best 9x9 Go programs in Beijing? (2) will they play at human World Championship level? and (3) what about the progress in 19x19 Go? A tournament in combination with a conference is the best venue for showing progress. This year, it happens in Beijing.

If we now return to the four suggested editorial titles then we see the following. First, we may dream of scientific progress. According to the theory by Ray Kurzweil (on the singularity point; for a definition, see the appropriate website) it may be remarked that we have seen such a point in chess in 1997 when Kasparov was for the first time defeated by Deep Blue, a milestone in our community. We then assumed that many milestones would follow soon. Meanwhile we have seen milestones in Backgammon, Checkers, Othello and Scrabble, but currently we may dream of progress in 9x9 Go. Your Editor looks forward to see what Beijing will bring in this respect.

Second, playing in the World Computer-Chess Championship or in the Computer Olympiad is only for stars, as is participating in the Computer Games Conference. For them, the right slogan clearly is: “We are the Stars”. The challenge is with the ICGA and the local organizers to treat all of you accordingly. We are sure that the organizers will do their utmost.

Third, for an appropriate service, it holds that “Everyone is No. 1”. In sport, science, and business this should be changed into “Everyone would be No. 1”. That is exactly why you come to China. We wish all participants that they find the right place in a friendly tournament that meets and exceeds all your dreams.

Over the years, the ICGA has broadened its scope considerably. This is now the first time (since 1977 when the ICCA started) that China is our host. We are grateful for the initiative to host the ICGA events. We wish Professor Xinhe Xu, Professor Zhu Shin-Wen, Miss Chu Hao, and Mr. Xu Chong-Ming very much success with the organization. The ICGA is characterized by the spirit that we all experienced for many years: Forever Friends. With this feeling we all come to China to meet your gamers. We are told that there are currently 37.5 million gamers in China. It will be fantastic when they join the ICGA as a member from 2008 onwards. Your Editor looks forward to meet members, participants, and organizers soon in China.

Jaap van den Herik

Venue of the three events in Beijing, China.

The credits of the photographs in this issue are to: the Chinese Organisation (p. 2), Rémi Coulom (pp. 41, 43, 44), Tobias Tscheuscher (p. 46), and Eric van Reem (p. 49).

---

[1] Féderation Internationale des Echecs, the World Chess Federation.

[2] International Olympic Committee.