Thesis (M.SC.) - Carleton University, 2007. / Includes bibliographical references (p. 54-55). Also available in electronic format on the Internet.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1970. / Typescript. Vita. Includes bibliographical references.

by Horace Wai-Kit, Chan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 109-112). / Acknowledgement --- p.i / Abstract --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Objective --- p.3 / Chapter 1.3 --- Organization of This Thesis --- p.3 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Definitions --- p.5 / Chapter 2.1.1 --- Theoretical Definition of Solving a Game --- p.5 / Chapter 2.1.2 --- Definition of Computer Go --- p.7 / Chapter 2.2 --- State of the Art of Computer Go --- p.7 / Chapter 2.3 --- A Framework for Computer Go --- p.11 / Chapter 2.3.1 --- Evaluation Function --- p.11 / Chapter 2.3.2 --- Plausible Move Generator --- p.14 / Chapter 2.4 --- Problems Tackled in this Research --- p.14 / Chapter 3 --- Application of TD in Game Playing --- p.15 / Chapter 3.1 --- Introduction --- p.15 / Chapter 3.2 --- Reinforcement Learning and TD Learning --- p.15 / Chapter 3.2.1 --- Models of Learning --- p.16 / Chapter 3.2.2 --- Temporal Difference Learning --- p.16 / Chapter 3.3 --- TD Learning and Game-playing --- p.20 / Chapter 3.3.1 --- Game-Playing as a Delay-reward Prediction Problem --- p.20 / Chapter 3.3.2 --- Previous Work of TD Learning in Backgammon --- p.20 / Chapter 3.3.3 --- Previous Works of TD Learning in Go --- p.22 / Chapter 3.4 --- Design of this Research --- p.23 / Chapter 3.4.1 --- Limitations in the Previous Researches --- p.24 / Chapter 3.4.2 --- Motivation --- p.25 / Chapter 3.4.3 --- Objective and Methodology --- p.26 / Chapter 4 --- Deriving a New Updating Rule to Apply TD Learning in Multi-layer Perceptron --- p.28 / Chapter 4.1 --- Multi-layer Perceptron (MLP) --- p.28 / Chapter 4.2 --- Derivation of TD(A) Learning Rule for MLP --- p.31 / Chapter 4.2.1 --- Notations --- p.31 / Chapter 4.2.2 --- A New Generalized Delta Rule --- p.31 / Chapter 4.2.3 --- Updating rule for TD(A) Learning --- p.34 / Chapter 4.3 --- Algorithm of Training MLP using TD(A) --- p.35 / Chapter 4.3.1 --- Definitions of Variables in the Algorithm --- p.35 / Chapter 4.3.2 --- Training Algorithm --- p.36 / Chapter 4.3.3 --- Description of the Algorithm --- p.39 / Chapter 5 --- Experiments --- p.41 / Chapter 5.1 --- Introduction --- p.41 / Chapter 5.2 --- Experiment 1 : Training Evaluation Function for 7 x 7 Go Games by TD(λ) with Self-playing --- p.42 / Chapter 5.2.1 --- Introduction --- p.42 / Chapter 5.2.2 --- 7 x 7 Go --- p.42 / Chapter 5.2.3 --- Experimental Designs --- p.43 / Chapter 5.2.4 --- Performance Testing for Trained Networks --- p.44 / Chapter 5.2.5 --- Results --- p.44 / Chapter 5.2.6 --- Discussions --- p.45 / Chapter 5.2.7 --- Limitations --- p.47 / Chapter 5.3 --- Experiment 2 : Training Evaluation Function for 9 x 9 Go Games by TD(λ) Learning from Human Games --- p.47 / Chapter 5.3.1 --- Introduction --- p.47 / Chapter 5.3.2 --- 9x 9 Go game --- p.48 / Chapter 5.3.3 --- Training Data Preparation --- p.49 / Chapter 5.3.4 --- Experimental Designs --- p.50 / Chapter 5.3.5 --- Results --- p.52 / Chapter 5.3.6 --- Discussion --- p.54 / Chapter 5.3.7 --- Limitations --- p.56 / Chapter 5.4 --- Experiment 3 : Life Status Determination in the Go Endgame --- p.57 / Chapter 5.4.1 --- Introduction --- p.57 / Chapter 5.4.2 --- Training Data Preparation --- p.58 / Chapter 5.4.3 --- Experimental Designs --- p.60 / Chapter 5.4.4 --- Results --- p.64 / Chapter 5.4.5 --- Discussion --- p.65 / Chapter 5.4.6 --- Limitations --- p.66 / Chapter 5.5 --- A Postulated Model --- p.66 / Chapter 6 --- Conclusions --- p.69 / Chapter 6.1 --- Future Direction of Research --- p.71 / Chapter A --- An Introduction to Go --- p.72 / Chapter A.l --- A Brief Introduction --- p.72 / Chapter A.1.1 --- What is Go? --- p.72 / Chapter A.1.2 --- History of Go --- p.72 / Chapter A.1.3 --- Equipment used in a Go game --- p.73 / Chapter A.2 --- Basic Rules in Go --- p.74 / Chapter A.2.1 --- A Go game --- p.74 / Chapter A.2.2 --- Liberty and Capture --- p.75 / Chapter A.2.3 --- Ko --- p.77 / Chapter A.2.4 --- "Eyes, Live and Death" --- p.81 / Chapter A.2.5 --- Seki --- p.83 / Chapter A.2.6 --- Endgame and Scoring --- p.83 / Chapter A.2.7 --- Rank and Handicap Games --- p.85 / Chapter A.3 --- Strategies and Tactics in Go --- p.87 / Chapter A.3.1 --- Strategy vs Tactics --- p.87 / Chapter A.3.2 --- Open-game --- p.88 / Chapter A.3.3 --- Middle-game --- p.91 / Chapter A.3.4 --- End-game --- p.92 / Chapter B --- Mathematical Model of Connectivity --- p.94 / Chapter B.1 --- Introduction --- p.94 / Chapter B.2 --- Basic Definitions --- p.94 / Chapter B.3 --- Adjacency and Connectivity --- p.96 / Chapter B.4 --- String and Link --- p.98 / Chapter B.4.1 --- String --- p.98 / Chapter B.4.2 --- Link --- p.98 / Chapter B.5 --- Liberty and Atari --- p.99 / Chapter B.5.1 --- Liberty --- p.99 / Chapter B.5.2 --- Atari --- p.101 / Chapter B.6 --- Ko --- p.101 / Chapter B.7 --- Prohibited Move --- p.104 / Chapter B.8 --- Path and Distance --- p.105 / Bibliography --- p.109

