Programme modulaire pour la résolution des ...
Type de document :
Thèse
Titre :
Programme modulaire pour la résolution des jeux combinatoires : application au Sprouts et au Cram
Titre en anglais :
A modular program to solve combinatorial games : application to Sprouts and Cram
Auteur(s) :
Viennot, Simon [Auteur]
Systèmes Multi-Agents et Comportements [SMAC]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Systèmes Multi-Agents et Comportements [SMAC]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Directeur(s) de thèse :
Jean-Paul Delahaye
Date de soutenance :
2011-11-08
Organisme de délivrance :
Université des Sciences et Technologie de Lille - Lille I
Mot(s)-clé(s) :
Algorithme de parcours d'arbre
Stratégie gagnante
Théorie des jeux
Jeux de stratégie (mathématiques)
Espaces compacts
Arbres (théorie des graphes)
Jeux de nim
Stratégie gagnante
Théorie des jeux
Jeux de stratégie (mathématiques)
Espaces compacts
Arbres (théorie des graphes)
Jeux de nim
Discipline(s) HAL :
Informatique [cs]/Intelligence artificielle [cs.AI]
Résumé :
Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent ...
Lire la suite >Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent être utilisés pour accélérer les calculs. Nous détaillons en particulier l'utilisation du concept d'arbre canonique réduit dans les calculs en version misère. Ces méthodes ont été appliquées avec succès au calcul de deux jeux impartiaux en apparence très différents : le Sprouts, où les joueurs relient des points par des lignes, et le Cram, qui consiste à remplir un plateau avec des dominos. Nous exposons ensuite une méthode originale de suivi des calculs de jeux, avec des interactions en temps réel par l'opérateur humain. Enfin, nous décrivons l'architecture du programme modulaire qui nous a permis de réaliser de nombreux calculs différents au sein d'un cadre commun, et qui pourrait être étendu à l'avenir à d'autres jeux ou algorithmes.Lire moins >
Lire la suite >Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent être utilisés pour accélérer les calculs. Nous détaillons en particulier l'utilisation du concept d'arbre canonique réduit dans les calculs en version misère. Ces méthodes ont été appliquées avec succès au calcul de deux jeux impartiaux en apparence très différents : le Sprouts, où les joueurs relient des points par des lignes, et le Cram, qui consiste à remplir un plateau avec des dominos. Nous exposons ensuite une méthode originale de suivi des calculs de jeux, avec des interactions en temps réel par l'opérateur humain. Enfin, nous décrivons l'architecture du programme modulaire qui nous a permis de réaliser de nombreux calculs différents au sein d'un cadre commun, et qui pourrait être étendu à l'avenir à d'autres jeux ou algorithmes.Lire moins >
Résumé en anglais : [en]
The goal of this thesis is to compute the winning strategies of combinatorial games. We show how to accelerate the computation of impartial games when some positions can be splitted into sums of independent components. We ...
Lire la suite >The goal of this thesis is to compute the winning strategies of combinatorial games. We show how to accelerate the computation of impartial games when some positions can be splitted into sums of independent components. We detail in particular the concept of reduced canonical tree in misere computations. We have applied these algorithms successfully to the game of Sprouts, where two players draw lines between spots, and the game of Cram, where the players fill a grid with dominoes. Then, we present an innovative method for monitoring the computation and allowing the human operator to interact in real-time. We also describe the architecture of the modular program that allowed us to compute a lot of different results in a single framework.Lire moins >
Lire la suite >The goal of this thesis is to compute the winning strategies of combinatorial games. We show how to accelerate the computation of impartial games when some positions can be splitted into sums of independent components. We detail in particular the concept of reduced canonical tree in misere computations. We have applied these algorithms successfully to the game of Sprouts, where two players draw lines between spots, and the game of Cram, where the players fill a grid with dominoes. Then, we present an innovative method for monitoring the computation and allowing the human operator to interact in real-time. We also describe the architecture of the modular program that allowed us to compute a lot of different results in a single framework.Lire moins >
Langue :
Français
Collections :
Source :
Fichiers
- https://tel.archives-ouvertes.fr/tel-00839388/document
- Accès libre
- Accéder au document
- https://tel.archives-ouvertes.fr/tel-00839388/document
- Accès libre
- Accéder au document
- https://tel.archives-ouvertes.fr/tel-00839388/document
- Accès libre
- Accéder au document
- https://tel.archives-ouvertes.fr/tel-00839388/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- these_simon_viennot.pdf
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- these_simon_viennot.pdf
- Accès libre
- Accéder au document