1 |
Towards solving the game of Go in One dimension /Lewis, Isabel Christina. January 1900 (has links)
Thesis (M.SC.) - Carleton University, 2007. / Includes bibliographical references (p. 54-55). Also available in electronic format on the Internet.
|
2 |
Feature extraction and representation for pattern recognition and the game of GoZobrist, Albert Lindsey, January 1970 (has links)
Thesis (Ph. D.)--University of Wisconsin--Madison, 1970. / Typescript. Vita. Includes bibliographical references.
|
3 |
Application of temporal difference learning and supervised learning in the game of Go.January 1996 (has links)
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
|
4 |
Game playing via abstract feature recognition the game of GO /Molin, Arthur William. January 1988 (has links)
Thesis (M.S.)--University of California, Santa Cruz, 1988. / Typescript. Includes bibliographical references.
|
5 |
Decision forests for computer Go feature learningVan Niekerk, Francois 04 1900 (has links)
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.
|
6 |
Neuroevolução aplicada no treinamento de redes neurais convolucionais para aprender estratégias específicas do jogo GoSakurai, Rafael Guimarães January 2017 (has links)
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.
|
7 |
Étude des conditions et des contraintes d'implémentation d'un jeu de société à l'école, comme vecteur d'apprentissages mathématiques : cas du jeu de Go au cycle 3 / Study of the conditions and implementation constraints of a board game at school,as a mathematical learning medium : case of Go game in elementary schoolHaye, Thomas 11 October 2019 (has links)
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.
|
Page generated in 0.0451 seconds