Thesis (M.S.)--University of California, Santa Cruz, 1988. / Typescript. Includes bibliographical references.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: In computer Go, moves are typically selected with the aid of a tree search algorithm. Monte-Carlo tree search (MCTS) is currently the dominant algorithm in computer Go. It has been shown that the inclusion of domain knowledge in MCTS is able to vastly improve the strength of MCTS engines. A successful approach to representing domain knowledge in computer Go is the use of appropriately weighted tactical features and pattern features, which are comprised of a number of hand-crafted heuristics and a collection of patterns respectively. However, tactical features are hand-crafted specifically for Go, and pattern features are Go-specific, making it unclear how they can be easily transferred to other domains. As such, this work proposes a new approach to representing domain knowledge, decision tree features. These features evaluate a state-action pair by descending a decision tree, with queries recursively partitioning the state-action pair input space, and returning a weight corresponding to the partition element represented by the resultant leaf node. In this work, decision tree features are applied to computer Go, in order to determine their feasibility in comparison to state-of-the-art use of tactical and pattern features. In this application of decision tree features, each query in the decision tree descent path refines information about the board position surrounding a candidate move. The results of this work showed that a feature instance with decision tree features is a feasible alternative to the state-of-the-art use of tactical and pattern features in computer Go, in terms of move prediction and playing strength, even though computer Go is a relatively well-developed research area. A move prediction rate of 35.9% was achieved with tactical and decision tree features, and they showed comparable performance to the state of the art when integrated into an MCTS engine with progressive widening. We conclude that the decision tree feature approach shows potential as a method for automatically extracting domain knowledge in new domains. These features can be used to evaluate state-action pairs for guiding searchbased techniques, such as MCTS, or for action-prediction tasks. / AFRIKAANSE OPSOMMING: In rekenaar Go, word skuiwe gewoonlik geselekteer met behulp van ’n boomsoektogalgoritme. Monte-Carlo boomsoektog (MCTS) is tans die dominante algoritme in rekenaar Go. Dit is bekend dat die insluiting van gebiedskennis in MCTS in staat is om die krag van MCTS enjins aansienlik te verbeter. ’n Suksesvolle benadering tot die voorstelling van gebiedskennis in rekenaar Go is taktiek- en patroonkenmerke met geskikte gewigte. Hierdie behels ’n aantal handgemaakte heuristieke en ’n versameling van patrone onderskeidelik. Omdat taktiekkenmerke spesifiek vir Go met die hand gemaak is, en dat patroonkenmerke Go-spesifiek is, is dit nie duidelik hoe hulle maklik oorgedra kan word na ander velde toe nie. Hierdie werk stel dus ’n nuwe verteenwoordiging van gebiedskennis voor, naamlik besluitboomkenmerke. Hierdie kenmerke evalueer ’n toestand-aksie paar deur rekursief die toevoerruimte van toestand-aksie pare te verdeel deur middel van die keuses in die besluitboom, en dan die gewig terug te keer wat ooreenstem met die verdelingselement wat die ooreenstemmende blaarnodus verteenwoordig. In hierdie werk, is besluitboomkenmerke geëvalueer op rekenaar Go, om hul lewensvatbaarheid in vergelyking met veldleidende gebruik van taktiek- en patroonkenmerke te bepaal. In hierdie toepassing van besluitboomkenmerke, verfyn elke navraag in die pad na onder van die besluitboom inligting oor die posisie rondom ’n kandidaatskuif. Die resultate van hierdie werk het getoon dat ’n kenmerkentiteit met besluitboomkenmerke ’n haalbare alternatief is vir die veldleidende gebruik van taktiek- en patroonkenmerke in rekenaar Go in terme van skuifvoorspelling as ook speelkrag, ondanks die feit dat rekenaar Go ’n relatief goedontwikkelde navorsingsgebied is. ’n Skuifvoorspellingskoers van 35.9% is behaal met taktiek- en besluitboomkenmerke, en hulle het vergelykbaar met veldleidende tegnieke presteer wanneer hulle in ’n MCTS enjin met progressiewe uitbreiding geïntegreer is. Ons lei af dat ons voorgestelde besluitboomkenmerke potensiaal toon as ’n metode vir die outomaties onttrek van gebiedskennis in nuwe velde. Hierdie eienskappe kan gebruik word om toestand-aksie pare te evalueer vir die leiding van soektog-gebaseerde tegnieke, soos MCTS, of vir aksie-voorspelling.

