Sommaire

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