14 mars 2022
Yann Strozecki (UVSQ, laboratoire DAVID)Les jeux stochastiques simples sont des jeux à deux joueurs, avec du hasard et à information parfaite. Deux joueurs déplacent à tour de rôle un jeton sur un graphe dans le but d’atteindre chacun un puits différent. L’objectif est de trouver le couple de stratégies optimales.
Trouver ce couple est relativement difficile : on ne connaît aucun algorithme polynomial ou quasi polynomial, contrairement aux jeux de parité, même si le problème n’est pas NP-complet (sous hypothèse de complexité).
Les algorithmes de résolution se rangent principalement dans trois catégories : programmation quadratique, propagation de valeur, et amélioration de stratégies.
On présente dans cet exposé un méta-algorithme qui généralise tous les algorithmes d’améliorations de stratégies connus. Cela nous permet de redémontrer facilement la correction de ces algorithmes, de supprimer certaines hypothèses ainsi que de donner de meilleures bornes de complexité.