Doctorat en sciences psychologiques / info:eu-repo/semantics/nonPublished

L'objectif de notre travail est de déterminer des algorithmes qui facilitent la résolution de jeux combinatoires par des calculs informatiques. En premier lieu, nous expliquons comment l'implémentation du nimber permet d'accélérer le calcul de jeux impartiaux en version normale. Puis, nous proposons des raffinements ou des généralisations d'algorithmes de parcours des arbres de jeu, en particulier le PN-search, tout en discutant de l'intérêt de l'intervention humaine lors de l'exécution de ces algorithmes. Enfin, nous présentons des algorithmes de vérification, dont le but initial était de s'assurer de la validité de nos calculs, mais qui permettent également d'obtenir des arbres solutions de taille réduite. Ces techniques sont appliquées à l'étude de deux jeux : le Sprouts, où les joueurs relient des points par des lignes, et le Dots-and-boxes, dont le but est de compléter le maximum de boîtes en plaçant des arêtes. Le Sprouts est un jeu combinatoire impartial, dont la nature topologique rend difficile la représentation informatique. Nous explicitons une telle représentation, avant d'étudier une généralisation où le jeu se déroule sur des surfaces compactes. Le Dots-and-boxes est un jeu partisan, et nous détaillons diverses simplifications théoriques qui nous ont permis d'obtenir informatiquement des résultats nouveaux sur ce jeu.

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.