Système d'Apprentissage par Auto-Observation. Application au Jeu de Go
T. Cazenave
LIP6 1997/034: Rapport de Recherche
LIP6 /
LIP6 research
reports
249 pages - Décembre/December 1997 -
French document.
PostScript : 1193 Ko
/Kb
Contact :
par
mail / e-mail
Thème/Team:
Apprentissage et Acquisition de Connaissances
Titre français : Système d'Apprentissage par Auto-Observation. Application au Jeu de Go
Titre anglais : System Learning by Self-Observation. Application to the Game of Go
Résumé : Cette thèse décrit un système d'apprentissage par auto-observation, Introspect.
Ce système créé automatiquement, pour un domaine donné, des connaissances qui permettront d'effectuer des coupes dans les arbres de recherche développés dans ce domaine. Il a été principalement appliqué dans le domaine du jeu de Go, pour l'apprentissage de la démonstration de théorèmes tactiques. Gogol, le programme de Go dont la partie tactique a
été écrite par Introspect, fait partie du groupe des programmes de Go qui suivent les quatre meilleurs programmes mondiaux. C'est le meilleur programme de Go basé sur un mécanisme d'apprentissage. La combinaison des diverses méthodes décrites dans cette thèse a permis d'écrire en une année un programme de Go qui a sa place dans les compétitions mondiales de programmes de Go alors que les meilleurs programmes de Go ont demandé entre 15 et 20 années de développement.
Introspect ne possède au départ qu'une définition simple et concise des buts qu'il doit atteindre et un ensemble de règles décrivant les conséquences directes d'une action dans le domaine dans lequel il doit apprendre. A partir des exemples qu'il rencontre, il se spécialise
automatiquement en un autre programme qui permet de prévoir efficacement à long terme les conséquences de ses actions sur l'achèvement des buts définis.
Introspect utilise une représentation des connaissances à base de logique des prédicats. Il représente ses connaissances de façon différente suivant qu'il veut apprendre de nouvelles connaissances ou qu'il veut utiliser les connaissances qu'il a apprises.
Dans la phase d'apprentissage, il utilise une représentation générale qui lui permet d'apprendre des règles générales en utilisant peu d'exemples. Il possède un mécanisme de compilation logique qui lui permet de filtrer les règles apprises rapidement. De plus, afin de pouvoir s'auto-observer, il résout les problèmes avec une représentation qu'il peut manipuler. Il interprète ses règles et mémorise leurs déclenchements. A partir de la trace de résolution de problème, il peut expliquer pourquoi il a été amené à déduire des faits intéressants. Il obtient alors une liste de faits explicative. Cette liste de faits est généralise pour créer de nouvelles règles, en remplaçant les faits contenant des variables instanciées par des prédicats contenant des variables.
Dans la phase d'utilisation des connaissances apprises, Introspect n'a plus besoin d'avoir une représentation générale mais coûteuse de ses connaissances, il évalue partiellement certaines prémisses des règles apprises pour pouvoir les matcher plus rapidement. Il compile aussi ses règles en programmes C++ pour pouvoir les utiliser plus efficacement.
Dans le domaine des jeux, une extension de la théorie combinatoire des jeux à des valeurs inconnues est définie qui permet de représenter des connaissances partielles sur des jeux complexes. Les jeux combinatoires ainsi définis représentent des informations sur des morceaux d'arbres de recherche.
Les programmes créés par Introspect se prètent bien à la parallélisation. La méthode d'apprentissage proposée est générale et peut être appliquée à d'autres domaines que celui du jeu de Go. Des exemples d'applications pour le jeu d'Abalone et pour la prévision en Gestion sont donnés. Dans ces domaines aussi, Introspect remplace la recherche combinatoire par le filtrage d'une base de règles apprises.
Abstract : This thesis describes a system learning by self-observation, Introspect.
This system automatically creates, for a given domain, the knowledge to cut the search trees of this domain. It has mainly been applied to the game of Go, it learns to prove tactical Go theorems. Gogol, the Go program whose tactical part has been written by Introspect, is in the group of Go programs following the best four Go programs. It is the best learning Go program. The mechanisms described in this thesis have enabled to write in one year a Go program which figures well in international competitions, whereas the best Go programs have been improved during the last 15 or 20 years.
Introspect begins with a simple and short description of the goals it has to achieve and with a set of rules describing the direct consequences of its actions. Using some examples, it specializes automatically itself into another program which forecasts efficiently in the long term the consequences of its action on the achievement of the predefined goals.
Introspect uses a knowledge representation based on first order logic. It represents its knowledge differently when it learns and when it uses its learned rules.
When learning, it uses a general representation so as to learn general rules using few examples. It has a logic compilation mechanism which enables it to match the learned rules rapidly. Moreover, so as to observe itself, it solves problems with a knowledge representation it can manipulate. It interprets the rules and memorizes their firings. Using the problem solving trace, it can explain why it has deduced interesting facts. It obtains a list of explaining facts. This list of facts is generalized so as to create new rules, by replacing facts containing instanciated variables by predicates containing variables.
When using the learned knowledge, Introspect no more needs a general but costful knowledge representation, it partially evaluates some premises of the learned rules so as to match them more rapidly. It also compiles its rules into C++ programs so as to be more efficient.
In the domain of games, an extension of Combinatorial Game Theory to unknown values is defined. It enables to represent partial information about complex games and information on subtrees of the total search tree.
The programs written by Introspect can be easily parallelized. The learning method is general and can be applied to other domains than the game of Go. I give some examples of applications to the game of Abalone and to the management of a firm. In these domains too, Introspect replaces some tree search by the firing of some learned rules.
Mots-clés : Apprentissage, Auto-observation, Généralisation, Explication, Compilation, Théorie Combinatoire des Jeux, Jeu de Go, Gestion
Key-words : Machine Learning, Self-observation, Generalization, Explanation, Compilation, Combinatorial Game Theory, Game of Go, Management
Publications internes LIP6
1997 / LIP6 research reports 1997
Responsable
Éditorial / Editor
webmaster@lip6.fr