Blog ENI : Toute la veille numérique !
-25€ dès 75€ sur les livres en ligne, vidéos... avec le code FUSEE25. J'en profite !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Design Patterns
  3. Intelligence Artificielle
Extrait - Design Patterns Apprendre la conception de logiciels en réalisant un jeu vidéo (avec exercices et corrigés)
Extraits du livre
Design Patterns Apprendre la conception de logiciels en réalisant un jeu vidéo (avec exercices et corrigés) Revenir à la page d'achat du livre

Intelligence Artificielle

Préparation

Avant de démarrer la conception et l’implantation d’intelligences artificielles, quelques préparatifs s’imposent. Le premier concerne la possibilité de rendre non-modifiable l’état du jeu, ce qui permet de prévenir les erreurs. Le second concerne la définition d’une interface pour toutes les intelligences artificielles.

1. État du jeu non modifiable

Jusqu’à présent, l’état du jeu a toujours été modifiable par n’importe quel acteur, y compris ceux qui n’ont aucune raison de le modifier. Par exemple, le moteur de rendu ne doit pas modifier l’état du jeu, au risque de perturber l’équilibre de l’ensemble. De même, une intelligence artificielle ne doit pas modifier l’état du jeu, sauf dans le cas où elle est autorisée à tricher.

Pour garantir qu’un objet et ceux qu’il contient ne seront pas modifiés, il y a deux principales voies : se faire confiance et/ou faire confiance aux membres de son équipe, ou tout simplement rendre impossibles les modifications. Dans le premier cas, même les développeurs les plus rigoureux peuvent parfois faire des erreurs, en particulier lorsqu’une méthode modifie les données d’une manière contre-intuitive ou non documentée. Ce type de scénario est courant au bout de plusieurs années de développement, où le projet est constitué de milliers de classes.

La méthode la plus sûre consiste à rendre les modifications impossibles. Il existe plusieurs approches. Dans cette section, deux approches sont proposées, l’une lorsque les classes à protéger ne sont pas modifiables (ex. : bibliothèque externe), et l’autre lorsque les classes peuvent être modifiées.

a. Approche avec le Patron Proxy

Lorsque les classes à protéger ne sont pas modifiables, il est possible d’utiliser le patron Proxy. Pour rappel, celui-ci consiste à définir une nouvelle classe qui copie le contenu des classes à traiter, tout en répondant à la même interface. Puis, les objets sont remplacés par leur proxy : les utilisateurs de la classe ciblée ne voient pas la différence...

Intelligence Artificielle sans planification

Une première catégorie d’intelligences artificielles est présentée dans cette section. Elle concerne des IA qui prennent une décision en fonction de l’état actuel du jeu, sans se projeter dans l’avenir.

1. Heuristique simple

Les IA les plus simples à implanter sont celles qui reposent sur des heuristiques, des fonctions imaginées pour résoudre un problème très précis. Leur efficacité dépend du niveau d’astuce dont peut faire preuve leur créateur. Elles n’offrent généralement aucune garantie de réussite pour toutes les situations, par contre elles promettent d’être meilleures que le hasard.

Pour le jeu exemple Pacman, une heuristique simple à mettre en place consiste à choisir, parmi les commandes possibles de Pacman, celles qui n’ont pas de fantôme en vue. Par exemple, s’il y a un fantôme dans les cellules proches à droite de Pacman, on évite la direction droite. Cela peut être implanté de la manière suivante dans la méthode createCommand() d’une nouvelle classe ExplorationAI qui implante l’interface AI. Celle-ci commence par demander la liste des commandes possibles pour l’état actuel du jeu :