Orientador: Prof. Dr. Fabrício Olivetti de França / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2017. / Go é um jogo de tabuleiro que chama muita atenção na área de Inteligência Artificial, por ser um problema complexo de resolver e precisar de diferentes estratégias para obter um bom nível de habilidade no jogo. Até 2015, todos os melhores programas de Go precisavam começar a partida com vantagem para poder ganhar de um jogador profissional, mas no final de 2015, o programa AlphaGo foi o primeiro e único até o momento capaz de vencer um jogador profissional sem precisar de vantagem, combinando o uso de redes neurais convolucionais profundas para direcionar as buscas em árvores de Monte-Carlo. Esta dissertação tem como objetivo principal criar um agente inteligente de Go que decide seus próximos movimentoscom base no cenário atual do tabuleiro e em modelos de predição criados para três estratégias específicas do jogo. Para isso, duas hipóteses foram testadas: i) é possívelespecializar agentes inteligentes para o aprendizado de estratégias parciais do jogo de Go, ii) a combinação dessas estratégias permitem a construção de um agente inteligente para o jogo de Go. Para a primeira hipótese um agente foi treinado para aprender, com base em um jogador heurístico e posteriormente com base nos melhores agentes treinados, a posicionar as pedras para permitir a expansão do território, este agente aprendeu a generalizar esta estratégia contra os indivíduos treinados em diferentes estágios e também a capturar pedras. Também foram treinados dois agentes com base na resolução de problemas, com objetivo de aprenderem as estratégias específicas de captura e defesa das pedras. Em ambos os treinamentos foi possível notar que o conhecimento para resolver um problema era propagado para as próximas gerações de indivíduos, mas o nível de aprendizado foi baixo devido ao pouco treinamento. Para a segunda hipótese, um agente foi treinado para decidir qual das três estratégias específicas utilizar de acordo com o estado atual do tabuleiro. Foi possível constatar que este agente, jogando contra outros indivíduos da população, evoluiu na escolha de melhores estratégias, permitindo a dominação de territórios, captura e defensa das pedras. Os agentes foram criados utilizando Redes Neurais Convolucionais, sem qualquer conhecimento prévio sobre como jogar Go, e o treinamento foi feito com Neuroevolução. Como resultado foi possível perceber a evolução dos agentes para aprender as estratégias e comportamentos distintos de forma segmentada. O nível do agente inteligente gerado ainda está distante de um jogador profissional, porém ainda existem opções de melhorias para serem testadas com parametrização, reformulação da função de aptidão, entre outros. Esses resultados propõem novas possibilidades para a criação de agentes inteligentes para jogos complexos. / Go is a board game that draws a lot of attention in the Artificial Intelligence area, because it is a complex problem to solve and needs different strategies in order to obtain a good skill level in the game. By 2015, all the Go¿s best programs must start the match with advantage to win over a professional player, but in the end of 2015, the AlphaGo program was the first and, so far, the only one capable of beating a professional player without needing advantage, combining the use of deep convolutional neural networks to orientate the searches on Monte-Carlo trees. This dissertation has as main objective to create an intelligent agent of Go that decides its next movements based on current scenario of the board and in prediction models created for three specific strategies of the game. For this purpose, two hypothesis were tested: i) whether it is possible to specialize intelligent agents to learn partial strategies of Go game, ii) whether the combination of these strategies allows the construction of an intelligent agent to play Go. For the first hyphotesis, an agent was trained to learn, based on matches again a heuristic player and later based on the best trained agents, to position the stones to allow the expansion of territory, this agent learn to generalize this strategy against individuals trained in different stages and capture stones too. Two agents were also trained based on problem solving, in order to learn the specific strategies of catching and defense of stones. In both trainings were possible to note that the knowledge to solve a problem was propagated to the next generations of individuals, but the level of learning was low due to the short training. For the second hyphotesis, an agent was trained to decide which of the three specific strategies to use according to the current state of the board. It was possible to verify that this agent, playing against other individuals population, evolved in choosing better strategies, allowing territories domination, capture and defend stones. The agents was created using Convolution Neural Networks, without any previous knowledge about how to play Go, and the training was performed using Neuroevolution. As a result, it was possible to perceive the evolution of agents to learn different strategies and behaviours in a segmented way. The intelligent agent generated¿s skill still far from a professional player, however there are still options for improvement to be tested with parameterization, reformulation of fitness function, and others. These results propose new opportunities for the creation of intelligent agents for complex games.

