Algorithme de résolution de jeu

Le cadre de ce projet est relié à la théorie des jeux et surtout à une classe de jeu particulière : les jeux stochastiques dans lesquels le jeu varie en fonction des actions des agents et d’un environnement aléatoire. Ces jeux peuvent représenter un grand nombre de situations : en économie, en sécurité des réseaux, en partage de ressources ou encore en modélisation de systèmes multi agents. En effet, ils permettent de modéliser plus finement les interactions entre les agents (les joueurs) au cours du temps dans un environnement qui évolue. Ces jeux sont parfois appelés Competitive MDP puisqu’ils peuvent être vus comme des processus de décision à plusieurs agents [2].

Le but du projet est de coder des algorithmes de résolution de tels jeux et de les appliquer à un ensemble de jeux simples de type ami-ennemi (friend or foe) tels que « papier, caillou ciseau » ou un modèle très très simplifié de jeu de football. Nous considérerons deux grandes classes de résolution : une basée sur des méthodes par apprentissage [3] et l’autre basée sur des méthodes numériques plus classiques avec une méthode dite de Newton [2].

Le langage de programmation est libre entre python et C mais l’usage du C permet d’utiliser une bibliothèque open source Marmote [1] et plus précisément sa bibliothèque de résolution des Processus de Décision Markovien qui offre un certain nombre de fonctionnalités déjà implémentées mais aucune résolution de jeu n’est encore codée toutefois.

Les tâches à réaliser vont être de plusieurs types et vont permettre d’appréhender les principaux aspects du développement d’un algorithme scientifique (potentiellement en intégrant un code déjà existant).
Ce projet va se diviser en plusieurs phases :
- a) Appréhender et comprendre le cadre des jeux et celui des algorithmes de résolution associés.
- b) Conceptualiser et réfléchir à une architecture de code.
- c) Développement, test, et évolution de plusieurs algorithmes de résolution des jeux stochastiques.
- d) Comparaison de l’efficacité sur des jeux simples.

[1] http://marmotecore.gforge.inria.fr/dokuwiki/doku.php?id=start
[2] Filar J., Vrieze K. : « Competitive Markov Decision Processes », Springer 1996.
[3] M. Littman : « Friend-or-Foe : Q-learning in General-Sum Games », ICML 2001.