TABLE OF CONTENTS

 

Table of Contents.................................................................................................................................................................. 65

Some Realized Breakthroughs (H.J. van den Herik) ........................................................................................................ 65

Checking Life-and-Death Problems in Go I: The Program ScanLD (T. Wolf and L. Shen)...................................... 67

Factors Affecting Diminishing Returns for Searching Deeper (M. Guid and I. Bratko)............................................. 75

Avoiding Rotated Bitboards with Direct Lookup (S. Tannous)..................................................................................... 85

Note:........................................................................................................................................................................................ 92

An Efficient Heuristic for Evolving an Agent in the Strategy Game of Ayo

(O.O. Olugbara, M.O. Adigun, S.O. Ojo, and T.O. Adewoye) ....................................................................... 92

Information for Contributors................................................................................................................................................ 97

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

                The 15th World Computer-Chess Championship

                (J. Noomen, J. Uiterwijk, and H.J. van den Herik)............................................................................................. 98

                The World Computer Speed-Chess Championship 2007.............................................................................. 107

                The 12th Computer Olympiad (H.J. van den Herik, M. Winands, and J. Hellemons)................................. 108

                        Steenvreter Wins 9×9 Go Tournament (E. van der Werf).............................................................. 109

                        MoGo Wins 19×19 Go Tournament (S. Gelly and Y. Wang)............................................................... 111

                        NeuChess Wins Chinese Chess Tournament (C. Xu)......................................................................... 113

                        BGBlitz Wins Backgammon Tournament (F. Berger)......................................................................... 114

                        X6 Wins Connect6 Tournament (I-C. Wu).............................................................................................. 116

                Computer Games Workshop 2007 (T. Cazenave, C. Kruskal, and B. Bouzy).............................................. 118

                Showdown in Elista (S. Bushinsky).................................................................................................................. 121

                The 6th International Polish Computer-Chess Championship (M. Szmit).................................................... 124

                The 2nd Open French Championship Rapid Polish Draughts (S. Koudache)............................................. 125

                Calendar of Computer-Games Events in 2007-2008........................................................................................ 126

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

How the ICGA Journal Reaches You................................................................................................................................ 128

 

 

Some Realized Breakthroughs

 

In the world of cyclists there used to be a famous saying: “Quality has wings”. In fact, this holds for any sport and even for the games in the Computer Olympiad, where we saw Steenvreter (Erik van der Werf) winning the competition in the 9x9 Go tournament. The expected breakthrough by Mogo (Sylvain Gelly and Yizao Wang) was restricted to 19x19 Go. The real breakthrough was not the application but the underlying methods, consisting of two elements. The UCT algorithm in combination with a Monte-Carlo search technique constitutes the new idea. Four persons are to be recognized here: Brügmann and Bouzy for introducing Monte-Carlo techniques into the computer-Go programming world in the 1990s and Kocsis and Szepesvári for the development of the UCT algorithm in 2005. The combination of both techniques is powerful. It has a breakthrough time of only two years.

 

In Reykjavik 2005, we had another breakthrough which we then called a revolution. Zappa (Anthony Cozzie) and Fruit (Fabien Letouzey) took over the hegemony of Junior and Shredder. For a while it looked as if the computer-chess world had two successors, which would have their own fight in the years to come. However, this turned out to be far from the truth. In Turin 2006, we saw that Junior and Shredder were back in the race, in particular Junior by winning the world title. Fruit did not participate then and Zappa ended up in an unexpected fourth place. The third place in Turin went to Vasik Rajlich’s program Rajlich. As a Tournament Director I was privileged to talk to him on the pairing in relation to the Swiss system, on the elimination of a team, on his career, and on his expectations. From all conversations it was clear that Vasik was a very motivated, self-driven person who did not enjoy finishing in third place in his first appearance on the world scene. He would like to be the best.

 

However, for being the best, you have to work hard, you have to be motivated, you have to be talented, you have to attract talented collaborators, and you have to be lucky. Creating your own setting is an important part of the way that ultimately leads to success. Vasik Rajlich returned from the USA to Europe and set his goal: to become the best among the computer-chess programmers. This is really a challenge. Here I would like to state that our community has many talented contenders. To write a world-championship chess program is a sign of talent combined with persistence and deep understanding. In Turin 2006, Vasik Rajlich was knocking on the door. In Amsterdam 2007, the young Czech programmer realized his breakthrough.

 

For the insiders it was not a surprise. Many insiders will remember what happened to Deep Blue in Hong Kong 1995 where Fritz took full advantage out of the few chances offered to it. That unexpected breakthrough by Fritz in 1995 ultimately led to the 4-2 victory in 2006 by Deep Fritz 10 over the human World Champion Kramnik (see ICGA Journal, Vol. 29, No. 4, pp. 208-213), with special attention to game 6 (showing the new idea 10. Re3, 11. Rg3). The clear winner of all these developments is computer chess in general, or let me broaden the area, the Computer Games World (see the introduction of Checking Life-and-Death Problems in Go on p. 67 of this issue).

 

Let us now return to Rybka’s performance. In Turin 2006, Rajlich’s program lost to Shredder, and finished on equal footing (second and third) with the former World Champion. For Vasik it was a disappointing experience not to win the “Shannon horse”. The report in this issue is a combination of writings by Jeroen Noomen, Jos Uiterwijk, and Jaap van den Herik. From Jeroen Noomen’s contribution I adopt the performances by Rybka in the period 2006-2007 as a proof of the realized breakthrough. The signs are overwhelming and the results are in accordance with the expectations. So, with much pleasure the Editor congratulates Vasik with his first World Computer Chess title. Below we mention for Rybka the following results after Turin 2006.

 

