La recherche que nous avons menée s'inscrit dans les projets de l'équipe de recherche Maths à Modeler. En particulier dans celui portant sur les situations de recherche pour la classe (SiRC). Cette recherche est centrée sur l'étude du rôle, pour l'apprentissage des savoir-faire fondamentaux, de l'activité mathématique, des jeux combinatoires et plus particulièrement des jeux de type Nim. Nous mettons sous l'expression « savoir-faire fondamentaux » les savoirs, méthodes et techniques qui sont à la base de toute activité mathématique : l'expérimentation, l'étude de cas particuliers, l'énoncé et l'étude de conjectures, la construction d'exemples et contre-exemples, la modélisation, l'élaboration et l'écriture de preuves, la définition d'objets, etc. (Grenier et Payan, 2002). Le sujet est la construction, l'expérimentation et l'analyse de SiRC basées sur des jeux combinatoires de type Nim pour des élèves, afin de leur faire construire et développer les savoir- faire indispensables à la mise en œuvre d'une « démarche mathématique ». Notre problématique porte donc sur l'identification des savoirs notionnels et des savoir-faire fondamentaux de l'activité mathématique qui sont mis en œuvre dans les jeux combinatoires de type Nim et la détermination des conditions et contraintes épistémologiques et didactiques favorisant l'apprentissage en classe de ces savoirs. Pour mener à bien notre étude, nous nous sommes appuyés d'une part sur certains éléments de la théorie des situations didactiques de Brousseau (Brousseau, 2004) et de la théorie des champs conceptuels de Vergnaud (Vergnaud, 1994) et, d'autre part, sur le modèle SiRC, contribuant à préciser ce modèle. Nous nous sommes servis de l'étude épistémologique et didactique des jeux de type Nim, pour mener les analyses mathématique et didactique de deux SiRC : la première, nommée « jeu d'Euclide géométrique », situation de jeu de type Nim, construite spécifiquement pour cette recherche, basée sur un jeu d'Euclide classique. La seconde, nommée le « jeu du chocolat », situation expérimentée régulièrement dans l'équipe Maths à Modeler, mais dont l'étude didactique n'avait pas vraiment été faite. Les analyses et expérimentations que nous avons menées montrent que les situations basées sur des jeux de type Nim, peuvent induire une activité mathématique qui va au-delà du développement et de la pratique de techniques mathématiques : Elles peuvent ouvrir l'accès à des savoir-faire plus généraux propres de l'activité mathématique. / This research is included in the project of the research group "Maths à modeler". In particular, in the part that corresponds to the study of "situations de recherche pour la classe" (SiRC). This research is focused in the study of the role played by the mathematical activity, the combinatorial games and particularly the games of Nim-type in learning the fundamental know-hows. We put under the term "fundamental know-hows" all the knowledge, methods and techniques found in all mathematical activity: experimenting, studying particular cases, conjecturing, building examples and counter-examples, modeling, proving, defining, etc. (Grenier et Payan, 2002). The main aim of this research is the construction, the experimentation and the analysis of SiRC based on combinatorial games of Nim-type for students designed to make them build and develop the know-hows required for the implementation of a "mathematical process". Our main problem is then identifying the fundamental and notional know-hows of the mathematical activity that are used in combinatorial games of Nim-type and establishing the epistemological and didactical conditions and constrains that favor the learning of these know-hows in the classroom. To achieve our aim, our research is supported, on one hand, by some aspects of the theory of didactical situation by Brousseau (Brousseau, 2004) and the theory of conceptual fields by Vergnaud (Vergnaud, 1994) and, on the other hand, by the SiRC model, where we also contribute to precise it. We based our research in the epistemological and didactical study of Nim-type games to conduct mathematical and didactical analysis of two SiRC: the first one, called "the geometrical Euclid game", is a situation of Nim-type created specifically for this research and based on the classical Euclid game. The second one, called "the chocolate game", is a situation frequently experimented by the research group math à modeler whose didactical analysis had not been done yet. The analysis and experimentations we have conducted show that the situations based on Nim-type games can lead to a mathematical activity that goes beyond developing and practicing mathematical techniques. They can open access to more general know-hows specific to the mathematical activity.

