Feedback

Faculté des Sciences
Faculté des Sciences
MASTER THESIS
VIEW 76 | DOWNLOAD 12

Jeux de coloriage impartiaux

Download
Bouvier, Arnaud ULiège
Promotor(s) : Rigo, Michel ULiège
Date of defense : 28-Jun-2016 • Permalink : http://hdl.handle.net/2268.2/1562
Details
Title : Jeux de coloriage impartiaux
Translated title : [fr] Jeux de coloriage impartiaux
Author : Bouvier, Arnaud ULiège
Date of defense  : 28-Jun-2016
Advisor(s) : Rigo, Michel ULiège
Committee's member(s) : Leroy, Julien ULiège
Mathonet, Pierre ULiège
Vandomme, Elise ULiège
Language : French
Number of pages : 64
Keywords : [fr] Jeux
[fr] Sprague-Grundy
[fr] Coloriage
[fr] Graphe
[fr] Stratégie
Discipline(s) : Physical, chemical, mathematical & earth Sciences > Mathematics
Target public : Researchers
Professionals of domain
Student
Institution(s) : Université de Liège, Liège, Belgique
Degree: Master en sciences mathématiques, à finalité didactique
Faculty: Master thesis of the Faculté des Sciences

Abstract

[fr] Contrairement aux jeux dits "partisans", la particularité des jeux combinatoires impartiaux est que les deux joueurs ont des options de jeu identiques. Un des attraits de ces jeux aux règles généralement simples, est que les stratégies gagnantes sont parfois très compliquées à trouver, notamment pour les jeux de coloriage impartiaux. Ce travail s'articule principalement autour de l'article de G. Beaulieu, K. Burke et E. Duchêne, intitulé "Impartial Coloring Games". Il se décompose en huit chapitres.
En guise d’introduction, deux jeux combinatoires impartiaux très célèbres sont étudiés : le jeu des bâtonnets et le jeu de Marienbad. Ceux-ci permettent de présenter au lecteur les notions de stratégie et de position gagnantes ainsi que des démarches permettant d’obtenir une telle stratégie. De par sa simplicité, le jeu des bâtonnets est mis en lien avec un jeu joué sur un graphe, ce qui amène au cœur du sujet : les jeux de coloriage impartiaux.
Afin de pouvoir approfondir notre étude, certains outils théoriques relatifs aux notions de calculabilité et de la théorie de la complexité (machine de Turing, fonction calculable par machine de Turing, espaces PSPACE, problèmes décidables par machine de Turing, …) sont rappelés.
Ensuite, la fonction de Sprague-Grundy et certaines de ses extensions et applications, ainsi que les notions de mex, de jeu de coloriage successif et de valeur de Grundy d’une position d’un jeu de coloriage successif sont étudiées. La valeur de Grundy est alors étendue aux autres jeux combinatoires impartiaux par le biais du graphe des positions d’un jeu acyclique.
Enfin, lorsque le graphe sur lequel se déroule la partie est non connexe, il est naturel de considérer que l’on joue simultanément à plusieurs jeux de coloriage indépendants, sur des graphes connexes. Ceci mène à la notion de somme de jeux, à l’introduction de la somme de Nim et à un résultat très important en théorie des jeux combinatoires : le théorème de Sprague-Grundy.
Les définitions et résultats obtenus précédemment sont alors appliqués à divers jeux de coloriage impartiaux tels que les k-coloriages propres, coloriages orientés, faibles, 2-distants et séquentiels. Entre autres, pour les jeux précités, il est montré que déterminer si une position de ces jeux est gagnante est un problème PSPACE-complet.


File(s)

Document(s)

File
Access Mémoire_Bouvier.pdf
Description:
Size: 676.6 kB
Format: Adobe PDF

Author

  • Bouvier, Arnaud ULiège Université de Liège > Master sc. math., fin. dida. (ex 2e ma.)

Promotor(s)

Committee's member(s)

  • Total number of views 76
  • Total number of downloads 12










All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.