NK Leiden 2006        : 1st place 9 out of 9

Paderborn 2006         : 1st place 6.5 out of 7

CCT9 2007                 : 1st place 6 out of 7 (2 draws)

ICT Leiden 2007       : 1st place 7.5 out of 9 (3 draws)

and now

WCCC 2007               : 1st place 10 out of 11 (2 draws)

 

In the last five tournaments Rybka scored 39 out of 43, was undefeated, and played only eight draws. A score of 90.7 per cent. The ICGA community is proud of such a World Champion.

 

 

                                                                                                                                                                    Jaap van den Herik

 

 

Welcome and Farewell

 

The composition and production of the ICGA Journal is an interesting and laborious task, which can only be fulfilled by the excellent support of the Editorial Board. When I took up the Editorship in 1983, I was privileged to have the help of the late Professor Bob Herschberg and Professor Tony Marsland (as Associate Editors) and Professor Monty Newborn (as ICCA President and since 1986 as Associate Editor). The professors Marsland and Newborn served the Journal for more than twenty years. They now step down to give new blood the opportunity to take their place. In one of the next issues we will provide an overview of their computer-chess activities and their services to our community. The Editorial Board and all other ICGA officers would like to thank them for the smooth cooperation over many years.

 

The same Board and officers are grateful to be able to welcome Professor Xinhe Xu (Northeastern University, China) to join the Editorial Board. We expect to cooperate equally well with Professor Xinhe, who we know as the driving force of the ICGA 2008 events (the 16th WCCC, the 13th Computer Olympiad, and the CG 2008).

 

 

 

Text Box: ICGA Journal readers who are interested in information on our publications are referred to our website. A complete list of all articles, notes, and literature reviews published in the ICCA Journal and the ICGA Journal is accessible on the Internet at http://www.icga.org

 

 

 

 

 

Factors Affecting Diminishing Returns
for Searching Deeper
[1]

 

 

Matej Guid and Ivan Bratko

Ljubljana, Slovenia

 

 

ABSTRACT

 

The phenomenon of diminishing returns for additional search effort has been observed by several researchers. We study experimentally additional factors which influence the behaviour of diminishing returns that manifest themselves in go-deep experiments. The results obtained on a large set of more than 40,000 positions from chess grandmaster games using the programs Crafty, Rybka, and Shredder show that diminishing returns depend on (a) the values of the positions, (b) the quality of the evaluation function of the program used, and to some extent also on (c) the phase of the game, and the amount of material on the board.

 

 

AVOIDING ROTATED BITBOARDS WITH DIRECT LOOKUP

 

Sam Tannous

Durham, North Carolina, USA

 

ABSTRACT

 

This paper describes an approach for obtaining direct access to the attacked squares of sliding pieces without resorting to rotated bitboards. The technique involves creating four hash tables using the built in hash arrays from an interpreted, high level language. The rank, file, and diagonal occupancy are first isolated by masking the desired portion of the board. The attacked squares are then directly retrieved from the hash tables. Maintaining incrementally updated rotated bitboards becomes unnecessary as does all the updating, mapping and shifting required to access the attacked squares. Finally, rotated bitboard move generation speed is compared with that of the direct hash table lookup method.

 

 

CHECKING LIFE-AND-DEATH PROBLEMS IN GO

 

I: THE PROGRAM SCANLD1

 

Thomas Wolf2 and Lei Shen3

St. Catharines, Canada

 

ABSTRACT

In this article we introduce the program SCANLD (built on GOTOOLS) which checks solutions of life-and-death problems for correctness. It is a task for which computer programs are especially useful. They do the computations, they also do the handling of data in checking all moves of all solutions for optimality, and they report any errors that occur. Their refutation and their correction would be tedious and error prone if done with a computer, but interactively.

After discussing the different types of checks that are performed and giving some statistics resulting from checking a 500-problem tsume-go book, some examples are given. A detailed list of mistakes that have been found is given in an on-line addendum to the article.

 

 

NOTE

 

An Efficient Heuristic for Evolving an Agent in

The Strategy Game of Ayo

O.O. Olugbara[2], M.O. Adigun1, S.O. Ojo[3], and T.O. Adewoye[4]

Zululand, South Africa , Botswana, Botswana , Ilorin, Nigeria

 

 

ABSTRACT

 

The game of Ayo is a member of the Mancala family. The problem of developing heuristics for playing Mancala games by a computer agent is an open issue. This note presents a heuristic that uses a hybrid combination of minimax search and case-based reasoning, to evolve an agent that can play Ayo. The evaluation of such an evolved agent shows that this combination can result in an efficient heuristic. 

 

 

 



[1] This article is a revised version of a contribution with the same title to the Computer Games Workshop 2007 held in Amsterdam, The Netherlands, June 15-17, 2007. The revised version has been subjected to the Journal’s normal refereeing procedure.

[2] University of Zululand, Department of Computer Science, South Africa. Email: oluolugbara@gmail.com.

[3] University of Botswana, Department of Computer Science, Botswana.

[4] University of Ilorin, Department of Business Administration, Nigeria.