@InProceedings{abe2002, author = {Abe, Nobuharu and Kotani, Yoshiyuki}, title = {Learning for the Value of Moves by Iteration of Generation of Decision Tree in {G}o}, year = {2002}, booktitle = {Game Informatics Workshop 2002}, publisher = {Information Processing Society of Japan}, keywords = {candidate moves, decision tree generation} } @InProceedings{abramson2001, author = {Abramson, Myriam and Wechsler, Harry}, title = {Competitive Reinforcement Learning for Combinatorial Problems}, booktitle = {INNS-IEEE International Joint Conference on Neural Networks (IJCNN 2001)}, year = {2001}, abstract = { This paper shows that the competitive learning rule found in Learning Vector Quantization (LVQ) serves as a promising function approximator to enable reinforcement learning methods to cope with a large decision search space, defined in terms of different classes of input patterns, like those found in the game of Go. In particular, this paper describes S[arsa]LVQ, a novel reinforcement learning algorithm and shows its feasibility for Go. As the distributed LVQ representation corresponds to a (quantized) codebook of compressed and generalized pattern templates, the state space requirements for online reinforcement methods are significantly reduced, thus decreasing the complexity of the decision space and consequently improving the play performance. As a result of competitive learning, SLVQ can win against heuristic players and starts to level off against stronger opponents such as Wally. SLVQ outperforms S[arsa]Linear when playing against both a heuristic player and Wally. Furthermore, while playing Go, SLVQ learns to stay alive while SLinear fails to do so. }, keywords = {Learning Vector Quantization, SLVQ, SARSA}, url = {http://mysite.verizon.net/mabramso/research/ijcnn2001.pdf} } @Misc{abramson2002, author = {Abramson, Myriam and Wechsler Harry}, title = {A Competitive Reinforcement Learning Approach to {G}o}, year = {2002}, note = {Submitted to CG2002}, keywords = {LVQ, reinforcement learning, Wally, Gobble}, } @InProceedings{abramson2003, author = {Abramson, Myriam and Wechsler Harry}, title = {Tabu Search Exploration for On-Policy Reinforcement Learning}, booktitle = {International Neural Network Conference, Portland, OR}, year = {2003}, url = {http://mysite.verizon.net/mabramso/research/tabuijcnn03.pdf}, keywords = {Reinforcement learning, tabu search, Sarsa Learning Vector Quantization}, abstract = { On-policy reinforcement learning provides online adaptation, a characteristic of intelligent systems and lifelong learning. Unlike dynamic programming, an exhaustive sweep of the search space is not necessary for convergence in reinforcement learning with an efficient exploration strategy. For efficient and ``believable'' online performance, an exploration strategy also has to avoid cycling through previous solutions and know when to stop without getting stuck in a local optimum. This paper addresses the above problem with tabu search (TS) exploration. Several strategies for reinforcement learning are introduced. Experimental results are presented in the game of Go, a deterministic, perfect-information two-player game, and Sarsa Learning Vector Quantization (SLVQ), an on-policy reinforcement learning algorithm. } } @InProceedings{abramson2003b, author = {Abramson, Myriam and Wechsler Harry}, title = {A Distributed Reinforcement Learning Approach to Pattern Inference in {G}o}, booktitle = {International Conference on Machine Learning Applications, Los Angeles, CA}, year = {2003}, url = {http://mysite.verizon.net/mabramso/research/icmla2003.pdf}, keywords = {reinforcement learning, LVQ}, abstract = { This paper shows that the distributed representation found in Learning Vector Quantization (LVQ) enables reinforcement learning methods to cope with a large decision search space, defined in terms of equivalence classes of input patterns like those found in the game of Go. In particular, this paper describes S[arsa]LVQ, a novel reinforcement learning algorithm and shows its feasibility for pattern-based inference in Go. As the distributed LVQ representation corresponds to a (quantized) codebook of compressed and generalized pattern templates, the state space requirements for online reinforcement methods are significantly reduced, thus decreasing the complexity of the decision space and consequently improving the play performance from pattern-based inference alone. A novel exploration strategy for reinforcement learning based on tabu search is introduced. Experimental results are shown against Minimax and Wally. } } @PhdThesis{abramson2003c, author = {Abramson, Myriam}, title = {Learning Coordination Strategies}, school = {George Mason University}, year = {2003}, url = {http://mysite.verizon.net/mabramso/research/Dissert.pdf}, keywords = {Reinforcement learning, tabu search, Sarsa Learning Vector Quantization}, abstract = { How do we learn to accomplish complex tasks without knowledge of the end state? This absence of teleological explanation characterizes complex systems. Rather, intelligent behavior to accomplish complex tasks emerges from the coordination of many actions or many agents. Reinforcement learning is a general and powerful methodology to learn complex tasks by acquiring complementary behaviors from local interactions. To represent the actions of other agents, an efficient encoding of the state space must be found with a function approximator. This thesis claims that learning coordination strategies of localized behaviors can be achieved through self-organized and distributed reinforcement learning. The distributed representation found in Learning Vector Quantization (LVQ) enables reinforcement learning (RL) methods to cope with a large decision search space defined in terms of equivalence classes of input patterns like those found in complex problems. In particular, this thesis introduces S[arsa]LVQ, a new hybrid reinforcement learning algorithm, and shows its feasibility for Go, a coordination strategy game, and control tasks. As the distributed LVQ representation corresponds to a (quantized) codebook of compressed and generalized pattern templates, the state space requirements for reinforcement methods are significantly reduced, thus decreasing the complexity of the decision space and consequently improving performance. Exploration can drastically in?uence the speed and convergence of this incremental algorithm. To this end, novel approaches to exploration based on tabu search (TS) are introduced. TS is a flexible memory-based search mechanism. This thesis shows how TS can be integrated with an RL algorithm like SLVQ and how to avoid cycling through previous solutions. The learning by parts paradigm inspired from behavioral psychology scales up SLVQ to partially observable states with a mixed-strategy approach. } } @Proceedings{aips2002, editor = {Drabble, Brian and Koehler, Jana and Refanidis, Ioannis}, title = {Sixth International Conference on AI Planning \& Scheduling, Workshop Notes, Planning and Scheduling with Multiple Criteria}, year = {2002}, organization = {Laboratory for Analysis and Architecture of Systems, Toulouse}, url = {http://www.laas.fr/aips/ws-tu1.pdf}, } @InProceedings{allis1991, author = {Allis, Victor L.}, title = {Which games will survive?}, year = {1991}, booktitle = {Heuristic Programming in Artificial Intelligence 2}, editor = {Levy, David and Beal, Don}, publisher = {Ellis Horwood}, keywords = {complexity, scrabble, othello, checkers, nim, nine men's morris, go-moku, renju, chess, chinese-chess, draughts, bridge, backgammon}, } @PhdThesis{allis1994, author = {Allis, Victor L.}, title = {Searching for Solutions in Games and Artificial Intelligence}, school = {University of Limburg}, year = {1994}, abstract = { In this thesis ``intelligent'' games are investigated from the perspective of Artificial Intelligence (AI) research. Games were selected in which, at least partially, human expert players outperformed their artificial opponents. By investigating a game, we envision at least two possible outcomes. If we achieve a playing strength sufficient to defeat the best human players, analysis of the means which led to this improvement may uncover new AI techniques. If the playing strength keeps falling short, even after prolonged attempts, of that of the best human players a better understanding of the problems inherent in playing the game at a high level may be acquired. We remark that there is a possibility that the results do not lead to progress (i.e., no new AI techniques and no better understanding of the inherent problems). In the first case, the improvement may be due to entirely domain-specific techniques which cannot be generalized to AI techniques. In the second case, we may find that we have difficulty in isolating the problems from our failed attempts. By investigating a representative set of games, the probability increases that new AI techniques are developed or insight into problems hindering progress is obtained. For our investigations, we have selected a set of games called the Olympic List, consisting of: awari, backgammon, bridge, chess, Chinese chess, checkers, connect-four, draughts, go, go-moku, nine men's morris, othello, qubic, renju and scrabble. The research is in two parts. First, we have investigated three games which we believed could be solved: awari, qubic and go-moku. Games can be solved if it is possible to determine strategies leading to the best possible result for both players. For qubic and go-moku we have been able to find strategies which guarantee a win for the first player. For awari this has not yet been achieved, but we did create a program that outperforms the strongest human players. Analysis and generalization of the methods used in solving qubic and go-moku resulted in two new AI techniques: the search techniques proof-number search (pn-search) and dependency-based search (dbsearch). Awari is close to its solution, indeed so close that we believe that extant techniques suffice to solve it. Second, for each game of the Olympic List we have investigated whether the difference in playing skill of human beings and computer programs gives us reason to believe that there is an intrinsic obstacle to progress. We have found that, based on insufficient flexibility and learning ability, an experience obstacle exists. This obstacle is particularly conspicuous in bridge and go. We conjecture that, while such obstacles exist in the games domain, these same obstacles will stand in the way of progress in other domains. This thesis consists of six chapters. In chapter 1, the relevance of investigating games is discussed, leading to the formulation of a problem statement and three research questions. In chapter 2, pn-search is defined. It is shown that pn-search traverses a set of state spaces much more efficiently than alternative search algorithms; awari serves to provide an example. In chapter 3, db-search is defined, a search algorithm that traverses a state space significantly reduced when compared to traditional search algorithms. It is shown that under clearly defined conditions the reduced state space is complete, which means that it contains all solutions present in the original state space. The potential of db-search is demonstrated on an example domain. In chapter 4, it is demonstrated how pn-search and db-search solved qubic. Similarly, in chapter 5 it is demonstrated how pn-search and db-search combined solved go-moku. In chapter 6 all games of the Olympic List are investigated, resulting in, among others, a prediction of the playing strengths of the strongest computer programs in the year 2000 and a discussion of the future of games in our society. }, keywords = { go, AI, pn-search, db-search, proof-number, awari, backgammon, bridge, chess, Chinese chess, checkers, connect-four, draughts, go-moku, nine men's morris, othello, qubic, renju, scrabble }, url = {http://fragrieu.free.fr/SearchingForSolutions.pdf} } @Article{alpert1999, author = {Alpert, Mark}, title = {Not just Fun and Games}, year = {1999}, journal = {Scientific American}, volume = {4}, keywords = {profile John H. Conway}, } @Misc{althoefer2000, author = {Alth\"ofer, Ingo}, title = {3-Hirn - New Ways in {G}o with Computers}, year = {2000}, note = {Notes on seminar, given at the European Go Congress, Berlin, 10 August, 2000}, keywords = {3-Hirn, Dreihirn}, url = {http://www.mathematik.uni-jena.de/www/fakultaet/iam/personen/StrausTalke.html}, } @InProceedings{althoeffer2002, author = {Alth\"ofer, Ingo and Snatzke, Raymond Georg}, title = {Playing Games with Multiple Choice Systems}, booktitle = {Computers and Games Conference 2002}, year = {2002} } @Article{althoeffer2003, author = {Ingo Alth\"ofer}, title = {A 20-Choice Experiment in {G}o for Human + Computer}, journal = {ICGA Journal}, year = {2003}, volume = {26}, number = {2}, } @InProceedings{araki2007, author = {Araki, Nobuo and Yoshida, Kazuhiro and Tsuruoka, Yoshimasa and Tsujii, Jun'ichi}, title = {Move Prediction in {G}o with the Maximum Entropy Method}, booktitle = {2007 IEEE Symposium on Computational Intelligence and Games}, year = {2007}, keywords = {move prediction, pattern learning, maximum entropy method, re-ranking}, url = {http://www-tsujii.is.s.u-tokyo.ac.jp/~ark/publications/CIG2007.pdf}, abstract = { We address the problem of predicting moves in the board game of Go. We use the relative frequencies of local board patterns observed in game records to generate a ranked list of moves, and then apply the maximum entropy method (MEM) to the list to re-rank the moves. Move prediction is the task of selecting a small number of promising moves from all legal moves, and move prediction output can be used to improve the efficiency of the game tree search. The MEM enables us to make use of multiple overlapping features, while avoiding problems with data sparseness. Our system was trained on 20000 expert games and had 33.9 \% prediction accuracy in 500 expert games. } } @Article{benson1976, author = {Benson, David B.}, title = {Life in the Game of {G}o}, year = {1976}, journal = {Information Sciences}, volume = {10}, pages = {17-29}, publisher = {American Elsevier Publishing Company}, keywords = {life and death, algorithm, static}, url = {http://www.cs.ualberta.ca/~games/go/seminar/2002/020717/benson.pdf} } @InProceedings{benson1979, author = {Benson, David B.}, title = {Tree-Analysis Techniques in Tsumego}, year = {1979}, booktitle = {International Joint Conference on Artificial Intelligence}, pages = {50-52}, keywords = {tsumego, tree, search}, } @InBook{berlekamp1996a, author = {Berlekamp, Elwyn}, title = {The Economist's View of Combinatorial Games}, booktitle = {Games of No Chance}, year = {1996}, publisher = {Cambridge University Press}, pages = {365-405}, keywords = {go, combinatorial game theory, thermograph, temperature}, url = {http://www.msri.org/publications/books/Book29/files/ber.pdf}, } @InBook{berlekamp1996b, author = {Berlekamp, Elwyn and Kim, Yonghoan}, title = {Where Is the ``Thousand-Dollar Ko''?}, year = {1996}, keywords = {go, combinatorial game, endgame, ko}, pages = {203-226}, booktitle = {Games of No Chance}, publisher = {Cambridge University Press}, url = {http://www.msri.org/publications/books/Book29/files/kim.pdf}, } @InBook{berlekamp2001, author = {Berlekamp, Elwyn}, title = {Idempotents Among Partisan Games}, year = {2001}, keywords = {Idempotents, Combinatorial game theory}, booktitle = {More Games of No Chance}, pages = {1-23}, publisher = {Cambridge University Press}, url = {http://math.berkeley.edu/~berlek/papers/idem.ps}, } @Misc{bewersdorff1998, author = {Bewersdorff, Joerg}, title = {{G}o und {M}athematik}, year = {1998}, note = {In German}, keywords = {go, mathematics, combinatorial game theory}, url = {http://www.galois-theorie.de/pdf/go.pdf}, } @InBook{bewersdorff2003, author = {Bewersdorff, Joerg}, title = {Gl\"uck, Logik and Bluff}, chapter = {Environmental {G}o}, publisher = {Vieweg}, year = {2003}, edition = {3} } @MastersThesis{boon1991, author = {Boon, Mark}, title = {Overzicht van de ontwikkeling van een {G}o spelend programma}, year = {1991}, school = {University Amsterdam}, note = {In Dutch.}, keywords = {Goliath}, } @Article{bouzy1992, author = {Bouzy, Bruno and Victorri, Bernard}, title = {{G}o et intelligence artificielle}, year = {1992}, journal = {Revue de l'AFIA}, volume = {10}, note = {In French}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/AFIA92.article.pdf}, } @PhdThesis{bouzy1995, author = {Bouzy, Bruno}, title = {Modelisation cognitive du joueur de {G}o}, year = {1995}, school = {Universite Paris}, note = {In French}, keywords = {Indigo}, url = {ftp://ftp-igs.joyjoy.net/Go/computer/bbthese.ps.Z}, } @InProceedings{bouzy1995b, author = {Bouzy, Bruno}, title = {Les ensemble flous au jeu de {G}o}, year = {1995}, booktitle = {Actes des Recontres francophones sur la Ligique Floue et ses Applications, LFA 1995}, note = {In French}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/flou.article.pdf}, } @InProceedings{bouzy1995c, author = {Bouzy, Bruno}, title = {The {INDIGO} program}, year = {1995}, booktitle = {Proceedings of the 2nd Game Programming Workshop in Japan, Kanagawa 1995}, keywords = {INDIGO}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/indigo.article.pdf}, } @TechReport{bouzy1995d, author = {Bouzy, Bruno}, title = {Towards Spatial Reasoning about ``Natural'' Objects}, institution = {LIAFA - Universit\'e Denis Diderot}, year = {1995}, url = {http://www.liafa.jussieu.fr/web9/rapportrech/rapport/1995/tospare.pdf}, keywords = {Spatial reasoning, Objects, Natural versus Artificial, Relationships, Fractal dimension}, abstract = { Until now, most of works about Spatial Reasoning focused on artificial objects. This paper addresses Spatial Reasoning in the game of Go that is a domain where the objects look like 'natural'. Two criterias toward a definition of ``natural'' objects is proposed: fractal structure of objects and dependency between genesis and use of objects. Combinatorial complexity of the game of Go obliges the Computer Go community to study spatial representations of human players that are complex. These representations contain the concepts of grouping and fractioning. Spatial Reasoning in Go is qualitative. It creates objects and relationships between them. Our work is linked with mereotopology and Geographical Information Systems. We assume that studies about Spatial Reasoning in Go is a path toward a general theory of Spatial Reasoning about natural objects. } } @Misc{bouzy1996, author = {Bouzy, Bruno}, title = {Un modele du jeu de {G}o base sur les interactions}, year = {1996}, note = {In French}, url_ = {http://www.math-info.univ-paris5.fr/~bouzy/publications/SMA96.article.ps.gz}, } @Misc{bouzy1996b, author = {Bouzy, Bruno}, title = {Spatial reasoning in the game of {G}o}, year = {1996}, keywords = {spatial reasoning, objects, relationships}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/SRGo.article.pdf}, } @Misc{bouzy1996c, author = {Bouzy, Bruno and Cazenave, Tristan}, title = {Shared concepts between complex domains and the game of {G}o}, year = {1996}, keywords = {economy, social sciences, war simulation, linguistic, biology, earth sciences}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/UES96.article.pdf}, } @Misc{bouzy1996d, author = {Bouzy, Bruno}, title = {There are no winning moves except the last}, year = {1996}, keywords = {INDIGO}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/incertitude.article.pdf}, } @Misc{bouzy1996e, author = {Bouzy, Bruno}, title = {Incremental Updating of Objects in {INDIGO}}, year = {1996}, keywords = {incremental}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/incremental.article.pdf}, } @Misc{bouzy1996f, author = {Bouzy, Bruno}, title = {On Meta-games approaches to Computer {G}o}, year = {1996}, keywords = {meta-game}, url_ = {http://www.math-info.univ-paris5.fr/~bouzy/publications/IJCAI95-Meta.article.ps.gz}, } @InProceedings{bouzy1999, author = {Bouzy, Bruno}, title = {Complex games in practice}, booktitle = {Fifth Game Programming Workshop in Japan}, year = {1999}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/GPW99.pdf}, keywords = {Group strength, Monocolor Tree Search, Killing and Living Moves Numbers} } @InProceedings{bouzy2001, author = {Bouzy, Bruno}, title = {{G}o patterns generated by retrograde analysis}, year = {2001}, booktitle = {Computer Olympiads, Maastricht}, keywords = {Retrograde analysis}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/RAGO.pdf}, } @Misc{bouzy2001b, author = {Bouzy, Bruno and Cazenave, Tristan}, title = {Computer {G}o: an {AI} Oriented Survey}, year = {2001}, note = {Preprint for article in AI Journal. To be published.}, keywords = {survey}, url = {http://www.math-info.univ-paris5.fr/~bouzy/CG-AISurvey.ps.gz}, } @Article{bouzy2001c, author = {Bouzy, Bruno}, title = {Le role des concepts spatiaux dans la programmation du jeu de go}, journal = {Revue d'Intelligence Artificielle}, year = {2001}, note = {In French}, kewords = {Spatial reasoning}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/RoleConceptsSpatiauxPdG.pdf}, } @InProceedings{bouzy2002, author = {Bouzy, Bruno}, title = {A small {G}o board study of metric and dimensional Evaluation functions}, booktitle = {3rd Computer and Games Conference, Edmonton}, year = {2002}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/CG2002-Bouzy.pdf}, keywords = {very-little-knowledge evaluation function, distance, dimension}, abstract = { The difficulty to write successful 19x19 go programs lies not only in the combinatorial complexity of go but also in the complexity of designing a good evaluation function containing a lot of knowledge. Leaving these obstacles aside, this paper defines very-little-knowledge evaluation functions used by programs playing on very small boards. The evaluation functions are based on two mathematical tools, distance and dimension, and not on domain-dependent knowledge. After a qualitative assessment of each evaluation function, we built several programs playing on 4x4 boards by using tree search associated with these evaluation functions. We set up an experiment to select the best programs and identify the relevant features of these evaluation functions. Thanks to the results obtained by these very-little-knowledge-based programs, we can foresee the usefulness of each evaluation function. } } @Article{bouzy2003, author = {Bouzy, Bruno}, title = {The move decision strategy of {I}ndigo}, journal = {ICGA Journal}, year = {2003}, volume = {26}, number = {1}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/MyBouzy-ICGAJournal.pdf}, keywords = {Quick & slow evaluation, strategic evaluation, urgent move selection, single-agent & two-agent search}, abstract = { This paper describes the move decision strategy of Indigo. By using the example of Indigo, the paper shows that the move decision process of a Go program can be very different from the processes used in other games with lower complexity than the complexity of Go, even if the basic modules are conventional (move generator, evaluation function and tree search). Indigo uses them in a specific way, adapted to computer Go, which may be of interest for researchers on other mind games as complex as Go. The evaluation function can be quick , slow or strategic . It may or may not include local tree search. The move generation brings about different kinds of moves: urgent moves, life and death moves and calm moves. Urgent moves are statically qualified with a global urgency. A two-player quiescence search verifies that the urgent move does not decrease the position evaluation. Calm moves are used within two-player selective global search at a very low depth. Besides, Indigo also uses single-agent search to refine the strategic importance of goals. Lastly, Indigo chooses either the calm move, the life and death move or the urgent move to be the global move. } } @Article{bouzy2003b, author = {Bouzy, Bruno}, title = {Mathematical morphology applied to computer go}, journal = {IJPRAI}, year = {2003}, volume = {17}, number = {2}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/MyBouzy-IJPRAI.pdf}, keywords = {Mathematical morphologu, territory, dilation, erosion, closing}, abstract = { This paper shows how mathematical morphological operators can be applied to computer go. On one hand, mathematical morphology is a very powerful tool within image processing community. On the other hand, the Zobrist's model is well-known within the computer go community for its influence recognition. We present a model, derived from the closing operator of mathematical morphology and from the Zobrist's model, which yields very good results for territory recognition. Moreover, we give efficient implementations of the dilation operator and territory recognition for computer go. This model was found when developing Indigo, our go playing program, and is now used with success in GnuGo, the go playing program of the Free Software Foundation. } } @InProceedings{bouzy2003c, author = {Bouzy, Bruno and Helmstetter, Bernard}, title = {{M}onte {C}arlo {G}o Developments}, booktitle = {Advances in Computer Games conference (ACG-10), Graz 2003}, pages = {159-174}, year = {2003}, editor = {H. Jaap van den Herik, Hiroyuki Iida, Ernst A. Heinz}, publisher = {Kluwer}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-helmstetter.pdf}, keywords = {Monte-Carlo approach, heuristics}, abstract = { We describe two Go programs, OLGA and OLEG, developed by a Monte-Carlo approach that is simpler than Bruegmann's (1993) approach. Our method is based on Abramson (1990). We performed experiments to assess ideas on (1) progressive pruning, (2) all moves as first heuristic, (3) temperature, (4) simulated annealing, and (5) depth-two tree search within the Monte-Carlo framework. Progressive pruning and the all moves as first heuristic are good speed-up enhancements that do not deteriorate the level of the program too much. Then, using a constant temperature is an adequate and simple heuristic that is about as good as simulated annealing. The depth-two heuristic gives deceptive results at the moment. The results of our Monte-Carlo programs against knowledge-based programs on 9x9 boards are promising. Finally, the ever-increasing power of computers lead us to think that Monte-Carlo approaches are worth considering for computer Go in the future. } } @InProceedings{bouzy2003d, author = {Bouzy, Bruno}, title = {Associating domain-dependent knowledge and {M}onte {C}arlo approaches within a {G}o program}, booktitle = {Joint Conference on Information Sciences}, year = {2003}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/Bouzy-JCIS03.pdf}, keywords = {Monte Carlo, Indigo, Olga}, } @InProceedings{bouzy2004, author = {Bouzy, Bruno}, title = {Associating shallow and selective global tree search with {M}onte {C}arlo for 9x9 {G}o}, booktitle = {4rd Computer and Games Conference, Ramat-Gan}, year = {2004}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/cg04-bouzy.pdf}, keywords = {Min-max, progressive pruning, Indigo}, } @Article{bouzy2004b, author = {Bouzy, Bruno}, title = {{G}o {I}ntellect wins 9x9 {G}o tournament}, journal = {ICGJ}, year = {2004}, volume = {27}, number = {3}, pages = {170-191}, keywords = {9th Computer Olympiad} } @Article{bouzy2004c, author = {Bouzy, Bruno}, title = {The 4th {C}omputers and {G}ames conference}, journal = {ICGJ}, year = {2004}, volume = {27}, number = {3}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/CG04-report.pdf}, keywords = {9th Computer Olympiad} } @InProceedings{bouzy2005, author = {Bruno Bouzy and Guillaume Chaslot}, title = {Extraction bayesienne et integration de patterns representes suivant les K plus proches voisins pour le go 19x19}, booktitle = {Actes de la conference EGC05}, year = {2005}, note = {In French}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-chaslot-egc05.pdf} } @Article{bouzy2005b, author = {Bouzy, Bruno}, title = {Associating domain-dependent knowledge and {M}onte {C}arlo approaches within a {G}o program}, journal = {Information Sciences}, year = {2005}, note = {To appear}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/Bouzy-InformationSciences.pdf}, keywords = {Monte Carlo, domain-dependent knowledge, Indigo}, abstract = { This paper underlines the association of two computer go approaches, a domain-dependent knowledge approach and Monte Carlo. First, the strengthes and weaknesses of the two existing approaches are related. Then, the association is described in two steps. A first step consists in using domain-dependent knowledge within the random games enabling the program to compute evaluations that are more significant than before. A second step simply lies in pre-processing the Monte Carlo process with a knowledge-based move generator in order to speed up the program and to eliminate tactically bad moves. We set up experiments demonstrating the relevance of this association, used by Indigo at the 8th computer olympiad as well. } } @InProceedings{bouzy2005c, author = {Bruno Bouzy and Guillaume Chaslot}, title = {Bayesian generation and integration of K-nearest-neighbor patterns for 19x19 {G}o}, booktitle = {IEEE 2005 Symposium on Computational Intelligence in Games, Colchester, UK}, pages = {176-181}, year = {2005}, editor = {G. Kendall and Simon Lucas}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-chaslot-cig05.pdf}, keywords = {K-nearest-neighbor, pattern database}, abstract = { This paper describes the generation and utilisation of a pattern database for 19x19 go with the K-nearest-neighbor representation. Patterns are generated by browsing recorded games of professional players. Meanwhile, their matching and playing probabilities are estimated. The database created is then integrated into an existing go program, INDIGO, either as an opening book or as an enrichment of other pre-existing hand-crafted databases used by INDIGO move generator. The improvement brought about by the use of this pattern database is estimated at 15 points on average, which is significant on go standards. } } @InProceedings{bouzy2005d, author = {Bouzy, Bruno}, title = {History and Territory Heuristics for {M}onte-{C}arlo {G}o}, year = {2005}, booktitle = {Joint Conference on Information Sciences, Salt Lake City, Heuristic Search and Computer Game Playing Session}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-jcis05.pdf}, keywords = {territory heuristic, history heuristic, Indigo}, abstract = { This paper assesses two heuristics within the 19x19 Monte Carlo go framework of INDIGO [4, 5, 7]: the territory heuristic and the history heuristic, both in their ``internal'' and ``external'' versions. The external territory heuristic is more effective, leading to a 40- point improvement on 19x19 boards. The external history heuristic brings about a 10-point improvement. The internal territory heuristic yields a few points improvement, and the internal history heuristic has already been assessed on 9x9 boards [7]. Most of these heuristics were used by INDIGO at the 2004 Computer Olympiad [10]. } } @InProceedings{bouzy2005e, author = {Bouzy, Bruno}, title = {Move Pruning Techniques for {M}onte-{C}arlo {G}o}, booktitle = {11th Advances in Computer Game conference, Taipei}, year = {2005}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-acg11.pdf}, keywords = {Monte-Carlo Go, progressive pruning, Miai pruning, set pruning}, abstract = { Progressive Pruning (PP) is used in the Monte-Carlo go playing program Indigo. For each candidate move, PP launches random games starting with this move. PP gathers statistics on moves, and it prunes moves statistically inferior to the best one [5]. This papers yields two new pruning techniques: Miai Pruning (MP) and Set Pruning (SP). In MP the second move of the random games is selected at random among the set of candidate moves. SP consists in gathering statistics about two sets of moves, GOOD and BAD, and it prunes the latter when statistically inferior to the former. Both enhancements clearly speed up the process on 9x9 boards, and MP improves slightly the playing level. Scaling up MP to 19x19 boards results in a 30\% speed-up enhancement and in a four-point improvement on average. } } @InProceedings{bouzy2006, author = {Bruno Bouzy and Guillaume Chaslot}, title = {{M}onte-{C}arlo {G}o Reinforcement Learning Experiments}, booktitle = {IEEE 2006 Symposium on Computational Intelligence in Games}, year = {2006}, editor = {G. Kendall and S. Louis}, address = {Reno, USA}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-chaslot-cig06.pdf}, keywords = {Monte-Carlo Go, reinforcement learning, Indigo}, abstract = { This paper describes experiments using reinforcement learning techniques to compute pattern urgencies used during simulations performed in a Monte-Carlo Go architecture. Currently, Monte-Carlo is a popular technique for computer Go. In a previous study, Monte-Carlo was associated with domain-dependent knowledge in the Go-playing program Indigo. In 2003, a 3x3 pattern database was built manually. This paper explores the possibility of using reinforcement learning to automatically tune the 3x3 pattern urgencies. On 9x9 boards, within the Monte-Carlo architecture of Indigo, the result obtained by our automatic learning experiments is better than the manual method by a 3-point margin on average, which is satisfactory. Although the current results are promising on 19x19 boards, obtaining strictly positive results with such a large size remains to be done. } } @InProceedings{bouzy2007, author = {Guillaume Chaslot and Mark Winands and H. Jaap van den Herik and Jos Uiterwijk and Bruno Bouzy}, title = {Progressive Strategies for {M}onte-{C}arlo Tree Search}, booktitle = {Joint Conference on Information Sciences, Salt Lake City 2007, Heuristic Search and Computer Game Playing Session}, year = {2007}, url = {http://www.math-info.univ-paris5.fr/~bouzy/publications/CWHUB-pMCTS-2007.pdf}, keywords = {Monte-Carlo, progressive bias, progressive unpruning, Mango}, abstract = { Monte-Carlo Tree Search (MCTS) is a new best-first search guided by the results of Monte-Carlo simulations. In this article we introduce two progressive strategies for MCTS, called progressive bias and progressive unpruning. They enable the use of relatively time-expensive heuristic knowledge without speed reduction. Progressive bias directs the search according to heuristic knowledge. Progressive unpruning first reduces the branching factor, and then increases it gradually again. Experiments assess that the two progressive strategies significantly improve the level of our Go program Mango. Moreover, we see that the combination of both strategies perform even better on larger board sizes. } } @Article{bremer2004, author = {Lars Bremer}, title = {Denk mal! - Die zwei st\"arksten Go-Programme im Vergleich}, journal = {CSS}, year = {2004}, number = {2}, note = {In German}, keywords = {Go++, GNU Go}, url_ = {http://www.mustrum.de/pdf/denkmal4.pdf} } @Article{brooks2002, author = {Brooks, Michael}, title = {Go for it}, journal = {New Scientist}, year = {2002}, volume = {174}, pages = {38}, month = {April}, keywords = {Michael Reiss, Martin M\"uller, Jonathan Schaeffer, Go4++} } @Misc{bruegmann1993, author = {Br\"ugmann, Bernd}, title = {Monte {C}arlo {G}o}, year = {1993}, keywords = {go, statistical, simulated annealing}, url = {ftp://ftp.cgl.ucsf.edu/pub/pett/go/ladder/mcgo.ps}, } @TechReport{burmeister1995, author = {Burmeister, Jay and Wiles, Janet}, title = {An Introduction to the Computer {G}o Field and Associated {I}nternet Resources}, year = {1995}, institution = {Department of Computer Science, University of Queensland}, number = {CS-TR-339}, keywords = {Internet, introduction, overview}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/CS-TR-339.html}, } @InProceedings{burmeister1995b, author = {Burmeister, Jay and Wiles, Janet and Purchase, Helen}, title = {The Integration of Cognitive Knowledge into Perceptual representations in Computer {G}o}, year = {1995}, booktitle = {2nd Game Programming Workshop in Japan}, address = {Kanagawa}, keywords = {perception, cognition, knowledge}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/c-p.integration.pdf}, } @InProceedings{burmeister1995c, author = {Burmeister, Jay and Wiles, Janet}, title = {Accessing {G}o and Computer {G}o Resources on the {I}nternet}, year = {1995}, booktitle = {2nd Game Programming Workshop in Japan}, address = {Kanagawa}, keywords = {Internet}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/comp-go.internet.pdf}, } @InProceedings{burmeister1995d, author = {Burmeister, Jay and Wiles, Janet}, title = {The Challenge of {G}o as a Domain for {AI} Research: A Comparision Between {G}o and Chess}, year = {1995}, booktitle = {3rd Australian and New Zealand Conference on Intelligent Information Systems}, address = {Perth}, keywords = {chess}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/go-vs-chess.pdf}, } @InProceedings{burmeister1995e, author = {Burmeister, Jay and Wiles, Janet and Purchase, Helen}, title = {On Relating Local and Global Factors: A Case Study from the Game of {G}o}, year = {1995}, booktitle = {3rd Australian and New Zealand Conference on Intelligent Information Systems}, address = {Perth}, keywords = {top-down, bottom-up, local, global, integration}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/l-g.factors.pdf}, } @InProceedings{burmeister1996, author = {Burmeister, Jay and Wiles, Janet}, title = {The Use of Inferential Information in Remembering {G}o Positions}, year = {1996}, month = {September}, booktitle = {Third Game Programming Workshop}, address = {Kanagawa, Japan}, keywords = {memory, inference, human}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/inf.info.pdf}, } @InProceedings{burmeister1997, author = {Burmeister, Jay and Wiles, Janet}, title = {{AI} Techniques Used in Computer {G}o}, year = {1997}, booktitle = {Fourth Conference of the Australasian Cognitive Science Society}, address = {Newcastle}, keywords = {AI}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/comp-go.AI.pdf}, } @InProceedings{burmeister1997b, author = {Burmeister, Jay and Saito, Yasuki and Yoshikawa, Atsushi and Wiles, Janet}, title = {Memory Performance of Master {G}o Players}, year = {1997}, booktitle = {IJCAI workshop Using Games as an Experimental Testbed for AI Research}, month = {August}, address = {Nagoya}, keywords = {memory, human}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/go-master.pdf}, } @PhdThesis{burmeister2001, author = {Jay Burmeister}, title = {Studies in Human and Computer {G}o: Assessing the Game of {G}o as a Research Domain for Cognitive Science}, school = {The University of Queensland}, year = {2001}, address = {Australia}, month = {October}, url = {http://www.itee.uq.edu.au/~janetw/Computer Go/PhD_thesis.pdf}, keywords = {Cognitive psychology, learning, Many Faces of Go, Go4++, sequential pennies-guessing task, sequential construction task}, abstract = { This thesis assesses the game of Go as a research domain for Cognitive Science by investigating some of the research issues within the domain of Go, and in particular, by assessing Go as a research domain for both Artificial Intelligence and Cognitive Psychology. The following general assessment questions were used: To what extent does the domain of Go facilitate the investigation of research questions? What type of research issues can be investigated within the domain of Go? Does investigation within the domain of Go give rise to further interesting research questions? Do useful generalisations arise from research conducted within the domain of Go? What types of generalisations can be made? In what ways does the domain of Go facilitate an exchange of ideas between disciplines? The methodology used to answer these questions involved case studies of Computer Go programs and experimental studies in the memory field. In Computer Go the research issues addressed were related to knowledge, search and their interaction. The AI techniques used in Computer Chess are generally not successful in Computer Go. It is commonly believed that the large branching factor in Go is the reason why brute-force search techniques used in Computer Chess do not work in Computer Go. However, the main reason for the failure is that static evaluation of Go positions is not possible due to the necessity of life and death analysis (although the large branching factor is certainly a contributing factor to the failure). Case studies of two Go programs (Many Faces of Go and Go4++) as well as an overview of the current top Go programs are presented. Together they show how the techniques developed by the Computer Go community address the difficulties associated with programming a game that resists the brute-force search approach. The memory research issues addressed the use of Go for studying the factors that affect memory for Go moves and the extent to which inference impacts on memory performance for sequences of Go moves. Three experimental studies comprising experiments and case studies were conducted using beginner, experienced, and master Go players as participants. The experimental studies were instrumental in the development of a new experimental paradigm for testing memory performance for sequences of moves from a Go game, and in particular, the development of two new experimental tasks, namely the sequential pennies-guessing task and the sequential construction task. An extension of this paradigm led to the development of a potential technique for learning Go involving the use of interactive memory tasks. The results of the experimental studies indicated that inference impacts to some extent on memory performance, that memory for sequences of moves is related to Go skill, and that Go is a better domain than chess for investigating memory for sequences. Following the assessment of Go as a research domain for Artificial Intelligence and Cognitive Psychology, this thesis concludes that: the game of Go provides a good research domain for Artificial Intelligence, facilitating investigation into areas such as planning, problem solving, pattern recognition, and opponent modelling; and the game of Go provides a good research domain for Cognitive Psychology, facilitating investigation into areas such as memory, implicit learning, pattern recognition, perceptual learning, problem solving, and attention. Based on these conclusions, this thesis finds that: The game of Go provides a good research domain for Cognitive Science. } } @InProceedings{cai2001, author = {Cai, Xindi and Wunsch, D.C. II}, title = {A parallel computer-{G}o player, using {HDP} method}, booktitle = {IJCNN '01. International Joint Conference on Neural Networks.}, pages = {2373-2375}, year = {2001}, volume = {4}, url = {http://www.ece.umr.edu/acil/Publications/CONFERENCE/A parallel computer-Go.pdf} } @Article{caldwell1997, author = {Caldwell, Thomas}, title = {Can Computers '{G}o' Beyond Chess?}, year = {1997}, journal = {Computing Japan Magazin}, volume = {9}, keywords = {comparison, chess, Bozulich, Nihon Ki-in}, url = {http://www.cjmag.co.jp/magazine/issues/1997/sept97/0997wchess.html}, } @Article{cant2001, author = {Richard Cant, Julian Churchill, David Al-Dabass}, title = {Using hard and soft Artificial Intelligence algorithms to simulate human {G}o playing techniques}, journal = {International Journal of Simulation Systems, Science \& Technology}, publisher = {United Kingdom Simulation Society}, year = {2001}, volume = {2}, number = {1}, pages = {31-49}, month = {June}, url = {http://ducati.doc.ntu.ac.uk/uksim/journal/Vol-2/No-1/RichardCant/Cant.pdf}, keywords = {Neural Networks, Alpha beta search, NeuralGo, Many Faces of Go}, abstract = { We describe the development of a Go playing computer program that combines the use of hard Artificial Intelligence (AI) techniques (alpha-beta search trees) with soft AI techniques (neural networks). The concept is based on a model of human play where selection of plausible moves is made using a gestalt process based on experience and the plausible moves are subjected to an objective analysis. The performance of the program is analysed by play against a standard computer Go program and it is shown that the use of hard AI enhances the performance of the soft AI system. } } @InProceedings{cant2002, author = {Cant, Richard and Churchill, Julian and Al-Dabass, David}, title = {A Hybrid Artificial Intelligence Approach with Application to Games}, booktitle = {IEEE02}, year = {2002}, keywords = {Neural Networks, Alpha beta search}, url = {http://ducati.doc.ntu.ac.uk/uksim/dad/webpagepapers/IEEE02/CantChrchill-Hawaii.pdf} } @Misc{cazenave1994, author = {Cazenave, Tristan}, title = {Systeme Apprenant a jouer au {G}o}, year = {1994}, howpublished = {Deuxieme Rencontres des jeunes chercheurs en IA}, address = {Marseille}, note = {In French}, keywords = {learning}, url = {http://www.ai.univ-paris8.fr/~cazenave/rjcia.pdf}, } @TechReport{cazenave1995, author = {Cazenave, Tristan}, title = {Management of Uncertainty in Combinatorial Game Theory}, year = {1995}, institution = {Laforia}, address = {Paris}, number = {95-10}, keywords = {uncertainty, risk, combinatorial game theory}, url = {http://www.ai.univ-paris8.fr/~cazenave/cgtmu.ps.gz}, } @InProceedings{cazenave1996, author = {Cazenave, Tristan}, title = {Automatic acquisition of tactical {G}o rules}, year = {1996}, booktitle = {3rd Game Programming Workshop in Japan}, address = {Hakone}, keywords = {machine learning, meta knowledge, knowledge acquisition, game theory, Gogol}, url = {http://www.ai.univ-paris8.fr/~cazenave/gpw96.pdf}, } @Misc{cazenave1996b, author = {Cazenave, Tristan}, title = {Automatic ordering of predicates by metarules}, year = {1996}, howpublished = {International Workshop ``META'96'', Bonn 1996}, keywords = {meta programming, meta reasoning, first order logic, machine learning}, url = {http://www.ai.univ-paris8.fr/~cazenave/meta96.pdf}, } @Misc{cazenave1996c, author = {Cazenave, Tristan}, title = {Self fuzzy learning}, year = {1996}, howpublished = {International Workshop ``LPSC'96''}, address = {Bonn}, keywords = {explanation based learning, fuzzy logic, strategy}, url = {http://www.ai.univ-paris8.fr/~cazenave/fuzzy.pdf}, } @Misc{cazenave1996d, author = {Cazenave, Tristan}, title = {Learning to forecast by explaining the consequences of actions}, year = {1996}, howpublished = {International Workshop ``MALFO'96''}, address = {Madrid}, keywords = {explanation based learning, metaknowledge, combinatorial game theory, Gogol}, url = {http://www.ai.univ-paris8.fr/~cazenave/malfo96.pdf}, } @Misc{cazenave1996e, author = {Cazenave, Tristan and Nigro, Jean-Marc}, title = {Constraint based explanations in games}, year = {1996}, howpublished = {International Conference ``IPMU'96''}, address = {Granada}, keywords = {explanation based learning}, url = {http://www.ai.univ-paris8.fr/~cazenave/ipmu96.pdf}, } @PhdThesis{cazenave1997, author = {Cazenave, Tristan}, title = {Syst\`eme d'Apprentissage Par Auto-Observation. Application au jeu de {G}o.}, year = {1997}, school = {Universite Paris}, note = {In French}, keywords = {machine learning, self observation, combinatorial game theory, generalization, explanation, compilation, management}, url = {http://www.ai.univ-paris8.fr/~cazenave/these.pdf}, } @Misc{cazenave1997b, author = {Cazenave, Tristan}, title = {{G}ogol (an Analytical Learning Program)}, year = {1997}, howpublished = {FOST cup, IJCAI'97}, address = {Nagoya}, keywords = {Gogol}, url = {http://www.ai.univ-paris8.fr/~cazenave/fost97.pdf}, } @InProceedings{cazenave1997c, author = {Cazenave, Tristan and Moneret, R\'egis}, title = {Development and Evaluation of Strategic Plans}, year = {1997}, booktitle = {Game Programming Workshop in Japan'97}, address = {Hakone}, keywords = {evaluation, AND/OR search, probability estimation, goals}, url = {http://www.ai.univ-paris8.fr/~cazenave/gpw97.pdf}, } @InProceedings{cazenave1998, author = {Cazenave, Tristan}, title = {Controlled Partial Evaluation of Declarative Logic Programs}, year = {1998}, booktitle = {ACM Computing Surveys 1998, Symposium on Partial Evaluation}, keywords = {tactical theorem prover, partial dediction, partial evaluation,}, url = {http://www.ai.univ-paris8.fr/~cazenave/sope.pdf}, } @InProceedings{cazenave1998b, author = {Cazenave, Tristan}, title = {Metaprogramming Forced Moves}, year = {1998}, booktitle = {ECAI-98}, keywords = {forced moves, metaprogramming}, url = {http://www.ai.univ-paris8.fr/~cazenave/ecai98.pdf}, } @InProceedings{cazenave1998c, author = {Cazenave, Tristan}, title = {Speedup Mechanisms For Large Learning Systems}, year = {1998}, booktitle = {IPMU 98, Paris}, keywords = {knowledge representation, generality, efficiency, speedup rules}, url = {http://www.ai.univ-paris8.fr/~cazenave/ipmu98.pdf}, } @InProceedings{cazenave1998d, author = {Cazenave, Tristan}, title = {Integration of Different Reasoning Modes in a {G}o Playing and Learning System}, year = {1998}, booktitle = {AAAI Spring Symposium on Multimodal Reasoning}, address = {Stanford}, keywords = {rule-based reasoning, case-based reasoning, constrained-based reasoning, tactics, strategy, planning}, url = {http://www.ai.univ-paris8.fr/~cazenave/multimodal98.pdf}, } @Misc{cazenave1998e, author = {Cazenave, Tristan}, title = {Strategic Evaluation in Complex Domains}, year = {1998}, howpublished = {FLAIRS 98}, address = {Sanibel}, keywords = {evaluation}, url = {http://www.ai.univ-paris8.fr/~cazenave/Flairs98.pdf}, } @Misc{cazenave1998f, author = {Cazenave, Tristan}, title = {Machine Self-Consciousness More Efficient Than Human Self-Consciousness}, year = {1998}, howpublished = {European Meeting on Cybernetics and Systems Research}, address = {Vienna}, keywords = {consciousness, introspection, cognitive science}, url = {http://www.ai.univ-paris8.fr/~cazenave/emcsr98.pdf}, } @InProceedings{cazenave1999, author = {Cazenave, Tristan}, title = {Generation of Patterns With External Conditions for the Game of {G}o}, year = {1999}, booktitle = {Advances in Computer Games Conference}, address = {Paderborn}, keywords = {pattern databases, external conditions}, url = {http://www.ai.univ-paris8.fr/~cazenave/acg9-final.pdf}, } @Misc{cazenave2000, author = {Cazenave, Tristan}, title = {Generating Search Knowledge in a Class of Games}, year = {1999}, note = {Submitted paper}, keywords = {Introspect, search knowledge, meta-knowledge}, url = {http://www.ai.univ-paris8.fr/~cazenave/cazenave_heuristic.ps.gz}, } @Misc{cazenave2000b, author = {Cazenave, Tristan}, title = {Abstract Proof Search}, year = {2000}, note = {Submitted paper}, keywords = {Computer Go, Search, Theorem Proving, Capture Game}, url = {http://www.ai.univ-paris8.fr/~cazenave/APS-final.pdf}, } @Misc{cazenave2001, author = {Cazenave, Tristan}, title = {A Problem Library for Computer {G}o}, year = {2001}, howpublished = {IJCAI-01 Workshop on Empirical AI}, keywords = {problem collections, evaluation of programs}, url = {http://www.ai.univ-paris8.fr/~cazenave/GoTest-IJCAI01.pdf}, } @InProceedings{cazenave2001b, author = {Cazenave, Tristan}, title = {Theorem Proving in the Game of {G}o}, year = {2001}, booktitle = {First International Conference on the Scientific Study of {G}o}, address = {Seoul}, keywords = {theorem proving}, url = {http://www.ai.univ-paris8.fr/~cazenave/TheoremProvingInGo.pdf}, } @InProceedings{cazenave2001c, author = {Cazenave, Tristan}, title = {Iterative Widening}, year = {2001}, booktitle = {IJCAI-01}, keywords = {abstract proof search}, url = {http://www.ai.univ-paris8.fr/~cazenave/iw00.pdf}, } @Misc{cazenave2002, author = {Cazenave, Tristan}, title = {La Recherche Abstraite Graduelle de Preuve}, year = {2002}, howpublished = {RFIA-02}, address = {Angers}, note = {In French.}, keywords = {AtariGo, Capture Go, AND/OR tree search, problem solving, Hex, Gomoku}, url = {http://www.ai.univ-paris8.fr/~cazenave/AGPS-RFIA.pdf}, } @Article{cazenave2002b, author = {Cazenave, Tristan}, title = {Gradual Abstract Proof Search}, journal = {ICGA}, year = {2001}, volume = {25}, number = {1}, pages = {3-15}, url = {http://www.ai.univ-paris8.fr/~cazenave/gaps.pdf}, keywords = {Gradual Abstract Proof Search, GAPS, Atari-Go, Phutball}, abstract = { Gradual Abstract Proof Search (GAPS) is a new 2-player search technique. It has been used to prove that 11x11 Phutball is a win for the first player in 25 plies or less, that 6x6 Atari-Go with a crosscut in the center is a win for the first player in 15 plies or less. I give domain dependent optimizations for the two games. I also describe theoretical and experimental comparisons with other related algorithms. } } @InProceedings{cazenave2002c, author = {Cazenave, Tristan}, title = {A Generalized Threats Search Algorithm}, booktitle = {Computers and Games 2002, Edmonton, Canada}, year = {2002}, url = {http://www.ai.univ-paris8.fr/~cazenave/gta.pdf}, keywords = {Generalized Threats Search, GTS, Atari-Go} } @InProceedings{cazenave2002d, author = {Cazenave, Tristan}, title = {Admissible Moves in Two-Player Games}, booktitle = {SARA 2002, LNCS 2371}, pages = {52-63}, year = {2002}, url = {http://www.ai.univ-paris8.fr/~cazenave/admissibleSARA2002.pdf}, keywords = {admissible heuristics, Gradual Abstract Proof Search, AtariGo}, abstract = { Some games have abstract properties that can be used to design admissible heuristics on moves. These admissible heuristics are useful to speed up search. They work well with depth-bounded search algorithms such as Gradual Abstract Proof Search that select moves based on the distance to the goal. We analyze the benefits of these admissible heuristics on moves for rules generation and search. We give experimental results that support our claim for the game of AtariGo. } } @InProceedings{cazenave2002e, author = {Cazenave, Tristan}, title = {Comparative evaluation of strategies based on the values of direct threats}, booktitle = {Board Games in Academia V, Barcelona}, year = {2002}, url = {http://www.ai.univ-paris8.fr/~cazenave/ts.pdf}, keywords = {Threats, BMove, MaxMove, SenteQ, Thermostrat, HotStrat} } @InProceedings{cazenave2002f, author = {Cazenave, Tristan}, title = {Metarules to Improve Tactical {G}o Knowledge}, booktitle = {Joint Conference on Information Sciences, Durham, NC}, year = {2002}, url = {http://www.ai.univ-paris8.fr/~cazenave/jcis2002.pdf}, keywords = {automatically generated rules databases, exceptions, metarules}, abstract = { Three main problems arise with automatically generated rules databases. They are too large to fit in memory, they can take a lot of time to generate, and it takes time to match many rules on a board. I propose to use exceptions and metarules to reduce the size of the databases. The reduction in size enables larger rules to be used, at the cost of small overheads in generation and matching times. However, the reduction in search depth provided by the new larger rules decreases much the overall search time, stopping search at smaller depths. } } @Article{cazenave2003, author = {Cazenave, Tristan}, title = {Metarules to Improve Tactical {G}o Knowledge}, journal = {Information Sciences}, year = {2003}, volume = {154}, number = {3-4}, pages = {173-188}, month = {September}, keywords = {Retrograde analysis, Metaknowledge, Pattern databases, Search}, abstract = { Three main problems arise with automatically generated rules databases. They can be too large to t in memory, they can take a lot of time to generate, and it can take time to match many generated rules on a board. I propose to use exceptions and metarules to reduce the size of the databases. The reduction in size enables larger rules to be used, at the cost of small overheads in generation and matching times. However, the reduction in search depth provided by the new larger rules decreases the overall search time of a tsumego problem solver. } } @Misc{cazenave2003b, author = {Cazenave, Tristan}, title = {Recherche s\'elective et g\'en\'eration automatique de programmes}, howpublished = {Habilitation thesis. Universit\'e Paris}, year = {2003}, note = {In French}, url = {http://www.ai.univ-paris8.fr/~cazenave/habil.ps} } @Article{cazenave2004, author = {Cazenave, Tristan and Helmstetter, Bernard}, title = {Search for transitive connections}, journal = {Information Sciences}, year = {2005}, url = {http://www.ai.univ-paris8.fr/~cazenave/transitive-IS-final.pdf}, keywords = {Transitivity, connections, generalized threats} } @InProceedings{cazenave2004b, author = {Cazenave, Tristan}, title = {Generalized Widening}, booktitle = {ECAI 2004}, year = {2004}, url = {http://www.ai.univ-paris8.fr/~cazenave/openld.pdf}, keywords = {Threat based search, Iterative Widening}, abstract = { We present a new threat based search algorithm that outperforms other threat based search algorithms and selective knowledge-based alpha-beta for open life and death problem solving in the game of Go. It generalizes the Iterative Widening algorithm which consists in iteratively increasing the threat searched at the root. The main idea of Generalized Widening is to perform Iterative Widening at all max nodes of the search tree instead of performing it only at the root. Experimental results show it can be three times faster than selective knowledge-based alpha-beta using the same knowledge, and eight times faster than simple Iterative Widening. The performance against alpha-beta can possibly be greatly enhanced by adding more knowledge in the selection of moves during the verification of the threats. } } @InProceedings{cazenave2004c, author = {Bernard Helmstetter and Tristan Cazenave}, title = {Incremental Transpositions}, booktitle = {Computers and Games Conference 2004, Ramat-Gan, Israel}, year = {2004}, url = {http://www.ai.univ-paris8.fr/~cazenave/it.pdf}, keywords = {permutation of moves} } @InProceedings{cazenave2005, author = {Tristan Cazenave}, title = {The separation game}, booktitle = {JCIS 2005}, year = {2005}, url = {http://www.ai.univ-paris8.fr/~cazenave/separation.pdf}, abstract = { The separation game is different from the connection game, but has some similarities with it. In the game of Go, it is often useful because it helps enclosing groups and areas. An evaluation function, moves generation functions and a search algorithm for the separation game are described in this paper. } } @InProceedings{cazenave2005b, author = {Tristan Cazenave and Bernard Helmstetter}, title = {Combining tactical search and {M}onte-{C}arlo in the game of {G}o}, booktitle = {IEEE CIG 2005}, year = {2005}, url = {http://www.ai.univ-paris8.fr/~cazenave/searchmcgo.pdf}, keywords = {Monte-Carlo, tactical goals}, abstract = { We present a way to integrate search and Monte-Carlo methods in the game of Go. Our program uses search to find the status of tactical goals, builds groups, selects interesting goals, and computes statistics on the realization of tactical goals during the random games. The mean score of the random games where a selected tactical goal has been reached and the mean score of the random games where it has failed are computed. They are used to evaluate the selected goals. Experimental results attest that combining search and Monte-Carlo significantly improves the playing level. } } @InProceedings{cazenave2005c, author = {Tristan Cazenave}, title = {A {P}hantom {G}o program}, booktitle = {Advances in Computer Games 11}, year = {2005}, url = {http://www.ai.univ-paris8.fr/~cazenave/phantomgo.pdf}, keywords = {Phantom Go, Monte-Carlo}, abstract = { Phantom Go is often played at Go congress and provides enjoyable games both for the players and the surrounding public. Phantom Go is a game with hidden information. Monte-Carlo methods work well in Go and in games of incomplete information, and as Phantom Go is Go with incomplete information, Monte-Carlo methods are expected to work well in Phantom Go. This paper demonstrates that it is the case and shows the results of a Monte-Carlo based program that plays Phantom Go. In the second section, we present the game of Phantom Go. In the third section, we recall previous work on Monte-Carlo Go. In the fourth section, we detail how Monte-Carlo is adapted to Phantom Go. In the fifth section, we give experimental results. The last section outlines future work and concludes. } } @InProceedings{cazenave2007, author = {Tristan Cazenave and Nicolas Jouandeau}, title = {On the Parallelization of {UCT}}, booktitle = {CGW 2007}, pages = {93-101}, year = {2007}, month = {June}, url = {http://www.ai.univ-paris8.fr/~cazenave/parallelUCT.pdf}, keywords = {UCT, parallelization}, abstract = { We present three parallel algorithms for UCT. For 9�~W9 Go, they all improve the results of the programs that use them against GNU GO 3.6. The simplest one, the single-run algorithm, uses very few communications and shows improvements comparable to the more complex ones. Further improvements may be possible sharing more information in the multiple-runs algorithm. } } @Booklet{cgj, title = {Computer {G}o}, howpublished = {Published in cooperation with the American Go Association and the Canadian Go Association}, url = {http://www.daogo.org/} } @Proceedings{cg1998, title = {Computers and Games, First International Conference}, year = {1998}, editor = {Jaap, Herik and Iida, Hiroyuku}, volume = {1558}, series = {Lecture Notes in Computer Science}, address = {Tsukuba, Japan}, month = {November}, publisher = {Springer} } @Proceedings{cg2000, title = {Computers and Games, Second International Conference}, year = {2000}, month = {October}, editor = {Jaap, Herik and Iida, Hiroyuku}, volume = {2063}, series = {Lecture Notes in Computer Science}, address = {Hamamatsu, Japan}, publisher = {Springer} } @Proceedings{cgl1998, title = {Complex Games Lab Workshop}, editor = {Frank, Ian and Matsubara, Hitoshi and Tajima, Morihiko and Yoshikawa, Atsushi and Grimbergen, Reijer and M\"uller, Martin}, year = {1998}, month = {November}, day = {10}, organization = {Electrotechnical Laboratory, Machine Inference Group, Tsukuba, Japan}, url = {http://www.cs.ualberta.ca/~mmueller/cgo/cg98-workshop/cg98-workshop-papers.pdf} } @Misc{cgm, key = {Computer Go Mailing List}, title = {The {C}omputer-{G}o Mailing List}, year = {}, url = {http://computer-go.org/mailman/listinfo/computer-go }, } @MastersThesis{chan1996, author = {Chan, Horace Wai-kit}, title = {Application of Temporal Difference Learning and Supervised Learning in the Game of {G}o}, year = {1996}, school = {Chinese University of Hong Kong}, keywords = {neural networks, temporal difference learning}, url = {http://www.cs.cuhk.hk/~king/PUB/horace_thesis.ps.gz}, } @InProceedings{chan1996b, author = {Chan, Horace Wai-Kit and King, Irwin and Lui, John}, title = {Performance analysis of a new updating rule for TD(lambda) learning in feedforward networks for position evaluation in {G}o game.}, year = {1996}, booktitle = {IEEE International Conference on Neural Networks}, volume = {3}, pages = {1716-1720}, keywords = {neural networks, temporal difference learning}, url = {http://www.cse.cuhk.edu.hk/~king/PUB/icnn96-tdgo.pdf}, } @Misc{chaslot2007, author = {Chaslot G.M.J.B. and Winands M.H.M. Winands and Uiterwijk J.W.H.M. and van den Herik H.J. and Bouzy B}, title = {Progressive Strategies for {M}onte-{C}arlo Tree Search}, howpublished = {Draft, submitted to JCIS workshop 2007}, year = {2007}, url = {http://www.cs.unimaas.nl/g.chaslot/papers/pMCTS.pdf}, keywords = {Monte Carlo, tree search, progressive bias, progressive unpruning, MANGO}, } @InBook{chen1991, author = {Chen, Ken}, title = {Attack and Defense}, year = {1991}, booktitle = {Heuristic Programming in Artificial Intelligence}, publisher = {Ellis Horwood Limited}, volume = {3}, pages = {146-156}, keywords = {Go Intellect, tacticts, attack, defense}, } @InBook{chen1992, author = {Chen, Ken}, title = {Pattern Knowledge Prevailed}, year = {1992}, booktitle = {Heuristic Programming in Artificial Intelligence}, publisher = {Ellis Horwood Limited}, volume = {3}, pages = {42-46}, keywords = {3rd Computer Olympiad Go results}, } @Article{chen1999, author = {Ken Chen, Zhixing Chen}, title = {Static analysis of life and death in the game of {G}o}, journal = {Information Sciences}, year = {1999}, volume = {121}, pages = {113-134}, keywords = {Heuristic programming, Approximation algorithms, Machine game playing, Combinatorial game theory}, abstract = { This paper describes heuristic rules for static life/death analysis for general classes of groups in the game of Go, as implemented in authors' world championship computer Go programs Go Intellect and HandTalk. We shall show that for many life and death problems in Go, the effect of a tree search can be approximated by a static analysis on the group's interior and surroundings. We investigate eye-spaces with or without opponent's dead stones and try to provide a foundation towards conquering the combinatorial explosion of Go game tree. } } @Article{chen2000, author = {Chen, Ken}, title = {Some Practical Techniques for Global Search in {G}o}, journal = {ICGA Journal}, volume = {23}, number = {2}, pages = {67-74}, month = {June}, year = {2000}, keywords = {candidate move generation, target value technique, urgency value, global selective search}, abstract = { A position evaluation and a candidate-move-generation strategy for global selective search in Go are described. Moreover, some Go-specific enhancements to the basic global selective alpha-beta game-tree search procedure are discussed. Finally, empirical results on the performance of the enhancements are presented. } } @Article{chen2001, author = {Chen, Keh-Hsun}, title = {Computer {G}o: Knowledge, Search, and Move Decision}, journal = {ICGA}, year = {2001}, volume = {24}, number = {4}, pages = {203-215}, url = {http://www.coit.uncc.edu/drchen/Papers/ComputerGo.pdf}, abstract = { This paper intends to provide an analytical overview of the research performed in the domain of computer Go. Domain knowledge that is essential to Go-playing programs is identified. Various computation and search techniques that can be used effectively to obtain helpful domain knowledge are presented. Four different move-decision paradigms applied by today's leading Go programs are discussed. Conclusions are drawn and two proposals of improvements to current move-decision paradigms are presented. } } @Article{chen2001b, author = {Chen, Keh-Hsun}, title = {A study of decision error in selective game tree search}, journal = {Information Sciences}, year = {2001}, volume = {135}, pages = {177-186}, url = {http://www.coit.uncc.edu/drchen/Papers/DecisionError.pdf}, keywords = {selective game tree search, heuristic evaluation, mini-max backup, decision error}, abstract = { In this paper, we study decision errors caused by the omission of part of the legal candidate moves and the inaccuracy of static evaluation in a selective minimax game tree search. Error upper bounds are presented in Section 2. A simple game tree model, which captures some basic characteristics of the Go game tree, is introduced in Section 3 for a decision error simulation study. Section 4 presents the result of this simulation study, which shows that a global selective search can be effective for game trees similar to this model. The result also reveals the existence of pathology in selective minimax game tree search. } } @Article{chen2003, author = {Chen, Ken}, title = {GNUGo Wins 19x19 {G}o Tournament}, journal = {ICGA Journal}, year = {2003}, volume = {26}, number = {4}, keywords = {8th Computer Olympiad, Graz} } @Article{chen2003b, author = {Chen, Keh-Hsun}, title = {Soft decomposition search and binary game forest model for move decision in {G}o}, journal = {Information Sciences}, year = {2003}, volume = {154}, pages = {157-172}, keywords = {Combinatorial game theory, Soft decomposition search, Binary game forest, Temperature, Mean, Move-decision strategy}, url = {http://www.coit.uncc.edu/drchen/Papers/SoftDecomposition.pdf}, abstract = { In this paper, a new approach to game tree search in Go, called soft decomposition search, is proposed. A simplified approximation model, binary game forest, for move selection in Go is presented. A new paradigm for move decision in computer Go based on soft decomposition search and binary game forest is introduced. } } @Article{chen2004, author = {Chen, Keh-Hsun}, title = {Maximizing the chance of winning in searching {G}o game trees}, journal = {Information Sciences}, year = {2004}, note = {Accepted for print}, abstract = { The current global selective search and decomposition search in Go typically back up territory scores. This approach is inherently flawed. We propose a new strategy of backing up ``chance of winning''. We show how an evaluation function on the chance of winning can be constructed. Also we develop a probabilistic combinatorial game model and an algorithm for decomposition search to work with probabilistic outcomes in maximizing the chance of winning. } } @InProceedings{chen2006, author = {Keh-Hsun Chen and Peigang Zhang}, title = {A Heuristic Search Algorithm for Capturing Problems in {G}o}, booktitle = {Computers and Games, CG 2006}, year = {2006}, keywords = {search, capture problems}, abstract = { We propose a highly selective heuristic search algorithm for capturing problems in Go. This iterative deepening search works on the crucial chain that the prey block is in. It uses first three order liberties of the chain as the basis of position evaluation adjusted by the presence of few-liberty surrounding opponent blocks. It solved most capturing problems in Kano's four volumes of graded Go problems and it is fast enough to be used by Go programs in real time. } } @Article{chenx2002, author = {Chen, X. and Zhang, D. and Zhang, X. and Li, Z. and Meng, X. and He, S. and Hu, X.}, title = {A functional {MRI} study of high-level cognition II: The game of {GO}}, journal = {Cognitive Brain Research}, year = {2002}, url = {http://sheng-lab.psych.umn.edu/pdf_files/Chen_fMRI_GO.pdf}, keywords = {Neural basis; Functional MRI; High-level cognition}, abstract = { GO is a board game thought to be different from chess in many aspects, most significantly in that GO emphasizes global strategy more than local battle, a property very difficult for computer programs to emulate. To investigate the neural basis of GO, functional magnetic resonance imaging (fMRI) was used to measure brain activities of subjects engaged in playing GO. Enhanced activations were observed in many cortical areas, such as dorsal prefrontal, parietal, occipital, posterior temporal, and primary somatosensory and motor areas. Quantitative analysis indicated a modest degree of stronger activation in right parietal area than in left. This type of right hemisphere lateralization differs from the modest left hemisphere lateralization observed during chess playing. } } @Misc{chenz1999, author = {Chen, Zhixing}, title = {Programming Technics in {H}andtalk}, year = {1999}, note = {Available by Internet}, keywords = {Handtalk}, } @Misc{chenz1999b, author = {Chen, Zhixing}, title = {Programming Technics in {W}ulu}, year = {1999}, note = {Available by Internet}, keywords = {Wulu}, } @Misc{chenz1999c, author = {Chen, Zhixing}, title = {Programming Technics in {G}oemate}, year = {1999}, note = {Available by Internet}, keywords = {Goemate}, } @Article{chenz2002, author = {Chen, Zhixing}, title = {Semi-Empirical Quantitative Theory of {G}o: Part {I}: Estimation of the Influence of a Wall}, journal = {ICGJ}, year = {2002}, volume = {25}, number = {4}, pages = {211-218} } @InProceedings{churchill2001, author = {Churchill, Julian and Cant, Richard and Al-Dabass, David}, title = {A New Computational Approach to the Game of {G}o}, year = {2001}, booktitle = {Game-On 2001 conference}, keywords = {Computer Go, Neural Networks, Alpha beta search algorithms}, url = {http://ducati.doc.ntu.ac.uk/uksim/dad/webpagepapers/Game-14.pdf}, } @Misc{cook2003, author = {Cook, Heather and Venghaus, Amanda and Drake, Peter}, title = {Machine Learning Applied to the Game of {G}o}, howpublished = {Twelfth Regional Conference on Undergraduate Research, Murdock College Research Program. Conference poster}, year = {2003}, keywords = {neural networks, machine learning, self play}, url = {http://www.lclark.edu/~sciences/GOposter.pdf}, } @Misc{coulom2006, author = {R\'emi Coulom}, title = {Efficient Selectivity and Backup Operators in {M}onte-{C}arlo Tree Search}, howpublished = {Submitted to CG 2006}, year = {2006}, url = {http://remi.coulom.free.fr/CG2006/CG2006.pdf}, keywords = {Monte-Carlo, min-max, Crazy Stone}, abstract = { Monte-Carlo evaluation consists in estimating a position by averaging the outcome of several random continuations, and can serve as an evaluation function at the leaves of a min-max tree. This paper presents a new framework to combine tree search with Monte-Carlo evaluation, that does not separate between a min-max phase and a Monte-Carlo phase. Instead of backing-up the min-max value close to the root, and the average value at some depth, a more general back-up operator is defined that progressively changes from averaging to min-max as the number of simulations grows. This approach provides a fine-grained control of the tree growth, at the level of individual simulations, and allows efficient selectivity methods. This algorithm was implemented in a 9x9 go-playing program, Crazy Stone, that won the 10th KGS computer-go tournament. } } @Misc{coulom2007, author = {R\'emi Coulom}, title = {Computing {E}lo Ratings of Move Patterns in the Game of {G}o}, howpublished = {Draft, submitted to ICGA Computer Games Workshop 2007}, year = {2007}, url = {http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf}, keywords = {Monte-Carlo, patterns, probability distribution, Bradley-Terry model, ELO, Crazy Stone}, abstract = { Move patterns are an essential method to incorporate domain knowledge into Go-playing programs. This paper presents a new Bayesian technique for supervised learning of such patterns from game records, based on a generalization of Elo ratings. Each sample move in the training data is considered as a victory of a team of pattern features. Elo ratings of individual pattern features are computed from these victories, and can be used in previously unseen positions to compute a probability distribution over legal moves. In this approach, several pattern features may be combined, without an exponential cost in the number of features. Despite a very small number of training games (652), this algorithm outperforms most previous pattern-learning algorithms, both in terms of mean log-evidence (-2.69), and prediction rate (34.9\%). A 19x19 Monte-Carlo program improved with these patterns reached the level of the strongest classical programs. } } @InProceedings{crasmaru1998, author = {Crasmaru, Marcel}, title = {On the Complexity of {T}sume-{G}o}, crossref = {cg1998}, pages = {222-231}, keywords = {Tsume-Go, NP-complete}, abstract = { In this paper, we explain why Go is hard to be programmed. Since the strategy of the game is closely related to the concept of alive-dead group, it is plainly necessary to analyze this concept. For this a mathematical model is proposed. Then we turn our research to Tsume-Go problems in which one of the players has always a unique good move and the other has always only two good moves available to choose from. We show that this kind of problems are NP-complete. } } @InProceedings{crasmaru2000, author = {Crasmaru, Marcel and Tromp, John}, title = {Ladders are {PSPACE}-Complete}, crossref = {cg2000}, pages = {241-249}, keywords = {Complexity of Go, Ladders, PSPACE-complete}, url = {http://www2.is.titech.ac.jp/research/research-report/C/C-142.ps.gz}, abstract = { In the game of Go,the question of whether a ladder - a method of capturing stones - works,is shown to be PSPACE-complete. Our reduction closely follows that of Lichtenstein and Sipser, who first showed PSPACE-hardness of Go by letting the outcome of a game depend on the capture of a large group of stones. A greater simplicity is achieved by avoiding the need for pipes and crossovers. } } @InProceedings{dahl1999, author = {Dahl, Fredrik A.}, title = {Honte, a {G}o-Playing Program Using Neural Nets}, year = {}, crossref = {fuernkranz1999}, keywords = {go, neural network, Honte}, url = {http://www.ai.univie.ac.at/icml-99-ws-games/papers/dahl.ps.gz}, } @InBook{davis2000, author = {Davis, Darryl and Berbank-Green, Barnaby}, title = {Towards an Architecture for A-life Agents II}, year = {2000}, booktitle = {New Frontiers In Computational Intelligence}, publisher = {IOS Press}, url = {http://www2.dcs.hull.ac.uk/NEAT/dnd/papers/nfici.pdf}, } @InProceedings{demaine2001, author = {Erik D. Demaine}, title = {Playing Games with Algorithms: Algorithmic Combinatorial Game Theory}, booktitle = {26th Symposium on Mathematical Foundations in Computer Science (MFCS 2001)}, pages = {18-32}, year = {2001}, volume = {2136}, series = {Lecture Notes in Computer Science}, url = {http://theory.lcs.mit.edu/~edemaine/papers/AlgGameTheoryMFCS2001/}, abstract = { Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to encourage further research. In particular, we begin with general background in combinatorial game theory, which analyzes ideal play in perfect-information games. Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results. Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer. } } @Misc{donnelly1994, author = {Donnelly, Paul and Corr, Patrick and Crookes, Danny}, title = {Evolving {G}o Playing Strategy in Neural Networks}, year = {1994}, organization = {Department of Computer Science, The Queen's University of Belfast}, keywords = {neural networks}, url = {ftp://ftp-igs.joyjoy.net/Go/computer/egpsnn.ps.Z}, } @InProceedings{doshay2005, author = {David G Doshay and Charlie McDowell}, title = {SlugGo: A Computer Baduk Program}, booktitle = {Third International Conference on Baduk}, year = {2005}, month = {October}, organization = {Myong-Ji University, Korea}, keywords = {SlugGo, GNU Go}, url = {http://sluggo.dforge.cse.ucsc.edu/icob.pdf} } @Misc{drake2004, author = {Drake, P. and Levenick, J. and Veenstra, L. and Venghaus, A.}, title = {Pattern matching in the Game of {G}o}, howpublished = {Submitted}, year = {2004}, url = {https://webdisk.lclark.edu/xythoswfs/webui/_xy-13652_1-tid_F5nG4R87}, abstract = { Human Go players look for certain local patterns on the board. Many Go programs contain large databases of such patterns. It is a challenge to efficiently search the board for thousands of patterns. This article presents a simple but efficient scheme by which each pattern is stored in canonical form. This eliminates redundancy due to reflection and rotation when automatically extracting patterns from recorded games. Experimental results provide insight into setting parameters for automatic pattern extraction. } } @InProceedings{drake2006, author = {Drake, Peter and Schreiner, Niku and Tomlin, Brett and Veenstra, Loring}, title = {An Efficient Algorithm for Eyespace Classification in {G}o}, booktitle = {International Conference on Artificial Intelligence}, year = {2006}, publisher = {CREA Press}, keywords = {graph theory, eyes}, url = {http://www.lclark.edu/~drake/go/icai2006-final-drake.pdf}, abstract = { Writing programs to play the classical Asian game of Go is considered one of the grand challenges of artificial intelligence. One of the key tactical issues in Go is whether a group of pieces can divide the area it surrounds ("eyespace") into two separate regions, thus rendering the group immune to capture. Human players quickly learn to recognize various eyespace patterns, invariant under translation, rotation, reflection, and distortion. In this paper, we present an efficient canonical form for classifying such patterns. This representation, along with an algorithm for finding the inside of a group, is used to quickly analyze the life and death (capturability) status of all groups on the board. } } @Misc{drake2007, author = {Drake, Peter and Pouliot, Andrew and Schreiner, Niku and Vanberg, Bjorn}, title = {The Proximity Heuristic and an Opening Book in {M}onte {C}arlo {G}o}, howpublished = {Submitted}, year = {2007}, url = {https://webdisk.lclark.edu/xythoswfs/webui/_xy-2352013_1-t_Gct7yJ5s%22}, keywords = {Monte Carlo, UCT, Orego}, abstract = { Writing programs to play the classical Asian game of Go is widely considered to be a grand challenge of artificial intelligence. Several researchers have recently begun exploring statistical sampling techniques called Monte Carlo Go. This paper describes one such program, Orego. It presents a method for generating random moves efficiently and without bias. The proximity heuristic, emphasizing moves near the last move played, is introduced and discussed. This paper describes how heuristics may be efficiently incorporated into Monte Carlo Go programs. A method is described for using recorded games to overcome the nonsensical opening play typical of Monte Carlo Go programs. Experimental results demonstrate that the proximity heuristic significantly strengthens Orego in play against a more traditional Go program, GNU Go. } } @InProceedings{drake2007b, author = {Peter Drake and Steve Uurtamo}, title = {Heuristics in {M}onte {C}arlo {G}o}, booktitle = {Proceedings of the 2007 International Conference on Artificial Intelligence}, year = {2007}, publisher = {CSREA Press}, url = {https://webdisk.lclark.edu/xythoswfs/webui/_xy-2793610_1-t_RYPP7Zcz}, keywords = {Monte Carlo, UCT, heuristics}, abstract = { Writing programs to play the classical Asian game of Go is considered one of the grand challenges of artificial intelligence. Traditional game tree search methods have failed to conquer Go because the search space is so vast and because static evaluation of board positions is extremely difficult. There has been considerable progress recently in using Monte Carlo sampling to select moves. This paper presents four heuristics used to bias the selection of moves during Monte Carlo sampling: the proximity heuristic (play near the last move), the avoid-the-first-two-lines heuristic (don't play at the edge of the board), the first-order history heuristic (play the move that has fared best elsewhere in the tree), and the second-order history heuristic (play the move that has fared best elsewhere in the tree in response to a particular move from the opponent). Experimental results show that the use of these heuristics significantly improves the ability of our program to defeat GNU Go, a widely-used Go program based on traditional, knowledge-intensive techniques. } } @InProceedings{drake2007c, author = {Peter Drake and Steve Uurtamo}, title = {Move Ordering vs Heavy Playouts: Where Should Heuristics Be Applied in {M}onte {C}arlo {G}o?}, booktitle = {Proceedings of the 3rd North American Game-On Conference}, year = {2007}, url = {https://webdisk.lclark.edu/drake/publications/GAMEON-07-drake.pdf}, keywords = {Monte Carlo, UCT, heuristics}, abstract = { Writing programs to play the classical Asian game of Go is considered one of the grand challenges of artificial intelligence. Techniques used in a strong Go program would likely be applicable to other games and to non-game domains. Traditional game tree search methods have failed to conquer Go because the search space is so vast and because static evaluation of board positions is extremely difficult. There has been considerable progress recently in using Monte Carlo sampling to evaluate moves. Such programs can be strengthened further by adding domain-specific heuristics. This paper addresses the question of where such heuristics are most effectively applied: to modify the order in which moves are considered or to bias the sampling used to evaluate those moves. Experimental results are presented for three heuristics. We conclude that the sampling "playouts" are the most effective place to apply heuristics. } } } @InBook{durham1985, author = {Durham, Tony}, title = {A program with a touch of Zen}, year = {1985}, booktitle = {Durham, Tony: Computing Horizons}, publisher = {Addison-Wesley}, keywords = {Allan Scarff, Microgo, cellular automaton, Zen}, } @InProceedings{dyer1995, author = {Dyer, Dave}, title = {Searches, tree pruning and tree ordering in {G}o}, year = {1995}, booktitle = {2nd Game Programming Workshop in Japan}, address = {Kanagawa}, keywords = {search, pruning, alpha-beta, heuristic, ordering}, url = {http://www.andromeda.com/people/ddyer/go/search.html}, } @Misc{dyer1995b, author = {Dyer, Dave}, title = {An Eye Shape library for Computer {G}o}, year = {1995}, note = {draft, available from the author's homepage}, keywords = {eye shapes, database}, url = {http://www.andromeda.com/people/ddyer/go/shape-library.html}, } @Misc{dyer1995c, author = {Dyer, Dave}, title = {Scoring Completed Games}, year = {1995}, note = {Draft, avaliable from the author's homepage}, keywords = {scoring}, url = {http://www.andromeda.com/people/ddyer/go/scoring-games.html}, } @Misc{dyer1995d, author = {Dyer, Dave}, title = {Global Evaluation Strategies in {G}o}, year = {1995}, note = {Draft, avaliable from the author's homepage}, keywords = {global evaluation}, url = {http://www.andromeda.com/people/ddyer/go/global-eval.html}, } @Misc{dyer1995e, author = {Dyer, Dave}, title = {Signatures for {G}o game records}, year = {1995}, note = {Draft, avaliable from the author's homepage}, url = {http://www.andromeda.com/people/ddyer/go/signature-spec.html}, } @Misc{dyer1995f, author = {Dyer, Dave}, title = {Building a joseki dictionary from professional games}, year = {1995}, note = {Draft, avaliable from the author's homepage}, keywords = {joseki library}, url = {http://www.andromeda.com/people/ddyer/go/joseki-dictionary.html}, } @Article{eisenberg1997, author = {Eisenberg, Bart}, title = {Kasparov, Deep Blue, and the Games Machines Play}, year = {1997}, journal = {Pacific Connection}, volume = {8}, url = {http://www.gihyo.co.jp/SD/pacific/SD_9708.html}, } @MastersThesis{ekker2003, author = {Ekker, Reindert-Jan}, title = {Reinforcement Learning and Games}, school = {Rijksuniversiteit Groningen}, year = {2003}, keywords = {neural networks, reinforcement learning, 5x5 Go, temporal difference learning}, url = {http://members.home.nl/r.j.ekker/afstudeer/tekst.pdf} } @InProceedings{ekker2004, author = {R. Ekker and E.C.D. van der Werf and L.R.B. Schomaker}, title = {Dedicated {TD}-learning for Stronger Gameplay: applications to {G}o}, booktitle = {Proceedings of Benelearn 2004 Annual Machine Learning Conference of Belgium and The Netherlands}, pages = {46-52}, year = {2004}, editor = {A. Nowe and T. Lennaerts and K. Steenhaut}, keywords = {Temporal-difference learning, TD(mu), TD-leaf, TD-directed, residual algorithms}, url = {http://members.home.nl/r.j.ekker/afstudeer/paper_benelearn04.pdf} } @TechReport{enderton1991, author = {Enderton, Herbert}, title = {The {G}olem {G}o Program}, year = {1991}, institution = {School of Computer Science, Carnegie-Mellon University}, number = {CMU-CS-92-101}, keywords = {go, Golem, neural networks, relaxation}, url = {ftp://ftp-igs.joyjoy.net/Go/computer/golem.sh.Z}, } @Misc{enzenberger1996, author = {Enzenberger, Markus}, title = {The Integration of A Priori Knowledge into a {G}o Playing Neural Network}, year = {1996}, note = {Available by Internet}, keywords = {go, neural network, NeuroGo, learning}, url = {http://www.cs.ualberta.ca/~emarkus/neurogo/neurogo.ps.gz}, } @InProceedings{enzenberger2003, author = {Enzenberger, Markus}, title = {Evaluation in {G}o by a Neural Network Using Soft Segmentation}, booktitle = {10th Advances in Computer Games conference}, pages = {97-108}, year = {2003}, keywords = {neural networks, segmentation, connectivity, NeuroGo}, url = {http://www.cs.ualberta.ca/~emarkus/neurogo/neurogo3.pdf}, abstract = { In this article a neural network architecture is presented that is able to build a soft segmentation of a two-dimensional input. This network architecture is applied to position evaluation in the game of Go. It is trained using self-play and temporal difference learning combined with a rich two-dimensional reinforcement signal. Two experiments are performed, one using the raw board position as input, the other one doing some simple preprocessing of the board. The second network is able to achieve playing strength comparable to a 13-kyu Go program. } } @TechReport{eppstein1996, author = {Eppstein, David}, title = {Dynamic Connectivity in Digital Images}, year = {1996}, institution = {ICS, UCI}, number = {TR 96-13}, keywords = {dynamic planar connectivity, percolation, lower bounds, image processing, go, lines of action}, url = {http://www.ics.uci.edu/~eppstein/pubs/all.html}, } @Article{farr2002, author = {Farr, G.E.}, title = {The {G}o polynomials of a graph}, year = {2002}, journal = {Theoretical Computer Science}, } @Misc{fellows2005, author = {Christopher Fellows and Yuri Malitsky and Gregory Wojtaszczyk}, title = {Go{NN} -- Incorporating a Neural Network into the Game of {G}o}, howpublished = {AI Project, CS 473, Cornell University}, year = {2005}, url = {http://www.people.cornell.edu/pages/ynm2/Papers/Incorporating a Neural Net into the Game of Go - Final Report.pdf}, abstract = { While Backgammon, Checkers and even Chess playing programs are seen defeating human world champions, there has been very little progress made in the game of Go. In fact, the best commercially available programs play only slightly better than moderate amateurs. This is because, unlike the other games, Go has a much larger branching factor and no good evaluation function. This makes searching even a handful of moves ahead impossible. Thus, the majority of modern programs use finely tuned heuristics to try to take advantage of Go's dependence on making good local shapes. But judging from performance, something is definitely lacking. Thus, it is our goal to strengthen the publicly available GnuGo program by integrating machine learning into the game of Go. This framework has the potential of not only learning to play Go, but to also help classify which characteristics are most effective when evaluating a Go board position. } } @Misc{fellows2006, author = {Christopher Fellows and Yuri Malitsky and Gregory Wojtaszczyk}, title = {Exploring {G}nu{G}o's Evaluation Function with a {SVM}}, howpublished = {AAAI-06 student posters}, year = {2006}, url = {http://www.people.cornell.edu/pages/ynm2/Papers/AAAI06 - Exploring GnuGos Evaluation Function with a SVM.pdf}, keywords = {GNU Go, Support Vector Machine}, abstract = { While computers have defeated the best human players in many classic board games, progress in Go remains elusive. The large branching factor in the game makes traditional adversarial search intractable while the complex interaction of stones makes it difficult to assign a reliable evaluation function. This is why most existing programs rely on hand-tuned heuristics and pattern matching techniques. Yet none of these solutions perform better than an amateur player. Our work introduces a composite approach, aiming to integrate the strengths of the proved heuristic algorithms, the AI-based learning techniques, and the knowledge derived from expert games. Specifically, this paper presents an application of the Support Vector Machine (SVM) for training the GnuGo evaluation function. } } @Misc{fotland1992, author = {Fotland, David}, title = {{Many Faces of Go}}, year = {1992}, month = {Februar}, day = {20}, howpublished = {1st Cannes/Sophia-Antipolis Go Research Day}, keywords = {Many Faces of Go, Fotland biography}, } @Misc{fotland1993, author = {Fotland, David}, title = {Knowledge Representation in {The Many Faces of Go}}, year = {1993}, note = {Available by Internet}, keywords = {Many Faces of Go}, url = {ftp://ftp-igs.joyjoy.net/Go/computer/mfg.tex.Z}, } @Article{fotland2002, author = {Fotland, David}, title = {Static Eye Analysis in ``{T}he {M}any {F}aces of {G}o''}, journal = {ICGJ}, year = {2002}, volume = {25}, number = {4}, pages = {203-210} } @Article{fotland2004, author = {Fotland, David}, title = {{G}o {I}ntellect wins 19x19 {G}o tournament}, journal = {ICGJ}, year = {2004}, volume = {27}, number = {3}, pages = {169-170}, keywords = {9th Computer Olympiad} } @Misc{fraser2000, author = {Fraser, William Edward}, title = {Thermographic Analysis of {G}o Endgames Using Brute Force}, howpublished = {Combinatorial Game Theory Workshop}, month = {July}, year = {2000}, address = {Mathematical Sciences Research Institute, Berkeley}, keywords = {Thermographs}, url = {http://www.msri.org/publications/ln/msri/2000/gametheory/fraser/1/banner/01.html} } @Proceedings{fuernkranz1999, editor = {F\"urnkranz, Johannes and Kubat, Miroslav}, title = {Workshop Notes: Machine Learning in Game Playing}, year = {1999}, organization = {16th International Conference on Machine Learning (ICML-99), Bled, Slovenia}, keywords = {go, machine learning}, url = {http://www.ai.univie.ac.at/icml-99-ws-games}, } @InBook{fuernkranz2000, author = {F\"urnkranz, Johannes}, title = {Machine learning in games: A survey}, year = {2001}, booktitle = {J. F\"urnkranz and M. Kubat, editors, Machines that Learn to Play Games}, publisher = {Nova Science Publishers, Huntington, NY}, note = {To appear.}, keywords = {Machine Learning, Game Playing}, url = {http://www.ai.univie.ac.at/cgi-bin/tr-online?number+2000-31}, } @TechReport{gelly2006, author = {Sylvain Gelly and Yizao Wang and R\'emi Munos and Olivier Teytaud}, title = {Modification of {UCT} with Patterns in {M}onte-{C}arlo {G}o}, institution = {INRIA, France}, year = {2006}, number = {6062}, month = {November}, keywords = {UCT, UCB1, Monte-Carlo, MoGo}, url = {http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf}, abstract = { Algorithm UCB1 for multi-armed bandit problem has already been extended to Algorithm UCT (Upper bound Confidence for Tree) which works for minimax tree search. We have developed a Monte-Carlo Go program, MoGo, which is the first computer Go program using UCT. We explain our modification of UCT for Go application and also the intelligent random simulation with patterns which has improved significantly the performance of MoGo. UCT combined with pruning techniques for large Go board is discussed, as well as parallelization of UCT. MoGo is now a top level Go program on 9x9 and 13x13 Go boards. } } @Misc{gelly2006a, author = {Sylvain Gelly and Yizao Wang}, title = {Exploration exploitation in {G}o: {UCT} for {M}onte-{C}arlo {G}o}, booktitle = {NIPS: Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop}, month = {December}, year = {2006}, url = {http://eprints.pascal-network.org/archive/00002713/01/nips_exploration_exploitation.pdf}, keywords = {Monte Carlo, UCT, MoGo}, abstract = { Algorithm UCB1 for multi-armed bandit problem has already been extended to Algorithm UCT which works for minimax tree search. We have developed a Monte-Carlo program, MoGo, which is the first computer Go program using UCT. We explain our modifications of UCT for Go application, among which efficient memory management, parametrization, ordering of non-visited nodes and parallelization. MoGo is now a top-level Computer-Go program on 9x9 Go board. } } @Misc{gelly2006b, author = {Sylvain Gelly and Yizao Wang and R\'emi Munos and Olivier Teytaud}, title = {{M}o{G}o: Improvements in {M}onte-{C}arlo {C}omputer-{G}o using {UCT} and sequence-like simulations}, howpublished = {Presentation given at the University of Alberta}, month = {December}, year = {2006} } @InProceedings{gelly2007, author = {Sylvain Gelly and David Silver}, title = {Combining Online and Offline Knowledge in {UCT}}, booktitle = {International Conference on Machine Learning, ICML 2007}, year = {2007}, url = {http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf}, keywords = {UCT, offline knowledge, default policy, Rapid Action Value Estimation, RAVE, RLGO}, abstract = { The UCT algorithm learns a value function online using sample-based search. The TD($\lambda$) algorithm can learn a value function offline for the on-policy distribution. We consider three approaches for combining offline and online value functions in the UCT algorithm. First, the offline value function is used as a default policy during Monte-Carlo simulation. Second, the UCT value function is combined with a rapid online estimate of action values. Third, the offline value function is used as prior knowledge in the UCT search tree. We evaluate these algorithms in 9x9 Go against GnuGo 3.7.10. The first algorithm performs better than UCT with a random simulation policy, but surprisingly, worse than UCT with a weaker, handcrafted simulation policy. The second algorithm outperforms UCT altogether. The third algorithm outperforms UCT with handcrafted prior knowledge. We combine these algorithms in MoGo, the world's strongest 9x9 Go program. Each technique significantly improves MoGo's playing strength. } } @PhdThesis{gelly2007b, author = {Sylvain Gelly}, title = {A Contribution to Reinforcement Learning; Application to {C}omputer-{G}o}, school = {Universit\'e Paris-Sud}, year = {2007}, keywords = {MoGo, UCT, RAVE}, url = {http://www.lri.fr/~gelly/paper/SylvainGellyThesis.pdf} } @InProceedings{globus2000, author = {Uri Globus and Markian Hlynka}, title = {Robust Algorithms for Computer {G}o}, booktitle = {5th Joint International Conference on Advanced Science and Technology (JICAST2000)}, year = {2000}, month = {December}, organization = {Shizuoka University, Hamamatsu, Japan}, kewords = {algorithms, robustness, chaos theory, fractals}, abstract = { Go, an oriental game several times older than western chess, is, for computers, an extremely difficult game. Based on simple rules, the scope and possible interactions far outstrip conventional game techniques such as alpha-beta. Go is identified as one of the Challenge Problems of AI. [4] The best Go programs have their strengths, to be sure. Overall, however, they are relatively poor performers when compared to humans, and when compared to computer programs that play Chess, Checkers, and other traditional games. Go programs exhibit inconsistent play and, while they may appear strong at first, over several games their weaknesses become apparent. Even with incredibly large handicaps, on the order of 29 stones, master players have docu-mented wins against some of the best programs. [1] This paper presents some background on computer Go, and discusses why traditional game techniques are insufficient to the task. One factor which seems to be a major weakness of current approaches is a lack of robustness. A preliminary investigation of this phenomenon has lead to identification of areas for future work. } } @Article{girvan1990, author = {Girvan, Ray}, title = {Go in the machine}, journal = {New Scientist}, year = {1990}, volume = {128}, month = {December}, keywords = {Cosmos, Nemesis} } @InProceedings{globus2000b, author = {Uri Globus and Markian Hlynka}, title = {The Butterfly and the Board: A preliminary look at chaos theory as a model for robust {G}o algorithms}, booktitle = {IPSJ SIGNotes Game Informatics}, year = {2000}, number = {5}, kewords = {algorithms, robustness, chaos theory, fractals}, abstract = { The game of Go is extraordinarily difficult for computers. Its scope far outstrips conventional game-programming techniques [1]. This is reflected in the fact that Go is identified as one of the Challenge Problems of AI [4]. Go's search space is simply too large to be tackled in its entirety. The result, an unavoidable lack of robustness in many current approaches, indicates the difficulties with conventional models. Thus, new models are required to render Go in its entirety a feasible undertaking. Preliminary work toward this end led to the consideration of nonlinear systems and chaos theory. } } @Misc{goldis1999, author = {Goldis, Bjorn}, title = {Towards Abstraction in {G}o Knowledge Representation}, year = {1999}, keywords = {overview}, } @Article{good1965, author = {Good, I.J.}, title = {The Mystery of {G}o}, year = {1965}, journal = {New Scientist}, volume = {427}, pages = {172-174}, keywords = {introduction, boxes}, } @TechReport{gory2004, institution = {Department of Computer Science, University of Bristol}, author = {Imran Ghory}, number = {CSTR-04-004}, title = {Reinforcement Learning in Board Games}, month = {May}, year = {2004}, abstract = { This project investigates the application of the TD(lambda) reinforcement learning algorithm and neural networks to the problem of producing an agent that can play board games. It provides a survey of the progress that has been made in this area over the last decade and extends this by suggesting some new possibilities for improvements (based upon theoretical and past empirical evidence). This includes the identification and a formalization (for the first time) of key game properties that are important for TD-Learning and a discussion of different methods of generate training data. Also included is the development of a TD-learning game system (including a game-independent benchmarking engine) which is capable of learning any zero-sum two-player board game. The primary purpose of the development of this system is to allow potential improvements of the system to be tested and compared in a standardized fashion. Experiments have been conduct with this system using the games Tic-Tac-Toe and Connect 4 to examine a number of different potential improvements. }, keywords = {TD-Learning}, url={http://www.cs.bris.ac.uk/Publications/Papers/2000100.pdf} } @Misc{graepel1999, author = {Graepel, Thore}, title = {A Machine Learning Approach to the Game of {G}o}, year = {1999}, note = {Draft, was available from the author's hompage}, keywords = {graph, representation, common fate graph, CFG, temporal difference learning}, } @Misc{graepel2000, author = {Graepel, Thore and Goutrie, Mike and Kr\"uger, Marco and Herbrich, Ralf}, title = {{G}o, {SVM}, {G}o}, year = {2000}, keywords = {Go, Machine Learning, Common Fate Graph, Relative Subgraph Features, Support Vector Machine, Kernel Perceptron, Tsume Go, 9x9}, url = {http://stat.cs.tu-berlin.de/~ralfh/go.ps.gz}, } @InProceedings{graepel2001, author = {Graepel, Thore and Goutrie, Mike and Kr\"uger, Marco and Herbrich, Ralf}, title = {Learning on graphs in the game of {G}o}, year = {2001}, booktitle = {International Conference on Artificial Neural Networks (ICANN-01)}, address = {Vienna, Austria}, keywords = {CFG, common fate graph, learning, SVM, support vector machine, kernel perceptron, life-and-death}, url = {http://research.microsoft.com/~rherb/papers/graegoukrueher01.ps.gz}, } @Misc{graepel2002, author = {Graepel, Thore}, title = {Computer Go and Machine Learning}, howpublished = {Slides of talk given in a course on machine learning at ETH Z\"urich}, month = {June}, year = {2002}, keywords = {Machine learning, Common Fate Graph, Support Vector Machine} } @PhdThesis{graepel2002b, author = {Graepel, Thore}, title = {{PAC}-{B}ayesian Pattern Classification with Kernels: Theory, Algorithms, and an Application to the Game of {G}o}, school = {Department of Computer Science, Technical University of Berlin}, year = {2002}, address = {Berlin, Germany}, keywords = {pattern classification, machine learning, kernel methods, PAC-Bayesian framework, support vector machines, common fate graph}, abstract = { The thesis deals with problems of pattern classification in the framework of machine learning. The focus of the work is on kernel methods for the supervised classification of objects. The thesis gives a detailed introduction into the field of kernel algorithms and learning theory. New contributions include learning theoretical results in the PAC-Bayesian framework, efficient sampling algorithms for Bayesian classification in kernel space, and an application of kernel methods to pattern analysis in the game of Go. Learning Theory: In the PAC-Bayesian framework we derive new bounds on the prediction error of linear classifiers (in kernel space) in terms of the normalised margin achieved on the training sample, taking into account both the concentration of the training data and the margin distribution. Assuming sparseness of the dual variables we extend the PAC-Bayesian framework to data-dependent hypotheses. Finally, we prove egalitarian bounds on the probability of finding classifiers with high prediction error in subsets of hypothesis space with low empirical risk - results that emphasise the importance of model selection. Learning Algorithms: We discuss Bayesian classification in kernel space and identify Bayesian transduction and the Bayes point machine as optimal procedures for classification in a Bayesian sense. Assuming a uniform prior over normalised weights for a given kernel we devise sampling schemes for the resulting piecewise constant posterior: The kernel Gibbs sampler, a Markov chain Monte Carlo method able to deal with label noise, and the permutational perceptron sampler for large scale sampling. The classification techniques are tested on handwritten-digit recognition tasks and compare favourably to support vector machines when rejecting test data based on confidence measures. Application: We apply kernel classifiers to the domain of pattern classification in the Japanese game of Go, which serves as a test domain for classification problems involving symbolic or structured objects. In order to learn mappings from points on the board to numbers that indicate territorial status or move quality we define the common fate graph as a compact representation for Go positions and show how a feature space based on relative subgraph features can be constructed. Building on the this representation we train a support vector machine to learn the quality of moves from a collection of Go problems and from actual 9x9 game records. As a result, we obtain classifiers that solve certain Go problems and play 9x9 Go at a non-trivial level of playing strength. }, url = {http://edocs.tu-berlin.de/diss/2002/graepel_thore.pdf} } @Misc{graepel2005, author = {David Stern and Ralf Herbrich and Thore Graepel}, title = {Bayesian Pattern Ranking for Move Prediction in the Game of {G}o}, howpublished = {Draft}, year = {2005}, keywords = {Automatic pattern learning, move prediction, Go player, Bayesian learning, expert games}, abstract = { We investigate the problem of learning to predict moves in the board game of Go from game records of expert players. In particular, we obtain a probability distribution for professional play over legal moves in a given position. This distribution has numerous applications in computer Go, among them serving as a) an efficient stand-alone Go player, b) a move selector/sorter for game tree search and c) a training tool for Go players. Our method comprises two major components: a) a pattern extraction scheme for efficiently harvesting patterns of given size and shape from expert game records and b) a Bayesian learning algorithm that learns a distribution over the values of a move given a board position based on the local pattern context. The system is trained on 20,000 expert games and shows excellent prediction performance as indicated by its ability to predict the moves made by professional Go players in 26\% of test positions. } } @InProceedings{graepel2006, author = {David Stern and Ralf Herbrich and Thore Graepel}, title = {Bayesian Pattern Ranking for Move Prediction in the Game of {G}o}, booktitle = {International Conference on Machine Learning (ICML-2006)}, year = {2006}, url = {http://www.icml2006.org/icml_documents/camera-ready/110_Bayesian_Pattern_Ran.pdf}, keywords = {Automatic pattern learning, move prediction, Go player, Bayesian learning, expert games}, abstract = { We investigate the problem of learning to predict moves in the board game of Go from game records of expert players. In particular, we obtain a probability distribution over legal moves for professional play in a given position. This distribution has numerous applications in computer Go, including serving as an efficient stand-alone Go player. It would also be effective as a move selector and move sorter for game tree search and as a training tool for Go players. Our method has two major components: a) a pattern extraction scheme for efficiently harvesting patterns of given size and shape from expert game records and b) a Bayesian learning algorithm (in two variants) that learns a distribution over the values of a move given a board position based on the local pattern context. The system is trained on 181,000 expert games and shows excellent prediction performance as indicated by its ability to perfectly predict the moves made by professional Go players in 34\% of test positions. } } @Misc{greenberg1995, author = {Greenberg, Jeffrey}, title = {Programming {G}o by Breeding Software}, year = {1995}, note = {Available by Internet.}, keywords = {genetic programming}, url = {http://www.inventivity.com/OpenGo/Papers/jeffg/breed.html}, } @Misc{greenberg1997, author = {Greenberg, Jeffrey}, title = {Architecture of a {G}o Programming Environment}, year = {1997}, note = {Available from the author's homepage}, url = {http://www.concentric.net/~Jgberg/env.html}, } @Article{guterl1996, author = {Guterl, Fred}, title = {Silicon Gambit}, year = {1996}, month = {June}, journal = {Discover Magazin}, keywords = {go, bridge, chess}, } @Article{hamann1985, author = {Hamann, Christian M.}, title = {{C}hronologie der {P}rogrammierung des japanischen {B}rettspiels {G}o -- {E}ine {H}erausforderung an die {K}\"unstliche {I}ntelligenz}, year = {1985}, journal = {Angewandte Informatik}, volume = {12}, note = {In German}, keywords = {chronological survey, history, Go-Programming}, } @Article{hafner2002, author = {Katie Hafner}, title = {In an Ancient Game, Computing's Future}, journal = {The New York Times}, year = {2002}, month = {August}, day = {1}, keywords = {21st Century Cup}, } @MastersThesis{harling1994, author = {Harling, Torsten}, title = {{L}\"osungsstrategien beim {T}sume-{G}o und ihre {I}mplementation}, year = {1994}, school = {Technische Universit\"at Clausthal}, note = {In German}, keywords = {tsume-go, solver, GPS, GoTools}, } @Misc{harren2003, author = {Matthew Harren}, title = {Federations in {G}o endgames}, howpublished = {Available by Internet}, month = {December}, year = {2003}, note = {Term project, MATH 275 (Professor Elwyn Berlekamp), University of California, Berkeley}, url = {http://www.cs.berkeley.edu/~matth/analgo/Federations.html}, keywords = {combinatorial game theory, dependency, subgames}, abstract = { Combinatorial game theory relies on the ability to decompose games into sums of smaller independent games. This document describes an extension of the AnalGo endgame analyzer to consider cases when Go subgames are ``mostly'' independent but may interact under some circumstances. The new extension to AnalGo allows users to declare ``federations'' of subgames which may interact with one another. In these federations, users specify conditions under which regions interact, and the effects that these interactions could have. AnalGo then uses this information to combine the subgames. } } @Misc{hollosi1997, author = {Hollosi, Arno}, title = {{SGF} file format {FF[4]}}, note = {Smart game format specification. Available by Internet}, keywords = {sgf, file format, saving, games, records, FF[4]}, url = {http://www.red-bean.com/sgf/}, } @Article{hu1997, author = {Hu, Shui and Lehner, Paul E.}, title = {Multipurpose Strategic Planning In the Game of {G}o}, year = {1997}, month = {September}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {9}, keywords = {Computer Go, adversarial planning, automated planning, artificial intelligence}, } @InProceedings{huang2001, author = {Timothy Huang}, title = {Strategy game programming projects}, booktitle = {JCSC}, year = {2001}, volume = {16}, number = {4}, month = {May}, abstract = { In this paper, we show how programming projects centered around the design and construction of computer players for strategy games can play a meaningful role in the educational process, both in and out of the classroom. We describe several game-related projects undertaken by the author in a variety of pedagogical situations, including introductory and advanced courses as well as independent and collaborative research projects. These projects help students to understand and develop advanced data structures and algorithms, to manage and contribute to a large body of existing code, to learn how to work within a team, and to explore areas at the frontier of computer science research. } } @InProceedings{huang2002, author = {Huang, Tim}, title = {Towards a Probabilistic Model for Intent Inference in the Game of {G}o}, booktitle = {AAAI Fall Symposium on Intent Inference for Users, Teams and Adversaries}, year = {2002}, url = {http://www.cs.middlebury.edu/~huang/publications/aaaifs2002.pdf}, keywords = {opponent modeling, intent inference, probabilistic approach}, abstract = { Computer programs for the game of Go play only at the level of an advanced beginning player. The standard approach to constructing a program based on brute force game-tree search does not work well because of the game tree size and, more significantly, the difficulty in constructing fast, accurate heuristic evaluation functions. In this paper, we consider the use of intent inference in a Go program. In particular, we discuss how models of an opponent's long-term playing style and short-term intentions can direct the exploration of candidate moves and influence the evaluation of game positions. We propose a probabilistic approach to user modeling and intent inference, and we note key issues relevant to the implementation of an intent inference agent. } } @Article{huang2004, author = {Huang, Tim and Connell, Graeme and McQuade, Bryan}, title = {Experiments with Learning Opening Strategy in the Game of {G}o}, journal = {International Journal on Artificial Intelligence Tools}, year = {2004}, volume = {13}, number = {1}, pages = {101-104}, url = {http://www.cs.middlebury.edu/~huang/publications/ijait2004.pdf}, keywords = {temporal difference learning, self-play}, abstract = { We present an experimental methodology and results for a machine learning approach to learning opening strategy in the game of Go, a game for which the best computer programs play only at the level of an advanced beginning human player. While the evaluation function in most computer Go programs consists of a carefully crafted combination of pattern matchers, expert rules, and selective search, we employ a neural network trained by self-play using temporal difference learning. Our focus is on the sequence of moves made at the beginning of the game. Experimental results indicate that our approach is effective for learning opening strategy, that including higher-level features of the game can improve the quality of the learned evaluation function, and that different input representations of higher-level information can substantially affect performance. } } @Misc{huima1999, author = {Huima, Antti}, title = {Unsupervised Learning of {G}o Patterns}, year = {1999}, note = {Available from the author's homepage}, keywords = {neural networks, vector quantization}, } @Misc{huima2000, author = {Huima, Antti}, title = {A Group-Theoretic {Zobrist} Hash Function}, year = {2000}, keywords = {Zobrist, hash function, hash key, hash table, efficient, color, rotation, mirroring}, url = {http://fragrieu.free.fr/zobrist.pdf}, } @Article{johnson1997, author = {Johnson, George}, title = {To Test a Powerful Computer, Play an Ancient Game}, year = {1997}, month = {July 29}, day = {29}, journal = {The New York Times}, keywords = {David Mechner}, url = {http://mechner.com/david/compgo/times/}, } @Misc{kaminski2002, author = {Kaminski, Piotr}, title = {{L}as {V}egas {G}o}, howpublished = {Available by Internet.}, year = {2002}, url = {http://www.ideanest.com/vegos/LasVegasGo.pdf}, keywords = {Monte Carlo Go, simulated annealing, Gobble, Vegos} } @Misc{kawa2003, author = {Ryuichi Kawa}, title = {Inside {H}aruka}, howpublished = {CGF (Computer Go Forum) Journal Vol 5}, year = {2003}, note = {In Japanese.}, url = {http://www.cs.ualberta.ca/~games/go/seminar/2003/031103/vol5-4.pdf} } @Article{kao2000, author = {Kao, Kuo-Yuan}, title = {Mean and temperature search for {G}o endgames}, year = {2000}, journal = {Information Sciences}, volume = {122}, pages = {77-90} } @InProceedings{kendall2004, author = {Graham Kendall and Razali Yaakob and Philip Hingston}, title = {An Investigation of an Evolutionary Approach to the Opening of {G}o}, booktitle = {Proceedings of the 2004, IEEE Congress on Evolutionary Computation (CEC'04)}, year = {2004}, url = {http://www.scis.ecu.edu.au/research/wfg/publications/WFG2004b.pdf}, keywords = {neural networks, evolutionary strategy, Gondo}, abstract = { The game of Go can be divided into three stages; the opening, the middle, and the end game. In this paper, evolutionary neural networks, evolved via an evolutionary strategy, are used to develop opening game playing strategies for the game. Go is typically played on one of three different board sizes, i.e., 9x9, 13x13 and 19x19. A 19x19 board is the standard size for tournament play but 9x9 and 13x13 boards are usually used by less-experienced players or for faster games. This paper focuses on the opening, using a 13x13 board. A feed forward neural network player is played against a static player (Gondo), for the first 30 moves. Then Gondo takes the part of both players to play out the remainder of the game. Two experiments are presented which indicate that learning is taking place. } } @Article{kierulf1987, author = {Kierulf, Anders}, title = {Human-Computer Interaction in the Game of {G}o}, year = {1987}, journal = {Methodologies for Intelligent Systems}, keywords = {expert, tool, interactive}, } @InProceedings{kierulf1989, author = {Kierulf, Anders and Nievergelt, Jurg}, title = {Swiss Explorer blunders its way into winning the first Computer {G}o Olympiad}, year = {1989}, booktitle = {Heuristic Programming in Artificial Intelligence - The First Computer Olympiad. LEVY, D.N.L., BEAL, D.F. (Eds.) Ellis Horwood Ltd., Chichester, West Sussex, 1989.}, keywords = {Swiss Explorer, Stone, Go Intellect}, } @InProceedings{kierulf1991, author = {Kierulf, Anders and Gasser, Ralph and Geiser, Peter M. and M\"uller, Martin and Nievergelt, Jurg and Wirth, Christoph}, title = {Every interactive system evolves into hyperspace: The case of the Smart Game Board}, year = {1991}, booktitle = {Proc. Hypertext/Hypermedia 1991}, keywords = {Smart Game Board, visualization, navigation, hypertext, game-database}, } @InProceedings{kierulf1990, author = {Anders Kierulf, Ken Chen, Jurg Nievergelt}, title = {Smart {G}ame {B}oard and {G}o {E}xplorer: a study in software and knowledge engineering}, booktitle = {Communications of the ACM}, year = {1990}, month = {February}, volume = {33}, number = {2} } @InProceedings{kishimoto2003, author = {Akihiro Kishimoto and Martin M\"uller}, title = {A Solution to the {GHI} Problem for Depth-First Proof-Number Search}, booktitle = {7th Joint Conference on Information Sciences (JCIS2003)}, pages = {489-492}, year = {2003}, url = {http://www.cs.ualberta.ca/~kishi/gps_file/kishi_mueller_jcis.ps.gz}, keywords = {Graph history interaction, Df-pn} } @Misc{kishimoto2003b, author = {Akihiro Kishimoto}, title = {Inside {H}aruka}, year = {2003}, note = {Slides of a talk reviewing Ryuichi Kawa's paper} } @InProceedings{kishimoto2003c, author = {Akihiro Kishimoto and Martin M\"uller}, title = {Df-pn in {G}o: An Application to the One-Eye Problem}, booktitle = {Advances in Computer Games 10}, pages = {125-141}, year = {2003}, publisher = {Kluwer Academic Publishers}, url = {http://www.cs.ualberta.ca/~kishi/pdf_file/acg_kishimoto_mueller.pdf}, keywords = {proof-number search, df-pn, one-eye problem}, abstract = { Search algorithms based on the notion of proof and disproof numbers have been shown to be effective in many games. In this paper, we modify the depth-first proof-number search algorithm df-pn, in order to apply it to the game of Go. We develop a solver for one-eye problems, a special case of enclosed tsume-Go [life and death] problems. Our results show that this approach is very promising. } } @InProceedings{kishimoto2004, author = {Akihiro Kishimoto and Martin M\"uller}, title = {A General Solution to the Graph History Interaction Problem}, booktitle = {Nineteenth National Conference on Artificial Intelligence (AAAI'04)}, pages = {644-649}, year = {2004}, publisher = {AAAI Press}, url = {http://www.cs.ualberta.ca/~kishi/pdf_file/AAAI04KishimotoA.pdf}, keywords = {GHI problem, df-pn algorithm, alpha-beta algorithm, Kawano's simulation}, abstract = { Since the state space of most games is a directed graph, many game-playing systems detect repeated positions with a transposition table. This approach can reduce search effort by a large margin. However, it suffers from the so-called Graph History Interaction (GHI) problem, which causes errors in games containing repeated positions. This paper presents a practical solution to the GHI problem that combines and extends previous techniques. Because our scheme is general, it is applicable to different game tree search algorithms and to different domains. As demonstrated with the two algorithms and df-pn in the two games checkers and Go, our scheme incurs only a very small overhead, while guaranteeing the correctness of solutions. } } @PhdThesis{kishimoto2005, author = {Akihiro Kishimoto}, title = {Correct and Efficient Search Algorithms in the Presence of Repetitions}, school = {University of Alberta}, year = {2005}, month = {January}, url = {http://www.cs.ualberta.ca/~kishi/pdf_file/kishi_phd_thesis.pdf}, keywords = {Search, repetitions, One-eye problem, Tsume-Go, checkers, graph history interaction, GHI, proof-number search, df-pn} } @InProceedings{kishimoto2005b, author = {Akihiro Kishimoto and Martin M\"uller}, title = {Dynamic {D}ecomposition {S}earch: A {D}ivide and {C}onquer Approach and its Application to the One-Eye Problem in {G}o}, booktitle = {IEEE Symposium on Computational Intelligence and Games (CIG'05)}, pages = {164-170}, year = {2005}, url = {http://www.cs.ualberta.ca/~kishi/pdf_file/kishi_mueller_cig05.pdf}, abstract = { Abstract- Decomposition search is a divide and conquer approach that splits a game position into sub-positions and computes the global outcome by combining results of local searches. This approach has been shown to be successful to play endgames in the game of Go. This paper introduces dynamic decomposition search as a way of splitting a problem dynamically during search. Our results in solving one-eye problems in the game of Go show the promise of this approach. Additionally, we propose relaxed decomposition, a more ambitious way of splitting positions. } } @InProceedings{kishimoto2005c, author = {A. Kishimoto and M. M\"uller}, title = {Search versus knowledge for solving life and death problems in {G}o}, booktitle = {Twentieth National Conference on Artificial Intelligence (AAAI-05)}, pages = {1374-1379}, year = {2005}, url = {http://www.cs.ualberta.ca/~mmueller/ps/aaai05-tsumego.pdf}, keywords = {Life and Death, tsume-Go, TSUMEGO EXPLORER, GoTools}, abstract = { In games research, Go is considered the classical board game that is most resistant to current AI techniques. Large-scale knowledge engineering has been considered indispensable for building state of the art programs, even for subproblems such as Life and Death, or tsume-Go. This paper describes the technologies behind TSUMEGO EXPLORER, a high-performance tsume-Go search engine for enclosed problems. In empirical testing, this engine outperforms GoTools, which has been the undisputedly best tsume-Go program for 15 years. } } @InProceedings{kishimoto2006, author = {Yoshimoto, Haruhiro and Yoshizoe, Kazuki and Kaneko, Tomoyuki and Kishimoto, Akihiro and Taura, Kenjiro}, title = {{M}onte {C}arlo Has a Way to {G}o}, booktitle = {Twenty-First National Conference on Artificial Intelligence (AAAI-06)}, year = {2006}, url = {http://www.fun.ac.jp/~kishi/pdf_file/AAAI06YoshimotoH.pdf}, keywords = {Monte Carlo, parallelizing}, abstract = { Monte Carlo Go is a promising method to improve the performance of computer Go programs. This approach determines the next move to play based on many Monte Carlo samples. This paper examines the relative advantages of additional samples and enhancements for Monte Carlo Go. By parallelizing Monte Carlo Go, we could increase sample sizes by two orders of magnitude. Experimental results obtained in 9x9 Go show strong evidence that there are trade-offs among these advantages and performance, indicating a way for Monte Carlo Go to go. } } @Misc{klinger1996, author = {Klinger, Tim and Mechner, David A.}, title = {An Architecture for {G}o}, year = {1996}, keywords = {incremental}, url = {http://mechner.com/david/compgo/acg/}, } @PhdThesis{klinger2001, author = {Klinger, Tamir}, title = {Adversarial Reasoning: A Logical Approach for Computer {G}o}, year = {2001}, school = {New York University}, keywords = {knowledge-based program, life and death, goal theory, modal logic, strategic theories}, url = {http://mechner.com/david/compgo/thesis.pdf}, } @InProceedings{kocsis2006, author = {Kocsis, Levente and Szepesv\'ari, Csaba}, title = {Bandit based Monte-Carlo Planning}, booktitle = {ECML-06}, year = {2006}, keywords = {Monte-Carlo, planning, UCT}, url = {http://zaphod.aml.sztaki.hu/papers/ecml06.pdf}, abstract = { For large state-space Markovian Decision Problems Monte-Carlo planning is one of the few viable approaches to find near-optimal solutions. In this paper we introduce a new algorithm, UCT, that applies bandit ideas to guide Monte-Carlo planning. In finite-horizon or discounted MDPs the algorithm is shown to be consistent and finite sample bounds are derived on the estimation error due to sampling. Experimental results show that in several domains, UCT is significantly more efficient than its alternatives. } } @InProceedings{kojima1994, author = {Kojima, Takuya and Ueda, Kazuhiro and Nagano, Saburo}, title = {A Case Study on Acquisition and Refinement of Deductive Rules based on {EBG} in an Adversary Game: how to capture stones in {G}o}, booktitle = {First Game Programming Workshop in Japan}, pages = {34-43}, year = {1994}, keywords = {Learning, Explanation-Based Generalization, EBG}, abstract = { This paper proposes two deductive learning algorithms in an adversary game domain giving Go as an example, especially the way to capture stones; one is for acquiring rules and the other for refining the acquired rules. The rules to be acquired are called forcing rules. A player wins whenever he/she applies forcing rules. The algorithm for rule acquisition consists of three steps; the first step chooses good moves to be learned by interpreting moves using acquired rules, the second step extracts a relevant part of a board position by using Explanation-Based Generalization (EBG), and the last step transforms the position and the move into generalized ones. Since it is difficult to acquire proper rules from a single example in this domain, the system refines the acquired rules when negative examples for the applied rules are given; when the rules do not lead the system to win, the system refines the rules by tracing the applied forcing rules, which can be taken as understanding the causes for a player not to win. In short, this paper proposes two algorithms for learning rules in the domain of Go, on which only a few studies have been made. Moreover, these algorithms are supported by think-aloud protocol data of human novices. } } @MastersThesis{kojima1995, author = {Kojima, Takuya}, title = {A Model of Acquisition and Refinement of Deductive Rules in the Game of {G}o}, year = {1995}, school = {University of Tokyo}, note = {In Japanese}, keywords = {go, explanation-based generalization, EBG}, } @InProceedings{kojima1997a, author = {Kojima, Takuya}, title = {Flexible Acquisition of Various Types of Knowledge from Game Records: Application to the game of {G}o}, year = {1997}, booktitle = {Proceedings of the IJCAI-97 Workshop on Using Games as an Experimental Testbed for AI Research, Nagoya, Japan}, note = {Nagoya, Japan}, keywords = {knowledge acquisition}, } @InProceedings{kojima1997b, author = {Kojima, Takuya}, title = {An Evolutionary Algorithm Extended by Ecological Analogy and its Application to the Game of {G}o}, year = {1997}, booktitle = {Proceedings of the 15th International Joint Conference on Artificial Intelligence, Nagoya, Japan}, keywords = {evolution, ecology}, } @InProceedings{kojima1998, author = {Kojima, Takuya and Yoshikawa, Atsushi}, title = {A Two-Step Model of Pattern Acquisition: Application to {T}sume-{G}o}, crossref = {cg1998}, pages = {146-166}, keywords = {Knowledge acquisition, evolutionary learning, pattern acquisition, Tsume-Go}, abstract = { It has been said to be very useful for Go playing systems to have knowledge. We focus on pattern level knowledge and propose a new model of pattern acquisition based on our cognitive experiments. The model consists of two steps: pattern acquisition step, using only positive examples, and pattern refinement step, using both positive and negative examples. The latter step acquires precise conditions to apply and/or the way of conflict resolution. This model has advantages in computational time and precise control for conflict resolution. One algorithm is given for each step, and each algorithm can change independently, it is possible to compare algorithms with this model. Three algorithms are introduced for the first step and two for the second step. Patterns acquired by this model are applied to Tsume-Go problems (life and death problems) and the performance between six conditions are compared. In the best condition, the percentage of correct answers is about 31\%. This result equals the achievement of one dan human players. It is also shown that the patterns enhance search techniques when the search space is very large. } } @PhdThesis{kojima1998a, author = {Kojima, Takuya}, title = {Automatic Acquisition of {G}o Knowledge from Game Records: Deductive and Evolutionary Approaches}, year = {1998}, school = {University of Tokyo}, keywords = {knowledge}, } @InProceedings{kojima1999, author = {Kojima, Takuya and Yoshikawa, Atsushi}, title = {A Model of Inter-acquisition of Knowledge and Terms and its Application to {T}sume-{G}o}, year = {1999}, booktitle = {Game Programming Workshop in Japan (GPW'99)}, note = {In Japanese} } @InProceedings{kojima1999a, author = {Kojima, Takuya}, title = {Knowledge Acquisition from Game Records}, year = {1999}, crossref = {fuernkranz1999}, url = {http://www.ai.univie.ac.at/icml-99-ws-games/papers/kojima.ps.gz}, } @Misc{konidaris2002, author = {George Konidaris, Dylan Shell and Nir Oren}, title = {Evolving Neural Networks for the {C}apture {G}ame}, howpublished = {SAICSIT Postgraduate Symposium 2002}, year = {2002}, url = {http://www-robotics.usc.edu/~dshell/res/evneurocapt.pdf}, keywords = {Genetic algorithm, neural networks, Capture game, Atari-Go}, abstract = { This paper proposes the use of a genetic algorithm to develop neural networks to play the Capture Game, a subgame of Go. The motivation for this is twofold: to evaluate and possibly improve upon current genetic algorithm variants in order to produce a good player and (more importantly) to use this process to examine the properties and processes that are present in evolutionary systems in an attempt to shed some light on the phenomena that are required for an evolutionary process to produce robust, perpetually improving individuals and avoid local minima without any outside interaction. A brief survey of related work in the area is given, which highlights some of the interesting research questions that remain. This is followed by an outline of a distributed system that has been developed for use in the experimental evaluation of some of the proposed ideas and some of the initial results generated by the system. } } @TechReport{kunkle2002, author = {Kunkle, Daniel R.}, title = {The Game of {G}o and Multiagent Systems}, year = {2002}, institution = {Rochester Institute of Technology}, address = {Rochester NY}, keywords = {multiagent systems, autonomous agents}, url = {http://www.redfish.com/dkunkle/mypapers/goAndMultiagents.pdf}, keywords = {Multiagent systems, agents}, abstract = { Go is two-player board game that poses one of the largest challenges to game programmers today. Multiagent systems are those composed of multiple autonomous, interacting computer systems, or agents. These two seemingly diverse areas have a number of similarities, which will be explored here. } } @Misc{krueger2000, author = {Kr\"uger, Marco and Goutrie, Marc}, title = {Maschinelles {L}ernen und das asiatische {B}rettspiel {G}o}, howpublished = {Available from the author's homepage}, month = {July}, year = {2000}, note = {In German}, url_ = {http://user.cs.tu-berlin.de/~grisu/studium/go_germ.ps.gz}, keywords = {Common fate graph, Support Vector Machine} } @InBook{landman1996, author = {Landman, Howard}, title = {Eyespace Values in {G}o}, year = {1996}, pages = {227-257}, keywords = {go, combinatorial game theory, life-and-death, eyes}, booktitle = {Games of No Chance}, publisher = {Cambridge University Press}, url = {http://www.msri.org/publications/books/Book29/files/landman.pdf}, } @TechReport{lee2003, author = {Byung-Doo Lee, Hans Werner Guesgen, Jacky Baltes}, title = {The Application of TD(lambda) Learning to the Opening Games of 19x19 {G}o}, institution = {University of Auckland}, year = {2003}, number = {CITR-TR-136}, url = {http://www.citr.auckland.ac.nz/techreports/2003/CITR-TR-136.pdf}, abstract = { This paper describes the results of applying Temporal Difference (TD) learning with a network to the opening game problems in Go. The main difference from other research is that this experiment applied TD learning to the full-sized (19x19) game of Go instead of a simple version (e.g., 9x9 game). We discuss and compare TD(lambda) learning for predicting an opening game's winning and for finding the best game among the prototypical professional opening games. We also tested the performance of TD(lambda)s by playing against each other and against the commercial Go programs. The empirical result for picking the best game is promising, but there is no guarantee that TD(lambda) will always pick the identical opening game independent of different lambda values. The competition between two TD(lambda)s shows that TD(lambda) with a higher lambda has better performance. } } @TechReport{lee2004, author = {Byung-Doo Lee}, title = {Life-and-Death Problem Solver in Go}, institution = {University of Auckland}, year = {2004}, number = {CITR-TR-145}, url = {http://www.citr.auckland.ac.nz/techreports/2004/CITR-TR-145.pdf}, abstract = { The life-and-death problem in Go is a basic and essential problem to be overcome in implementing a computer Go program. This paper proposes a new heuristic searching model which can reduce the branching factor in a game tree. For constructing the first level of a game tree, we implement pattern clustering and eye shape analysis to get the set of the first moves, thereby reducing the branching factor of the game tree. The empirical result for game tree searching with these methods is promising. We also suggest several problems to address for making game tree searching more robust, such as: coping with situations where the number of legal moves in the surrounded group is more than 8, creating an accurate heuristic evaluation function, and dealing with ko fighting. } } @Article{lehner1997, author = {Hu,Shui and Lehner, Paul E.}, title = {Multipurpose Strategic Planning In the Game of {G}o}, year = {1997}, journal = {IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE}, volume = {19}, keywords = {adversarial planning}, } @InProceedings{lew2006, author = {Jakub Pawlewicz and Lukasz Lew}, title = {Improving Depth-first {PN}-Search: 1 + e Trick}, booktitle = {5th International Conference on Computers and Games, Turin, Italy}, year = {2006}, url = {http://www.mimuw.edu.pl/~lew/download.php?file_no=6}, keywords = {PN-Search, DF-PN, PDS, Atari Go}, abstract = { Various efficient game problem solvers are based on PN-Search. Especially depth-first versions of PN-Search like DF-PN or PDS - contrary to other known techniques - are able to solve really hard problems. However, the performance of DF-PN and PDS decreases dramatically when the search space significantly exceeds available memory. A simple trick to overcome this problem is presented. Experiments on Atari Go and Lines of Action show great practical value of the proposed enhancement. } } @Article{lichtenstein1980, author = {Lichtenstein, David and Sipser, Michael}, title = {{G}o is Polynominal-Space Hard}, year = {1980}, journal = {Journal of the ACM}, volume = {27}, number = {2}, pages = {393-401}, keywords = {computational complexity, planarity, Pspace hardness}, abstract = { It is shown that, given an arbitrary GO position on an n x n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is proved that GO ts Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and finally to GO. } } @InProceedings{lorentz1996, author = {Lorentz, Richard}, title = {Connectivity in {G}o}, year = {1996}, booktitle = {PROCEEDINGS OF THE GAME PROGRAMMING WORKSHOP IN JAPAN '96, H. Matsubara (ed.), Computer Shogi Association, Tokyo}, keywords = {connectivity, connections, algorithms}, } @InProceedings{lorentz1997, author = {Lorentz, Richard J.}, title = {2 x n {G}o}, year = {1997}, month = {October}, booktitle = {Game Programming Workshop in Japan (GPW'97), Hakone}, keywords = {non-standard, two rows}, } @InProceedings{lorentz1999, author = {Lorentz, Richard J. and Ha, Simon}, title = {Data Structures for 2 x n {G}o}, year = {1999}, booktitle = {Game Programming Workshop in Japan (GPW'99)}, } @Misc{lubberts2001, author = {Lubberts, Alex and Miikkulainen, Risto}, title = {Co-Evolving a {G}o-Playing Neural Network}, year = {2001}, organization = {Workshop, Genetic and Evolutionary Computation Conference, Gecco-2001, San Francisco}, keywords = {neural networks, competitive fitness sharing, shared sampling, hall of fame, SANE, co-evolution}, url = {ftp://ftp.cs.utexas.edu/pub/neural-nets/papers/lubberts.coevolution-gecco01.ps.gz}, } @Article{masanunga2000, author = {Masanunga, Hiromi and Horn, John}, title = {Characterizing mature human intelligence Expertise development}, journal = {Learning and individual differences}, year = {2000}, volume = {12}, pages = {5-33}, keywords = {Adult intelligence, Expertise, Fluid reasoning, Crystallized knowledge} } @Misc{matsubara1997, author = {Hitoshi Matsubara and Hiroyuki Iida and Reijer Grimbergen}, title = {Chess, Shogi, {G}o, natural developments in game research}, url = {http://citeseer.nj.nec.com/matsubara97ches.html} } @InProceedings{mayer2005, author = {H. A. Mayer and Peter Maier}, title = {Coevolution of Neural {G}o Players in a Cultural Environment}, booktitle = {Proceedings of the Congress on Evolutionary Computation 2005, Edinburgh, Scotland}, year = {2005}, url = {http://www.cosy.sbg.ac.at/~helmut/Research/Papers/edinburgh05.pdf}, keywords = {genetic algorithms, evolutionary computing, neural networks}, abstract = { We present experiments (co)evolving Go players based on artificial neural networks (ANNs) for a 5x5 board. ANN structure and weights are encoded in multi-chromosomal genotypes. In evolutionary scenarios a population of generalized multi-layer perceptrons (GMLPs) has to compete with a single Go program from a set of three players of different quality. Two coevolutionary approaches, namely, a dynamically growing culture, and a fixed-size elite represent the changing environment of the coevolving population. The playing quality of the (co)evolved players is measured by a strength value derived from games against the set of three programs. We also report on first experiments employing recurrent networks, which allow a direct structural representation of the Go board. Finally, the quality of all the best (co)evolved players is evaluated in a round robin tournament. } } @InProceedings{mayer2007, author = {Helmut A. Mayer}, title = {Board Representations for Neural {G}o Players Learning by Temporal Difference}, booktitle = {IEEE Symposium on Computational Intelligence and Games CIG 2007}, year = {2007}, url = {http://www.cosy.sbg.ac.at/~helmut/Research/Papers/honolulu07.pdf}, keywords = {neural networks, temporal difference learning, board representation}, abstract = { The majority of work on artificial neural networks (ANNs) playing the game of Go focus on network architectures and training regimes to improve the quality of the neural player. A less investigated problem is the board representation conveying the information on the current state of the game to the network. Common approaches suggest a straight-forward encoding by assigning each point on the board to a single (or more) input neurons. However, these basic representations do not capture elementary structural relationships between stones (and points) being essential to the game. We compare three different board representations for self-learning ANNs on a 5x5 board employing temporal difference learning (TDL) with two types of move selection (during training). The strength of the trained networks is evaluated in games against three computer players of different quality. A tournament of the best neural players, addition of alpha-beta search, and a commented game of a neural player against the best computer player further explore the potential of the neural players and its respective board representations. } } @Article{mechner1998, author = {David Mechner}, title = {All Systems {G}o}, journal = {The Sciences}, year = {1998}, volume = {38}, number = {1}, url = {http://mechner.com/david/compgo/sciences/}, } @InProceedings{meijer2001, author = {Meijer, Alex B. and Koppelaar, Henk}, title = {A learning architecture for the game of {G}o}, year = {2001}, booktitle = {2nd International Conference on Intelligent Games and Simulation (GAMEON 2001)}, address = {London}, keywords = {learning, HUGO, subgames, sente, fuzzy partial ordering}, url = {http://mmi.tudelft.nl/~meijer/files/meijer-gameon01}, } @InProceedings{meijer2001b, author = {Meijer, Alex B. and Koppelaar, Henk}, title = {Pursuing abstract goals in the game of {G}o}, year = {2001}, booktitle = {13th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC 2001)}, address = {Amsterdam}, keywords = {adversarial planning, search, goal-checking}, url = {http://mmi.tudelft.nl/~meijer/files/meijer-bnaic01.pdf}, } @InProceedings{meijer2003, author = {Meijer, Alex B. and Koppelaar, Henk}, title = {Towards Multi-Objective Game Theory - With Application to {G}o}, booktitle = {Game-On 2003, 4th Intl. Conf. on Intelligent Games and Simulation}, year = {2003}, url = {http://mmi.tudelft.nl/~meijer/files/meijer-gameon03.pdf}, keywords = {Combinatorial Games, Multiple Objectives, Computational Intelligence, Dependence of Games, Threat, Ko}, abstract = { We define a multi-goal as a conjunction and/or disjunction of ordinal-scaled objectives. We give exact formulas to compute the conjunction and disjunction of independent combinatorial games associated with the objectives. Dependence of games is formalized. We also propose a definition for the (con/dis)junction of effectively dependent games. In all the above formulas, we can work with uncertain and unresolved (ko) outcomes. With these formulas, the status of a multi-goal can be computed with considerable less effort compared to current search approaches. Algorithms to compute multiple solutions elegantly and to extract the threats to a won game from its search tree are outlined, implemented and applied. } } @PhdThesis{moews1993, author = {Moews, David}, title = {On Some Combinatorial Games Connected with {G}o}, year = {1993}, school = {University of California, Berkeley}, keywords = {Combinatorial Game Theory, Ko}, url = {http://xraysgi.ims.uconn.edu:8080/dmoews/thesis.ps}, } @Misc{moews1995, author = {Moews, David}, title = {Coin-Sliding and {G}o}, year = {1995}, keywords = {Coin-Sliding game}, } @InBook{moews1996, author = {Moews, David}, title = {Loopy Games and {G}o}, pages = {259-272}, year = {1996}, keywords = {go, combinatorial, loopy}, booktitle = {Games of No Chance}, publisher = {Cambridge University Press}, url = {http://www.msri.org/publications/books/Book29/files/moloopy.pdf}, } @Misc{mueller-prove1995, author = {M\"uller-Prove, Matthias}, title = {Lebende {B}l\"ocke beim {G}o - Ein formaler {A}nsatz unter {V}erwendung von {P}etri-{N}etzen}, year = {1995}, organization = {Universit\"at Hamburg}, note = {In German}, url = {http://www.mprove.de/script/95/studienarbeit/Studienarbeit.pdf}, } @Misc{mueller1991, author = {M\"uller, Martin}, title = {Measuring the performance of {G}o programs}, year = {1991}, howpublished = {International Go Congress, Beijing}, keywords = {rating}, url = {http://www.cs.ualberta.ca/~mmueller/ps/mueller91a.ps}, } @Misc{mueller1991b, author = {M\"uller, Martin}, title = {Pattern Matching in Explorer}, year = {1991}, howpublished = {Game Playing System Workshop, ICOT, Tokyo}, keywords = {Explorer, pattern matching}, url = {http://www.cs.ualberta.ca/~mmueller/ps/mueller91b.ps}, } @Misc{mueller1993, author = {M\"uller, Martin}, title = {Game Theories and Computer {G}o}, year = {1993}, howpublished = {{G}o and Computer Science Workshop (GCSW'93), INRIA, Sophia-Antipolis}, keywords = {combinatorial game theory,}, url = {http://www.cs.ualberta.ca/~mmueller/ps/mueller93.ps}, } @PhdThesis{mueller1995, author = {M\"uller, Martin}, title = {Computer {G}o as a Sum of Local Games: An Application of Combinatorial Game Theory}, year = {1995}, school = {ETH Z\"urich}, keywords = {combinatorial game theory, Smart game board, board partition, unconditional life}, url = {ftp://ftp.inf.ethz.ch/pub/publications/dissertations/th11006.ps.gz}, } @InBook{mueller1996a, author = {M\"uller, Martin and Gasser, Ralph}, title = {Experiments in Computer {G}o Endgames}, year = {1996}, pages = {273-284}, keywords = {go, endgame, ko, explorer}, booktitle = {Games of No Chance}, publisher = {Cambridge University Press}, url = {http://www.msri.org/publications/books/Book29/files/muller.pdf}, } @TechReport{mueller1996b, author = {M\"uller, Martin and Berlekamp, Elwyn and Spight, Bill}, title = {Generalized Thermography: Algorithms, Implementation, and Application to {G}o Endgames}, year = {1996}, institution = {ICSI, Berkeley}, number = {96-030}, keywords = {thermography, combinatorial game theory, Ko}, url = {http://www.cs.ualberta.ca/~mmueller/ps/tr-96-030a.ps.gz}, } @InProceedings{mueller1997b, author = {M\"uller, Martin}, title = {Playing it Safe: Recognizing Secure Territories in Computer {G}o by Using Static Rules and Search}, year = {1997}, booktitle = {Game Programming Workshop in Japan '97, MATSUBARA, H. (ed.), Computer Shogi Association, Tokyo, Japan}, keywords = {static, search, unconditional life}, url = {http://www.cs.ualberta.ca/~mmueller/ps/gpw97.ps.gz}, } @InBook{mueller1998, author = {M\"uller, Martin}, title = {Computer {G}o: A Research Agenda}, crossref = {cg1998}, pages = {252-264}, url = {http://www.cs.ualberta.ca/~mmueller/ps/cg1998.ps.gz}, keywords = {Review}, abstract = { The field of Computer Go has seen impressive progress over the last decade. However, its future prospects are unclear. This paper suggests that the obstacles to progress posed by the current structure of the community are at least as serious as the purely technical challenges. To overcome these obstacles, I develop three possible scenarios, which are based on approaches used in computer chess, for building the next generation of Go programs. } } @TechReport{mueller1999, author = {M\"uller, Martin}, title = {Partial Order Bounding: Using Partial Order Evaluation in Game Tree Search}, year = {1999}, institution = {Electrotechnical Laboratory, Tsukuba, Japan}, number = {TR-99-12}, keywords = {partial order bounding, semeai}, url = {http://www.cs.ualberta.ca/~mmueller/ps/TR9912.ps.gz}, } @Article{mueller1999b, author = {M\"uller, Martin}, title = {Computer {G}o: A Research Agenda}, year = {1999}, journal = {ICCA Journal}, volume = {22(2)}, pages = {104-112}, url = {http://www.cs.ualberta.ca/~mmueller/ps/icca1999.ps}, } @InProceedings{mueller1999c, author = {M\"uller, Martin}, title = {Decomposition Search: A Combinatorial Games Approach to Game Tree Search, with Applications to Solving {G}o Endgames}, year = {1999}, booktitle = {IJCAI-99}, volume = {1}, pages = {578-583}, keywords = {decomposition search, combinatorial game theory}, url = {http://www.cs.ualberta.ca/~mmueller/ps/ijcai1999.ps.gz}, } @TechReport{mueller1999d, author = {M\"uller, Martin}, title = {Proof-Set Search}, year = {1999}, institution = {Electrotechnical Laboratory, Tsukuba, Japan}, number = {TR-99-20}, keywords = {proof-set serach, transposition, proof-number search}, url = {http://www.cs.ualberta.ca/~mmueller/ps/pss-tr01-09.ps.gz}, } @InProceedings{mueller1999e, author = {M\"uller, Martin}, title = {Race to Capture: Analyzing Semeai in {G}o}, year = {1999}, booktitle = {Game Programming Workshop in Japan '99, MATSUBARA, H. (ed.), Computer Shogi Association, Tokyo, Japan}, keywords = {capturing race, semeai}, url = {http://www.cs.ualberta.ca/~mmueller/ps/gpw99.ps.gz}, } @InProceedings{mueller2000, author = {M\"uller, Martin}, title = {Not like other games - why tree search in {G}o is different}, year = {2000}, booktitle = {Fifth Joint Conference on Information Sciences (JCIS 2000)}, note = {Extended abstract, invited paper for special session on Heuristic Search and Computer Game Playing. To appear.}, keywords = {minimax, search, pass, ko, terminal position}, url = {http://www.cs.ualberta.ca/~mmueller/ps/jcis2000.ps.gz}, } @InProceedings{mueller2000c, author = {M\"uller, Martin}, title = {Review: Computer {G}o 1984--2000}, crossref = {cg2000}, pages = {405-413}, keywords = {Review, Go programs}, url = {http://www.cs.ualberta.ca/~mmueller/ps/CGGo2000.ps.gz}, abstract = { Computer Go is maybe the biggest challenge faced by game programmers. Despite considerable work and much progress in solving specific technical problems, overall playing strength of Go programs lags far behind most other games. This review summarizes the development of computer Go in recent years and points out some areas for future research. } } @Article{mueller2001, author = {M\"uller, Martin}, title = {Computer {G}o}, year = {2002}, journal = {Artificial Intelligence}, volume = {134}, pages = {145-179}, keywords = {survey}, url = {http://www.cs.ualberta.ca/~mmueller/ps/Go2000.ps.gz}, } @Article{mueller2001b, author = {M\"uller, Martin}, title = {Global and local game tree search}, year = {2001}, journal = {Information Sciences}, volume = {135}, pages = {187-206}, note = {The URL links to an older version of the article.}, keywords = {Local search, Game tree search, Decomposition search, Combinatorial game theory}, url = {http://www.cs.ualberta.ca/~mmueller/ps/mueller-infsci2000.ps.gz} } @Article{mueller2001c, author = {M\"uller, Martin}, title = {Partial Order Bounding: A new Approach to Evaluation in Game Tree Search}, year = {2001}, journal = {Artificial Intelligence}, volume = {129}, number = {1-2}, pages = {279-311}, keywords = {game tree search, partial order evaluation, partial order bounding}, url = {http://www.cs.ualberta.ca/~mmueller/ps/mueller-aij-rev2.ps.gz}, } @InProceedings{mueller2002, author = {M\"uller, Martin}, title = {Multicriteria Evaluation in Computer Game-Playing, and its Relation to {AI} Planning}, year = {}, crossref = {aips2002}, keywords = {planning}, url = {http://www.laas.fr/aips/ws-tu1.pdf}, } @Article{mueller2002b, author = {M\"uller, Martin}, title = {Computer {G}o}, year = {2002}, journal = {Artificial Intelligence}, volume = {134}, number = {1-2}, pages = {145-179}, keywords = {Go programs, game tree search, knowledge representation}, } @InProceedings{mueller2004, author = {Martin M\"uller and Markus Enzenberger and Jonathan Schaeffer}, title = {Temperature discovery search}, booktitle = {19th National Conference on Artificial Intelligence (AAAI 2004)}, pages = {658-663}, year = {2004}, address = {San Jose, CA}, url = {http://www.cs.ualberta.ca/~mmueller/ps/AAAI104MullerM.pdf}, keywords = {Temperature Discovery Search, combinatorial games, alpha-beta algorithm, Go, Amazons}, abstract = { Temperature Discovery Search (TDS) is a new minimax-based game tree search method designed to compute or approximate the temperature of a combinatorial game. TDS is based on the concept of an enriched environment, where a combinatorial game G is embedded in an environment consisting of a large set of simple games of decreasing temperature. Optimal play starts in the environment, but eventually must switch to G. TDS finds the temperature of G by determining when this switch must happen. Both exact and heuristic versions of TDS are described and evaluated experimentally. In experiments with sum games in Amazons, TDS outperforms an alpha-beta searcher. } } @InProceedings{munos2007, author = {Pierre-Arnaud Coquelin, R\'emi Munos}, title = {Bandit Algorithms for Tree Search}, booktitle = {23rd Conference on Uncertainty in Artificial Intelligence, UAI 2007, University of British Columbia, Vancouver}, year = {2007}, month = {May}, url = {http://hal.inria.fr/docs/00/15/02/07/PDF/BAST.pdf}, keywords = {UCT, Flat-UCB, BAST, Bandit Algorithm for Smooth Trees}, abstract = { Bandit based methods for tree search have recently gained popularity when applied to huge trees, e.g. in the game of go [Gelly et al., 2006]. Their efficient exploration of the tree enables to return rapidly a good value, and improve precision if more time is provided. The UCT algorithm [Kocsis and Szepesvari, 2006], a tree search method based on Upper Confidence Bounds (UCB) [Auer et al. 2002], is believed to adapt locally to the effective smoothness of the tree. However, we show that UCT is ``over-optimistic'' in some sense, leading to a worst-case regret that may be very poor. We propose alternative bandit algorithms for tree search. First, a modification of UCT using a confidence sequence that scales exponentially in the horizon depth is analyzed. We then consider Flat-UCB performed on the leaves and provide a finite regret bound with high probability. Then, we introduce and analyze a Bandit Algorithm for Smooth Trees (BAST) which takes into account actual smoothness of the rewards for performing efficient ``cuts'' of sub-optimal branches with high confidence. Finally, we present an incremental tree expansion which applies when the full tree is too big (possibly infinite) to be entirely represented and show that with high probability, only the optimal branches are indefinitely developed. We illustrate these methods on a global optimization problem of a continuous function, given noisy values. } } @InProceedings{nagai1998, author = {Nagai, Ayumu}, title = {A new AND/OR Tree Search Algorithm Using Proof Number and Disproof Number}, booktitle = {Complex Games Lab Workshop}, editor = {Frank, Ian and Matsubara, Hitoshi and Tajima, Morihiko and Yoshikawa, Atsushi and Grimbergen, Reijer and M\"uller, Martin}, organization = {Electrotechnical Laboratory, Machine Inference Group, Tsukuba, Japan}, year = {1998}, url = {http://www.cs.ualberta.ca/~mmueller/cgo/cg98-workshop/Nagai.pdf}, keywords = {search, proof number, PDS}, } @InProceedings{nakamura1997, author = {Nakamura, Teigo}, title = {Acquisition of Move Sequence Patterns from Game Record Database Using n-gram Statistics}, booktitle = {Game Programming Workshop 97}, year = {1997}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/gpw97.pdf} } @InProceedings{nakamura1999, author = {Nakamura, Teigo and Kajiyama, Takashi}, title = {Automatic Acquisition of Move Sequence Patterns from Encoded Strings of {G}o Moves}, booktitle = {Game Informatics}, volume = {GI-1-15}, year = {1999}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/gi99.pdf} } @InProceedings{nakamura1999b, author = {Nakamura, Teigo and Kajiyama, Takashi}, title = {Constructing A Stochastic Model for Encoded Strings of {G}o Moves}, booktitle = {Game Programming Workshop}, year = {1999}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/gpw99.pdf} } @InProceedings{nakamura2000, author = {Nakamura, Teigo and Kajiyama, Takashi}, title = {Feature Extraction from Encoded Texts of Moves and Categorization of Game Records}, booktitle = {Game Informatics}, volume = {GI-2-11}, year = {2000}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/gi00a.pdf} } @InProceedings{nakamura2000b, author = {Nakamura, Teigo and Kajiyama, Takashi}, title = {Acquisition of Sequence Patterns and their Co-occurrence Relations from Game Records of {G}o}, booktitle = {Game Informatics}, volume = {GI-4-10}, year = {2000}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/gi00b.pdf} } @TechReport{nakamura2002, author = {Teigo Nakamura and Elwyn Berlekamp}, title = {Analysis of Composite Corridors}, institution = {International Computer Science Institute, Berkeley}, year = {2002}, month = {February}, number = {TR-02-005}, keywords = {Combinatorial game theory, corridors, decomposition, multiple invasions theorem}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/tr-02-005.pdf} } @Article{nakamura2002b, author = {Teigo Nakamura}, title = {Acquisition of Move Sequence Patterns from Encoded Strings of {G}o Moves}, journal = {IPSJ Journal}, year = {2002}, volume = {43}, number = {10}, pages = {3030-3039}, note = {In Japanese.}, } @Misc{nakamura2002c, author = {Teigo Nakamura}, title = {Analysis of Ko}, howpublished = {Draft. Available from the author's homepage}, year = {2002}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/KoAnalysis.txt}, } @TechReport{nakamura2003, author = {Teigo Nakamura}, title = {Counting Liberties in Capturing Races using Combinatorial Game Theory}, institution = {IPSJ SIG Notes Game Informatics GI-9-5}, year = {2003}, note = {In Japanese.}, } @InProceedings{nakamura2003b, author = {Teigo Nakamura}, title = {Analysis of Capturing Races with Shared Liberties}, booktitle = {Game Programming Workshop 2003}, year = {2003}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/gpw03.pdf} } @Misc{nakamura2003c, author = {Teigo Nakamura}, title = {Brief Introduction to the Papers about {G}o in 2002}, howpublished = {CGF Journal Vol.5}, year = {2003}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/article2.pdf}, } @Article{nakamura2003d, author = {Teigo Nakamura}, title = {Combinatorial Game Theory and the Game of {G}o - Analyzing Semeai}, journal = {CGF Journal}, year = {2003}, volume = {5}, note = {In Japanese.}, url = {http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/article1.pdf} } @Misc{nakamura2005, author = {Teigo Nakamura}, title = {On Counting Liberties in Capturing Races of {G}o}, howpublished = {BIRS Combinatorial Game Theory Workshop; Presentation slides}, month = {June}, year = {2005}, url = {http://www.dumbo.ai.kyutech.ac.jp/~teigo/GoResearch/cgtw05banff.pdf} } @Article{nakamurak2004, author = {Katsuhiko Nakamura}, title = {Static analysis based on formal models and incremental computation in {G}o programming}, journal = {Theoretical Computer Science}, year = {2004}, note = {TCS special issue Computers and Games}, keywords = {incremental computation, set operation, Euler's formula, life and death, capturing race, semeai graph} } @Misc{naica-loebell2002, author = {Naica-Loebell, Andrea}, title = {Gro\"sartiges {T}estumfeld f\"ur k\"unstliche {I}ntelligenz}, year = {2002}, organization = {Online magazine Telepolis}, note = {In German}, keywords = {Michael Reiss, Martin Mueller, Bruno Bouzy}, url = {http://heise.de/tp/deutsch/inhalt/lis/12325/1.html}, } @Misc{newscientist1992, title = {It is all {G}o against computers}, howpublished = {New Scientist vol 135 issue 1831 - 25 July 92, page 11}, year = {1992}, keywords = {European Computer Go Championship, Canterbury, Allan Scarff} } @MastersThesis{nijhuis2006, author = {Emil H.J. Nijhuis}, title = {Learning Patterns in the Game of {G}o}, school = {Universiteit van Amsterdam}, year = {2006}, month = {December}, url = {http://www.science.uva.nl/research/ias/alumni/m.sc.theses/theses/EmilNijhuis.pdf}, keywords = {Support Vector Machines, Common Fate Graph}, abstract = { This thesis introduces concepts for learning expert human positional classifiers in the game of Go. While most studies in the field of Go focus on learning methods to find the best move, this thesis focuses on learning methods for evaluating the quality of Go stones in a position. A data set of 2,638 Go Tesuji problems has been created. For these problems expert human classifiers have been recorded using a first order logic annotation extension developed for the current standardized format SGF (Smart Go File). The learning of the human classifiers has been conducted with Support Vector Machines using low level features such as the Relative Subgraph Features (RSF) from the Common Fate Graph (CFG). Relative Subgraph Path Features (RSPF) have been developed for learning connectivity and proved to be an appropriate representation for the learning task. } } @MastersThesis{niu2004, author = {Xiaozhen Niu}, title = {Recognizing safe territories and stones in computer {G}o}, school = {Department of Computing Science, University of Alberta}, year = {2004}, keywords = {Safety solver, search, region-merging, weakly dependent regions, Explorer, GNU Go}, url = {http://www.cs.ualberta.ca/~games/go/seminar/notes/040225/thesis.pdf}, abstract = { Computer Go is a most challenging research domain in the field of Artificial Intelligence. Go has a very large branching factor, and whole board evaluation in Go is hard. Even though many game-tree search methods have been successfully implemented in other games such as chess and checkers, the AI community has not yet created a strong Go program due to the above two reasons. Currently most Go-playing programs use a combination of search and heuristics based on an influence function to determine whether territories are safe. However, to assure the correct evaluation of Go positions, the safety of stones and territories must be proved by an exact method. This thesis describes new, better search-based techniques including region-merging and a new method for efficiently solving weakly dependent regions for solving the safety of stones and territories. The improved safety solver has been tested in several Go endgame test sets. The performance is compared in the Go program Explorer and the state of the art Go program GNU Go. } } @InProceedings{niu2004b, author = {Xiaozhen Niu and Martin M\"uller}, title = {An improved safety solver for {C}omputer {G}o}, booktitle = {Computers and Games 2004, Ramat-Gan, Israel}, year = {2004}, url = {http://www.cs.ualberta.ca/~games/go/seminar/notes/040225/safety.pdf}, keywords = {safety, territory, exact, regions}, abstract = { Most Go-playing programs use a combination of search and heuristics based on an influence function to determine whether territories are safe. However, to assure the correct evaluation of Go positions, the safety of stones and territories must be proved by an exact method. The first exact algorithm, due to Benson [1], determines the unconditional safety of stones and territories. M\"uller [3] develops static rules for detecting safety by alternating play, and introduces search-based methods. This paper describes new, stronger search-based techniques including region-merging and a new method for efficiently solving weakly dependent regions. In a typical final position, more than half the points on the board can be proved safe by our current solver. This almost doubles the number of proven points compared to the 26.4\% reported in [3]. } } @InProceedings{niu2005, author = {Xiaozhen Niu and Akihiro Kishimoto and Martin M\"uller}, title = {Recognizing seki in computer {G}o}, booktitle = {11th Advances in Computer Games Conference}, year = {2005}, url = {http://www.cs.ualberta.ca/~mmueller/ps/seki.pdf}, keywords = {Seki, local search, global-level static analysis}, abstract = { Seki is a situation of coexistence in the game of Go, where neither player can profitably capture the opponent's stones. This paper presents a new method for deciding whether an enclosed area is or can become a seki. The method combines local search with global-level static analysis. Local search is used to identify possible seki, and reasoning on the global level is applied to determine which stones are safe with territory, which coexist in a seki and which are dead. Experimental results show that a safety-of-territory solver enhanced by this method can successfully recognize a large variety of local and global scale test positions related to seki. In contrast, the well-known program GNU Go can solve only easier problems from a test collection. } } @InProceedings{niu2006, author = {Xiaozhen Niu and Martin M\"uller}, title = {An open boundary safety-of-territory solver for the game of {G}o}, booktitle = {5th Conference on Computer and Games, CG2006}, year = {2006}, url = {http://www.cs.ualberta.ca/~mmueller/ps/safetysolver2.pdf}, keywords = {safety solver, open boundary problems}, abstract = { This paper presents SAFETY SOLVER 2.0, a safety-of-territory solver for the game of Go that can solve problems in areas with open boundaries. Previous work on assessing safety of territory has concentrated on regions that are completely surrounded by stones of one player. SAFETY SOLVER 2.0 can identify open boundary problems under real game conditions, and generate moves for invading or defending such areas. Several search enhancements improve the solver's performance. The experimental results demonstrate that the solver can find good moves in small to medium-size open boundary areas. } } @Article{ouchi2005, author = {Yasuomi Ouchi, Toshihiko Kanno, Etsuji Yoshikawa, Masami Futatsubashi, Hiroyuki Okada, Tatsuo Torizuka and Mitsuo Kaneko}, title = {Neural substrates in judgment process while playing {G}o: a comparison of amateurs with professionals}, journal = {Cognitive Brain Research}, year = {2005}, volume = {23/2-3}, pages = {164-170}, month = {May}, abstract = { A professional go player shows incomparable ability in judgment during go game. Positron emission tomography (PET) was used to investigate the neural substrates of professional go player's judgment process. Eight professional go players and six amateur players were instructed to think over silently in the opening-stage game (fuseki, territorial planning) problems and the life-or-death (tsume, checkmate judgment) problems presented on the monitor in front of them for 60 s of H_2^15 O PET scans and to state the answer afterwards. We found that in the territorial planning problems the parietal activation was equally observed in both groups with the additional prefrontal activation in the amateur group, and in the checkmate-decision problems the precuneus and cerebellum were activated in professionals while the premotor and parietooccipital cortices (visuospatial processing region) were extensively activated in amateurs. The comparison of the two groups showed stronger activations in the precuneus and cerebellum in the professionals in contrast to the premotor activation in amateurs during checkmate judgment. In addition, the cerebellum was remarkably activated in the higher ranking professional players. These findings suggested the cerebellum and precuneus play important roles in processing of accurate judgment by visual imagery and nonmotor learning memory processes in professional go players. } } @InProceedings{park2005, author = {Hyun-Soo Park and Kyung-Woo Kang and Hang-Joon Kim}, title = {Judgment of Static Life and Death in Computer {G}o Using String Graph}, booktitle = {Lecture Notes in Computer Science}, pages = {543-551}, year = {2005}, volume = {3611}, month = {July}, publisher = {Springer}, abstract = { A String Graph(SG) and Alive String Graph(ASG) were defined to facilitate a static analysis of completed and counted games of Go. For the judgment of life and death, rules are applied to the situation where a stone is included and not included, and these rules are defined as a String Reduction (SR), Empty Reduction (ER), Edge Transform (ET), and Circular Graph (CG) when the stone is not included, and a Dead Enemy String Reduction (DESR) and Same Color String Reduction (SCSR) when the stone is included. Whether an SG is an ASG or not is then determined using these rules. The performance of the proposed method was tested using a problem set of games played by professional players, and all the games had been played to completion and counted. The experiment determined the error on the judgment of life and death. The test was performed on the final positions of the 20 games. The total number of stones was 5,367 and the number of strings was 772. The experimental results produced a very low error ratio for the judgment of static life and death, where the error ratio for the stones was 0.18\% and that for the strings was 1.16\%. } } @Article{park2005b, author = {Hyun-Soo Park and Kyung-Woo Kang}, title = {Evaluation of Strings in Computer {G}o Using Articulation Points Check and Seki Judgment}, journal = {LNAI}, year = {2005}, volume = {3089}, keywords = {String Graph, Articulation Points, Seki, Evaluation}, url = {http://203.246.74.213/38090197.pdf}, abstract = { The purpose of this paper is to judge life and death in computer Go using Articulation Point Check(APC), Seki judgment and rules. To make static analysis possible, the researchers define a String Graph (SG) and judge the life and death of the strings using the rules. To judge the life and death of the strings, the researchers will adopt the APC Rule because it will judge life and death according to the numbers of the junctures. The researchers also suggest that Seki Rules be applied to judge Seki. By excluding Stones and using a String Graph (SG), the researchers postulate the use of SR (String Reduction), ER (Empty Reduction), ET (Edge Transformation) Rules, or CG (Circular Graph) in judging life and death. In addition, the DESR (Dead Enemy Strings Reduction) Rule was used when the dead enemy Stones were involved. Moreover, the SCSR (Same Color String Reduction) Rule was used when the dead enemy and Stones were empty and abridged. If our forces were involved in, the researchers abridged the String Graph by using SCSR (Same Color String Reduction) Rule and judged whether it was ASG(Alive String Graph) or not. The data that were used in the experiment were 31 IGS counted items among the Computer Go Test Collection composed of 11,191 points and 1,123 strings. The division of points and strings yielded 100\% accuracy. } } @Misc{pearson2002, author = {Pearson, Helen}, title = {Chess and {G}O no-brainers?}, year = {2002}, howpublished = {Nature Science Update}, keywords = {Brain scans, IQ, human intelligence, Go, chess}, } @InProceedings{pell1991, author = {Pell, Barney}, title = {Exploratory Learning in the Game of {G}o}, year = {1991}, booktitle = {Heuristic Programming in Artificial Intelligence 2: The 2nd Computer Olympiad}, publisher = {Ellis-Horwood}, keywords = {go, learning, exploration, probability}, url = {http://www.cl.cam.ac.uk/ftp/papers/reports/TR275-bdp-go.ps.gz}, } @TechReport{perezbergquist2001, author = {Perez-Bergquist, Andres Santiago}, title = {Applying {ESP} and Region Specialists to Neuro-Evolution for {G}o}, year = {2001}, institution = {The University of Texas at Austin, Department of Computer Sciences}, number = {CS-TR-01-24}, keywords = {Neural networks, ESP, SANE, GnuGo.}, url = {http://www.cs.utexas.edu/ftp/pub/techreports/tr01-24.pdf}, } @Misc{purkayastha2003, author = {Dev Purkayastha}, title = {Survey and Synthesis of {G}o-playing Agents}, howpublished = {Available by Internet.}, year = {2003}, url = {http://www.people.fas.harvard.edu/~purkayas/go-survey.pdf} } @InProceedings{raiko2004, author = {Raiko, Tapani}, title = {The {G}o-Playing Program Called {G}o81}, booktitle = {Proceedings of the Finnish Artificial Intelligence Conference, STeP 2004}, year = {2004}, keywords = {Go, swarm intelligence, PalmOS}, url = {http://www.cis.hut.fi/praiko/papers/go_step.pdf}, abstract = { Go is an ancient game, for which it has proven to be very difficult to create an artificial player. Go81 is yet another try in that direction. The main idea is as follows: firstly, create a so called ant that tries to play as well as possible, given that it has to be very fast and slightly randomized. Secondly, use these ants to play the game from the current state to the end several times and make use of the information from these possible futures. This approach avoids the evaluation of an unfinished game, which is perhaps the one thing that makes computer Go so difficult. Two versions of Go81, one for Palm and one for a Linux console, are tested against a shareware program AIGO for Palm and an open source project GNU Go accordingly. The Palm version is as strong as AIGO and the console version is two stones weaker than GNU Go on a 9 by 9 board. The proposed approach can also be used to generate interesting data to be studied with machine learning techniques. } } @InProceedings{raiko2005, author = {Raiko, Tapani}, title = {Nonlinear Relational {M}arkov Networks with an Application to the Game of {G}o}, booktitle = {15th International Conference on Artificial Neural Networks, ICANN 2005}, pages = {989-996}, year = {2005}, url = {http://www.cis.hut.fi/praiko/papers/icann05.pdf}, keywords = {joint probabilistic model, relational database, discrete and continuous attributes, relational Markov networks}, abstract = { It would be useful to have a joint probabilistic model for a general relational database. Objects in a database can be related to each other by indices and they are described by a number of discrete and continuous attributes. Many models have been developed for relational discrete data, and for data with nonlinear dependencies between continuous values. This paper combines two of these methods, relational Markov networks and hierarchical nonlinear factor analysis, resulting in joining nonlinear models in a structure determined by the relations in the data. The experiments on collective regression in the board game go suggest that regression accuracy can be improved by taking into account both relations and nonlinearities. } } @InProceedings{ralaivola2005, author = {L. Ralaivola, L. Wu, P. Baldi}, title = {{SVM} and pattern-enriched common fate graphs for the game of {G}o}, booktitle = {European Symposium on Artificial Neural Networks, Bruges, Belgium}, year = {2005}, url = {http://eprints.pascal-network.org/archive/00001460/01/gopaper.pdf}, keywords = {common fate graph, support vector machine}, abstract = { We propose a pattern-based approach combined with the concept of Enriched Common Fate Graph for the problem of classifying Go positions. A kernel function for weighted graphs to compute the similarity between two board positions is proposed and used to learn a support vector machine and address the problem of position evaluation. Numerical simulations are carried out using a set of human played games and show the relevance of our approach. } } @InProceedings{ramon2000, author = {Ramon, Jan and Francis, Tom and Blockeel, Hendrik}, title = {Learning a {G}o heuristic with {T}ilde}, crossref = {cg2000}, pages = {151-169}, keywords = {Machine Learning, Go, Decision trees, Inductive Logic Programming, Tsume-Go}, url = {http://www.cs.kuleuven.ac.be/~janr/}, abstract = { In Go,an important factor that hinders search is the large branching factor, even in local problems. Human players are strong at recognizing frequently occurring shapes and vital points. This allows them to select the most promising moves and to prune the search tree. In this paper we argue that many of these shapes can be represented as relational concepts. We present an application of the relational learner TILDE in which we learn a heuristic that gives values to candidate-moves in tsume-go (life and death) problems. Such a heuristic can be used to limit the number of evaluated moves. Even if all moves are evaluated, alpha-beta search can be sped up considerably when the candidate-moves are approximately ordered from good to bad. We validate our approach with experiments and analysis. } } @InProceedings{ramon2001, author = {Ramon, Jan and Blockeel, Hendrik}, title = {A survey of the application of machine learning to the game of {G}o}, booktitle = {First International Conference on Baduk}, pages = {1-10}, year = {2001}, editor = {Hahn and Sang-Dae}, month = {May}, organization = {Myong-ji University, Korea}, url = {http://www.cs.kuleuven.ac.be/~dtai/publications/files/36228.ps.gz}, keywords = {Machine learning, inductive logic programming}, abstract = { Unlike other games such as chess, draughts and backgammon, computers are currently quite weak at the game of go (baduk). Brute force is difficult due to the higher branching factor and game length. Human made algorithms become very complex before even approaching human strength on a subproblem of the game. One possible approach to this challenging problem is to use machine learning to let the program learn and improve without increased human effort. Machine learning has been successful in other games (e.g. draughts, backgammon). In this paper we give an overview of existing techniques. We discuss different aspects of learning, and propose some directions of research. In particular we believe that a first order representation language combined with a multistrategy learning system can achieve much more than what currently exists. } } @InProceedings{ramon2002, author = {Ramon, Jan and Jacobs, Nico and Blockeel, Hendrik}, year = {2002}, editor = {Bowling, M. and Kaminka, G. and Vincent, R.}, title = {{O}pponent modeling by analysing play}, url = {http://www.cs.kuleuven.ac.be/~dtai/publications/files/38667.ps.gz}, booktitle = {Proceedings of Workshop on agents in computer games}, keywords = {Opponent modeling, logical decision tree learning system, Tilde}, abstract = { Opponent modeling is useful for a player both to have a better chance to win and for teaching a novice player. In this paper we discuss opponent modeling by analysing the play of the opponent. We view this as two dual tasks: characterising the play of a particular opponent and recognising an unknown opponent. We learn understandable opponent models with a logical decision tree learning system. We illustrate our approach by an experiment in the game of go and discuss the application of similar ideas in other games. } } @InProceedings{ramon2003, author = {J. Ramon and J. Struyf}, title = {Computer science issues in {B}aduk}, booktitle = {Proceedings of the 2nd International Conference on Baduk}, pages = {163-182}, year = {2003}, editor = {N. Chihyung}, url = {http://www.cs.kuleuven.ac.be/~dtai/publications/files/40886.pdf}, keywords = {Internet Go}, abstract = { In this paper we discuss current issues in computer science and its application to Baduk. We present an overview of the current state of the art in a number of baduk-related domains and applications. Next, we present some suggestions for improvement. In particular we discuss Internet go, including the distribution of baduk information on the net and servers such as Dashn and KGS, training software such as Life and Death, Junsuk(joseki) and related tools and playing programs. We discuss these topics from the viewpoints of both the user and the area of artificial intelligence. } } @InProceedings{ramon2004, author = {J. Ramon and T. Croonenborghs}, title = {Searching for compound goals using relevancy zones in the game of {G}o}, booktitle = {Fourth International Conference on Computers and Games, Ramat-Gan, Israel}, year = {2004}, editor = {van den Herik, J. and Bjornsson, Y. and Netanyahu, N.}, url = {http://www.cs.kuleuven.ac.be/~dtai/publications/files/41320.ps.gz}, keywords = {search, relevancy zone, compund goals}, abstract = { In complex games with a high branching factor, global alpha-beta search is computationally infeasible. One way to overcome this problem, is by using selective goal-directed search algorithms. These goal-directed searches can use relevancy zones to determine which part of the board influences the goal. In this paper, we propose a general method that uses these relevancy zones for searching for compound goals. A compound goal is constructed from less complex atomic goals, using the standard connectives. In contrast to other approaches that treat goals separately in the search phase, compound goal search obtains exact results. } } @InProceedings{reitman1975, author = {Walter Reitman, James Kerwin, Robert Nado, Judith Reitman, and Bruce Wilcox}, title = {Goals and plans in a program for playing {G}o}, booktitle = {ACM Annual Conference}, year = {1975}, keywords = {Plans and Goals, Ill-structured Problems}, abstract = { A program that plays Go provides a basis for analyzing possibilities for extending present AI conceptions of planning and goal structures to problems that are ill-structured, dynamic, multi-person, resource-bound, and highly interactive. The focus is on mechanisms for communicating information and control over time and among a number of interacting processes, in a flexible but coherent manner. Using the capabilities of current computer languages, it is possible to specify planning and goal structures, and appropriate conventions for them, that will accommodate the demands of these increasingly complex and sophisticated problem environments. } } @InProceedings{reitman1975b, author = {Walter Reitman, Bruce Wilcox}, title = {Perception and Representation of Spatial Relations in a Program for Playing {G}o}, booktitle = {ACM Annual Conference}, pages = {37-41}, year = {1975}, abstract = { Observation of human spatial perception suggests several characteristics that may serve as useful guidelines in the design of perception components for artificial intelligence systems. This paper describes one component designed in accordance with these principles, a web perception processor for a Go playing program. After a brief discussion of some basic strategic Go concepts, the paper describes the construction and modification of perceptual webs. Then, using examples from a real game situation, it shows how web structures, and changes in those structures, provide meaningfully organized representations of significant strategic properties in actual play. The paper concludes with some observations on the central significance of perceptual processing for Go programs and human Go players alike. } } @Article{richards1996, author = {Richards, Norman and Moriarty, David and Miikkulainen, Risto}, title = {Evolving Neural Networks to Play {G}o}, year = {1996}, journal = {Applied Intelligence}, keywords = {neural networks, SANE}, url = {http://www.xs4all.nl/~janrem/Artikelen/richards.apin97.ps.gz}, } @InProceedings{rosin1995, author = {Rosin, Christopher D. and Belew, Richard K.}, title = {Methods for Competitive Co-evolution: Finding Opponents Worth Beating}, year = {1995}, booktitle = {6th International Conference on Genetic Algorithms. L.J. Eshelman, ed.}, keywords = {competitive co-evolution, cellular automata, learning, fitness}, url = {http://www-cse.ucsd.edu/users/crosin/}, } @PhdThesis{rosin1997, author = {Rosin, Christopher}, title = {Coevolutionary Search Among Adversaries}, year = {1997}, school = {University of California, San Diego}, keywords = {coevolution, fitness}, url = {http://www-cse.ucsd.edu/users/crosin/}, } @Article{runarsson2005, author = {Thomas Philip Runarsson and Simon Lucas}, title = {Co-evolution versus Self-play Temporal Difference Learning for Acquiring Position Evaluation in Small-Board {G}o}, journal = {IEEE Transactions on Evolutionary Computation}, volume = {9}, month = {December}, year = {2005}, url = {http://cerium.raunvis.hi.is/~tpr/papers/RuLu05.pdf}, abstract = { Two learning methods for acquiring position evaluation for small Go boards are studied and compared. In each case the function to be learned is a position-weighted piece counter and only the learning method differs. The methods studied are temporal difference learning using the self-play gradient-descent method and co-evolutionary learning, using an evolution strategy. The two approaches are compared with the hope of gaining a greater insight into the problem of searching for optimal zerosum game strategies. Using tuned standard setups for each algorithm, it was found that the temporal-difference method learned faster, and in most cases also achieved a higher level of play than co-evolution, providing that the gradient descent step size was chosen suitably. The performance of the co-evolution method was found to be sensitive to the design of the evolutionary algorithm in several respects. Given the right configuration, however, co-evolution achieved a higher level of play than temporal difference learning. Self-play results in optimal play against a copy of itself. A self-play player will prefer moves from which it is unlikely to lose even when it occasionally makes random exploratory moves. An evolutionary player forced to perform exploratory moves in the same way can achieve superior strategies to those acquired through self-play alone. The reason for this is that the evolutionary player is exposed to more varied game-play, because it plays against a diverse population of players. } } @MastersThesis{rutquist2000, author = {Rutquist, Per}, title = {Evolving an Evaluation Function to Play {G}o}, year = {2000}, school = {Ecole Polytechnique}, keywords = {evolution, genetic algorithms, temporal differences, GNU Go}, url = {http://www.eeaax.polytechnique.fr/papers/theses/per.ps.gz}, } @MastersThesis{rydberg1995, author = {Rydberg, Henrik}, title = {{GoLife I} - A program that plays {G}o}, year = {1995}, school = {Chalmers University of Technology, Gothenburg, Sweden}, keywords = {quality function}, url = {http://web.comhem.se/~u70903172/Codes/Golife/golife.pdf}, } @TechReport{sanechika1991a, author = {Sanechika, Noriaki and Oki, Hiroaki and Yoshikawa, S. and Yoshioka, T. and Uchida, S.}, title = {``Go Generation'' A {G}o Playing System}, year = {1991}, institution = {ICOT, Japan}, number = {TR545}, url = {http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tr-list-E.html}, } @TechReport{sanechika1991b, author = {Sanechika, Noriaki and Oki, Hiroaki and Akaosugi, Takashi and Sei, Shinichi}, title = {Methodology of {GOSEDAI}}, year = {1991}, institution = {ICOT, Japan}, number = {TR717}, url = {http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tr-list-E.html}, } @TechReport{sanechika1991c, author = {Sanechika, Noriaki}, title = {The Specifications of ''{G}O Generation''}, year = {1991}, institution = {ICOT, Japan}, number = {TR720}, url = {http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tr-list-E.html}, } @InProceedings{sanechika1997, author = {Sanechika, Noriaki and Tajima, Morihiko}, title = {Pruning Candidate Moves in the Game of {G}o by ({KPV}) Reasoning about Evaluation Components}, year = {1997}, booktitle = {Game Programming Workshop in Japan 1997}, keywords = {pruning, KPV, knowledge of position variation, NV-cut, no variation cut}, url_ = {http://www.etl.go.jp/etl/divisions/~tazima/references.html}, } @InProceedings{sanechika1999, author = {Sanechika, Noriaki and Tajima, Morihiko and M\"uller, Martin}, title = {Observable Definitions of Fuseki Concepts}, year = {1999}, booktitle = {Game Programming Workshop in Japan (GPW'99)}, note = {In Japanese} } @InProceedings{sanner2007, author = {Scott Sanner and Thore Graepel and Ralf Herbrich and Tom Minka}, title = {Learning {CRF}s with Hierarchical Features: An Application to {G}o}, booktitle = {Proceedings of the Workshop on Constrained Optimization and Structured Output Spaces (at ICML-07)}, year = {2007}, url = {http://www.cs.toronto.edu/~ssanner/Papers/crfgo.pdf}, keywords = {grid-based conditional random fields, hierarchical pattern features, BMA-Tree algorithm}, abstract = { We investigate the task of learning grid-based CRFs with hierarchical features motivated by the task of territory prediction in Go. We first analyze various independent and grid-based CRF classification models and state-of-the-art training/inference algorithms to determine which offers the best performance across a variety of metrics. Faced with the performance drawbacks of independent models and the computational drawbacks of intractable CRF models, we introduce the BMA-Tree algorithm that uses Bayesian model averaging of tree-structured predictors to exploit hierarchical feature structure. Our results demonstrate that BMA-Tree is superior to other independent classi?ers and provides a computationally effcient alternative to intractable grid-based CRF models when training is too slow or approximate inference is inadequate for the task at hand. } } @InProceedings{sasaki1998, author = {Sasaki, Nobusuke and Sawada, Yasuji and Yoshimura, Jin}, title = {A Neural Network Program of {T}sume-{G}o}, crossref = {cg1998}, pages = {167-182}, keywords = {Neural network, tsume-go, back-propagation, unique solution}, abstract = { Go is a difficult game to make a computer program because of the space complexity. Therefore, it is important to explore another approach that does not rely on search algorithms only. In this paper, we focus on tsume-go problems (local Go problems) that have a unique solution. A three-layer neural network program has been developed to find a solution at a given position of tsume-go problems, where the attacker is to kill the defender's territory on a 9x9 board. The network consists of 162 neurons for the input layer, 300 neurons for the middle layer, and 81 neurons for the output layer. We let the network learn the current stone patterns and, hence, process a direct answer. The network learns 2000 patterns of tsume-go by the back-propagation method. Within 500 repeats, the network learns 2000 patterns correctly. We tested the network ability: the top three selected moves contain about 60\% correct answers, and the top five, about 70\% for unknown problems at 500 repeats of learning. We compare the rate of correct answers by the network with that of human players who replied in a few seconds only. The ability of the network is roughly equivalent to 1-dan strength of human player. Application of neural networks for a computer program of tsume-go (and also Go) combined with a pattern classifier might provide a prospective approach to create a strong Go-playing program. } } @InProceedings{sasaki2002, author = {Sasaki, Nobusuke}, title = {Neural Network Systems for Solving {T}sume-{G}o}, year = {2002}, booktitle = {Game Informatics Workshop 2002}, publisher = {Information Processing Society of Japan}, note = {In Japanese}, } @Article{sasaki2003, author = {Sasaki, Nobusuke}, title = {The Gifu Challenge 2003 World Computer-{G}o Championship}, journal = {ICGA Journal}, year = {2003}, volume = {26}, number = {3}, } @InProceedings{schraudolph1994, author = {Schraudolph, Nicol N. and Dayan, Peter and Sejnowski, Terrence J.}, title = {Temporal Difference Learning of Position Evaluation in the Game of {G}o}, year = {1994}, booktitle = {Advances in Neural Information Processing 6}, publisher = {Morgan Kaufmann}, keywords = {go, neural network, temporal difference learning, TD}, url = {http://www.gatsby.ucl.ac.uk/~dayan/papers/sds94.pdf}, } @InBook{schraudolph2000, author = {Schraudolph, Nicol N. and Dayan, Peter and Sejnowski, Terrence J.}, title = {Learning to Evaluate {G}o Positions via Temporal Difference Methods}, year = {2000}, booktitle = {Soft Computing Techniques in Game Playing, Jain L.C. and Baba N. Eds.}, publisher = {Springer Verlag, Berlin}, keywords = {neural network, temporal difference learning}, url = {http://www.gatsby.ucl.ac.uk/~dayan/papers/sds00.pdf}, } @TechReport{sei1991a, author = {Sei, Shinichi and Ichiyoshi, Nobuyuki and Taki, Kazuo}, title = {Experimental Version of Parallel Computer {G}o-Playing System {GOG}}, year = {1991}, institution = {ICOT, Japan}, number = {TR 669}, keywords = {GOG}, url = {http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tr-list-E.html}, } @TechReport{sei1991b, author = {Sei, Shinichi and Oki, Hiroaki and Sanechika, Noriaki and Akaosugi, Takashi and Taki, Kazuo}, title = {Experimental Version of parallel Computer {G}o-Playing Systems {GOG}}, year = {1991}, institution = {ICOT, Japan}, number = {TR718}, keywords = {GOG}, url = {http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tr-list-E.html}, } @InProceedings{sei1998, author = {Sei, Shinichi}, title = {Memory-Based Approach in {G}o-program {KATSUNARI}}, booktitle = {Complex Games Lab Workshop}, editor = {Frank, Ian and Matsubara, Hitoshi and Tajima, Morihiko and Yoshikawa, Atsushi and Grimbergen, Reijer and M\"uller, Martin}, organization = {Electrotechnical Laboratory, Machine Inference Group, Tsukuba, Japan}, year = {1998}, url = {http://www.cs.ualberta.ca/~mmueller/cgo/cg98-workshop/Sei.pdf}, keywords = {pattern, knowledge, KATSUNARI, joseki}, } @InProceedings{sei2000, author = {Sei, Shinichi and Kawashima, Toshiaki}, title = {A Solution of {G}o on 4x4 Board by Game Tree Search Program}, booktitle = {4th Game Informatics Group Meeting in IPS Japan}, pages = {69-76}, year = {2000}, note = {In Japanese. English translation available}, url = {http://homepage1.nifty.com/Ike/katsunari/publications_e.html}, keywords = {solving, solution, small boards}, abstract = { We had made a search program to find a solution of Go on small boards (4x4 or smaller) based on Japanese Go rules. This paper describes the solutions and the method of our program. We found that the solution were a draw on the 4x4 board, victory for black on the 3x3 board, and a draw on the 2x2 board. } } @InBook{shimada1958, author = {Shimada, Takuya}, title = {Problems In Composing {I}go Rules}, year = {1958}, booktitle = {Mathematics of {G}o, Chapter 6}, keywords = {rules, dame, bent four in a corner}, url = {http://www.goban.demon.co.uk/go/shimada/chap6.html}, } @Misc{shotwell2002, author = {Shotwell, Peter}, title = {Reflections on Language and Philosophy in Regard to Cognitive Psychology, Artificial Intelligence and Educational Studies of Chess and {G}o}, howpublished = {Available at http://www.usgo.org}, year = {2002}, abstract = { The first version of this essay appeared in three installments about 15 years ago in the American Go Journal. Admittedly speculative, it surveyed what I found interesting in these fields. First, it explored the differences between traditional Eastern and Western ways of thinking about language and their traditional games of chess and go. It then examined how these differences may affect our understanding of historical and modern developments in cognitive psychology and assist in its future development. It focused particularly on the flaws of the then-popular idea that chess expertise is almost solely the result of learning and storing in long-term memory a great many `patterns' which can be retrieved and applied to a board position, and which can be best studied by memory-recall experiments. Looking further, there was an attempt to catalogue the potential value of go as a better microworld for the study of perception and artificial intelligence. Since then, while a few researchers have used go and have even called for it to replace chess as the new `fruit fly' of artificial intelligence and psychological studies of the acquisition of expertise, chess is still the chief basis for forming theoretical models of how we think when presented with perceptual tasks. What is new in this update is a survey of the very interesting models of thinking that have recently appeared in the field of board game playing. These include two competing Turing Test-like pattern-based computer simulations of how we learn to play chess, some long-term memory- and information processing-based approaches, and some of the preliminary work that is going on about the roles of the brain's hemispheres in board game playing. Despite this work, however, I feel that the reasons for the original background and conclusions have not changed, although they have been augmented and re-organized and the recent work of Delauze and Guattari has been included to further illustrate them. As before, it is left to the reader to decide if those thoughts are interesting, applicable or useful. } } @PhdThesis{siegel2005, author = {Aaron Siegel}, title = {Loopy Games and Computation}, school = {University of California, Berkeley}, year = {2005}, url = {http://www.integraldomain.net/aaron/thesis/thesis.pdf}, keywords = {combinatorial games theory, Go endgames, CGSuite Go Explorer}, abstract = { Over the past three decades, computers have come to play a fundamental role in the study of combinatorial games. This dissertation introduces the first thorough application of computers to loopy games, those in which repetition is permitted. We present several advances in the theory of loopy games and show that, with substantial computational assistance, many such games are just as tractable as their loopfree cousins. Among these advances are several new techniques for simplifying loopy games. These techniques are implemented in the computer algebra system CGSuite. Three case studies are then analyzed that illustrate the power of the new methods: Fox and Geese, Backsliding Toads and Frogs, and Hare and Hounds. All three examples are well-known loopy games that had proved difficult to penetrate by hand. Other theoretical results on loopy games include a study of long cycles, which are sequences of multiple canonical moves that result in repetition; new idempotents in the monoid of loopy games; and some preliminary results on pseudonumbers, a loopy generalization of the surreal numbers. Also included are two results on loopfree games. First is a new construction of the reduced canonical form of G, which is the simplest game infinitesimally close to G. A generalization is also given that applies to certain loopy games. The second result exposes new structure in the lattices Ln of games born by day n: for each n >= 1, L n admits a unique non-trivial automorphism. This automorphism associates to each game G a natural "companion" G?, and the association can be described explicitly. Finally, we discuss the architecture of CGSuite in detail, and we introduce an extension, the CGSuite Go Explorer, designed to facilitate endgame analysis of the Asian board game Go. Go Explorer is the first software to implement dogmatic analysis of hyperactive positions.CGSuite was instrumental to all of these investigations, but in most cases the resulting proofs make no appeal to the computer's output. Loopy games demonstrate, once again, that computational tools can provide valuable mathematical insights, without sacrificing mathematical purity. } } @InProceedings{silver2007, author = {David Silver and Richard Sutton and Martin M\"uller}, title = {Reinforcement learning of local shape in the game of {G}o}, booktitle = {IJCAI 2007}, year = {2007}, url = {http://www.cs.ualberta.ca/~mmueller/ps/silver-ijcai2007.pdf}, keywords = {temporal difference learning}, abstract = { We explore an application to the game of Go of a reinforcement learning approach based on a linear evaluation function and large numbers of binary features. This strategy has proved effective in game playing programs and other reinforcement learning applications. We apply this strategy to Go by creating over a million features based on templates for small fragments of the board, and then use temporal difference learning and self-play. This method identifies hundreds of low level shapes with recognisable significance to expert Go players, and provides quantitive estimates of their values. We analyse the relative contributions to performance of templates of different types and sizes. Our results show that small, translation-invariant templates are surprisingly effective. We assess the performance of our program by playing against the Average Liberty Player and a variety of computer opponents on the 9x9 Computer Go Server. Our linear evaluation function appears to outperform all other static evaluation functions that do not incorporate substantial domain knowledge. } } @InProceedings{silver2007b, author = {Anna Koop and Richard Sutton and David Silver}, title = {On the Role of Tracking in Stationary Environments}, booktitle = {ICML 2007}, year = {2007}, url = {http://www.cs.ualberta.ca/~silver/research/publications/files/tracking.pdf}, keywords = {tracking, temporal-difference, meta-learning, step-size adaptation}, abstract = { It is often thought that learning algorithms that track the best solution, as opposed to converging to it, are important only on non-stationary problems. We present three results suggesting that this is not so. First we illustrate in a simple concrete example, the Black and White problem, that tracking can perform better than any converging algorithm on a stationary problem. Second, we show the same point on a larger, more realistic problem, an application of temporal-difference learning to computer Go. Our third result suggests that tracking in stationary problems could be important for meta-learning research (e.g., learning to learn, feature selection, transfer). We apply a meta-learning algorithm for step-size adaptation, IDBD (Sutton, 1992a), to the Black and White problem, showing that meta-learning has a dramatic long-term effect on performance whereas, on an analogous converging problem, meta-learning has only a small second-order effect. This small result suggests a way of eventually overcoming a major obstacle to meta-learning research: the lack of an independent methodology for task selection. } } @TechReport{smith1996, author = {Smith, Warren D.}, title = {Hash functions for binary and ternary words}, year = {1996}, institution = {NEC Research Institute, Princeton NJ}, keywords = {hash function}, url = {http://www.neci.nj.nec.com/homepages/wds/works.html}, } @Misc{smithc2004, author = {Smith, Chris}, title = {A {C}omputer-{G}o Board Evaluation Function}, howpublished = {Honors Thesis. Department of Computer Science at Trinity University}, year = {2004}, url = {http://home.comcast.net/~logospathosethos/Honors_Thesis.doc}, keywords = {Evaluation function}, abstract = { This thesis describes a new board evaluation function for the Asian game of Go. By taking a given board position and reducing it to a numerical representation of which player is ahead classical, artificial intelligence tree-searching algorithms can be employed to create computer programs capable of playing Go. Unfortunately because of the enormous complexity of Go, a board evaluation simply cannot be used as the only factor in deciding future moves; however, the board evaluation function presented here aims to extract as much information from the Go board configuration as possible as to be used in conjunction with a move decision module. An analysis of other game playing computer programs'evaluation function presented. } } @InProceedings{spight1998, author = {Spight, William L.}, title = {Extended Thermography for Multiple {K}os in {G}o}, crossref = {cg1998}, pages = {232-251}, keywords = {Ko, multiple Kos, thermography}, abstract = { In evaluating a local position in go, players want to know its current territorial count and the value of a local play. Many go positions are combinatorial games; the mean value of the game corresponds to the count and its temperature corresponds to the value of the play. Thermography finds the mean value and temperature of a combinatorial game. However, go positions often include kos, repetitive positions which are not classical combinatorial games. Thermography has been generalized to include positions containing a single ko. This paper extends thermography further to include positions with multiple kos. It also introduces a method for pruning redundant branches of the game tree. } } @InProceedings{spight2000, author = {Spight, Bill}, title = {Analysis of the 4/21/98 {J}iang-{R}ui endgame}, booktitle = {More Games of No Chance}, pages = {89-105}, year = {2002}, editor = {Richard Nowakowski}, number = {42}, series = {Mathematical Sciences Research Institute Publications}, organization = {Mathematical Sciences Research Institute}, publisher = {Cambridge University Press}, keywords = {Thermographs}, url = {http://www.msri.org/communications/books/Book42/files/spight.pdf}, abstract = { Go thermography is more complex than thermography for classical combinatorial games because of loopy games called kos. In most situations, go rules forbid the loopiness of a ko by banning the play that repeats a position. Because of the ko ban one player may be able to force her opponent to play elsewhere while she makes more than one play in the ko, and that fact gives new slopes to the lines of ko thermographs. Each line of a thermograph is associated with at least one line of orthodox play [Berlekamp 2000, 2001]. Multiple kos require a new definition of thermograph, one based on orthodox play in an enriched environment, rather than on taxes or on composing thermographs from the thermographs of the followers [Spight 1998]. Orthodox play is optimal in such an environment. } } @InProceedings{spight2003, author = {William L. Spight}, title = {Evaluating Kos in a Neutral Threat Environment: Preliminary Results}, booktitle = {Lecture Notes in Computer Science}, pages = {413-428}, year = {2003}, volume = {2883}, abstract = { The idea of a komaster made it possible to use thermography to analyze loopy games, called kos, in Go. But neither player may be komaster. In that case a neutral threat environment permits the construction of thermographs for kos. Using neutral threat environments some hyperactive kos are evaluated and general results are derived for approach kos. } } @InProceedings{stanley2004, author = {Kenneth O. Stanley and Risto Miikkulainen}, title = {Evolving a Roving Eye for {G}o}, booktitle = {Genetic and Evolutionary Computation - GECCO 2004, Part II}, year = {2004}, pages = {1226-1238}, url = {http://www.cs.utexas.edu/users/nn/downloads/papers/stanley.gecco04.pdf}, keywords = {Neural network, input field}, abstract = { Go remains a challenge for artificial intelligence. Currently, most machine learning methods tackle Go by playing on a specific fixed board size, usually smaller than the standard 19x19 board of the complete game. Because such techniques are designed to process only one board size, the knowledge gained through experience cannot be applied on larger boards. In this paper, a roving eye neural network is evolved to solve this problem. The network has a small input field that can scan boards of any size. Experiments demonstrate that (1) The same roving eye architecture can play on different board sizes, and (2) experience gained by playing on a small board provides an advantage for further learning on a larger board. These results suggest a potentially powerful new methodology for computer Go: It may be possible to scale up by learning on incrementally larger boards, each time building on knowledge acquired on the prior board. } } @InProceedings{stern2004, author = {Stern, David and Graepel, Thore and MacKay, David J.C.}, title = {Modelling Uncertainty in the Game of {G}o}, booktitle = {Advances in Neural Information Processing Systems 17}, year = {2004}, url = {http://www.inference.phy.cam.ac.uk/dhs26/publications/nips2004.ps.gz}, keywords = {uncertainty, probability, Markov random field, learning} } @InProceedings{stern2007, author = {David Stern and Ralf Herbrich and Thore Graepel}, title = {Learning to Solve Game Trees}, booktitle = {ICML 2007}, year = {2007}, url = {http://www.machinelearning.org/proceedings/icml2007/papers/394.pdf}, keywords = {probability distributions, game tree search, graphical model} } @PhdThesis{stoutamire1991, author = {Stoutamire, David}, title = {Machine Learning, Game Play, and {G}o}, year = {1991}, school = {Case Western Reserve University}, keywords = {Learning, error function, hash, patterns}, url = {http://david.stoutamire.com/caisr_report.ps}, } @InProceedings{struyf2002, author = {J. Struyf, J. Ramon, H. Blockeel}, title = {Compact representation of knowledge bases in {ILP}}, booktitle = {Inductive Logic Programming, 12th International Conference, ILP 2002}, pages = {254-269}, year = {2003}, editor = {Matwin, S. and Sammut, C.}, volume = {2583}, series = {Lecture Notes in Computer Science}, url = {http://www.cs.kuleuven.ac.be/~dtai/publications/files/38663.ps.gz}, } @InBook{taatgen1994, author = {Taatgen, Niels A.}, title = {The study of learning mechanisms in unified theories of cognition}, year = {1994}, booktitle = {Computers in psychology 5}, publisher = {Lisse, the Netherlands: Swets \& Zeitlinger}, keywords = {cognition, psychology, UTC, Soar}, url = {http://tcw2.ppsw.rug.nl/~niels/publications/cip.ps}, } @InProceedings{tajima1998, author = {Tajima, Morihiko and Sanechika, Noriaki}, title = {Estimating the Possible Omission Number for Groups in {G}o by the Number of n-th Dame}, crossref = {cg1998}, pages = {265-281}, keywords = {PON, possible omission number, strength of groups, n-th dame}, url_ = {http://www.etl.go.jp/etl/divisions/~tazima/references.html}, abstract = { This paper describes a new method for estimating the strength of a group in the game of Go. Although position evaluation is very important in Computer Go, the task is very complex, so good evaluation methods have not yet been developed. One of the major factors in evaluation is the strength of groups. In general, this evaluation is a difficult problem, so it is desirable to have a simple method for making a rough estimate. We define PON (Possible Omission Number) as a precise measure for the strength of groups, and present a simple method for the rough estimation of PON by calculating n-th dame (liberties). We report some experiments indicating the effectiveness of the method. } } @InProceedings{tajima1999, author = {Tajima, Morihiko and Sanechika, Noriaki}, title = {Strategic Placing of Stones in the Opening of {G}o Based on the Possible Omission Number ({PON})}, year = {1999}, booktitle = {Game Programming Workshop in Japan '99}, note = {In Japanese}, keywords = {PON, possible omission number, fuseki}, url_ = {http://www.etl.go.jp/etl/divisions/~tazima/references.html}, } @InBook{tajima2000, author = {Tajima, Morihiko and Sanechika, Noriaki}, title = {An Improvement of the Method on the Strategic Placing of Stones Based on the Possible Omission Number}, year = {2000}, booktitle = {IPSJ SIG Notes, Vol.2000, No.98, pp.85-94}, keywords = {evaluation function, fuseki, strength od groups, possible omission number, PON}, url_ = {http://www.etl.go.jp/etl/divisions/~tazima/references.html}, } @InProceedings{tajima2001, author = {Tajima, Morihiko and Sanechika, Noriaki}, title = {Evaluation of the Method of Position Evaluation in the Opening of {G}o}, year = {2001}, booktitle = {6th Game Programming Workshop in Japan}, note = {In Japanese}, keywords = {collection of problems, evaluation function, fuseki}, url_ = {http://www.etl.go.jp/etl/divisions/~tazima/references.html}, } @Misc{tajima2002, author = {Tajima, Morihiko}, title = {Comparison of the Opening strategies of {G}o: {PON} based vs. Case Based}, year = {2002}, note = {Submitted to CG2002}, } @InBook{takizawa2001, author = {Takizawa, Takenobu}, title = {An Application of Mathematical Game Theory to {G}o Endgames: Some Width-Two-Entrance Rooms With and Without Kos}, year = {2001}, keywords = {endgame, combinatorial game theory, width-two-entrance rooms}, booktitle = {More Games of No Chance}, pages = {107-124}, publisher = {Cambridge University Press}, url = {http://msri.org/publications/books/Book42/files/takizawa.pdf}, abstract = { The author is part of a research group under the supervision of Professor Berlekamp. The group is studying the late-stage endgame of Go and has extended the theory of quasi-loopy games using the concept of a ko-master. This paper discusses some width-two-entrance rooms with and without kos that have arisen in this study. } } @TechReport{talby1997, author = {Talby, David}, title = {Revising Partition Search to Play {G}o}, year = {1997}, institution = {Hebrew University of Jerusalem}, keywords = {Partition search,}, url = {http://www.cs.huji.ac.il/~davidt/done/go/index.html}, } @MastersThesis{tavernier2002, author = {Tavernier, Wouter}, title = {De intelligentie van de toekomst: een praktische en filosofische reflectie over de grenzen en de toekomst van de machine}, year = {2002}, school = {Universiteit Gent}, note = {In Dutch.}, url = {http://studwww.rug.ac.be/~wtaverni/thesis.htm}, } @TechReport{tay2004, author = {Choon Tay}, title = {Solving {G}o on a 3x3 board using temporal-difference learning}, institution = {University of Western Australia}, year = {2004}, note = {Supervisor Cara MacNish}, url = {http://undergraduate.csse.uwa.edu.au/year4/Current/Students/Files/2004/ChoonTay/CorrectedDissertation.pdf}, keywords = {TD-learning}, abstract = { Go is a fascinating game that originated from China more than 3000 years ago. In terms of research effort and programming time spent on Go, it is second only to chess. However, computer Go has been much less successful than computer chess. The main reason lies with the enormous search space, which is approximately 3^(19x19) = 10^170. Another reason is that, until now no one has come out with an evaluation function that accurately describes the Go state. Many AI techniques that were used and worked for other board games were attempted on Go but without equivalent success. Recently, temporal-difference (TD) learning, a form of AI, was successfully applied in TD-Gammon, a backgammon playing program, attaining a level rivaling human grandmasters. Following the successful application of TD learning to backgammon, researchers began studies applying TD learning to Go, achieving the level of a poor commercial program. This has motivated this investigation of TD learning for use in the game of Go. Instead of using neural networks, we used lookup tables to store the utility value for various states of Go. With this limitation, we applied TD learning to a 3x3 Go board. We used TD(0), the simplest form of TD(lambda), and TD-directed(lambda) in our experiments with different learning rates. After training the learning agents for 60000 games, we observed that all agents are learning and some even managed to secure a 100\% win ratio against a non-perfect test agent. This project describes this approach and further enhancements that can be made to solve Go on small boards using TD-learning. } } @InBook{thomsen2000, author = {Thomsen, Thomas}, title = {Lambda-search in game trees -- with application to {G}o}, crossref = {cg2000}, pages = {19-38}, keywords = {Binary tree search, threat-sequences, null-moves, proof-number search, abstract game-knowledge, Go block tactics, lambda-search}, url = {http://www.t-t.dk/publications/index.html}, abstract = { This paper proposes a new method for searching two-valued (binary) game trees in games like chess or Go. Lambda-search uses null-moves together with different orders of threat-sequences (so-called lambda-trees), focusing the search on threats and threat-aversions, but still guaranteeing to find the mini-max value (provided that the game-rules allow passing or zugzwang is not a motive). Using negligible working memory in itself, the method seems able to offer a large relative reduction in search space over standard alpha-beta comparable to the relative reduction in search space of alpha-beta over minimax, among other things depending upon how non-uniform the search tree is. Lambda-search is compared to other resembling approaches, such as null-move pruning and proof-number search, and it is explained how the concept and context of different orders of lambda-trees may ease and inspire the implementation of abstract game-specific knowledge. This is illustrated on open-space Go block tactics, distinguishing between different orders of ladders, and offering some possible grounding work regarding an abstract formalization of the concept of relevancy-zones (zones outside of which added stones of any colour cannot change the status of the given problem). } } @Misc{tromp2006, author = {John Tromp and Gunnar Farneb\"ack}, title = {Combinatorics of {G}o}, howpublished = {Submitted to CG 2006}, year = {2006}, url = {http://homepages.cwi.nl/~tromp/go/gostate.ps}, keywords = {Number of legal positions, number of games, dynamic programming, game tree complexity, base of liberties} } @PhdThesis{upton1998, author = {Robin Upton}, title = {Dynamic Stochastic Control: A New Approach to Tree Search \& Game-Playing}, school = {University of Warwick, UK}, year = {1998}, url = {http://www.robinupton.com/research/phd/Game_Tree_Searching_with_DSC_(Upton,1998).pdf}, keywords = {game tree search, selective search, markov chain model, dynamic stochastic control, PCN*}, abstract = { This thesis demonstrates by example how dynamic stochastic control methods may usefully be applied to tackle problems of tree searching and computer game-playing. Underlying this work is the constant tension between what is optimal in theory and what is implementable in practice. Most of the games studied are solved (under certain conditions) in the sense that a policy is derived which is both optimal and implementable. We examine the various reasons why the general problem of devising an algorithm to play a perfect information game in real time cannot have such a solution, and consider how to respond to this difficulty. } } @misc{urvoy2002, author = {Urvoy, Tanguy}, title = {Pattern Matching in {G}O with {DFA}}, year = {2002}, url = {http://tanguy.urvoy.free.fr/Papers/dfabstract.pdf}, keywords = {Fast pattern matcher, Deterministic Finite State Automata}, abstract = { An important part of knowledge in Go programs is based on two dimensional patterns. When these patterns are used as heuristic in reading algorithms the pattern matching can become time critical. We present a pattern matching algorithm based on Deterministic Finite State Automata. This algorithm and its incremental extension are detailed in gnugo documentation. } } @Misc{veenstra2004, author = {Veenstra, L. and Venghaus, A. and Drake, P.}, title = {Pattern matching in the Game of {G}o}, howpublished = {Poster to be presented at the Thirteenth Regional Conference on Undergraduate Research, Murdock College Research Program at Lewis \& Clark College}, year = {2004}, url = {https://webdisk.lclark.edu/xythoswfs/webui/_xy-13651_1-tid_jDVKYDTf}, } @MastersThesis{vermeulen2002, author = {Vermeulen, Tijs}, title = {Computergo Alternatieve Technieken}, year = {2002}, school = {Universiteit Gent}, note = {In Dutch.}, url = {http://users.pandora.be/tijs.vermeulen/}, } @InProceedings{vila2004, author = {Vila, R. and Cazenave, T.}, title = {When one eye is sufficient}, year = {2003}, booktitle = {Advance in Computer Games 10}, publisher = {Kluwer}, url = {http://www.ai.univ-paris8.fr/~cazenave/eyeLabelling.pdf}, keywords = {eye, neighbour classification, life property}, abstract = { A new classification for eye shapes is proposed. It allows to decide statically the status of the eye in some restricted conditions. The life property enables to decide when one eye shape is alive regardless the number of opponent stones inside. The method is easy to program and can replace a possibly deep search tree with a fast, reliable and static evaluation. } } @TechReport{wangh2004, author = {Harry Wang}, title = {A Temporal Model with Influence and Territory in Computer Go}, institution = {University of California, Santa Cruz}, year = {2004}, month = {May}, url = {http://sluggo.dforge.cse.ucsc.edu/harryMS.pdf}, keywords = {SlugGo, GNU Go, MPI, Influence, Territory}, abstract = { In computer Go programming, utilizing knowledge from look-ahead intelligently is an area worthy of research. Look-ahead in the game of Go using brute-force search is not a feasible option [18]. Even when simple look-ahead is possible, specialized Go game concepts only understood by skilled Go players makes programming computer Go difficult. The authors believe that look-ahead evaluation in computer Go programs should mimic the same behavior of skilled Go players - a dynamic evaluation of influence and territory. In this paper, we describe a way to mimic the look-ahead behavior of skilled Go players in computer Go programs. We achieve this by setting up a temporal model that utilizes future Go board influence data and territorial data to determine the effectiveness of current candidate moves. In this model, we apply an Influence Weighting Curve (IWC) and a Territory Weighting Curve (TWC) to the normalized value of these future influence and territory values. The result of our techniques shows that our approach can increase the winning percentage of our Go program by 48\%. Our temporal model successfully mimics the basic thought process of a skilled Go player. Therefore the technique of using a Influence Weighting Curve (IWC) and a Territory Weighting Curve (TWC) should be applied to any Go programs that involve look-ahead. We applied our technique on SlugGo - a modified version of GNU Go that uses parallel computing techniques. GNU Go is an open-source computer Go program that had won the crown of 2003 Computer Olympiad [9]. After we applied our temporal influence/territory model to SlugGo, we won over 90\% of the games against the official release of GNU Go (version 3.4) after giving it 2 handicaps. } } @MastersThesis{wang2005, author = {Kai Wang}, title = {Improving SlugGo through Hashing and Sub-branching}, school = {University of California, Santa Cruz}, year = {2005}, month = {June}, url = {http://sluggo.dforge.cse.ucsc.edu/kaiMS.pdf}, keywords = {SlugGo, GNU Go}, abstract = { Go, a board game which originated from China, is now very popular in east Asia and gaining its popularity throughout the rest of the world. Due to its large board size (19x19) and complex life-and-death analysis, computer Go is still one of the toughest artificial intelligence problems faced by computer scientists. Even though it has been studied for more than 20 years, computer Go programs still remain at a very low level compared to human players. The SlugGo group at the University of California at Santa Cruz has been working on this problem. Based on GNU Go, the best open source program, a full-board lookahead scheme which simulates the strategy of human players has been implemented to improve the performance of GNU Go. The enhanced GNU Go is called SlugGo. In order to get better performance, SlugGo analyzes several choices provided by GNU Go. To find the best choice from the candidates, SlugGo looks ahead, finding possible responding moves to these choices, until reaching a predetermined depth. By applying this lookahead scheme, SlugGo can play better than GNU Go. In this thesis, two techniques, hashing and sub-branching, are used to further enhance SlugGo. To reduce the time, the hashing technique stores the already calculated board positions and applies them to later calculations. An overall of about 10\% timing performance gain is achieved. The sub-branching technique, rather than branching at the top only, branches to the maximal depth in the game tree allowed by the available computing resources. It is expected that sub-branching can make SlugGo play stronger. However, the preliminary results in this thesis show that further research is needed to improve this scheme. } } @InProceedings{werf2001, author = {van der Werf, Erik and van den Herik, Jaap}, title = {Visual Learning in {G}o}, year = {2001}, booktitle = {The CMG 6th Computer Olympiad Computer-Games Workshop Proceedings}, keywords = {Learning, Eye-based recurrent network architechture, ERNA, neural network}, url = {http://www.cs.unimaas.nl/~vanderwerf/publications.html}, } @InProceedings{werf2002, author = {van der Werf, Erik and Uiterwijk, Jos and Postma, Eric and van den Herik, Jaap}, title = {Local move prediction in {G}o}, booktitle = {3rd International Conference on Computers and Games, Edmonton}, year = {2002}, keywords = {expert moves, learning, feature extraction, move pair analysis, modified eigenspace separation, transform, move prediction}, url = {http://www.cs.unimaas.nl/~vanderwerf/pubdown/lmp_cg02.ps.gz}, abstract = { The paper presents a system that learns to predict local strong expert moves in the game of Go at a level comparable to that of strong human kyu players. This performance is achieved by four techniques. First, our training algorithm is based on a relative-target approach that avoids needless weight adaptations characteristic of most neural-network classifiers. Second, we reduce dimensionality through state-of-the-art feature extraction, and present two new feature-extraction methods, the Move Pair Analysis and the Modified Eigenspace Separation Transform. Third, informed pre-processing is used to reduce state-space complexity and to focus the feature extraction on important features. Fourth, we introduce and apply second-phase training, i.e., the retraining of the trained network with an augmented input constituting all pre-processed features. Experiments suggest that local move prediction will be a significant factor in enhancing the strength of Go programs. } } @InProceedings{werf2002b, author = {van der Werf, Erik and Uiterwijk, Jos and van den Herik, Jaap}, title = {Solving {P}onnuki-{G}o on Small Boards}, booktitle = {7th Computer Olympiad Computer-Games Workshop Proceedings, Maastricht}, year = {2002}, month = {July}, url = {http://www.cs.unimaas.nl/~vanderwerf/pubdown/ponnuki_olympiad02.ps.gz}, keywords = {Ponnuki Go, Atari Go, capture Go, evaluation function, search enhancements}, abstract = { This paper presents a search-based approach for the game of Ponnuki-Go. A novel evaluation function is presented that is used in an alpha-beta framework with several search enhancements. The search engine performs well on solving positions and on heuristic play. Optimal soluations were found for small empty boards up to 5x5, as well as some 6x6 variants. We believe that our system can also be applied to capture, life/death and connection problems in the game of Go. } } @Article{werf2003, author = {van der Werf, Erik and van den Herik, Jaap and Uiterwijk, Jos}, title = {Solving {G}o on Small Boards}, journal = {ICGA Journal}, year = {2003}, volume = {26}, number = {2}, pages = {92-107}, url = {http://www.cs.unimaas.nl/~vanderwerf/pubdown/solving_go_on_small_boards.ps.gz}, keywords = {solving, alpha-beta, GHI, 5x5, Migos}, } @InProceedings{werf2003b, author = {E.C.D. van der Werf, H.J. van den Herik, J.W.H.M. Uiterwijk}, title = {Learning to Score Final Positions in the Game of {G}o}, booktitle = {10th Advances in Computer Games conference}, pages = {143-158}, year = {2003}, url = {http://www.cs.unimaas.nl/~vanderwerf/pubdown/learning_to_score.pdf}, keywords = {learning, neural net, scoring, game records, life and death}, abstract = { This paper presents a learning system for scoring final positions in the Game of Go. Our system learns to predict life and death from labelled game records. 98.9\% of the positions are scored correctly and nearly all incorrectly scored positions are recognized. By providing reliable score information our system opens the large source of Go knowledge implicitly available in human game records, thus paving the way for a successful application of machine learning in Go. } } @InProceedings{werf2003c, author = {E.C.D. van der Werf, M.H.M. Winands and H.J. van den Herik and J.W.H.M. Uiterwijk}, title = {Learning to Predict Life and Death from {G}o Game Records}, booktitle = {Proceedings of JCIS 2003 7th Joint Conference on Information Sciences}, pages = {501-504}, year = {2003}, editor = {Ken Chen et al.}, address = {Research Triangle Park, North Carolina, USA}, organization = {JCIS/Association for Intelligent Machinery}, url = {http://www.cs.unimaas.nl/~vanderwerf/pubdown/lld_jcis03.pdf}, abstract = { This paper presents a learning system for predicting life and death in the game of Go. Learning examples are extracted from game records. On average our system correctly predicts life and death for 88\% of all blocks. Towards the end of a game the performance increases up to 99\%. Clearly, such a predictor will be an important component for building a full-board evaluation function. } } @Article{werf2003e, author = {E. van der Werf}, title = {Aya Wins 9x9 {G}o Tournament}, journal = {ICGA Journal}, year = {2003}, volume = {26}, number = {4}, keywords = {8th Computer Olympiad, Graz} } @InProceedings{werf2004, author = {E.C.D. van der Werf, H.J. van den Herik, J. W. H. M. Uiterwijk}, title = {Learning to Estimate Potential Territory in the Game of {G}o}, booktitle = {4th International Conference on Computers and Games (CG'04)}, year = {2004}, url = {http://www.cs.unimaas.nl/~vanderwerf/pubdown/predicting_territory.pdf}, } @PhdThesis{werf2004b, author = {E.C.D. van der Werf}, title = {{AI} techniques for the game of {G}o}, school = {Universiteit Maastricht, Maastricht, The Netherlands}, year = {2004}, url = {http://www.cs.unimaas.nl/~vanderwerf/pubdown/thesis_erikvanderwerf.ps.gz} } @Misc{wilcox1995, author = {Wilcox, Bruce}, title = {{RiscIgo} Design}, year = {1995}, crossref = {cgm}, note = {Computer {G}o Mailing List}, keywords = {RiscIgo}, } @Misc{wilcox1997, author = {Wilcox, Bruce}, title = {Chess is Easy. {G}o is Hard.}, year = {1997}, howpublished = {Computer Game Developers Conference}, number = {Paper 5502}, } @MastersThesis{willmott1997, author = {Willmott, Steven}, title = {Adversarial Planning techniques and the game of {G}o}, year = {1997}, school = {Departement of Artificial Intelligence, University of Edinburgh}, keywords = {adversarial}, url = {http://www.lsi.upc.es/~steve/Edinburgh/snw.ps.gz}, } @TechReport{willmott1998, author = {Willmott, Steven and Bundy, Alan and Levine, John and Richardson, Julian}, title = {Adversarial Planning in Complex Domains}, year = {January 1998}, institution = {Department of Artificial Intelligence, University of Edinburgh}, number = {889}, keywords = {adversarial, co-operative, agent}, url = {http://www.dai.ed.ac.uk/pub/daidb/papers/rp889.ps.gz}, } @InProceedings{willmott1998b, author = {Willmott, Steven and Bundy, Alan and Levine, John and Richardson, Julian}, title = {An Adversarial Planning Approach to {G}o}, crossref = {cg1998}, pages = {93-112}, keywords = {planning}, url = {http://ase.arc.nasa.gov/people/julianr/www/publications/gobi_llncs.ps}, abstract = { Approaches to computer game playing based on (typically alpha-beta) search of the tree of possible move sequences combined with an evaluation function have been successful for many games, notably Chess. For games with large search spaces and complex positions, such as Go, these approaches are less successful and we are led to seek alternative approaches. One such alternative is to model the goals of the players, and their strategies for achieving these goals. This approach means searching the space of possible goal expansions, typically much smaller than the space of move sequences. In this paper we describe how adversarial hierarchical task network planning can provide a framework for goal-directed game playing, and its application to the game of Go. } } @Article{willmott1999, author = {Willmott, Steven and Bundy, Alan and Levine, John and Richardson, Julian}, title = {Applying Adversarial Planning Techniques to {G}o}, year = {1999}, month = {March}, journal = {Journal of Theoretical Computer Science}, keywords = {adversarial planning, planning}, url = {http://dream.dai.ed.ac.uk/publications/98-03/willmott99.ps.gz} } @InProceedings{wolf1992, author = {Wolf, Thomas}, title = {{T}sume go with {R}isi{K}o}, year = {1992}, booktitle = {Game Festival in Cannes/France}, keywords = {tsume go, life and death}, url = {http://citeseer.ist.psu.edu/wolf92tsume.html}, } @InProceedings{wolf1993, author = {Wolf, Thomas}, title = {Quality improvements in the tsume go mass production}, year = {1993}, booktitle = {Proceedings of the Game Festival in Cannes/France, 1993}, keywords = {tsume go, life and death}, url = {http://citeseer.ist.psu.edu/wolf93quality.html}, } @InProceedings{wolf1994, author = {Wolf, Thomas}, title = {The program {G}oTools and its computer-generated tsume go database}, year = {1994}, booktitle = {1st Game Programming Workshop in Japan, Hakone, 1994}, keywords = {tsume go, life and death, database}, url = {http://www.qmw.ac.uk/~ugah006/gotools/hakone94.ps}, } @InProceedings{wolf1996, author = {Wolf, Thomas}, title = {About problems in generalizing a tsumego program to open positions}, year = {1996}, booktitle = {3rd Game Programming Workshop in Japan, Hakone, 1996}, keywords = {tsume go, life and death, open position}, url = {http://www.qmw.ac.uk/~ugah006/gotools/hakone96.ps}, } @Misc{wolf1996b, author = {Wolf, Thomas}, title = {About computer go and the tsume go program {G}oTools}, year = {1997}, crossref = {wolf1994}, note = {Based on an article from 1st game programming workshop, hakone, Japan, 1994}, keywords = {tsume go, life and death}, url = {http://citeseer.ist.psu.edu/wolf97about.html}, } @Article{wolf1997, author = {Wolf, Thomas}, title = {The diamond}, year = {1997}, volume = {Autumn 1997}, journal = {British Go Journal}, keywords = {tsume go}, url = {http://alpha.qmw.ac.uk/~ugah006/gotools/diamond/diamond.ps}, } @Article{wolf2000, author = {Wolf, Thomas}, title = {Forward pruning and other heuristic search technics in tsume go}, journal = {Information Sciences}, volume = {122}, number = {1}, pages = {59-76}, year = {2000}, keywords = {GoTools, tsume go, life and death, forward pruning, heuristic}, url = {http://lie.math.brocku.ca/twolf/papers/jis_nat.ps}, abstract = { GoTools is the name of a computer program to analyse life & death fights in the game of go. First, a motivation for programing go is given. General aspects of the heuristic search performed in GoTools are discussed. The absolute strength and the effect of forward tree pruning are tested in a competition between GoTools and dan level human players. It is found that with a speed up of a factor of 30 the program still finds for 70\% of the problems of a test set the correct first move. A suggestion is made to compare intelligence between contestants (in solving fully enclosed life/death problems) by comparing their relative increase in the time to solve problems with the increase of the difficulty of the problems. The rules of go are explained in the shortest possible form in the appendix. } } @Article{wolf2003, author = {Pratola, Matthew and Wolf, Thomas}, title = {Optimizing {G}o{T}ools' Search Heuristics using Genetic Algorithms}, journal = {ICGA Journal}, year = {2003}, volume = {26}, number = {1}, pages = {28-49}, url = {http://lie.math.brocku.ca/twolf/papers/ga-report.ps}, keywords = {GoTools, Life and Death, TsumeGo, Genetic Algorithms, Open Boundary}, abstract = { GOTOOLS is a program which solves life-and-death problems in the game of Go. This paper describes experiments using a Genetic Algorithm to optimize heuristic weights used by GOTOOLS' tree-search. The complete set of heuristic weights is composed of different subgroups, each of which can be optimized with a suitable fitness function. As a useful side product, an MPI interface for FreePascal (Message Passing Interface) was implemented to allow the use of a parallelized fitness function running on a Beowulf cluster. The aim of this exercise is to optimize the current version of GOTOOLS, and to make tools available in preparation of an extension of GOTOOLS for solving open boundary life-and-death problems, which will introduce more heuristic parameters to be fine-tuned. } } @Misc{wolf2006, author = {Wolf, Thomas}, title = {A library of eyes in {G}o, {I}: Life & death definition consistent with `bent-4'}, howpublished = {Preprint, accepted for publication in the proceedings of the International Workshop on Combinatorial Game theory at BIRS (Banff International Research Station)}, year = {2006}, url = {http://lie.math.brocku.ca/twolf/papers/bent4.pdf}, keywords = {life and death, ko, bent-4-in-the-corner, eye-library}, abstract = { In the game of Go we develop a consistent procedural definition of the status of life and death problems. This computationally efficient procedure determines the number of external ko threats that are necessary and sufficient to win, and in the case of positions of the type of bent-4-in-the-corner it finds that they are unconditionally dead in agreement with common practice. A rigorous definition of the status of life and death problems became necessary for building a library of monolithic eyes (i.e. eyes surrounded by only one chain). It is also needed for comparisons of life and death programs when solving automatically thousands of problems to analyse whether different results obtained by different programs are due to different status definitions or due to bugs. } } @Misc{wolf2006b, author = {Wolf, Thomas and Pratola,Matthew}, title = {A library of eyes in {G}o, {II}: Monolithic eyes}, howpublished = {Preprint, accepted for publication in the proceedings of the International Workshop on Combinatorial Game theory at BIRS (Banff International Research Station)}, year = {2006}, url = {http://lie.math.brocku.ca/twolf/papers/mono.pdf}, keywords = {life and death, ko, eye-library, monolithic, GoTools}, abstract = { We describe the generation of a library of eyes surrounded by only one chain which we call monolithic eyes. Apart from applying the library in the life \& death program GoTools it also can be used as a source for the study of unusual positions in Go as done in the second half of the paper. } } @Misc{wolf2007, author = {Thomas Wolf and Lei Shen}, title = {Checking Life & Death Problems in {G}o {I}: The Program {S}can{LD}}, howpublished = {Preprint}, year = {2007}, url = {http://lie.math.brocku.ca/twolf/papers/bugsintro.ps}, keywords = {life and death, solution checker}, abstract = { In this paper we introduce the program ScanLD (built on GoTools) which checks solutions of life & death problems for correctness. This is a task for which computer programs are especially useful. Not only can they do the computations, they can also do the handling of data in checking all moves of all solutions for optimality and reporting 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 long list of mistakes that have been found is given in an addendum to of the paper. } } @Misc{wolf2007b, author = {Thomas Wolf and Lei Shen}, title = {Checking Life & Death Problems in {G}o {II}: Results}, howpublished = {Preprint}, year = {2007}, url = {http://lie.math.brocku.ca/twolf/papers/bugsextra.ps}, keywords = {life and death, solution checker}, abstract = { In checking a collection of 500 life & death problems with the program ScanLD (built on GoTools) a list of problems with partially incorrect solutions has been obtained. In this paper the results of the computerized check are discussed. The program ScanLD is the subject of the earlier paper [1]. } } @Misc{wolf2007c, author = {Thomas Wolf}, title = {Two Applications of a Life & Death Problem Solver in {G}o}, howpublished = {Preprint, submitted to Journal of \"OGAI, special issue for the European Go Championship in Vienna 2007}, year = {2007}, url = {http://lie.math.brocku.ca/twolf/papers/over.ps}, keywords = {life and death, solution checker, single eyes, database}, abstract = { We describe two recent applications of the computer program GoTools that solves life & death problems in the game of Go. In one of them a large database of single eyes fully surrounded by one chain is constructed and the positions are analyzed. Strange positions that appear are filtered out and some are presented in this paper. A second application in the form of a program ScanLD allows to check thoroughly life & death problems together with given solutions. When applied to a book of 500 Korean problems, a substantial number of bugs was detected, some of which are shown in this paper. } } @Misc{wolfe1994, author = {Wolfe, David and Berlekamp Elwyn}, title = {Mathematical {G}o}, year = {1994}, organization = {Combinatorial Games Workshop, Math Science Research Institute Berkeley, July 1994}, note = {Talk slides}, keywords = {combinatorial game theory}, url = {http://www.gac.edu/~wolfe/papers/}, } @InBook{wolfe1996, author = {Wolfe, David}, title = {The Gamesman's Toolkit}, pages = {93-98}, year = {1996}, keywords = {go, program, calculate, UNIX, C, combinatorial}, booktitle = {Games of No Chance}, publisher = {Cambridge University Press}, url = {http://www.msri.org/publications/books/Book29/files/wolfe.pdf}, } @Misc{wolfe1999, author = {Wolfe, David}, title = {{G}o Endgames are {PSPACE}-hard}, year = {1999}, note = {Submitted to Theoretical Computer Science}, keywords = {Go, PSPACE, endgames, games}, url = {http://www.gac.edu/~wolfe/papers/}, } @Article{wolfrum1997, author = {Wolfrum, Stefan}, title = {Computer {G}o - Fern\"ostliche \"Uberlegenheit}, year = {1997}, journal = {PC Magazin (Germany)}, volume = {August 1997}, note = {In German}, } @InCollection{wu2007, title = {A Scalable Machine Learning Approach to {G}o}, author = {Lin Wu and Pierre Baldi}, booktitle = {Advances in Neural Information Processing Systems 19}, editor = {B. Sch\"{o}lkopf and J. Platt and T. Hoffman}, publisher = {MIT Press}, address = {Cambridge, MA}, pages = {1521--1528}, year = {2007}, url = {http://books.nips.cc/papers/files/nips19/NIPS2006_0223.pdf}, keywords = {evaluation function, neural network}, abstract = { Go is an ancient board game that poses unique opportunities and challenges for AI and machine learning. Here we develop a machine learning approach to Go, and related board games, focusing primarily on the problem of learning a good evaluation function in a scalable way. Scalability is essential at multiple levels, from the library of local tactical patterns, to the integration of patterns across the board, to the size of the board itself. The system we propose is capable of automatically learning the propensity of local patterns from a library of games. Propensity and other local tactical information are fed into a recursive neural network, derived from a Bayesian network architecture. The network integrates local information across the board and produces local outputs that represent local territory ownership probabilities. The aggregation of these probabilities provides an effective strategic evaluation function that is an estimate of the expected area at the end (or at other stages) of the game. Local area targets for training can be derived from datasets of human games. A system trained using only 9x9 amateur game data performs surprisingly well on a test set derived from 19x19 professional game data. Possible directions for further improvements are briefly discussed. } } @MastersThesis{yedwab1985, author = {Yedwab, Laura}, title = {On Playing Well in a Sum of Games}, year = {1985}, school = {Massachusetts Institute of Technology}, keywords = {sum of games, computational complexity, approximate solutions, optimal search strategies}, url = {http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-348.pdf}, } @Article{yang1991, author = {Yang, Z.J. and Yao, Jie}, title = {Cluster dimensionality in the game of {G}o}, journal = {Physica A}, year = {1991}, volume = {176}, pages = {447-453}, keywords = {cluster dimensionality, random site percolation, RSP, fractals} } @InProceedings{yen1998, author = {Shi-Jim Yen and Wen-Jyh Chen and Shun-Chin Hsu}, title = {Design and Implementation of a Heuristic beginning system for computer {G}o}, booktitle = {JCIS 1998}, pages = {381-384}, year = {1998}, publisher = {Association for Intelligent Machinery}, url = {http://www.csie.ndhu.edu.tw/~sjyen/Papers/1998OpenGame.pdf}, keywords = {beginning game, opening, Joseki, Moyo, Jimmy}, abstract = { There are roughly three stages in a Go game: the beginning game, the middle game, and the end game. This paper describes a computer Go beginning game system which includes occupying corners, joseki, extending edges, and dealing with Moyo. This beginning game system has been used in a computer Go program named Jimmy 4.0. Having been tested by professional Go players, this system is estimated at about 6 kyu in terms of its beginning game performance. } } @InProceedings{yen2001, author = {Yen, Shi-Jim and Shun-Chin Hsu}, title = {A Positional-Judgement System for Computer {G}o}, booktitle = {Advances in Computer Games}, pages = {313-326}, year = {2001}, volume = {9}, publisher = {Universiteit Maastricht}, url = {http://www.csie.ndhu.edu.tw/~sjyen/Papers/2001PJ.pdf}, keywords = {positional judgment, Jimmy}, abstract = { Computer Go offers researchers a new challenge and opens up a very wide scope of possibilities for artificial intelligence. In a computer Go program, the most important element is a positional judgment system. Following the methods of human Go experts, we designed and implemented a new model of positional judgment for computer Go. This model was employed successfully in a computer Go program, Jimmy-5.0, which beat the latest world-champion Go program, ManyFaces, in the 1998 FOST Go contest. } } @InProceedings{yen2002, author = {Yen, Shi-Jim and Yen, JC and Shun-Chin Hsu}, title = {Move strategies in middle game of computer {G}o}, booktitle = {7th TAAI, Taiwan}, year = {2002}, note = {In Chinese}, url = {http://www.csie.ndhu.edu.tw/~sjyen/Papers/2002MidGame.pdf}, } @InProceedings{yoshii1998, author = {Yoshii, Hiroto}, title = {Move Evaluation Tree System}, booktitle = {Complex Games Lab Workshop}, editor = {Frank, Ian and Matsubara, Hitoshi and Tajima, Morihiko and Yoshikawa, Atsushi and Grimbergen, Reijer and M\"uller, Martin}, organization = {Electrotechnical Laboratory, Machine Inference Group, Tsukuba, Japan}, year = {1998}, url = {http://www.cs.ualberta.ca/~mmueller/cgo/cg98-workshop/Yoshii.pdf}, keywords = {move evaluation tree system, METS, emergency value, database}, } @InProceedings{yoshikawa1998, author = {Yoshikawa, Atsushi and Kojima, Takuya and Saito, Yasuki}, title = {Relations between Skill and the Use of Terms -- An Analysis of Protocols of the Game of {G}o}, crossref = {cg1998}, pages = {282-299}, keywords = {Cognitive science, Special terms, Expert knowledge, Iceberg model}, abstract = { The use of Go terms while playing Go differs according to the player's skill. We conduct three experiments to examine this in detail. In the first experiment, players' spontaneous utterances (called protocols) were collected. We analyze these protocols in two ways. One is the number of Go terms used, and the other is the contents of the terms, such as strategic or tactical. The second experiment examines how well the players knew the configurations of the stones. From the two experiments, we find that even if the subjects know of many Go terms, their use depends on the subject's skill. The third experiment considers ``Soudan-Go,'' where two players form a team. They are in the same room and can freely talk to each other; their spontaneous utterances (protocols) were collected. We also analyze reports of ``Houchi Soudan-Go,'' which is a Soudan-Go match between professional players. We find that expert players often use Go terms and they understood their partner's intentions without needing a full explanation. Intermediate level players often talked over their plan and their opponent's plan using many Go terms. From our analyses we developed a hypothesis which we call the iceberg model. The purpose of the model is to explain the structure of a term in the human brain from the viewpoint of the role of the term. Although this is still a hypothesis, it will become an important guide when carrying out protocol analyses and modeling the thought processes of Go players. } } @InProceedings{yoshizoe2007, author = {Kazuki Yoshizoe and Akihiro Kishimoto and and Martin M\"uller}, title = {Lambda depth-first proof number search and its application to {G}o}, booktitle = {IJCAI 2007}, year = {2007}, url = {http://www.cs.ualberta.ca/~mmueller/ps/yoshizoe.pdf}, keywords = {LDFPN, DFPN, lambda search}, abstract = { Thomsen's lambda search and Nagai's depth-first proof-number (DFPN) search are two powerful but very different AND/OR tree search algorithms. Lambda Depth-First Proof Number search (LDFPN) is a novel algorithm that combines ideas from both algorithms. Lambda search can dramatically reduce a search space by finding different levels of threat sequences. DFPN employs the notion of proof and disproof numbers to expand nodes expected to be easiest to prove or disprove. The method was shown to be effective for many games. Integrating lambda order with proof and disproof numbers enables LDFPN to select moves more effectively, while preserving the efficiency of DFPN. LDFPN has been implemented for capturing problems in Go and is shown to be more efficient than DFPN and more robust than an algorithm based on classical lambda search. } } @TechReport{zaman1997, author = {Zaman, Raonak and Prokhorov, Danil and Wunsch, Donald C.}, title = {Adaptive Critic Design in Learning to Play Game of {G}o}, year = {1997}, institution = {Texas Tech University, Lubbock}, keywords = {ACD, adaptive critic, learning, TD, temporal difference learning}, url = {http://www.ece.umr.edu/acil/Publications/CONFERENCE/Adaptive_critic_design_in.pdf}, } @Misc{zaman1999, author = {Zaman, Raonak and Wunsch, Donald C.}, title = {{TD} Methods Applied to Mixture of Experts for Learning 9x9 {G}o Evaluation Function}, year = {1999}, organization = {Electrical Engr., Texas Tech University, Lubbock}, keywords = {TD, temporal difference learning, neural networks, Meta-Pi, mixture of experts}, url = {http://www.ece.umr.edu/acil/Publications/CONFERENCE/TD methods applied.pdf}, } @MastersThesis{zhang2004, author = {Xiaoyu Zhang}, title = {Parallel Computing as a Way to Go}, school = {University of California, Santa Cruz}, year = {2004}, month = {September}, url = {http://sluggo.dforge.cse.ucsc.edu/willMS.pdf}, keywords = {SlugGo, GNU Go}, abstract = { Go is an ancient game that originated in China over four thousand years ago. It is a board game composed of lines, points, and stones played between two players. The game has very simple rules that lead to complicated tactical and strategic challenges. Its complexity surpasses that of chess; the commercial chess programs play at the level of the best human players while the best Go programs are not a challenger for the average amateur Go player. The high branching factor of Go makes the traditional tree search approach with alpha-beta pruning infeasible. This thesis explores a highly pruned look ahead method run in parallel on a cluster of desktop computers. We chose message passing as our parallel programming model. We developed a lightweight API based on LAM/MPI (an implementation of the standard message passing interface API) for parallel computation on a Mac G4 cluster. The API supports the Pool Manager-Master/Worker model. We chose GNU GO, an open-source Go program, as our game engine to speed up the development. We added code to the standard distribution source code of GNU Go 3.4 and call our program SlugGo. Finally, some initial machine-learning attempts were made to help in weighting the effect of several game features on board evaluation. } } @InProceedings{zhao2005, author = {Ling Zhao and Martin M\"uller}, title = {Solving probabilistic combinatorial games}, booktitle = {11th Advances in Computer Games Conference}, year = {2005}, url = {http://www.cs.ualberta.ca/~mmueller/ps/solvepm.pdf}, keywords = {PCG, probability distribution, local evaluation, Monte-Carlo}, abstract = { Probabilistic combinatorial games (PCG) are a model for Go-like games recently introduced by Ken Chen. They differ from normal combinatorial games since terminal position in each subgame are evaluated by a probability distribution. The distribution expresses the uncertainty in the local evaluation. This paper focuses on the analysis and solution methods for a special case, 1-level binary PCG. Monte-Carlo analysis is used for move ordering in an exact solver, that can compute the winning probability of a PCG efficiently. Monte-Carlo interior evaluation is used in a heuristic player. Experimental results show that both types of Monte-Carlo methods work very well in this problem. } } @InProceedings{zobrist1971, author = {Albert L. Zobrist}, title = {Complex preprocessing for pattern recognition}, booktitle = {ACM annual conference 1971}, year = {1971}, keywords = {pattern recognition, perception, preprocessing , perceptual grouping, Gestalt cluster, internal representation, internal model, data structure, character recognizer, machine perception}, abstract = { The construction of pattern recognition machines may eventually depend upon the development of highly complex preprocessors. This claim is supported by a discussion of the importance of perceptual grouping. Since complex preprocessing will assess more of the basic structure of a visual scene, internal representations will have to be more descriptive in nature. Two approches to descriptive internal representation are mentioned. Two of the author's programs are reviewed. One plays the Oriental game of GO at a human level and the other can recognize digitized hand printed characters. Both programs use a geometry preserving representation of features, so that calculations involving the features can assess the original geometry of the input. In addition, the GO program calculates groups of stones and performs other types of ``complex'' processing. Practical and philosophical arguments are given for the Use of internal representation by pattern recognition programs. } }