Intelligence artificielle dans les jeux RTS IFT615 – Été 2011 Simon Chamberland

Intelligence artificielle dans les jeux RTS

IFT615 – Été 2011

Simon Chamberland

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

4

Real-Time Strategy But typique: anéantir l’adversaire! Joueurs jouent simultanément

Acquérir des ressources Construire une base Recruter des unités

Jeux RTS?

5

StarCraft 1998 - Blizzard Entertainment

Jeux RTS?

3 Races Terran Protoss Zerg

6

StarCraft

Jeux RTS?

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

8

Moins d’efforts que sur l’aspect graphique

Performance laissant habituellement à désirer

Sauf si l’IA « triche » Informations complètes

sur la carte Rythme plus élevé

d’acquisition de ressources

IA dans les jeux RTS

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

10

Temps réel Prendre une décision

rapidement!

Multitude d’unités Beaucoup d’actions

possibles…

Défis

11

Concurrence 5 actions sans concurrence 25 actions avec concurrence

Environnement dynamique Que fera l’adversaire?

Information incomplète Brouillard de guerre

Défis

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

13

StarCraft En marge d’une conférence sur les jeux

(AIIDE)

Compétition AIIDE 2010

14

Première compétition l’année dernière 28 participants Revient cette année!

Compétition AIIDE 2010

15

Différents tournois1. Contrôle d’unités

(micromanagement)

2. Contrôle d’unités+ terrain non trivial

3. Partie avec tech. limitée

4. Partie complète

Compétition AIIDE 2010

Muta/scourges vs muta/scourges

16

Différents tournois1. Contrôle d’unités

(micromanagement)

2. Contrôle d’unités+ terrain non trivial

3. Partie avec tech. limitée

4. Partie complète

Compétition AIIDE 2010

10 dragoons vs 10 dragoons

17

Différents tournois1. Contrôle d’unités

(micromanagement)

2. Contrôle d’unités+ terrain non trivial

3. Partie avec tech. limitée

4. Partie complète

Compétition AIIDE 2010

Tech ≤ dragoons, information parfaite

18

Différents tournois1. Contrôle d’unités

(micromanagement)

2. Contrôle d’unités+ terrain non trivial

3. Partie avec tech. limitée

4. Partie complète

Compétition AIIDE 2010

GL HF!

19

Exemple « épique » (partie complète)

Compétition AIIDE 2010

http://www.youtube.com/v/Kr_5XICVSEE

20

Overmind (UC Berkeley) – gagnant

Compétition AIIDE 2010

http://www.youtube.com/v/dOIgFkyfStg

21

Overmind (UC Berkeley) – gagnant Haut niveau: planificateur

Contraintes de ressources Assure une progression technologique de l’agent

Compétition AIIDE 2010

22

Overmind (UC Berkeley) – gagnant Haut niveau: planificateur

Contraintes de ressources Assure une progression technologique de l’agent

Bas niveau: microcontrôleurs Trajectoires: A* avec reconnaissance de menace Champs de potentiel

Compétition AIIDE 2010

23

Sherbrooke AI – Steve Tousignant, Anthony Jo Quinto et Frédéric St-Onge

2e (sur 7) dans le tournoi #1 Carte d’influence

Visibilité Densité d’unités Menaces

Compétition AIIDE 2010

24

Machines à états finis Scripts Cartes d’influence Champs de potentiel

Compétition AIIDE 2010 AIIDE - Techniques utilisées

25

Machines à états finis Scripts Cartes d’influence Champs de potentiel

Compétition AIIDE 2010 AIIDE - Techniques utilisées

Réseaux de neurones Swarm intelligence Inférence probabiliste Algorithmes

génétiques

26

Machines à états finis Scripts Cartes d’influence Champs de potentiel

Compétition AIIDE 2010 AIIDE - Techniques utilisées

Réseaux de neurones Swarm intelligence Inférence probabiliste Algorithmes

génétiques

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

28

Objectifs Testbed pour les algorithmes de

planification/reconnaissance de plan

Participer à AIIDE 2011!

Agent artificiel SPAR

29

Architecture

Agent artificiel SPAR

30

Architecture

Agent artificiel SPAR

31

Modules de prisede décision

Agent artificiel SPAR

Objectifs à long terme, i.e. composition de l’armée

Actions à accomplir (déplacer, attaquer, construire…)

Exécution des actions

Réactions (si → alors…)

32

Agent artificiel SPAR

Inférence par cas?

Planification

Ad hoc

Machines à états finis

Modules de prisede décision

33

Agent artificiel SPAR

Inférence par cas?

Planification

Ad hoc

Machines à états finis

Modules de prisede décision

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

35

Un seul agent Environnement potentiellement non-déterministe

Objectif: trouver des actions (un plan) permettant d’atteindre un but

Planification

36

Classique On a

Un état initial Un ensemble d’actions (déplacer, attaquer…) Un but à atteindre

Planification

37

Classique On a

Un état initial Un ensemble d’actions (déplacer, attaquer…) Un but à atteindre

Simuler des actionsdans le temps

Jusqu’à atteindrele but

Planification

Déplacer Défendre

Attaquer

38

Classique Choisir le « meilleur plan »

Qui respecte les contraintes Qui optimise une

métrique / fonction d’utilité

A*

Planification

Plan Jeux RTS? IA dans les jeux RTS

DéfisCompétition AIIDE 2010Agent artificiel SPAR

TechniquesPlanificationThéorie des jeux

40

Contexte multi-agent Objectif: trouver des actions maximisant l’utilité

