[PDF] Jeux pour linformatique et complexité des stratégies

View - Download Jeux pour linformatique et complexité des stratégies

Previous PDF

Next PDF

Jeux pour l"informatique et complexité des stratégies

Pierre Vandenhove

1,2 1 F.R.S.-FNRS & UMONS - Université de Mons, Belgium 2 Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, France

21 avril 2022 - Séminaire Jeunes

Introduction

Objectif : présenter monsujet de recherche.• Études de maths (option informatique) à l"UMONS.•

Doctorat commencé en octobre 2019.•

Cosupervisé par...Patricia Bouyer,

Université Paris-Saclay, LMF,

FranceMickael Randour,

UMONS Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove Plan Vérification formelle: vérifier le comportement de systèmes informatiques.

Modélisation via lathéorie des jeux.

Question de recherche : comprendre lacomplexité des stratégies dans ces jeux. Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Motivation : systèmes réactifs

Systèmes réactifs= systèmes qui interagissent continuellement avec leur environnement (serveur web, aspirateur automatique, avion...).• Réagiraux événements de l"environnement tout en accomplissant un objectif.• Sujets auxerreurs, parfois graves (pertes financières, morts).•

Solution 1 :tests? Pas exhaustif.•

Solution 2 :vérification formelleetsynthèse.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Vérification formelle

On souhaite unepreuveformelle du bon comportement d"un système.• On travaille avec desmodèles/abstractions de systèmes.• Spécification: description des comportements acceptables du système.Modèle formelMSystème Model checkerM |=??

Formule

logique?SpécificationModélisation

Formalisation

Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Synthétiser un contrôleur

Plus ambitieux : générer uncontrôleurqui garantit la spécification.•

Définition lacunaire du système.•

Environnement vu comme un adversaireantagoniste.SystèmeS incomplet

Environnement

Spécification

Jeu à deux

joueurs

Résolution

du jeuS gagne + stratégie gagnanteS ne peut pas garantir la victoire•

Modélisation via lathéorie des jeux.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Jeu sur graphe

Jeu sur grapheà deux joueurs reprenant les états du système.>?????C=f>,?g>?s 1s 2s 3s 6s 5s

4•

Certains sommets?contrôlés parle système(le joueur 1,P1), d"autresparl"environnement(le joueur 2,P2).• Interaction de duréeinfinieentre les deux joueurs.• On définit unobjectiftel queP1gagne ssi le système accomplitsa spécification.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Formellement>?????C=f>,?g>?s

1s 2s 3s 6s 5s

4•

ArèneAà deux joueurs :S1(?, pourP1) etS2(, pourP2), arêtesE.•

EnsembleCdecouleurs. Lesétatssont colorés.•Exemple : si les états visités sonts1s4s5s6s6..., la séquence de couleurs

générée est?????...?Cω.•

Objectif: ensembleW?Cω. Jeu àsomme nulle.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Exemple : jeu d"accessibilité>?????C=f>,?g>?s

1s 2s 3s 6s 5s

4•

Objectif :atteindre?:

W={c1c2...?Cω| ?i≥1,ci=?}.•

Qui peut garantir la victoire quand le jeu commence ens1?Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Exemple : jeu d"accessibilité>?????C=f>,?g>?s

1s 2s 3s 6s 5s

4•Une stratégie qui suffit pour gagner regarde uniquement l"état courant :

σ:Si→S.

Une telle stratégie est ditesans mémoire.• Les stratégies sans mémoire suffisent pour gagner danstoutesles arènes pour cet objectif, quand cela est possible!

Jamais nécessaire de changer d"avis dans un état.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Les stratégies sans mémoire ne suffisent pas toujours

C={a,b,c}.

Objectif : voir infiniment souventaetinfiniment souventb: W={c1c2...?Cω| ?∞i≥1,ci=a? ?∞i≥1,ci=b}.abs 1s 3s 2c

P1peut gagner en jouantacbcacbc..., mais pas sans mémoire.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Définition générale d"unestratégieUnehistoireest une séquences1...sn?S?"cohérente" d"états de l"arène.

Pouri? {1,2}, on note Histsi(A)les histoiress1...sntelles quesn?Si.Définition UnestratégiedePiest une fonctionσ:Histsi(A)→Stelle que si

σ(s1...sn) =sn+1, alors(sn,sn+1)est une arête deA.Problèmes pour implémenter un contrôleur :

il y a une infinité de stratégies,

Histsi(A)est infini.

Un ordinateur n"a pas une mémoire infinie!

Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Retour à l"exemple précédent

•Les stratégiessans mémoirene suffisent pas pour l"exemple précédent. •C={a,b,c}, voir infiniment souventaet infiniment souventb: W={c1c2...?Cω| ?∞i≥1,ci=a? ?∞i≥1,ci=b}.abs 1s 3s 2c Compromis : utiliser de lamémoire finie. Ici, il suffit de retenir si on vient de voiraoub!Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Stratégie à mémoire finie

On condense l"information des histoires Histsi(A)dans un objet fini perte d"information, mais potentiellement suffisant!•

Un modèle de calcul adapté dérive desautomates.DéfinitionStructure de mémoire(M,minit,αupd): ensemble fini d"étatsM, état initial

minit?M, fonctionupdateαupd:M×C→M.• Exemple pour se souvenir siaouba été vu en dernier :ababm 1m

