Ê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 Graph Search.
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.
Proximité ontologique
Cours associés (5)
PHYS-435: Statistical physics III
This course introduces statistical field theory, and uses concepts related to phase transitions to discuss a variety of complex systems (random walks and polymers, disordered systems, combinatorial o
ME-429: Multi-agent learning and control
Students will be able to formulate a multi-agent decision-making problem as a game and apply relevant mathematical theories and algorithms to analyze the interaction of the agents and predict the outc
MGT-300: Game theory and strategic decisions
Game theory studies the strategic interactions between rational agents. It has a myriad of applications in politics, business, sports. A special branch of Game Theory, Auction Theory, has recently g
Séances de cours associées (26)
Introduction à la théorie des jeux
Couvre les fondamentaux de la théorie des jeux, l'équilibre de Nash et les interactions stratégiques dans les systèmes multi-agents.
Agents intelligents : prendre des décisions et planifier
Couvre les agents intelligents, la prise de décision, la planification, l'apprentissage automatique et la théorie des jeux.
Monte Carlo Tree Search et Alpha Zero
Explore Monte Carlo Tree Search et Alpha Zero dans l'apprentissage par renforcement profond.
Publications associées (38)
Personnes associées (4)
Concepts associés (17)
Game complexity
Combinatorial game theory measures game complexity in several ways: State-space complexity (the number of legal game positions from the initial position), Game tree size (total number of possible games), Decision complexity (number of leaf nodes in the smallest decision tree for initial position), Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position), Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large).
Arbre de jeu
En théorie des jeux, un arbre de jeu est un arbre (au sens de la théorie des graphes) dont les nœuds sont des positions dans un jeu et dont les arêtes sont des mouvements. L'arbre de jeu complet est l'arbre de jeu commençant à la position initiale et contenant tous les mouvements possibles depuis chaque position. vignette| Les deux premiers de l'arbre de jeu pour le tic-tac-toe. Le diagramme ci-contre montre comment coder dans une représentation arborescente le premier tour de jeu au tic-tac-toe : ce sont les deux premiers niveaux dans l'arborescence, la racine représentant la position initiale (une grille vide, en l'occurrence).
Jeu séquentiel
vignette| Les échecs sont un exemple de jeu séquentiel. En théorie des jeux, un jeu séquentiel est un jeu où les joueurs choisissent leur actions à tour de rôle. Pour qu'un jeu soit séquentiel il faut que certaines informations sur les choix d'un joueur à son tour soient connues par les joueurs suivants avant qu'ils ne fassent eux-mêmes leur choix; sans cela, le tour du premier joueur n'aurait pas d'effet sur la stratégie des suivants. Les jeux séquentiels sont donc régis par l'axe du temps, et peuvent être représentés sous forme d'arbres de décision.