Intelligence Artificielle

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.

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())) ...

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 :

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 :

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 :

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

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