2•

Pour jouer, on se base sur l"état courant deAetsur l"état courant de

la mémoire (ici,m1oum2).Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Illustration

On définit une stratégie gagnanteσ:Si×M→S.abca,cb,cabs 1s 2s 3m 1m

2•

Cette structure de mémoire suffit pour gagner dans cette arène. Pourtoutearène, si gagner est possible, alors cette structure suffit!

Plus petite structure de mémoire qui suffise pourP1pour cet objectif.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Illustration

On définit une stratégie gagnanteσ:Si×M→S.abca,cb,cabs 1s 2s 3m 1m

2•

Cette structure de mémoire suffit pour gagner dans cette arène. Pourtoutearène, si gagner est possible, alors cette structure suffit!

Plus petite structure de mémoire qui suffise pourP1pour cet objectif.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Illustration

On définit une stratégie gagnanteσ:Si×M→S.abca,cb,cabs 1s 2s 3m 1m

2(s2,m1) =s3•

Cette structure de mémoire suffit pour gagner dans cette arène. Pourtoutearène, si gagner est possible, alors cette structure suffit!

Plus petite structure de mémoire qui suffise pourP1pour cet objectif.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Illustration

On définit une stratégie gagnanteσ:Si×M→S.abca,cb,cabs 1s 2s 3m 1m

2(s2,m1) =s3(s3,) =s2•

Cette structure de mémoire suffit pour gagner dans cette arène. Pourtoutearène, si gagner est possible, alors cette structure suffit!

Plus petite structure de mémoire qui suffise pourP1pour cet objectif.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Illustration

On définit une stratégie gagnanteσ:Si×M→S.abca,cb,cabs 1s 2s 3m 1m

2(s2,m1) =s3(s3,) =s2(s2,m2) =s1•

Cette structure de mémoire suffit pour gagner dans cette arène. Pourtoutearène, si gagner est possible, alors cette structure suffit!

Plus petite structure de mémoire qui suffise pourP1pour cet objectif.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Illustration

On définit une stratégie gagnanteσ:Si×M→S.abca,cb,cabs 1s 2s 3m 1m

2(s2,m1) =s3(s3,) =s2(s2,m2) =s1(s1,) =s2•

Cette structure de mémoire suffit pour gagner dans cette arène. Pourtoutearène, si gagner est possible, alors cette structure suffit!

Plus petite structure de mémoire qui suffise pourP1pour cet objectif.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Exemple nécessitant de la mémoire infinie

C={req,resp,wait}.

ObjectifW: nombre fini dereq ,ou?N?Ntel que chaquereq est suivi par resp en moins de Nétapes.reqresps 1s 3s 2wait P2gagne en augmentant de plus en plus le temps entre deux requêtes. •Ne peut pas être implémenté avec un automate fini

P2abesoindemémoire infinie.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Problèmes de recherche

Hiérarchie entre les stratégies

Sans mémoire(Si→S)(Mémoire finie(Si×M→S) Comprendre (conditions suffisantes ou caractérisations) dans quels contextesles stratégiessimplessuffisent.I Classes d"arènes (finies, dénombrables, infinies,stochastiques...).I Classes d"objectifs (W?Cω, maximiser une fonctionf:Cω→R, maximiser la probabilité d"un événement,ω-réguliers...).I Classes de stratégies "simples". Les stratégiessans mémoiresont bien

comprises, les stratégiesà mémoire finiemoins.•Complexité de calculer la quantité de mémoire pour un objectif donné.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

Conclusion : exemple de résultat

Généralisation de résultats sur les stratégies sans mémoire 1

2 Liftde 1 à 2 joueurs3,4 SoitWun objectif. Si•

dans tous les jeux deP1à 1 joueur, une mémoireM1suffit pourP1,

dans tous les jeux deP2à 1 joueur, une mémoireM2suffit pourP2,alors une mémoireM1? M2suffit pourP1etP2dans les jeux à 2 joueurs.Réduit un raisonnement sur lesjeuxà un raisonnement sur lesgraphes.Merci!

1.GimbertetZielonka, " Games Where You Can Play Optimally Without Any Memory », 2005.2.ColcombetetNiwiński, " On the positional determinacy of edge-labeled games », 2006.3.Bouyer,Le Rouxet al., " Games Where You Can Play Optimally with Arena-Independent Finite Memory », 2020.4.Bouyer,RandouretVandenhove, " Characterizing Omega-Regularity Through Finite-Memory Determinacy of Games

on Infinite Graphs », 2022.Jeux pour l"informatique et complexité des stratégiesPierre Vandenhove

quotesdbs_dbs14.pdfusesText_20

[PDF] pierre et jean pdf

[PDF] pigments de synthèse

[PDF] pih 2015-13

[PDF] pile ? combustible fonctionnement pdf

[PDF] pile electrochimique exercices corrigés pdf

[PDF] pile électrochimique pdf

[PDF] pilote de guerre fiche de lecture

[PDF] pilote de guerre pdf

[PDF] pilote de guerre saint exupéry brevet

[PDF] pilote de guerre saint exupéry extrait

[PDF] pilote de guerre saint exupéry résumé

[PDF] pinkove zvezdice 2015 33

[PDF] pinocchio carlo collodi

[PDF] pinocchio collodi résumé

[PDF] pinocchio histoire résumé