Challenge an opponent in a PyRat game

Project – Session 6

  • Théorie des jeux combinatoires
  • Calcul des positions gagnantes dans un jeu

Théorie des jeux combinatoires

Jouer à un jeu peut être vu comme un graphe de configurations

  • Explorer ce graphe (arène) peut se faire en utilisant une stratégie
  • Une stratégie est une fonction qui, donnée une configuration, retourne l’action suivante

Calcul des positions gagnantes dans un jeu

Le but est d’atteindre une configuration gagnante

  • D’abord, identifier les configurations qui sont gagnantes

Calcul des positions gagnantes dans un jeu

Le but est d’atteindre une configuration gagnante

  • Puis, étendre à toutes les configurations qui permettent d’atteindre une configuration gagnante en une seule action

Calcul des positions gagnantes dans un jeu

Le but est d’atteindre une configuration gagnante

  • Étendre à toutes les configurations qui permettent d’atteindre une configuration trouvée précédemment en une seule action

Calcul des positions gagnantes dans un jeu

Le but est d’atteindre une configuration gagnante

  • Continuer ce processus jusqu’à saturation pour identifier la région gagnante
  • Dans les autres configurations, l’adversaire peut gagner ou forcer un match nul

Calcul des positions gagnantes dans un jeu

Attention à la complexité

Récapitulatif de la session

Éléments principaux à retenir

  • La théorie des jeux peut être utilisée pour calculer les positions gagnantes dans un jeu multi-joueurs

  • Il existe de nombreux types de jeux (simultanés, information parfaite, etc.) $\rightarrow$ consultez les articles

  • Une stratégie est une fonction qui, donnée une configuration, retourne l’action suivante

  • Une stratégie détermine comment explorer l’arène du jeu

  • Le but est d’atteindre une configuration gagnante

  • Cela peut se faire de manière itérative pour identifier la région gagnante

  • D’autres approches existent (par exemple, basées sur des heuristiques) pour réduire la complexité

Récapitulatif de la session

Et ensuite ?

Activité pratique (~2h30)

Affrontez un adversaire

  • Pensez à votre propre stratégie
  • Consultez la page du tournoi
  • Inspirez-vous des articles ou inventez quelque chose de nouveau !

Tournoi

  • Lundi 16, 16:45
  • Pour le plaisir et la gloire !
  • Soumettez votre IA avant le vendredi 13, 23:59

Après la session

  • Relisez les articles de la session
  • Vérifiez votre compréhension avec le quiz
  • Complétez l’activité pratique

Évaluation

  • Présentation finale de votre stratégie
  • Consultez la page du projet pour les détails