La théorie des jeux combinatoires, également connue sous le nom de CGT, est une branche des mathématiques appliquées et de l'informatique théorique qui étudie les jeux combinatoires, et se distingue de la théorie des jeux "traditionnels" ou "économiques". La CGT est apparue en relation avec la théorie des jeux impartiaux, le jeu à deux joueurs de Nim en particulier, avec un accent sur la "résolution" de certains types de jeux combinatoires.
Un jeu doit remplir plusieurs conditions pour être un jeu combinatoire. Ces conditions sont les suivantes :
- Le jeu doit avoir au moins deux joueurs.
- Le jeu doit être séquentiel (c'est-à-dire que les joueurs alternent les tours).
- Le jeu doit comporter des informations parfaites (c'est-à-dire qu'aucune information n'est cachée, comme au poker).
- Le jeu doit être déterministe (c'est-à-dire non aléatoire). La chance ne fait pas partie du jeu.
- Le jeu doit avoir un nombre défini de coups possibles.
- Le jeu doit finir par s'arrêter.
- La partie doit se terminer lorsqu'un joueur ne peut plus bouger.
La théorie des jeux combinatoires se limite en grande partie à l'étude d'un sous-ensemble de jeux combinatoires à deux joueurs, finis, avec un gagnant et un perdant (c'est-à-dire qui ne se terminent pas par un match nul).
Ces jeux combinatoires peuvent être représentés par des arbres, dont chaque sommet est le jeu résultant d'un coup particulier du jeu situé directement en dessous sur l'arbre. Des valeurs de jeu peuvent être attribuées à ces jeux. Trouver ces valeurs de jeu est d'un grand intérêt pour les théoriciens de la CG, tout comme le concept théorique de l'addition de jeux. La somme de deux parties est la partie dans laquelle chaque joueur doit, à son tour, se déplacer dans une seule des deux parties, en laissant l'autre telle quelle.
Elwyn Berlekamp, John Conway et Richard Guy sont les fondateurs de cette théorie. Ils ont travaillé ensemble dans les années 1960. Leur ouvrage publié s'intitulait Winning Ways for Your Mathematical Plays.
