Ia et jeux

L’Intelligence Artificielle

et les Jeux

--------------------------------------------------------------------------------------------------------------------Sponsors :

Structure de la présentation

1.Jeux de réflexion1.1. Introduction1.2. Moulin, Puissance 4, Dame, Échecs, Go1.3. Backgammon, Poker1.4. Rubik’s Cube, Sokoban

2. Jeux vidéos2.1. Les algorithmes de pathfinding 2.2. Command & Conquer

1. Jeux de réflexion

1.1. Introduction

Divergence entre les jeux : • Nombre de joueurs

• Jeux à information parfaite / incomplète

• Jeux avec / sans facteur chance

…

1.1.1. Espace d’état

x x

1.1.2. Arbre du jeu

3601017210Go (19x19)

123104610Echecs

31102110Dame

21101410Puissance 4

50101010Moulin

Arbre du jeuEspace d'étatJeu

1.2. Jeux à deux joueursavec connaissance parfaite

L’algorithme minimax

L’algorithme alpha-beta

1.2.1. Puissance 4

Résolu en 1989 (par deux personnes différentes)

1.2.1. Puissance 4

Résolu en 1989 (par deux personnes différentes)

Deux approches :

• Alpha-beta avec élagage et tables de transposition

1.2.1. Puissance 4

Deux approches :

• Alpha-beta avec élagage et tables de transposition

• Utilisation de connaissances humaines

Résolu en 1989 (par deux personnes différentes)

1.2.1. Puissance 4

Deux approches :

• Alpha-beta avec élagage et tables de transposition

• Utilisation de connaissances humaines

Le programme VICTOR implémente la seconde approche etgagne systématiquement s’il commence.

Résolu en 1989 (par deux personnes différentes)

1.2.2. Le jeu du moulin

Résolu en 1995

1.2.2. Le jeu du moulin

Résolu en 1995

Deux étapes :

• DB de ± 8.000.000.000 de positions

• Exploration de profondeur 18

1.2.2. Le jeu du moulin

Résolu en 1995

Deux étapes :

• DB de ± 8.000.000.000 de positions

• Exploration de profondeur 18

Résultat :

• Nulle théorique

1.2.3. Le jeu de dame

Premier jeu où un programme bas le champion du monde (1994)

Résolu en 2007

1.2.3. Le jeu de dame

Premier jeu où un programme bas le champion du monde (1994)

Résolu en 2007

Deux étapes :

• DB de toutes les positions de 10 pièces ou moins

• Exploration totale sur 200 machines

1.2.3. Le jeu de dame

Premier jeu où un programme bas le champion du monde (1994)

Résolu en 2007

Deux étapes :

• DB de toutes les positions de 10 pièces ou moins

• Exploration totale sur 200 machines

Résultat :

• Nulle théorique

1.2.4. Le jeu d’échecs

Victoire de Deep Blue contre Kasparoven 1997

Loin d’être résolu

1.2.4. Le jeu d’échecs

Victoire de Deep Blue contre Kasparoven 1997

Loin d’être résolu

Implémentation :

• Machine parallèle à 30 nœuds de 120MHz• 480 circuits intégrés• Écrit en C• 200 millions positions/secondes

1.2.4. Le jeu d’échecs

Victoire de Deep Blue contre Kasparoven 1997

Loin d’être résolu

Implémentation :

• Machine parallèle à 30 nœuds de 120MHz• 480 circuits intégrés• Écrit en C• 200 millions positions/secondes

Meilleur programme actuel :

• Rybka (3250 élo)

1.2.5. Le Go

Amateur

Les pros battent les machines mêmeavec 9 jetons de handicap

1.2.5. Le Go

Amateur

Les pros battent les machines mêmeavec 9 jetons de handicap

Techniques actuelles :

• Évaluation par Monte-Carlo Tree Search• Exploration par UCT (variante de alpha-beta)

1.2.5. Le Go

Amateur

Les pros battent les machines mêmeavec 9 jetons de handicap

Techniques actuelles :

• Évaluation par Monte-Carlo Tree Search• Exploration par UCT (variante de alpha-beta)

Meilleur programme actuel :

• Mogo (1ère dan amateur)

1.3. Jeux avec facteur chance et/ou à connaissance imparfaite

Monte-Carlo Tree Search

