Dans le monde d’aujourd’hui, Théorie des jeux combinatoires est toujours un sujet d’intérêt pour de nombreuses personnes. Avec les progrès de la technologie et la mondialisation, Théorie des jeux combinatoires est devenu un sujet pertinent dans la société contemporaine. Que Théorie des jeux combinatoires soit une personne, un événement historique ou un phénomène actuel, son impact sur nos vies ne peut être sous-estimé. Dans cet article, nous explorerons en profondeur les différentes facettes de Théorie des jeux combinatoires, en analysant son importance, ses implications et son influence dans divers domaines. De son origine à son état actuel, Théorie des jeux combinatoires a laissé une marque indélébile sur la société, et il est essentiel d’en comprendre la portée pour mieux comprendre le monde qui nous entoure.
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.
La théorie des jeux combinatoires est apparue en relation avec la théorie des 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 jeu de nim, complètement résolu en 1901 par C. L. Bouton. Puis, en 1907, 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 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, 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 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 (1996), More Games of No chance (2002) et Games of No chance 3 (2009).
Les jeux initialement considérés par la théorie des jeux combinatoires possèdent les propriétés suivantes :
S'il existe des positions avec des options différentes pour les deux joueurs, le jeu est dit partisan, et si les options disponibles sont toujours les mêmes pour les deux joueurs, le jeu est dit 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.
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 {GL+H, G+HL| GR+H, G+HR}. 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.
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 réels et les ordinaux, correspondent à un certain jeu :
Les nombres surréels contiennent aussi des nombres inconnus jusqu'alors, comme :
Mais la plupart des jeux ne sont pas des nombres, comme :
Comme le note Winning Ways for your Mathematical Plays, la théorie des jeux combinatoires est remarquable pour ses nombreuses identités surprenantes, comme {↑|↓}=* ou {0|↑}=↑+↑+*.