ICGA Journal

Vol. 26, No. 2 - June 2003

Table of Contents

Table of Contents73
Deep Search and Chess Brains (H.J. van den Herik) 73
The Way to Go is Bottum Up (K-H. Chen) 73
Follow-up on “Self-play, Deep Search, and Diminishing Returns” (E.A. Heinz) 75
Reference Fallible Endgame Play (G.McC. Haworth) 81
Solving Go on Small Boards (E.C.D. van der Werf, H.J. van den Herik, and J.W.H.M. Uiterwijk) 92
A 20-Choice Experiment in Go for Human+Computer (I. Althöfer) 108
Note:115
Self Play: Statistical Significance (G.McC. Haworth) 115
Information for Contributors119
News, Information, Tournaments, and Reports:120
The 13th CSA World Computer-Shogi Championship (R. Grimbergen) 120
Calendar of Computer-Games Events in 2003 125
The Revenge Match Samb - Buggy (N. Guibert and W. Wesselink)126
The ChessBrain Project (C. Justiniano and C.M. Frayn) 132
Arimaa – a New Game Designed to be Difficult for Computers (O. Syed and A. Syed) 138
The 3rd International CSVN Tournament (Th. van der Storm) 140
 Computer-Chess History (Th. van der Storm) 141
The Swedish Rating List (T. Karlsson)143
How the ICGA Journal Reaches You144

 

Deep Search and Chess Brains

Chess is culture, Chess is sport, Chess is artificial intelligence. The slogan of the 2003 cultural capital of Europe reads: "Chess003". The promises are great, and according to the slogan a threefold combination of culture, sport, and AI is awaiting a large audience in the last extended week of November. A provisional schedule has been outlined in the previous ICGA Journal (Vol. 26, No. 1, pp. 60-64). Currently, preparations are in full swing.

The capital of Styria, Graz is expecting many participants; it soon will welcome deep search and chess brains in the Dom im Berg (the Dome in the Mountain), announced in their press communication as a high-tech space with multimedia equipment, located in the centre of the Schlossberg, and evoking memories of James Bond’s 007 Moonraker.

This issue of the Journal is a prelude to the festivities in Graz, since it deals with chess, Go, shogi, draughts, and Arimaa. Moreover, Ernst Heinz restarts the discussion on deep search and Guy Haworth replies at two issues, viz. human fallibility and statistical significance.

At this place it is time to thank Ken Chen for his continuous effort to make the game of Go familiar to our readership. For the last details we refer to his Editorial. Browsing through Reading the News section we congratulate Mr. Tanase and his team (IS Shogi, Shogi), Nicolas Guibert and his team (Buggy, International Draughts), and Johan de Koning (The King, Chess) with their respective victories. We expect that these successes will result in articles on Shogi Brains and Draughts Brains in one of the next issues of this Journal.

Next to the new game Arimaa (see pp. 138-139), your Editor would like to draw the readers’ attention to the game of Ataxx. We have received a suggestion to include this game into the roster of the Olympic games. Obviously, we are willing to do so and therefore we invite readers to submit a program for participation in the 8th Computer Olympiad in Graz. The rules of Ataxx and some illustrations of how the game is played are at braindamage.org/ataxx/. We look forward to see you in Graz and hope that you will convince your scientific collaborators to accompany you and to participate too.

The 13th WCCC, the 10th ACG, and the 8th Computer Olympiad deserve your participation.

Jaap van den Herik


THE WAY TO GO IS BOTTUM UP

The last two issues of the ICGA Journal spent many pages to the game of Go. Many ideas, proposals, and experiments were described with the aim to show that computer Go is a scientifically sound way to go towards understanding the intricacies of the game of Go.

Since NxN Go is NP-hard, we expect for large N, that NxN Go will overwhelm computer programs. Indeed, the standard sizes of the game of Go, N = 19, 13, and 9, result in extremely difficult problems for computer-Go programs. The current programs are far from human expert level at those common board sizes. However, when N is small, a computer can completely solve NxN Go and play perfect games. S. Sei and T. Kawashima solved NxN boards up to 4x4 Go via complete game-tree search. Their results were:

2x2 board - it is a draw (komi = 0),
3x3 board - Black playing at the centre takes over the whole board,
4x4 board - best sequence, with 2-2 as the first move, results in a draw (komi = 0).

In this issue, Erik van der Werf, Jaap van den Herik, and Jos Uiterwijk’s contribution, Solving Go on Small Boards, pushes the envelop to the 5x5 board. They use static recognition of unconditional territory, enhanced move ordering, symmetry lookup, and several other search enhancements to establish:

5x5 board - Black playing at the centre takes over the whole board.

The prevailing question now is: Can we push the envelop further to a 6x6 board, a 7x7 board, and so on? Time will tell to what extent we can achieve complete solutions.

In contrast to solving the game of Go for small boards, Ingo Althöfer’s contribution, A 20-Choice Experiment in Go for Human+Computer, gives us a reality check - the current Go programs are so weak that when teaming with a strong human player, Go programs are merely handicaps. The paper is entertaining and contains insightful comments about the weaknesses of current Go programs. I hope that the readers will enjoy these two interesting articles. They complete the series of special issues of the ICGA Journal on Go.

K-H. Chen


GRAZ2003 - CULTURAL CAPITAL OF EUROPE IS READY FOR A GREAT CHESS EVENT.