1.3.1. Backgammon

Dans les années 90, les softs de Backgammon ont largement dépassé le niveau humain

1.3.1. Backgammon

Dans les années 90, les softs de Backgammon ont largement dépassé le niveau humain

Technique utilisée :

• Réseau de neurone

1.3.1. Backgammon

Dans les années 90, les softs de Backgammon ont largement dépassé le niveau humain

Technique utilisée :

• Réseau de neurone

Meilleur programme actuel :

• GNU Backgammon (téléchargeable gratuitement)

1.3.2. Poker

En 2008, Polaris bat des pros en FL HU

Les programmes de NL FR sont prévisibles

1.3.2. Poker

En 2008, Polaris bat des pros en FL HU

Les programmes de NL FR sont prévisibles

Technique utilisée :

• FL HU : Combinaison de Monte-Carlo et importance sampling• NL FR : Il existe des tas de bots implémentant des stratégies systématiques. Des programmes s’adaptant aux adversaires sont également en développement.

1.3.2. Poker

En 2008, Polaris bat des pros en FL HU

Les programmes de NL FR sont prévisibles

Technique utilisée :

• FL HU : Combinaison de Monte-Carlo et importance sampling• NL FR : Il existe des tas de bots implémentant des stratégies systématiques. Des programmes s’adaptant aux adversaires sont également en développement.

Meilleur programme actuel :

• Son auteur ne le publie probablement pas

1.4. Les casse-tête

9810Sokoban

1910Rubik's Cube

Espace d'étatJeu

Exploration d’un graphe

Élimination des cycles

L’algorithme A*

L’algorithme A*

1.4.1. Le Rubik’s Cube

Les meilleurs softs jouent de manière optimale

1.4.1. Le Rubik’s Cube

Les meilleurs softs jouent de manière optimale

Techniques actuelles :

• A* avec une bonne heuristique• Utilisation d’une base de données de pattern connus

1.4.1. Le Rubik’s Cube

Les meilleurs softs jouent de manière optimale

Techniques actuelles :

• A* avec une bonne heuristique• Utilisation d’une base de donnée de pattern connus

Meilleur programme actuel :

• De nombreux programmes existent sur le web

1.4.2. Sokoban

Les bons joueurs humains sont toujours beaucoup plus forts que les meilleurs programmes

1.4.2. Sokoban

Les bons joueurs humains sont toujours beaucoup plus forts que les meilleurs programmes

Ma méthode consiste en une décomposition hiérarchique :

• un agent détermine dans quel ordre les goals seront remplis• un autre essaye de découvrir quelle pierre doit aller sur quel goal• un troisième aide le deuxième en lui fournissant des méthodes capables de déterminer si une pierre x peut atteindre un goal y• un quatrième repère le position de deadlock

1.4.2. Sokoban

Les bons joueurs humains sont toujours beaucoup plus forts que les meilleurs programmes

Ma méthode consiste en une décomposition hiérarchique :

• un agent détermine dans quel ordre les goals seront remplis• un autre essaye de découvrir quelle pierre doit aller sur quel goal• un troisième aide le deuxième en lui fournissant des méthodes capables de déterminer si une pierre x peut atteindre un goal y• un quatrième repère le position de deadlock

Meilleur programme documenté actuel :

• MovingStone écrit par Jean-Noël Demaret et moi-même

2. Jeux vidéos

2.1. Pathfinding

Exemple de problème

Y A B X

Exemple de problème

Y X

A B

Exemple de problème

Y X

A B

Exemple de problème

Y X

A B

Exemple de problème

Y X

Boom

2.2. Command & Conquer

2.2.1. Prédécesseur

Dune (1990) et Dune II (1992)

2.2.2. Conflit du Tibérium

1995

2.2.3. Alerte Rouge

1996

2.2.4. Generals

2003

Récapitulatif

1. Jeux de réflexion

• Résolus• Plus fort que l’homme• Toujours faible

7. Jeux vidéos

• Le pathfinding est toujours un problème• L’IA a évolué moins vite que les interfaces

graphiques

Conclusion

• La recherche en IA doit continuer

• Si vous êtes intéressés, prenez contact avec moi vanlishoutf@hotmail.com

• Des stages au Giga en recherche en bioinformatique sont également possibles