Combinatorial game theory

Reading time15 min

En bref

Résumé de l’article

Dans cet article, nous vous présentons quelques éléments de la “théorie des jeux”.
Cette branche des mathématiques étudie les stratégies, et a de nombreuses applications dans des domaines tels que l’optimisation, la politique ou l’économie.

Points clés

  • La théorie des jeux représente un jeu dans un espace abstrait de configurations.

  • Une stratégie consiste en une fonction qui explique quelle configuration suivante atteindre, étant donné la configuration actuelle du jeu.

  • Il existe des résultats mathématiques sur les jeux, tels que le théorème de von Neumann.

  • Ces résultats s’appliquent à de nombreux domaines de la vie réelle.

Contenu de l’article

1 — Vidéo

Veuillez regarder la vidéo ci-dessous.
Vous pouvez également lire la transcription si vous préférez.

Information

C’est encore moi !
Bienvenue, je suis ravi de vous revoir.
Commençons par quelques notions de base sur la théorie des jeux.

La théorie des jeux est le domaine scientifique qui s’intéresse à l’étude des jeux, des stratégies et des conditions de victoire.

Contexte

Les jeux jouent un rôle important dans de nombreux domaines scientifiques. Les jeux sont largement utilisés en économie et en mathématiques, mais ont aussi des applications en cryptographie où, typiquement, le but d'un jeu est de protéger des informations, ainsi que dans les systèmes d'exploitation où le but du jeu est généralement de prévenir les erreurs, ou encore en intelligence artificielle.

Les jeux sont un cadre très adapté pour notre jeu dans le labyrinthe, et une excellente excuse pour explorer des algorithmes avancés.

Si vous parvenez à coder un programme qui calcule les positions gagnantes dans un jeu, vous serez prêt pour presque tous les défis de programmation !

Définitions de base

Rappelons que nous souhaitons jouer à un jeu dans un labyrinthe où deux joueurs, un rat et un python, essaient de ramasser tous les morceaux de fromage avant leur adversaire.

Pendant le jeu, ces joueurs peuvent prendre des décisions simultanément.
Par exemple, le python peut décider de se déplacer à gauche tandis que le rat décide de monter.

Pour décrire un jeu, nous utilisons un graphe très spécifique que nous appelons “l’arène”.
L’arène est un graphe où chaque sommet résume l’état actuel du jeu.
Par état du jeu, nous entendons les positions des joueurs, les positions des morceaux de fromage restants, et le score de chaque joueur.

Par exemple, il y a un sommet initial qui correspond à la configuration initiale où le rat et le python ont tous deux un score de 0 et sont à leurs positions de départ, et tous les morceaux de fromage sont dispersés dans le labyrinthe. Ensuite, il y a aussi des sommets correspondant à toutes les configurations possibles qui pourraient survenir durant une partie de PyRat. Les sommets sont reliés par des arêtes étiquetées selon deux variables. La première variable correspond à la décision prise par le rat et la seconde à la décision prise par le python.

Êtes-vous prêt pour un exemple ? Considérons un jeu simple où un labyrinthe de 3 par 3 contient un seul morceau de fromage au centre et où le rat et le python sont tous deux en compétition pour l'obtenir. À partir de la configuration initiale, plusieurs choses peuvent se produire. Le rat peut se déplacer à droite, en haut, ou ne pas bouger, et le python peut se déplacer à gauche, en bas, ou ne pas bouger. Nous avons donc 3 fois 3, soit 9, configurations qui peuvent être atteintes à partir de la configuration initiale.

Voici ce qui se passe si le rat monte et que le python va à gauche. Voici ce qui se passe si le rat monte et que le python reste immobile. Voici ce qui se passe si le rat monte et que le python descend. Voici ce qui se passe si le rat va à droite et que le python va à gauche. Voici ce qui se passe si le rat va à droite et que le python reste immobile. Voici ce qui se passe si le rat va à droite et que le python descend. Voici ce qui se passe si le rat reste immobile et que le python va à gauche. Voici ce qui se passe si le rat reste immobile et que le python descend. Et enfin, voici ce qui se passe si le rat et le python restent tous deux immobiles.

Il y a plusieurs sommets dans l’arène correspondant à la fin du jeu, lorsque le rat ou le python atteint la position centrale qui contient le fromage.
Le premier joueur à atteindre cette position sera le gagnant.

Une "stratégie" d'un joueur est une fonction qui associe à chaque sommet de l'arène, ce qui peut aussi être décrit comme chaque état du jeu, un coup pour ce joueur.

Un exemple de stratégie est un algorithme glouton qui consiste à se diriger systématiquement vers le morceau de fromage le plus proche dans le labyrinthe. Une fois que les deux joueurs ont choisi leurs stratégies, le jeu peut être entièrement connu et le gagnant peut être identifié en laissant la partie de PyRat se dérouler.

Ainsi, une partie peut être vue comme une marche dans l’arène, dépendant des deux stratégies choisies.

Mots de conclusion

Voilà, c’est tout pour moi !
Dans la prochaine leçon, Patrick vous montrera comment calculer de bonnes stratégies.

Pour aller plus loin

2 — Le théorème minimax de von Neumann

2.1 — Catégories de jeux

Il existe plusieurs catégories de jeux, selon que les joueurs jouent simultanément (ex. pierre-papier-ciseaux) ou non (ex. échecs), si les joueurs peuvent cacher certaines informations (ex. poker), etc.

Dans le cas de PyRat, nous considérons un jeu “simultané”.
Cela signifie que les deux joueurs prennent des décisions en même temps.
C’est le cas dans une partie normale de PyRat, car les mouvements sont appliqués à une période fixe.

PyRat est aussi un jeu à “information parfaite”, car toutes les informations sur le plateau, toutes les décisions possibles qui peuvent être prises (et les gains qui en résulteraient), ainsi que l’objectif du jeu, sont connus de tous les joueurs.

De plus, le jeu est “non coopératif”, car chaque joueur essaie de gagner contre l’autre.

En outre, PyRat est un jeu à “somme nulle”, car un morceau de fromage pris par un joueur ne sera pas pris par l’adversaire.

Enfin, PyRat admet un nombre fini de stratégies pures, car le nombre de décisions possibles par sommet de l’arène est un entier.
Une stratégie pure est une définition complète de la façon dont un joueur jouera une partie.
En particulier, elle détermine le coup qu’un joueur fera pour chaque situation qu’il pourrait rencontrer.
Lorsqu’une stratégie attribue des probabilités à chaque décision, on parle de stratégie mixte.

2.2 — Le théorème

Le théorème minimax de John von Neumann est un résultat important en théorie des jeux.
Dans un jeu non coopératif, simultané, à information parfaite, avec un nombre fini de stratégies pures et à somme nulle, le théorème affirme qu’il existe au moins une situation d’interaction stable, à savoir une situation dans laquelle aucun des deux joueurs n’a intérêt à changer sa stratégie mixte si l’autre ne la change pas.

En d’autres termes, ce que dit le théorème, c’est qu’il existe une situation dans laquelle les deux joueurs devraient se stabiliser, car changer de stratégie n’améliorerait pas les gains tant que l’adversaire ne change pas non plus de stratégie.

Pour aller plus loin