[pt] A teoria dos Jogos Combinatórios é o estudo de jogos com informação completa. Isso é, todos os jogadores conhecem todos os possíveis movimentos, além disso, temos que não há sorte ou a habilidade de realizar um movimento, então, em teoria jogar perfeitamente é possível. Exemplos de jogos assim são jogo da velha, xadrez, damas, Nim... a lista continua. Nessa dissertação focamos no jogo Maker-Breaker. Ele tem dois jogadores que sequencialmente escolhem um vértice de um hipergrafo. O objetivo de Maker é escolher todos os vértices de uma aresta e o objetivo de Breaker é prevenir isso. Para entender em quais tipos de hipergrafos Maker ou Breaker ganha e quais são as estratégias de vitória utilizamos SAT, probabilidade, teoria dos grafos em geral e mais. / [en] The theory of Combinatorial Games is the study of games with perfect information. This means that all players have knowledge of all possible moves, also there isn t luck or skill to perform a move, so, in theory perfect play is possible. Examples of games like these are tic-tac-toe, chess, checkers, Nim... the list goes on. In this dissertation we focus on the Maker-Breaker game. It has two players that pick a vertex from a hypergraph. The goal of Maker is to claim all vertices of an edge and the goal of Breaker is to prevent it. To understand in which types of hypergraphs does Maker or Breaker win and what are the winning strategies, we make use of SAT, Probability, general Graph Theory and more.

The thesis contains a textbook for gifted secondary school students. Its aim is to give to these students (or to their teachers) a Czech-written text covering fundamental principles in the field of game theory. In the first part we introduce the combinatorial games and some elementary methods of their solution. The second part is devoted to the game of Nim, to the Sprague-Grundy function and to the sums of the combinatorial games. It also contains a necessary introduction to the binary numeral system. In the third part we present the concept of matrix and bimatrix games. There is a lot of exercises and examples in the textbook. At the end we bring solutions to the most of them, providing the active reader with the opportunity of checking their own solutions.

Dans cette thèse, nous étudions les jeux combinatoires sousdifférentes contraintes. Un jeu combinatoire est un jeu à deux joueurs, sanshasard, avec information complète et fini acyclique. D’abord, nous regardonsles jeux impartiaux en version normale, en particulier les jeux VertexNimet Timber. Puis nous considérons les jeux partisans en version normale, oùnous prouvons des résultats sur les jeux Timbush, Toppling Dominoeset Col. Ensuite, nous examinons ces jeux en version misère, et étudionsles jeux misères modulo l’univers des jeux dicots et modulo l’univers desjeux dead-endings. Enfin, nous parlons du jeu de domination qui, s’il n’estpas combinatoire, peut être étudié en utilisant des outils de théorie des jeuxcombinatoires. / In this thesis, we study combinatorial games under differentconventions. A combinatorial game is a finite acyclic two-player game withcomplete information and no chance. First, we look at impartial gamesin normal play and in particular at the games VertexNim and Timber.Then, we consider partizan games in normal play, with results on the gamesTimbush, Toppling Dominoes and Col. Next, we look at all these gamesin misère play, and study misère games modulo the dicot universe and modulothe dead-ending universe. Finally, we talk about the domination game which,despite not being a combinatorial game, may be studied with combinatorialgames theory tools.

