TABLE OF CONTENTS

 

Table of Contents................................................................................................................................................................ 129

Science and Checkers (H.J. van den Herik) .................................................................................................................... 129

Searching Solitaire in Real Time (R. Bjarnason, P. Tadepalli, and A. Fern)................................................................ 131

An Efficient Approach to Solve Mastermind Optimally (L-T. Huang, S-T. Chen, S-Ch. Huang,

............... and S.-S. Lin)........................................................................................................................................................ 143

Note: ..................................................................................................................................................................................... 150

                Gentlemen, Stop your Engines! (G. McC. Haworth)....................................................................................... 150

Information for Contributors.............................................................................................................................................. 157

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

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

                        Dam 2.2 Wins Draughts Tournament (T. Tillemans)........................................................................... 158

                        SIA Wins Surakarta Tournament (M. Winands).................................................................................... 162

                        8QP Wins Amazons Tournament (M. Winands).................................................................................... 163

                        Tacos Wins Shogi Tournament (J. Hashimoto)................................................................................... 164

                        Golois Wins Phantom-Go Tournament (T. Cazenave and J. Borsboom)......................................... 165

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

                The 17th CSA World Computer-Shogi Championship (R. Grimbergen)....................................................... 167

                Golden Summer for Rybka (H. Secelle and E. van Reem)............................................................................ 171

                Obituary Donald Michie (1923-2007 (D. Levy)................................................................................................ 177

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

                Correspondence:.................................................................................................................................................. 183

                        Monte-Carlo Backgammon (G. Tesauro).................................................................................................. 183

How the ICGA Journal Reaches You................................................................................................................................ 184

 

Science and Checkers

 

Within a time span of three months after the ICGA events in Amsterdam, the Netherlands, in June 2007 three notable events occurred. They vary from a quite sad announcement to gloriously heralding two successes that deserved to be communicated widely and broadly within our community.

 

Let me start with the sad news. On July 7 Donald Michie and his former wife Ann McLaren were travelling from Cambridge to London, were involved in a car accident, and died. It was a shock to our community, to the English scientific world, and to the world at large. Donald had earned much recognition for his research during the Second World War in close collaboration with Alan Turing at Bletchley Park. Yet, the fame of his former wife Ann McLaren with whom he lived (again) together after the death of his wife Jean Hayes and his retirement from Glasgow/Edinburgh, might even be larger than his own. In retrospect, Donald and Ann were a perfect couple to whom the scientific world should say: thank you, Ann, thank you, Donald, for your contributions to science.

 

In the current issue David Levy gives an extensive and insightful account of Donald’s life and his ideas for motivating young researchers. I may call myself a follower of Donald’s ideas. His keynote lecture on the Human Window at the Advances in Computer Chess Conference in London 1981 inspired me to choose the following title for my inaugural address at the Universiteit Maastricht: Informatica en het Menselijk Blikveld (Computer Science and the Human Window). Three years later, inspired by Michie in the domain of chess and by Turing through his paper Can Machines Think I took as title for my inaugural address in Leiden: Kunnen Computers Rechtspreken? (Can Computers Judge Court Cases?). David Levy provides many more examples of Michie’s stimulating efforts. In search of memories of Donald we found a picture of Bletchley researchers after a 12-board chess match, but Donald was missing. So, we are grateful to the Michie family for providing us the right to reproduce some of their Website pictures. We wish them strength with their loss.

 

Meanwhile the world is continuing its activities. At the end of July, Professor Jonathan Schaeffer saw all his efforts and those of his team members result in a thrilling publication in Science. On the solution of Checkers.

 

To start with the end, the game is scientifically proved to be a draw by the Schaeffer team. This result is achieved after 18 years of research. Moving to the beginning, after the World Computer-Chess Championship in Edmonton, Alberta in 1989, Schaeffer moved from chess to checkers. He himself is a genuine chess-player but he saw the potential for scientific results by continuing the early work on learning by Arthur Samuel (1959, 1963). He gloriously succeeded and our community may be proud of such an ardent researcher, who has inspired many junior researchers to go their way. The ICGA congratulates our former secretary/treasurer and looks forward to receiving the “true” story of the team result to be published in the December issue, together with some technical algorithmic details. We congratulate all authors with their publication in the July issue of Science.

 

The third event concerns an announcement. On October 11, 2007 ICGA President David Levy defended his Ph.D. thesis, titled Intimate Relationships with Artificial Partners. Currently, the press (even the world press) has shown interest in his scientific endeavours. Indeed, the title is intriguing, and reading the thesis does not diminish your expectations in any way. However, the very true statements that are put forward are without any claim on being spectacular or being wild. No, not at all. His analysis is profound and based on a plethora of results that have been published in the literature.

 

What David did is simply putting a new brick in our scientific building. Some regard his brick as being extraordinary. For a better perspective, we refer to a variety of websites that commented on the publication. The title of his thesis is sufficient for Google to provide you with many references.

 

In summary, in the December issue we will pay attention to our (former) ICCA/ICGA officers, namely by reviewing their work (Levy), highlighting their past performances (Marsland and Newborn), and publishing their findings (Schaeffer).

 

Jaap van den Herik

 

 

The credits of the photographs in this issue are to: Johanna Hellemons, Eric van Reem, Jos Uiterwijk, AI Factory, and the family of Donald Michie.

 

SEARCHING SOLITAIRE IN REAL TIME

 

Ronald Bjarnason Prasad Tadepalli Alan Fern1

Corvallis, USA

 

ABSTRACT

 

This article presents a new real-time heuristic search method for planning problems with distinct stages. Our multistage nested rollout algorithm allows the user to apply separate heuristics at each stage of the search process and tune the search magnitude for each stage. We propose a searchtree compression that reveals a new state representation for the games of Klondike Solitaire and Thoughtful Solitaire, a version of Klondike Solitaire in which the location of all cards is known.

 

Moreover, we present a Thoughtful Solitaire solver based on these methods that can determine over 80% of Thoughtful Solitaire games in less than 4 seconds. Finally, we demonstrate empirically that no less than 82% and no more than 91.44% of Klondike Solitaire games have winning solutions, leaving less than 10% of games unresolved.

 

 

An Efficient Approach to Solve Mastermind Optimally[1]

 

Li-Te Huang[2], Shan-Tai Chen[3], Shih-Chieh Huang2 and Shun-Shii Lin[4]

 

Taipei/Taoyuan, Taiwan, R.O.C.

 

ABSTRACT

 

The Mastermind game is well-known around the world. In recent decades, several approaches have been adopted for solving Mastermind in the worst case. An optimal strategy has finally been proposed by Koyoma and Lai in 1993 by using an exhaustive search for finding the optimal strategy in the expected case. In this paper, a more efficient backtracking algorithm with branch-and-bound pruning (BABBP) for Mastermind in the expected case is introduced, and an alternative optimal strategy is obtained eventually. Furthermore, the novel approach may be presumably applied to other games with some modifications in order to speed up the search.

 

 

NOTE

 

Gentlemen, STOP YOUR ENGINES!

G. M cC. Haworth[5]

 

Reading, England

 

 

ABSTRACT

 

For fifty years, computer chess has pursued an original goal of Artificial Intelligence, to produce a chess-engine to compete at the highest level. The goal has arguably been achieved, but that success has made it harder to answer questions about the relative playing strengths of man and machine. The proposal here is to approach such questions in a counter-intuitive way, handicapping or stopping-down chess engines so that they play less well. The intrinsic lack of man-machine games may be side-stepped by analysing existing games to place computer-engines as accurately as possible on the FIDE ELO scale of human play. Move-sequences may also be assessed for likelihood if computer-assisted cheating is suspected.

 


[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] Graduate Institute of Information and Computer Education, National Taiwan Normal University, No. 88, Sec. 4, Ting-Chow Rd., Taipei, Taiwan, R.O.C.

[3] Department of Computer Science, Chung Cheng Institute of Technology, National Defense University, Taoyuan, Taiwan, R.O.C.

[4] Department of Computer Science and Information Engineering, National Taiwan Normal University, No. 88, Sec. 4, Ting-Chow Rd., Taipei, Taiwan, R.O.C. Email: linss@csie.ntnu.edu.tw

[5] Reading, England. Email: guy.haworth@bnc.oxon.org