L’utilisation du jeu pour faire apprendre des mathématiques aux élèves s’impose de plus en plus comme une pratique pédagogique de référence au niveau de l’institution scolaire. Ce terme générique recouvre cependant des mises en œuvre très différentes n’induisant pas le même vécu pour les élèves. Notre travail a pour objectif d’explorer certaines de ces pratiques et de déterminer les conditions pour que les élèves jouent et développent des compétences mathématiques au cours d’une même séquence d’apprentissage. Nous cherchons dans un premier temps à cerner les activités qui peuvent être des jeux en classe, sachant que le contexte scolaire influe fortement, et négativement, sur la possibilité pour les élèves de vivre de réels moments de jeux. Nous proposons une caractérisation de ces activités à partir de quatre outils conceptuels, le game (la structure de jeu), le play (l’attitude de jeu), le potentiel ludique et le potentiel d’apprentissage. Nous dégageons ensuite deux modalités principales d’utilisation du jeu en classe : la ludicisation d’une situation didactique ou l’exploitation d’un jeu existant. Faisant l’hypothèse que la seconde possibilité est plus à même d’induire une attitude de jeu chez les élèves, nous concevons une séquence d’apprentissage basée du jeu de go dans une classe de cycle 3 de l’école élémentaire pour en étudier les impacts en termes d’apprentissages mathématiques. Pour ce faire, nous présentons une méthode d’analyse des jeux qui, appliquée au jeu de go, nous permet de dégager deux potentiels d’apprentissages important : l’argumentation heuristique (Duval, 1992) en résolution de problèmes et l’appréhension séquentielle des figures (Duval, 1994) en géométrie dans le cadre des contraintes actuelles de l’institution scolaire. La séquence, d’une dizaine de séances, est mise en œuvre par des enseignants expérimentateurs non spécialistes du jeu de Go. Nous analysons ensuite la séquence effective de manière à déterminer si les élèves ont vécu des moments de jeu suivant leurs propres conceptions du jeu et si des apprentissages mathématiques ont émergé. Nous nous posons enfin la question de la mobilisation de ces compétences, construites dans le cadre du jeu de go, dans d’autres domaines mathématiques. A partir de cette expérimentation nous cherchons à dégager l’ensemble des conditions et des contraintes pour l’implémentation d’un jeu de société à l’école élémentaire. / Using the game to teach mathematics to pupils became increasingly an obvious standard pedagogical practice in the scholastic institution. This generic term also reflects very different implementations that do not result in the same experience according to pupils. The objective of our work is to explore some of these practices and to determine the conditions in order for the pupils to play and develop mathematical competence during the same learning sequence. In the first instance, we are trying to define the activities that can be in-class games, keeping in mind that the school environment strongly and negatively influences the ability to experience real playing periods. We suggest a characterisation of these activities from four conceptual tools: the game (the structure of the game), the play (the game attitude), the playful potential and the learning potential. Then, we will draw two main conditions of in-class use of games: the “gameifying” of a didactic situation or the exploitation of an existing game. Assuming that the second possibility is more likely to lead to a gaming attitude for pupils, we are designing a learning sequence based on the strategy board game “go” in a junior division classroom at an elementary school, in order to study mathematical learning impacts. To do so, we are introducing a method of game analysis that, applied to Go, can extract two important learning potentials: the heuristic argumentation (Duval, 1992) for problem-solving and the sequential apprehension of figures (Duval, 1994) for geometry. This analysis method is implemented as part of the current constraints of the scholastic institution. The sequence, made of ten sessions, is implemented by experimenter teachers who are not Go specialists. We will then analyse the actual sequence in order to determine if the pupils have experienced gaming periods according to their own game understanding and if mathematical learning has emerged. We ultimately ask the question: how these skills, built as part of the Go game, have been deployed in other mathematical fields? From this experimentation, we want to clear the conditions and constraints of a boarding game implementation at the elementary school.