Les jeux combinatoires, mathématiques et informatique

Le jeudi 28 octobre 2021 13h, Amphi 63, bâtiment 4A (4 cantons), nous aurons un séminaire sur “Les jeux combinatoires, mathématiques et informatique”, par Pierre Hyvernat (LAMA, Univ. Savoie Mont Blanc).

Résumé : Le morpion, le jeu de dames, les échecs, le go… Tous ces jeux ont en commun le fait qu’ils ne comportent pas d’aléatoire (jet de dés, distribution de cartes, etc.) et que l’état global est connu de tous. En conséquence, lors d’une partie, les joueurs ne peuvent s’appuyer sur rien d’autre que leurs connaissances des règles. Ceci implique aussi que la recherche de stratégies gagnantes est un problème particulièrement adapté aux ordinateurs, qui peuvent étudier de nombreux coups possibles très rapidement. Malheureusement, sauf pour des cas très simples, cette recherche reste vouée à l’échec à cause du nombre gigantesque de possibilités. L’étude de ces jeux doit donc commencer par une analyse de leurs propriétés mathématiques. C’est uniquement en prenant la structure du jeu considéré en compte que l’ordinateur peut espérer découvrir une stratégie gagnante et tenter de battre les joueurs humains. Pendant cette conférence, je montrerais sur des petits exemples (style morpion) le genre de propriétés que les mathématiciens recherchent, et comment on peut les mettre en œuvre pour gagner à tous les coups. En plus de ces jeux volontairement très simples, j’essaierai d’expliquer ce qui se passe dans des cas plus intéressants tels que le jeu de dames, le jeu d’échec ou le jeu de go.)