Approche computationnelle des jeux
Ref: 1SC2810
Description
La théorie des jeux est l'étude formelle de l'interaction entre les systèmes ou agents rationnels définis par des objectifs qu'ils cherchent à atteindre et par les options stratégiques qui se présentent à eux afin de les atteindre, stratégies qui peuvent éventuellement être interdépendantes (c’est-à-dire des situations dans lesquelles le sort de chaque participant dépend non seulement des décisions qu’il prend, mais également des décisions prises par les autres participants). Dans ce cours, nous aborderons plus spécifiquement l'approche computationnelle des jeux qui se base sur des modélisations informatiques des situations de jeux (modèles à base d'états et graphes, modèles à base de contraintes.. ) et qui s'attache à automatiser la recherche de stratégies et à analyser leurs performances (optimalité). Ce cours abordera la théorie et la pratique de la recherche de solutions optimales et satisfaisantes pour les jeux combinatoires à plusieurs joueurs, tels que les jeux populaires tels que Soduku, Sokoban, Othello, Dames… Il inclura les points suivants : la représentation pertinente des informations, la prise de décisions intelligentes (c'est-à-dire satisfaisantes, quasi-optimales ou optimales), la modélisation de séquences d'actions, la prise en compte des gains et de la structure de l’information et la capitalisation de l'expérience, l'agrégation de préférences conflictuelles, les algorithmes de parcours des espaces de jeu combinatoires.
Période(s) du cours
ST2
Prérequis
Le cours d’algorithmique et complexité, commun à tous lors de cette séquence.
Syllabus
Théorie des jeux
Terminologie (jeu, paiement., stratégies, ..), Modélisation et différentes représentations d'un jeu (forme stratégique - forme extensive), Domaine d'applications : économie, tarification, enchères, routage, ...
Jeu sous forme normale : Stratégies dominées, prudentes, bien-être social, optimum de Pareto. Exemples représentatifs : Dilemme du prisonnier, Bataille des sexes, Jeux coopératifs. Stratégies pures et mixtes, Equilibres de Nash. Jeux compétitifs, Jeux répétés. Jeux bayesiens.
Jeux sous forme extensive : définition, modélisation (arbre de jeu), à information parfaite ou imparfaite, avec hasard, sélection de stratégie, induction à rebours, équilibres parfaits en sous-jeux, représentation équivalente sous forme stratégique
Jeux de réflexion (Soduku, Nonogramme, …) : introduction, modélisation à l'aide de contraintes - Algorithmes de résolution des problèmes de satisfaction de contraintes (propagation, arc consistance)
Jeux séquentiels à 2 joueurs : étude théorique, résolution pratique et recherche d'une stratégie gagnante. Cette partie sera illustrée par des exemples typiques de jeux combinatoires comme le jeu de Nim. Algorithmes pour les stratégies par méthode adversariale (minmax, alphabeta) ou approchée (Monte Carlo, Algorithme A*...)
Jeux à information incomplète : jeux et équilibres bayésiens.
Jeux de réflexion (Soduku, Nonogramme, …) : introduction, modélisation à l'aide de contraintes - Algorithmes de résolution des problèmes de satisfaction de contraintes (propagation, arc consistance)
Composition du cours
Organisation classique avec des séance de cours, TD et TP
Ressources
Ordinateurs personnels
Support de cours, bibliographie
Diapositives du cours - Polycopié - Sujets et corrigés des TDs