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




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?




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




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




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!


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


Muta/scourges vs muta/scourges

16


(micromanagement)



4. Partie complète


10 dragoons vs 10 dragoons

17


(micromanagement)



4. Partie complète


Tech ≤ dragoons, information parfaite

18


(micromanagement)



4. Partie complète


GL HF!

19

Exemple « épique » (partie complète)


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

20

Overmind (UC Berkeley) – gagnant


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

21

Overmind (UC Berkeley) – gagnant Haut niveau: planificateur

Contraintes de ressources Assure une progression technologique de l’agent


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


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


24

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

Compétition AIIDE 2010 AIIDE - Techniques utilisées

25



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

génétiques

26



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

génétiques




28

Objectifs Testbed pour les algorithmes de

planification/reconnaissance de plan

Participer à AIIDE 2011!

Agent artificiel SPAR

29

Architecture


30

Architecture


31

Modules de prisede décision


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


Inférence par cas?

Planification

Ad hoc

Machines à états finis


33


Inférence par cas?

Planification

Ad hoc

Machines à états finis





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




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


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


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



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



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



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

?



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



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?

Documents

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