public Command createCommand() { 
   List<Command> list = commandsLister.listCommands(state, 
charIndex); 
   if (list.isEmpty()) 
       return null; 

Les différentes commandes sont analysées une à une :

   Characters chars = state.getChars();  
   MobileElement me = chars.get(charIndex); 
   Command oppositeCommand = null; 
   List<Command> commands = new ArrayList(); 
   for (Command command : list) { 
       if (!(command instanceof DirectionCommand)) 
           continue; 
       DirectionCommand dirCommand = (DirectionCommand)command; 

Si un personnage est trouvé dans la zone proche dans la direction de la commande, alors on continue :

       Direction direction = dirCommand.getDirection(); 
       if (findCharacter(dirCommand.getDirection())) ...

Intelligence Artificielle avec planification

Cette section est particulièrement difficile et peut être ignorée par les débutants.

Les approches précédentes prennent une décision uniquement basée sur l’état actuel du jeu. Elles ne tiennent pas compte des conséquences des choix faits, ou bien d’une manière très approximative. Les gammes de méthodes présentées dans cette section proposent d’explorer les différentes possibilités en modifiant l’état du jeu, comme si les commandes étaient véritablement exécutées.

1. Parcourir les états futurs

a. Graphes d’états

Imaginer ou simuler les conséquences d’une action peut être formalisé sous la forme de graphes d’états. L’idée est de représenter chaque état particulier du jeu par le sommet d’un graphe, et chaque changement qui permet de passer d’un état à un autre par un arc.

Par exemple, un sommet de ce graphe pour le jeu de taquin en 3x3 peut être présenté de la manière suivante :

images/05RI014.png

Ce sommet contient l’intégralité des données du jeu, soit 9 valeurs de 0 à 8.

Si le chiffre 2 est déplacé, un nouvel état est créé, auquel un nouveau sommet peut être associé. L’arc qui représente la transition entre ces deux sommets correspond alors au déplacement du chiffre 2 de la case centrale vers celle au milieu haut :

images/05RI015.png

Il peut y avoir plusieurs possibilités de mouvement, par exemple depuis le deuxième sommet, parmi les possibilités, le chiffre 4 et le chiffre 5 peuvent être déplacés au centre :

images/05RI016.png

Ce principe se répète ainsi à l’infini, tant qu’il existe un mouvement possible entre des sommets.

D’un point de vue informatique, les sommets sont des instances de classes qui contiennent les données du jeu, comme la classe State du jeu exemple Pacman. Les arcs sont l’ensemble des commandes qui, une fois appliquées au moteur de règles, transforment un état du jeu en un autre. Dans le jeu exemple Pacman, les implantations de l’interface Command sont les valeurs de ces arcs.

Le graphe et ses sommets...

Solution des exercices

1. Exercice 1.3.1 : Galaxie non modifiable

La version avec le patron Décorateur est présentée ici. La solution complète est dans le dossier « examples/chap05/stellaris01 » du projet Java exemple. Seuls les points saillants sont présentés ici.

Pour chaque classe, une interface est définie avec les mêmes méthodes, puis une classe modifiable nommée MutableXXX, et une classe non modifiable nommée ImmutableXXX. En outre, une méthode supplémentaire toImmutable() est définie pour permettre de créer une version non modifiable à partir de tout objet.

Par exemple, l’interface Building est définie comme suit :

public interface Building { 
 
   public BuildingType getType(); 
 
   public int getLevel(); 
 
   public void setType(BuildingType type); 
 
   public void setLevel(int level); 
    
   public ImmutableBuilding toImmutable(); 
    
} 

La version modifiable reprend le code original :

public class MutableBuilding implements Building { 
 
   private BuildingType type; 
 
   private int level; 
 
   public MutableBuilding(BuildingType type, int level) { 
       this.type = type; 
       this.level = level; 
   } 
 
   public BuildingType getType() { 
       return type; 
   } 
 
   public int getLevel() { 
       return level; 
   } 
 
   public void setType(BuildingType type) { 
       this.type = type; 
   } 
 
   public void setLevel(int level) { 
       this.level = level; 
   } 
 
   public ImmutableBuilding toImmutable() { 
       return new ImmutableBuilding(this); 
   } 
} 

La dernière méthode, toImmutable(), renvoie une version non modifiable qui la décore.

La version non modifiable est définie de la manière suivante :...