Voir la source de Théorie des jeux combinatoires

[[Image:Mathematicians playing Konane.jpg|vignette|Mathématiciens jouant à [[Konane]] lors d'un séminaire sur la théorie des jeux combinatoires.]]
{{Autre4||la théorie qui inclut les jeux où le hasard intervient ou les jeux à information incomplète|Théorie des jeux}}

La '''théorie des jeux combinatoires''' est une théorie mathématique qui étudie les jeux à deux joueurs comportant un concept de ''position'', et où les joueurs jouent à tour de rôle un ''coup'' d'une façon définie par les règles, dans le but d'atteindre une certaine condition de victoire. La théorie des jeux combinatoires a pour objet les jeux à information complète où le hasard n'intervient pas, comme les [[échecs]], les [[dames]] ou le [[jeu de go]].

== Historique ==
[[Fichier:John H Conway 2005.jpg|vignette|John Horton Conway, né le 26 décembre 1937 à Liverpool et mort le 11 avril 2020 à New Brunswick (New Jersey), est un mathématicien britannique. Il s'est intéressé aux théories des groupes finis, des nœuds, des nombres, des jeux combinatoires et du codage.]]
La théorie des jeux combinatoires est apparue en relation avec la théorie des [[jeu impartial|jeux impartiaux]], où les coups disponibles à partir d'une position sont les mêmes pour les deux joueurs. Un jeu impartial particulièrement important est le [[Jeux de Nim|jeu de nim]], complètement résolu en 1901 par C. L. Bouton. Puis, en 1907, [[Willem Abraham Wythoff|Willem Wythoff]] invente et publie une solution du [[jeu de Wythoff]], une variante du jeu de Nim. Dans les années 1930, Sprague et Grundy démontrent alors indépendamment le [[théorème de Sprague-Grundy]], qui stipule que tout jeu impartial est équivalent à un certain tas du jeu de Nim. Ce théorème a ainsi montré que des unifications importantes étaient possibles lorsque les jeux sont considérés à un niveau combinatoire.

Les premiers [[jeu partisan|jeux partisans]], dans lesquels les coups disponibles ne sont plus forcément identiques pour les deux joueurs, semblent avoir été considérés par John Milnor en 1953<ref>Richard J. Nowakowski ''{{lien brisé|url=http://www.mathstat.dal.ca/~rjn/papers/HistoryCGT.pdf |titre=The History of Combinatorial Game Theory }}'' Jan. 2009</ref>, mais c'est la rencontre de [[Elwyn Berlekamp]], [[John Conway]] et [[Richard Guy]] qui est le point de départ d'une théorie complète dans les années 1960.

Le premier livre traitant de la théorie des [[jeu partisan|jeux partisans]], ''[[On Numbers and Games]]'', est publié par [[John Conway]] en 1976. Il y est notamment défini les [[nombres surréels]] et le concept plus général de [[jeu partisan]]. Puis, en 1982, l'ensemble des résultats de Berlekamp, Conway et Guy est publié dans leur livre ''[[Winning Ways for your Mathematical Plays]]'', qui reste à ce jour la référence en la matière.

À partir de 1982, le sujet a ensuite fait l'objet de nombreuses publications. Une sélection d'articles par Richard J. Nowakowski a notamment été publiée dans la série de livres ''Games of No chance''<ref>{{Ouvrage |langue=en |auteur1=Richard J. Nowakowski |titre=Games of no chance |sous-titre=combinatorial games at MSRI, 1994 |lieu=Cambridge, New York et Melbourne |éditeur=[[Cambridge University Press]] |nature ouvrage=[[actes de congrès]] |collection=[[Mathematical Sciences Research Institute]] publications |numéro dans collection=29 |année=1996 |pages totales=537 |isbn=0-521-57411-0 |issn=0940-4740 |oclc=1036013393 |bnf=37499237z |sudoc=026271184 |s2cid=119025791 |lire en ligne=http://library.msri.org/books/Book29/contents.html}}.</ref> (1996), ''More Games of No chance''<ref>{{Ouvrage |langue=en |auteur1=Richard J. Nowakowski |titre=More games of no chance |lieu=Cambridge |éditeur=Cambridge University Press |nature ouvrage=actes de congrès |collection=Mathematical Sciences Research Institute publications |numéro dans collection=42 |année=2002 |pages totales=535 |isbn=0-521-80832-4 |isbn2=978-0-521-80832-3 |isbn3=978-0-521-15563-2 |issn=0940-4740 |bnf=38966676m |sudoc=076722821 |lire en ligne=http://library.msri.org/books/Book42/contents.html}}.</ref> (2002) et ''Games of No chance 3''<ref>Richard J. Nowakowski ''[http://www.msri.org/communications/books/Book56/ Games of No chance 3]'' Cambridge University Press, Cambridge, 2002.</ref> (2009).

== Définition des jeux ==

Les jeux initialement considérés par la théorie des jeux combinatoires possèdent les propriétés suivantes<ref>{{Ouvrage|lang=en|prénom1=Elwyn|nom1=Berlekamp|prénom2=John H.|nom2=Conway|prénom3=Richard|nom3=Guy|titre=Winning Ways for your Mathematical Plays|éditeur=[[A K Peters]]|année=2001|volume=1|page=14}}.</ref> :
* Deux joueurs, appelés '''Left''' (gauche) et '''Right''' (droite), jouent alternativement.
* Le jeu consiste en un certain nombre, généralement fini, de '''positions''', et une position particulière est appelée '''position de départ'''.
* Les règles précisent clairement les coups qu'un joueur peut réaliser à partir d'une position donnée. Les positions accessibles par un joueur sont appelées ses '''options'''.
* Les deux joueurs connaissent parfaitement l'état du jeu, c'est-à-dire que le jeu est à information complète.
* Il n'y a aucune intervention du hasard.
* La partie se termine lorsqu'un joueur ne peut plus jouer, et les règles assurent que toute partie se termine en un nombre fini de coups (ce qui est appelé la '''condition de terminaison''').
* Dans la convention normale de jeu, le joueur qui ne peut plus jouer est le perdant.

S'il existe des positions avec des options différentes pour les deux joueurs, le jeu est dit [[jeu partisan|partisan]], et si les options disponibles sont toujours les mêmes pour les deux joueurs, le jeu est dit [[jeu impartial|impartial]].

Les jeux comme les [[échecs]] ou les [[dames]] n'appartiennent pas à cette catégorie de jeux puisqu'ils font intervenir la notion de partie nulle.

Une définition récursive et formelle des jeux a été donnée dans ''[[On Numbers and Games]]'' en 1976 : si L et R sont chacun un ensemble de jeux, alors '''{L|R}''' est un jeu. L représente l'ensemble des options du joueur Left et R l'ensemble des options du joueur Right. Les noms des joueurs viennent du fait que les options de Left sont écrites à gauche, et celles de Right à droite dans la notation précédente.

== Somme de jeux ==

La somme de deux jeux G et H, notée G+H, est définie comme le jeu où un joueur peut jouer soit dans G soit dans H, en laissant l'autre composante intacte. Formellement, la somme G+H est définie par {G<sup>L</sup>+H, G+H<sup>L</sup>| G<sup>R</sup>+H, G+H<sup>R</sup>}. Le principal but de la théorie des jeux combinatoires est de définir une méthode permettant de déterminer quel est le joueur qui gagne une somme de jeux, à partir d'informations indépendantes sur chacune des composantes.

== Notation des jeux ==

Certains jeux possèdent une notation particulière.

Les [[nombres surréels]] sont un cas particulier de jeu, et tous les nombres classiques, en particulier les [[nombre réel|réels]] et les [[nombre ordinal|ordinaux]], correspondent à un certain jeu :
: <math>{0} = \left\{ |  \right\}</math>
: <math>{1} = \left\{ 0 |  \right\}, {2} = \left\{1 |  \right\}, {3} = \left\{2 |  \right\}</math>
: <math>{-1} = \left\{ |0  \right\}, {-2} = \left\{ | -1 \right\}, {-3} = \left\{ | -2 \right\}</math>
: <math>{1 \over 2} = \left\{ 0 | 1 \right\}</math>
: <math>\omega = \left\{ 0,1,2,3,\cdots | \right\}</math>
:<math>\omega + 1 = \left\{ \omega | \right\}</math>

Les nombres surréels contiennent aussi des nombres inconnus jusqu'alors, comme :
:<math>\omega - 1 = \left\{0,1,2,3,\cdots | \omega \right\}</math>

Mais la plupart des jeux ne sont pas des nombres, comme :
: * = {0|0} étoile (star en anglais), qui vérifie * + * = 0
: *n = {*0, *1, ... *(n-1) | *0, *1, ... *(n-1) } [[nimber]] n
: x* = {x | x} = x + * pour tout nombre x
: ↑ = {0|*} haut (up en anglais)
: ↓ = {*|0} bas (down en anglais)

Comme le note [[Winning Ways for your Mathematical Plays]]<ref>{{en}} E. Berlekamp, J. H. Conway et R. Guy, ''Winning Ways for your Mathematical Plays'', A. K. Peters Ltd., 2001, {{vol.|1}}, {{p.|71}}.</ref>, la théorie des jeux combinatoires est remarquable pour ses nombreuses identités surprenantes, comme {↑|↓}=* ou {0|↑}=↑+↑+*.

== Notes et références ==
{{Traduction/Référence|en|Combinatorial game theory|377067896|type=note}}
{{Références}}

== Voir aussi ==
{{Autres projets
  | wikiversity       = Jeux combinatoires
  | wikiversity titre = Jeux combinatoires
}}
=== Bibliographie ===
* {{Ouvrage |langue=en |nom1={{Lien|langue=en|fr=Michael H. Albert}} |prénom2=Richard J. |nom2=Nowakowski |prénom3=David |nom3=Wolfe |titre=Lessons in Play |sous-titre=An Introduction to Combinatorial Game Theory |éditeur=[[A K Peters]] |année=2007 |pages totales=304 |isbn=978-1-56881-277-9}}.
* {{Ouvrage |langue=en |auteur1=[[Jörg Bewersdorff]] |titre=Luck, Logic, and White Lies |sous-titre=The Mathematics of Games |éditeur=A K Peters |année=2004 |pages totales=486 |passage=169-261 |isbn=978-1-56881-210-6}}.

=== Liens ===
{{Liens}}

{{Palette|Théorie des jeux}}
{{portail|mathématiques|informatique théorique}}

[[Catégorie:Théorie des jeux combinatoires| ]]
[[Catégorie:Combinatoire]]
[[Catégorie:John Horton Conway]]