d’un agent Problème: l’utilité dépend des décisions des autres

agents!

Théorie des jeux

41

Hypothèses principales Agent rationnel

Voulant maximiser son utilité

Agent égoïste N’est pas concerné par

l’utilité des autres

Très utilisée en économie

Théorie des jeux

42

Jeux séquentiels à deux joueurs (Avec information parfaite et somme nulle) On a

Un ensemble d’actions, {Agent} et {Adversaire} Une fonction d’utilité

Théorie des jeux

43

Jeux séquentiels à deux joueurs (Avec information parfaite et somme nulle) On a

Un ensemble d’actions, {Agent} et {Adversaire} Une fonction d’utilité

Trouver des actions maximisant l’utilité de l’agent

Selon un modèle de l’adversaire

Théorie des jeux

44

Jeux séquentiels à deux joueurs Minimax (ou alpha-beta pruning)

On assume que l’adversaire joue optimalement Maximiser son pire gain

Théorie des jeux

45

Jeux simultanés à deux joueurs L’agent et l’adversaire jouent en même

temps Ex: ciseau-roche-papier

Théorie des jeux

46

Jeux simultanés à deux joueurs L’agent et l’adversaire jouent en même

temps Ex: ciseau-roche-papier

Le résultat dépend des deux actions

Théorie des jeux

Ciseaux Roche Papier

Ciseaux 0 -1 1

Roche 1 0 -1

Papier -1 1 0

47

Jeux simultanés à deux joueurs (Avec information imparfaite et somme nulle) On a

Un ensemble d’actions, {Agent} et {Adversaire} Une fonction d’utilité

Trouver des actions maximisant l’utilité de l’agent

Selon un modèle de l’adversaire

Théorie des jeux

48

A ou B?

Théorie des jeux

A? B?

? ?

49

A ou B?

Théorie des jeux

Adversaire/Agent

A’ B’

A 2 -2

B -4 3

A’: attaquer base AB’: attaquer base B

A: défendre base AB: défendre base B

50

A ou B?

Si on connaît a priori le modèle de probabilité de l’adversaire:

Processus de décision de Markov

Théorie des jeux

Adversaire/Agent

A’ (60%)

B’ (40%)

A 2 -2

B -4 3

A’: attaquer base AB’: attaquer base B

A: défendre base AB: défendre base B

51

A ou B?

Si on connaît a priori le modèle de probabilité de l’adversaire:

Processus de décision de Markov

Théorie des jeux

Adversaire/Agent

A’ (60%)

B’ (40%)

A 2 -2

B -4 3

Action = AV = 0.4

52

A ou B?

Si on n’a aucune information

Théorie des jeux

Adversaire/Agent

A’(?)

B’(?)

A 2 -2

B -4 3

A’: attaquer base AB’: attaquer base B

A: défendre base AB: défendre base B

53

A ou B?

Si on n’a aucune information Équilibre de Nash

On assume que l’adversaire joue optimalement Chaque stratégie est la meilleure face à l’autre

Théorie des jeux

Adversaire/Agent

A’(?)

B’(?)

A 2 -2

B -4 3

A’: attaquer base AB’: attaquer base B

A: défendre base AB: défendre base B

54

A ou B?

Si on n’a aucune information Équilibre de Nash

On assume que l’adversaire joue optimalement Chaque stratégie est la meilleure face à l’autre

Théorie des jeux

Action = (64% A, 36% B)V = -0.18

Adversaire/Agent

A’(45%)

B’(55%)

A (64%) 2 -2

B (36%) -4 3

55

Game Tree

Théorie des jeux

s1

A’ B’B’

A’

A B

56

Game Tree

Théorie des jeux

2 -2 -4 3

A B

?s1

A’ B’B’

A’

Feuilles

57

Game Tree

Théorie des jeux

2 -2 -4 3

A B

?

A’: attaquer base AB’: attaquer base B

A: défendre base AB: défendre base B

Adversaire/Agent

A’ B’

A 2 -2

B -4 3

58

Game Tree

Théorie des jeux

2 -2 -4 3

A B

-0.18

A’: attaquer base AB’: attaquer base B

A: défendre base AB: défendre base B

Adversaire/Agent

A’(45%)

B’(55%)

A (64%) 2 -2

B (36%) -4 3

Action = (64% A, 36% B)V = -0.18

59

Game Tree

Théorie des jeux

-4 1 -1-0.18 Adversaire/Agent

C’ D’

C -0.18 -4

D 1 -1

C D

C’ D’D’

C’

60

Game Tree

Théorie des jeux

-0.18 -4 1 -1

-1

Adversaire/Agent

C’(0%)

D’(100%)

C (0%) -0.18 -4

D (100%) 1 -1

Action = D (domination stricte)

V = -1

C D

61

Jeux simultanés à deux joueurs Somme générale (non-constante)

Ex: dilemme des prisonniers

Théorie des jeux

1/2 Se taire Dénoncer

Se taire (-0.5, -0.5) (-10, 0)

Dénoncer (0, -10) (-5, -5)

62

Jeux simultanés à deux joueurs Somme générale (non-constante)

Ex: dilemme des prisonniers

Théorie des jeux

1/2 Se taire Dénoncer

Se taire (-0.5, -0.5) (-10, 0)

Dénoncer (0, -10) (-5, -5)

Un seul équilibre (de Nash): (Dénoncer, Dénoncer)!

63

Intelligence artificielle dans les jeux RTS: plus compliqué que jouer aux échecs…

Tirer profit de la reconnaissance de plan

Conclusion

Reconnaissance de plan

Prise de décision

Questions?