Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Théorie des jeux combinatoires
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.