• Langue : Français
• Discipline : Informatique
• Identifiant : 2011LIL10048
• Type de thèse : Doctorat
• Date de soutenance : 08/11/2011

Résumé en langue originale

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.

Résumé traduit

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.