La thèse porte sur les deux thèmes des Jeux combinatoires et de la théorie des graphes. Elle est divisée en deux parties.1) Le jeu de Domination et ses variantes: Il s'agit d'un jeu combinatoire qui consiste à marquer les sommets d'un graphe de telle sorte qu'un sommet marqué n'ait aucun voisin marqué. Le joueur marquant le dernier sommet est déclaré gagnant. Le calcul des stratégies gagnantes étant NP-difficile pour un graphe quelconque, nous avons étudié des familles particulières de graphes comme les chemins, les scies ou les chenilles. Pour ces familles on peut savoir en temps polynomial si un graphe est perdant. Nous avons également étudié 28 variantes du jeu de domination, dont les 12 variantes définies par J. Conway sur un jeu combinatoire quelconque. 2) Le nombre chromatique ludique des arbres: Ce paramètre est calculé à partir d'un jeu de coloration où Alice et Bob colorient alternativement et proprement un sommet d'un graphe G avec l'une des k couleurs. L'objectif d'Alice est de colorier complètement le graphe alors que Bob doit l'en empêcher. Nous nous sommes intéressés au jeu avec 3 couleurs sur un arbre T. Nous souhaitons déterminer les arbres ayant un nombre chromatique ludique 3, soit ceux pour lesquels Alice a une stratégie gagnante avec 3 couleurs. Ce problème semblant difficile à résoudre sur les arbres, nous avons résolu des sous-familles: les 1-chenilles puis les chenilles sans trous. / Part 1: Domination Game and its variantsDomination game is a combinatorial game that consists in marking vertices of a graph so that a marked vertex has no marked neighbors. The first player unable to mark a vertex loses the game.Since the computing of winning strategies is an NP-hard problem for any graphs, we examine some specific families of graphs such as complete k-partite graphs, paths or saws. For these families, we establish the set of losing elements. For other families, such as caterpillars, we prove that exists a polynomial algorithm for the computation of outcome and winning strategies. No polynomial algorithm has been found to date for more general families, such as trees.We also study 28 variants of Domination game, including the 12 variants defined by J. Conway for any combinatorial game. Using game functions, we find the set of losing paths for 10 of these 12 variants. We also investigate 16 variants called diameter, for instance when rules require to play on the component that has the largest diameter.Part 2: The game chromatic number of treesThis parameter is computed from a coloring game: Alice and Bob alternatively color the vertices of a graph G, using one of the k colors in the color set. Alice has to achieve the coloring of the entire graph whereas Bob has to prevent this. Faigle and al. proved that the game chromatic number of a tree is at most 4. We undertake characterization of trees with a game chromatic number of 3. Since this problem seems difficult for general trees, we focus on sub-families: 1-caterpillars and caterpillars without holes.For these families we provide the characterization and also compute winning strategies for Alice and Bob. In order to do so, we are led to define a new notion, the bitype, that for a partially-colored graph G associates two letters indicating who has a winning strategy respectively on G and G with an isolated vertex. Bitypes allow us to demonstrate several properties, in particular to compute the game chromatic number of a graph from the bitypes of its connected components.

Depuis son introduction pour le jeu de Go, Monte Carlo Tree Search (MCTS) a été appliqué avec succès à d'autres jeux et a ouvert la voie à une famille de nouvelles méthodes comme Mutilple-MCTS ou Nested Monte Carlo. MCTS évalue un ensemble de situations de jeu à partir de milliers de fins de parties générées aléatoirement. À mesure que les simulations sont produites, le programme oriente dynamiquement sa recherche vers les coups les plus prometteurs. En particulier, MCTS a suscité l'intérêt de la communauté car elle obtient de remarquables performances sans avoir pour autant recours à de nombreuses connaissances expertes a priori. Dans cette thèse, nous avons choisi d'aborder MCTS comme un système apprenant à part entière. Les simulations sont alors autant d'expériences vécues par le système et les résultats sont autant de renforcements. L'apprentissage du système résulte alors de la complexe interaction entre deux composantes : l'acquisition progressive de représentations et la mobilisation de celles-ci lors des futures simulations. Dans cette optique, nous proposons deux approches indépendantes agissant sur chacune de ces composantes. La première approche accumule des représentations complémentaires pour améliorer la vraisemblance des simulations. La deuxième approche concentre la recherche autour d'objectifs intermédiaires afin de renforcer la qualité des représentations acquises. Les méthodes proposées ont été appliquées aux jeu de Go et du Clobber solitaire impartial. La dynamique acquise par le système lors des expérimentations illustre la relation entre ces deux composantes-clés de l'apprentissage / Monte Carlo Tree Search (MCTS) has been initially introduced for the game of Go but has now been applied successfully to other games and opens the way to a range of new methods such as Multiple-MCTS or Nested Monte Carlo. MCTS evaluates game states through thousands of random simulations. As the simulations are carried out, the program guides the search towards the most promising moves. MCTS achieves impressive results by this dynamic, without an extensive need for prior knowledge. In this thesis, we choose to tackle MCTS as a full learning system. As a consequence, each random simulation turns into a simulated experience and its outcome corresponds to the resulting reinforcement observed. Following this perspective, the learning of the system results from the complex interaction of two processes : the incremental acquisition of new representations and their exploitation in the consecutive simulations. From this point of view, we propose two different approaches to enhance both processes. The first approach gathers complementary representations in order to enhance the relevance of the simulations. The second approach focuses the search on local sub-goals in order to improve the quality of the representations acquired. The methods presented in this work have been applied to the games of Go and Impartial Solitaire Clobber. The results obtained in our experiments highlight the significance of these processes in the learning dynamic and draw up new perspectives to enhance further learning systems such as MCTS