TABLE DES MATIERES
1 Introduction_______________________________________________ 14
1.1 Problématique__________________________________________________ 14
1.2 Plan de l’exposé________________________________________________ 15
2 Les jeux__________________________________________________ 17
2.1 Pourquoi étudier les jeux________________________________________ 17
2.2 Différents types de jeux__________________________________________ 18
2.2.1 Information disponible__________________________________________________ 18
2.2.2 Equité_______________________________________________________________ 22
2.2.3 Somme des jeux______________________________________________________ 22
2.2.4 Itération_____________________________________________________________ 22
2.3 Résultats de la Théorie des jeux__________________________________ 23
2.3.1 Information complète et parfaite__________________________________________ 23
2.3.2 Information complète et imparfaite________________________________________ 23
2.3.3 Information incomplète_________________________________________________ 24
2.4 Le travail présenté______________________________________________ 24
2.5 Jeux et intelligence artificielle____________________________________ 25
3 Anticipation_______________________________________________ 27
3.1 Définition______________________________________________________ 27
3.1.1 L'anticipation stratégique_______________________________________________ 27
3.1.2 L'anticipation aveugle__________________________________________________ 27
3.2 Domaines de recherche__________________________________________ 28
3.3 Les méthodes de l’Anticipation____________________________________ 29
3.4 Théorie de l'anticipation_________________________________________ 32
3.5 Applications publiées____________________________________________ 34
3.5.1 En Mathématiques :___________________________________________________ 34
3.5.2 En Economie :________________________________________________________ 35
3.5.3 En systèmes / logiciels (performances et optimisations) :_____________________ 35
3.5.4 En Robotique / Cybernetique :___________________________________________ 36
3.5.5 En Sciences Naturelles :_______________________________________________ 36
3.5.6 Dans le domaine des agents d’interface___________________________________ 37
3.5.7 Les Animats :________________________________________________________ 37
3.5.8 Divers :______________________________________________________________ 38
3.6 Analyse et critique de ces travaux :________________________________ 38
3.7 Problématique de l’Anticipation___________________________________ 40
3.8 Influence de l’anticipant sur l’anticipé______________________________ 40
4 Théorie des jeux___________________________________________ 43
4.1 Présentation___________________________________________________ 43
4.2 Les règles du jeu_______________________________________________ 44
4.3 Jeux sous forme extensive_______________________________________ 44
4.3.1 Exemple_____________________________________________________________ 45
4.3.2 Arbre simplifié________________________________________________________ 47
4.3.3 Exemple_____________________________________________________________ 47
4.3.4 Résolution des jeux sous forme extensive simplifiée_________________________ 48
4.4 Stratégies : forme normale_______________________________________ 54
4.4.1 Exemple_____________________________________________________________ 54
4.5 Equilibres______________________________________________________ 55
4.5.1 Définition____________________________________________________________ 55
4.5.2 Exemples____________________________________________________________ 55
4.5.3 Théorème____________________________________________________________ 56
4.6 Des jeux particuliers_____________________________________________ 56
4.6.1 Définition____________________________________________________________ 57
4.6.2 Théorème____________________________________________________________ 57
4.6.3 Point selle___________________________________________________________ 57
4.6.4 Stratégies mixtes_____________________________________________________ 58
4.6.5 Le théorème du MinMax________________________________________________ 59
4.6.6 Le théorème des stratégies optimales_____________________________________ 60
4.6.7 Détermination des stratégies optimales____________________________________ 60
4.6.8 Jeux 2 x n et jeux m x 2________________________________________________ 65
4.6.9 Cas général__________________________________________________________ 66
4.7 Les limites de la théorie des jeux__________________________________ 66
4.7.1 Jeux à information complète et parfaite____________________________________ 66
4.7.2 Jeux à information complète mais imparfaite________________________________ 69
4.7.3 Jeux à information incomplète___________________________________________ 70
4.8 Les limites des applications partielles de la théorie des jeux__________ 70
4.8.1 Les fonctions d’évaluation_______________________________________________ 70
4.8.2 La profondeur de recherche_____________________________________________ 71
4.9 Intérêt du cadre théorique________________________________________ 72
5 Apprentissage et Anticipation dans les jeux_____________________ 73
5.1 Apprentissage dans les jeux______________________________________ 73
5.1.1 Apprentissage par cœur________________________________________________ 73
5.1.2 Apprentissage supervisé________________________________________________ 75
5.1.3 Apprentissage par renforcement__________________________________________ 75
5.1.4 Apprentissage par découverte___________________________________________ 84
5.2 L’anticipation dans les jeux_______________________________________ 85
Le modèle coopératif :________________________________________________________ 86
5.2.2 Le modèle passif :_____________________________________________________ 87
5.2.3 Le modèle compétitif :__________________________________________________ 88
5.2.4 Modélisation de l’adversaire_____________________________________________ 90
5.2.5 Quelques systèmes utilisant un modèle de l’adversaire_______________________ 91
5.2.6 Les contre-mesures__________________________________________________ 101
6 Les stratégies humaines____________________________________ 105
6.1 Introduction___________________________________________________ 105
6.2 La mémoire humaine____________________________________________ 106
6.2.1 Mémoire sensorielle__________________________________________________ 107
6.2.2 Mémoire à court terme________________________________________________ 107
6.2.3 Mémoire à long terme_________________________________________________ 108
6.2.4 Mémoire et stratégies humaines________________________________________ 108
6.3 Le hasard_____________________________________________________ 110
6.3.1 Les problèmes du hasard______________________________________________ 110
6.3.2 L’humain est-il capable de manipuler le hasard ?___________________________ 111
6.4 L’adaptation___________________________________________________ 113
6.4.1 Adaptations réactives_________________________________________________ 113
6.4.2 Adaptations cognitives________________________________________________ 114
6.5 L’apprentissage________________________________________________ 114
6.5.1 Apprentissage par cœur_______________________________________________ 114
6.5.2 Apprentissage supervisé_______________________________________________ 114
6.5.3 Apprentissage par imitation____________________________________________ 115
6.5.4 Apprentissage par renforcement_________________________________________ 115
6.5.5 Apprentissage par découverte__________________________________________ 115
6.6 La rationalité__________________________________________________ 115
6.7 Les fonctions d’utilité___________________________________________ 117
6.8 Anticipation___________________________________________________ 118
6.8.1 Modélisation________________________________________________________ 118
6.8.2 Réflexivité de l’anticipation_____________________________________________ 118
6.9 Prise en compte des stratégies humaines_________________________ 119
7 La méthode S.A.G.A.C.E.___________________________________ 124
7.1 Introduction___________________________________________________ 124
7.2 Les systèmes de classeurs______________________________________ 126
7.2.1 Les différents modules d’un système de classeurs_________________________ 126
7.2.2 Cycles d’un système de classeur_______________________________________ 128
7.2.3 Apprentissage dans les systèmes de classeurs____________________________ 129
7.3 Les jeux utilisés_______________________________________________ 136
7.3.1 Pair / Impair (ou « matching pennies »)___________________________________ 137
7.3.2 Pierre / Ciseaux / Papier_______________________________________________ 137
7.3.3 ALESIA____________________________________________________________ 138
7.3.4 Le jeu des trois pierres________________________________________________ 139
7.3.5 SUNTZU____________________________________________________________ 140
7.4 Architecture générale de S.A.G.A.C.E._____________________________ 143
7.5 Implémentation de S.A.G.A.C.E.__________________________________ 145
7.5.1 Les bases de règles du S.C. Stratégique_________________________________ 145
7.5.2 Les bases de règles du S.C. d’anticipation________________________________ 168
7.5.3 L’interface entre les deux systèmes de classeurs__________________________ 180
7.5.4 Entraînement du système (génération de situations)________________________ 185
8 Expérimentations_________________________________________ 187
8.1 S.A.G.A.C.E. pour SUNTZU : Méthodes de créations de règles________ 187
8.1.1 Algorithme génétique_________________________________________________ 189
8.1.2 Généralisation_______________________________________________________ 189
8.1.3 Imitation____________________________________________________________ 189
8.1.4 Regrets____________________________________________________________ 190
8.1.5 Combinaison des méthodes____________________________________________ 191
8.2 S.A.G.A.C.E. pour ALESIA________________________________________ 192
8.2.1 Jeux contre un adversaire artificiel simple_________________________________ 192
8.2.2 Adversaires probabilistes______________________________________________ 193
8.2.3 Adversaires théoricien_________________________________________________ 195
8.2.4 Adversaires adaptatifs_________________________________________________ 195
8.2.5 Adversaires théoriciens adaptatifs_______________________________________ 197
8.2.6 Jeux contre NASH____________________________________________________ 202
8.2.7 Jeux contre un adversaire humain_______________________________________ 205
8.2.8 Une série d’étude____________________________________________________ 207
8.2.9 Création de règles____________________________________________________ 209
8.3 S.A.G.A.C.E. pour « Pierre / Ciseaux / Papier »______________________ 210
8.3.1 L’algorithme de Minasi________________________________________________ 210
8.3.2 « Minasi » contre un adversaire humain_______ ___________________________ 212
8.3.3 S.A.G.A.C.E. contre un adversaire humain_______________________________ 213
8.3.4 S.A.G.A.C.E. contre « Minasi »________________________________________ 215
8.4 S.A.G.A.C.E. pour « Pair / impair » (ou « Matching Pennies »)_________ 216
8.4.1 L’algorithme de Shannon______________________________________________ 216
8.4.2 « Shannon » contre des joueurs humains_________________________________ 218
8.4.3. « Minasi » contre un adversaire humain_________________________________ 219
8.4.4 S.A.G.A.C.E. contre un adversaire humain________________________________ 220
8.4.5 Prédiction et hasard__________________________________________________ 221
8.4.6 Martingale__________________________________________________________ 222
8.4.7 Autres séries d‘expériences____________________________________________ 222
8.5 S.A.G.A.C.E. pour le jeu des trois pierres__________________________ 227
8.5.1 Théorie contre un adversaire humain_____________________________________ 227
8.5.2 Apprentissage par renforcement contre un adversaire humain_________________ 228
8.5.3 S.A.G.A.C.E. contre un adversaire humain________________________________ 231
9 Conclusions et perspectives_________________________________ 232
9.1 Résumé_______________________________________________________ 232
9.2 Qualités de S.A.G.A.C.E._________________________________________ 232
9.3 Limitations de S.A.G.A.C.E_______________________________________ 233
9.3.1 les Métaconnaissances_______________________________________________ 233
9.3.2 le bluff______________________________________________________________ 234
9.4 1ère Perpective. Ajout d’une nouvelle dimension : le bluff____________ 234
9.4.1 Bluff par imitation_____________________________________________________ 235
9.4.2 Bluff par « regrets »___________________________________________________ 236
9.4.3 Bluff par recombinaison de critères______________________________________ 236
9.4.4 Choix d’un jeu approprié_______________________________________________ 236
9.5 2ème Perpective : généralisation de l’approche_____________________ 237
9.6 3ème Perpective : application à d’autres domaines___________________ 237
9.6.1 Méthode des regrets__________________________________________________ 237
9.6.2 Amorçage__________________________________________________________ 238
9.6.3 Interfaces collaboratrices hommes-machines______________________________ 238
ANNEXE A Captures d’écran___________________________ 239
ANNEXE B SUNTZU - exemples -__________________ 244
ANNEXE C ALESIA - aspects théoriques -_________________ 249
10 Bibliographie_____________________________________________ 254