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. / The aim of this thesis is to determine algorithms that help to solve combinatorial games by computation. First, we explain how the implementation of the nimber speeds up the computation of impartial games in normal version. Then, we propose refinements or generalizations of tree-traversal algorithms, especially the PN-search, while discussing the benefit of human intervention during the execution of these algorithms. Finally, we present verification algorithms, whose initial goal was to ensure the validity of our computation, but also allowed us to obtain small solution trees. We have applied these methods to the game of Sprouts, where players connect dots with lines, and Dots-and-boxes, where players complete boxes by drawing edges. Sprouts is an impartial combinatorial game, whose topological nature makes it difficult to represent for a computer. We explain such a representation, before studying a generalization where the game is played on compact surfaces. Dots-and-boxes is a partizan game, and we detail various theoretical simplifications that allowed us to compute new results for this game.
| Identifer | oai:union.ndltd.org:theses.fr/2011LIL10046 |
| Date | 08 November 2011 |
| Creators | Lemoine, Julien |
| Contributors | Lille 1, Delahaye, Jean-Paul, Cazenave, Tristan |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0021 seconds