Théorie des genres
Ne doit pas être confondu avec Théorie du genre.
Le fond de cet article est à vérifier ().
Améliorez-le ou discutez des points à vérifier. Si vous venez d’apposer le bandeau, merci d’indiquer ici les points à vérifier.
Cet article doit être recyclé ().
Une réorganisation et une clarification du contenu paraissent nécessaires. , discutez des points à améliorer ou précisez les sections à recycler en utilisant {{section à recycler}}.
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
Pour l’article homonyme, voir genre.
La théorie des genres appliquée aux jeux impartiaux est une théorie qui appartient au domaine mathématique de la théorie des jeux et qui soutient que certains jeux faisant appel à une misère peuvent être analysés pour prédire leurs résultats
La théorie des genres a été publiée pour la première fois dans le livre On Numbers and Games puis plus tard dans Winning Ways for your Mathematical Plays Volume 2.
Contrairement au Théorème de Sprague-Grundy pour les jeux impartiaux en jeu normal la théorie des genres n'est pas une théorie complète pour les jeux impartiaux en jeu misère
Genre d'un jeu
[modifier | modifier le code]Le genre d'un jeu est défini en utilisant le mex (minimum exclu) des options d'un jeu.
g+ est la valeur du nimbre d'un jeu selon la convention de jeu normale.
g- ou λ0 représente la classe de résultat d'un jeu selon la convention du jeu misère.
Plus précisément, pour trouver g+, *0 est défini comme ayant g+ = 0, et tous les autres jeux ont g+ égal au mex de ses options.
λ1, λ2..., est égal à la valeur g− d'un jeu ajouté à un nombre de jeux *2 nim, où le nombre est égal à l'indice.
Ainsi le genre d'un jeu est gλ0λ1λ2....
*0 a une valeur de genre 0120. Notez que l'exposant continue indéfiniment, mais en pratique, un exposant s'écrit avec un nombre fini de chiffres, car on peut prouver qu'à un moment donné, les 2 derniers chiffres alternent indéfiniment…
Résultats des sommes des jeux
[modifier | modifier le code]Il peut être utilisé pour prédire le résultat de:
- La somme de n'importe quels nimbres et de n'importe quels jeux apprivoisés[Quoi ?]
- La somme d'un jeu donné en fonction de son genre, d'un nombre quelconque de jeux nim *1, *2 ou *3, et éventuellement d'un autre jeu nim avec un numéro 4 ou supérieur.
- La somme d'un jeu rétif et de n'importe quel nombre de jeux Nim de n'importe quelle taille.
En outre, certaines paires rétives ou agitées peuvent former des jeux apprivoisés, si elles sont équivalentes. Deux jeux sont équivalents s'ils ont les mêmes options, où les mêmes options sont définies comme des options pour des jeux équivalents. Ajouter une option à partir de laquelle il existe un mouvement réversible n'affecte pas l'équivalence.
Certaines paires rétives, lorsqu'elles sont ajoutées à un autre jeu rétif de la même espèce, restent apprivoisées.
Un jeu semi-apprivoisé, ajouté à lui-même, est équivalent à *0.
Mouvements réversibles
[modifier | modifier le code]Il est important pour une meilleure compréhension de la théorie des genres de savoir comment fonctionnent les mouvements réversibles. Supposons qu'il y ait deux jeux A et B, où A et B ont les mêmes options (mouvements disponibles), alors ils sont bien sûr équivalents.
Si B a une option supplémentaire, disons pour un jeu X, alors A et B restent équivalents s'il existe un mouvement de X vers A.
Autrement dit, B est identique à A de toute manière, à l’exception d’un mouvement supplémentaire (X), qui peut être inversé.
Types de jeux
[modifier | modifier le code]Différents jeux (positions) peuvent être classés en plusieurs types:
Nim
[modifier | modifier le code]Cela ne signifie pas qu'une position est exactement comme un tas Nim selon la convention de jeu en misère mais classer un jeu comme nim signifie qu'il est équivalent à un tas Nim.
Un jeu est un jeu nim si:
- il a un genre 01, 10, 22, 33…
- Il a des mouvements uniquement vers des tas Nim individuels, c'est-à-dire se déplace vers une position *1, ou *2, mais pas par exemple *x+*y (mais voir le point suivant)
- il peut également avoir des mouvements vers des jeux qui ne sont pas nim, à condition qu'ils ne soient pas nécessaires pour déterminer le genre, et que ces jeux ont chacun au moins une option vers un jeu nim du même genre
Apprivoisé
[modifier | modifier le code]Il s'agit de positions que l'on peut considérer comme des positions Nim (notez la différence entre les positions Nim, qui peuvent être plusieurs tas Nim ajoutés ensemble, et un seul tas Nim, qui ne peut être qu'un seul tas Nim). Un jeu G est apprivoisé si :
- il a un genre 01, 10, or 00, 11, 22, 33...
- toutes les options de G sont apprivoisées
- G peut également avoir des options sauvages (positions qui ne sont pas apprivoisées ou nim) si elles n'affectent pas le genre,et chaque option a des mouvements réversibles vers des jeux apprivoisés avec le genre g? et ?λ .
Notez que les mouvements vers g? et ?λ peuvent en réalité être la même option. (? signifie n'importe quel nombre)
Rétif
[modifier | modifier le code]Agité
[modifier | modifier le code]Semi-apprivoisé
[modifier | modifier le code]Sauvage
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- Sur les nombres et les jeux par John Horton Conway
- Des moyens gagnants pour vos pièces mathématiques par Elwyn Berlekamp, John Conway et Richard Guy
Notes et références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Genus theory » (voir la liste des auteurs).
