Description du projet
Dans les jeux à plusieurs participants où les règles du jeu
interdisent normalement à des joueurs de coopérer, une collusion
correspond à une situation où certains joueurs collaborent
secrètement afin d'augmenter leur gains conjoints ou de favoriser le
score d'un des joueurs. Par exemple, dans le cas d'un jeu tel que le
poker si deux joueurs s'entendent sur une stratégie commune et
partagent l'information partielle du jeu concernant leurs mains, ils
peuvent gagner en moyenne plus d'argent conjointement que si chacun
jouait indépendamment et honnêtement.
Une des difficultés principales pour détecter une collusion est que du point de vue d'un observateur extérieur et pour une partie particulière, les joueurs suivent les règles du jeu et donc leur comportement pourraient correspondre à celui adopter par des joueurs honnêtes et indépendants. Une collusion ne peut donc être détecter qu'a posteriori en observant le comportement des joueurs sur le long terme (pendant plusieurs parties) et en détectant une déviation statistiquement significative du comportement d'un certain groupe de joueurs (ou de leurs gains conjoints) par rapport à celui de joueurs "moyens honnêtes".
Une des difficultés principales pour détecter une collusion est que du point de vue d'un observateur extérieur et pour une partie particulière, les joueurs suivent les règles du jeu et donc leur comportement pourraient correspondre à celui adopter par des joueurs honnêtes et indépendants. Une collusion ne peut donc être détecter qu'a posteriori en observant le comportement des joueurs sur le long terme (pendant plusieurs parties) et en détectant une déviation statistiquement significative du comportement d'un certain groupe de joueurs (ou de leurs gains conjoints) par rapport à celui de joueurs "moyens honnêtes".
Sujet de projet
L'objectif est de ce projet est de développer une méthode pour
modéliser et détecter les collusions pour le jeu Pakupaku. Le Pakupaku
est une variante du jeu Pacman où chaque joueur est un pacman
cherchant à manger le plus possible de pastilles possibles qui ont été
déposées aléatoirement sur une aire de jeu en un temps donné. Il
existe plusieurs versions du jeu, ainsi les joueurs pourraient avoir
une connaissance complète de l'aire de jeu ou seulement partielle (les
pacmans ne voient que dans un certain rayon autour de leur position), ou encore
et il serait possible de choisir la disposation des pastilles dans l'aire de jeu.
Le projet se déroulera en plusieurs étapes qui sont :
1. Le développement d'un outil graphique permettant de visualiser le jeu Pakupaku et de simuler les parties dans lesquelles joueurs sont honnêtes et indépendants (par exemple en suivant une stratégie de déplacement aléatoire) ; la fonctionalité de simulation devra permettre d'établir des statistiques sur des échantillons de parties.
2. L'identification et la modélisation des différentes stratégies de collusion possibles dans le jeu Pakupaku. Par exemple, un type de collusion possible est celle où les joueurs partagent l'information qu'ils ont à propos de leur environnement (l'aire de jeu) alors qu'un autre type de collusion pourrait être qu'un des joueurs cherche à suivre les autres pacmans afin de leur voler leurs pastilles et ainsi favoriser le score de l'autre joueur participant à la collusion.
3. La mise au point d'une méthode de détection de collusion se basant sur les travaux réalisés lors des étapes précédentes. Il est probable que cette méthode requiert l'observation de plusieurs parties de Pakupaku avant de pouvoir ensuite évaluer s'il y a eu collusion ou non, et si oui de quel type et quels en sont les membres.
1. Le développement d'un outil graphique permettant de visualiser le jeu Pakupaku et de simuler les parties dans lesquelles joueurs sont honnêtes et indépendants (par exemple en suivant une stratégie de déplacement aléatoire) ; la fonctionalité de simulation devra permettre d'établir des statistiques sur des échantillons de parties.
2. L'identification et la modélisation des différentes stratégies de collusion possibles dans le jeu Pakupaku. Par exemple, un type de collusion possible est celle où les joueurs partagent l'information qu'ils ont à propos de leur environnement (l'aire de jeu) alors qu'un autre type de collusion pourrait être qu'un des joueurs cherche à suivre les autres pacmans afin de leur voler leurs pastilles et ainsi favoriser le score de l'autre joueur participant à la collusion.
3. La mise au point d'une méthode de détection de collusion se basant sur les travaux réalisés lors des étapes précédentes. Il est probable que cette méthode requiert l'observation de plusieurs parties de Pakupaku avant de pouvoir ensuite évaluer s'il y a eu collusion ou non, et si oui de quel type et quels en sont les membres.
Environnement technique
- programmation en Java
- machine hôte Linux
Prérequis
Ce projet convient particulièrement aux étudiants intéressés par le domaine de la théorie des jeux et/ou de la sécurité, ou à ceux qui souhaitent s'initier à ces domaines. Ainsi, aucune connaissance préalable du domaine n'est requise ; les notions nécessaires à la réalisation du projet seront apprises au cours de son déroulement.
Aspects logistiques
Objectifs : Analyse / pré-étude, Spécifications fonctionnelles, Conception logicielle
Communication : Rapport avant ?? décembre 2011, minuit, Présentation orale le ?? janvier 2012
Objectifs : Développement, Tests
Communication : Rapports finaux le ?? - Présentation orale ?? mai 2012 - Démonstrations ?? mai 2012