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


Deux approches :

• Alpha-beta avec élagage et tables de transposition

1.2.1. Puissance 4

Deux approches :


• Utilisation de connaissances humaines


1.2.1. Puissance 4

Deux approches :


• Utilisation de connaissances humaines

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


1.2.2. Le jeu du moulin

Résolu en 1995


Résolu en 1995

Deux étapes :

• DB de ± 8.000.000.000 de positions

• Exploration de profondeur 18


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



Résolu en 2007

Deux étapes :

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

• Exploration totale sur 200 machines



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




Implémentation :

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




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


Techniques actuelles :

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

1.2.5. Le Go

Amateur



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


• 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


Technique utilisée :

• Réseau de neurone

http://en.wikipedia.org/wiki/File:Artificial_neural_network.svg

1.3.1. Backgammon



• Réseau de neurone


• GNU Backgammon (téléchargeable gratuitement)

http://en.wikipedia.org/wiki/File:Artificial_neural_network.svg

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




• 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




• 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.


• 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

http://en.wikipedia.org/wiki/File:Rubik's_cube.svg




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





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


• 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


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


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


Y X

A B


Y X

A B


Y X

A B


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 [email protected]

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

mailto:[email protected]

Technology

Ia et jeux