Jeu et graphe biparti

Les jeux à deux joueurs sont souvent modélisés par des graphes bipartis. Les sommets de ces graphes représentent les états possibles du jeu.

Ces états sont divisés en deux ensembles : ceux contrôlés par le joueur 1 et ceux contrôlés par le joueur 2. Chaque arête représente une action qui mène d'un état à un autre. Un jeu commence par un état initial et se termine dans un état final, qui peut indiquer la victoire de l'un des joueurs ou, pour certains jeux, une égalité.

Stratégie et stratégie gagnante

Une stratégie est une règle permettant à un joueur (humain ou IA) de choisir une action en fonction de l'état actuel.

Une stratégie gagnante assure la victoire, quel que soit le comportement de l'adversaire.

Une position gagnante est un état gagnant pour un joueur si celui-ci peut appliquer une stratégie gagnante à partir de cet état.

Enfin, un attracteur est un ensemble d'états depuis lesquels un joueur peut garantir, en suivant une stratégie déterminée, de rejoindre une position gagnante.

Pour construire une IA adoptant une stratégie gagnante, on associe à chaque état une action menant vers une position gagnante ou un attracteur.

Algorithmes Minmax

L'algorithme Minmax, ou Minimax, est une méthode utilisée pour explorer l'arbre des états possibles dans des jeux à deux joueurs. Chaque nœud de l'arbre représente un état du jeu, et les deux joueurs alternent leurs actions en cherchant des objectifs opposés : le joueur 1 cherche à maximiser son gain, tandis que le joueur 2 cherche à le minimiser.

Élagage Alpha-Bêta

L'élagage Alpha-Bêta est une amélioration de l'algorithme Minmax, conçue pour réduire le nombre de branches à explorer sans compromettre l'exactitude des résultats. Lorsqu'il devient évident qu'une branche ne peut pas modifier le résultat final (par exemple, si elle conduit à un score moins favorable que celui déjà calculé), elle est ignorée.

Jeux Complexes et heuristique

Jeux simples et jeux complexes

Pour un jeu simple (ex : morpion), il est envisageable d'explorer tous les états possibles du jeu pour établir les stratégies gagnantes. Pour les jeux complexes (ex : échecs) cette méthode n'est plus viable, et il convient alors de se concentrer sur la recherche d'heuristiques.

Heuristique

Une heuristique est une méthode d'estimation utilisée pour orienter la recherche ou la prise de décision en se basant sur des approximations, permettant de gagner en rapidité et efficacité tout en évitant une exploration exhaustive.

Algorithme A*

L'algorithme A* est un algorithme de recherche informé qui combine le coût réel accumulé jusqu'à un état donné avec une estimation heuristique du coût restant pour atteindre l'objectif. Cette approche guide efficacement la recherche vers les états les plus prometteurs dans un jeu ou un problème.

Une heuristique admissible, qui ne surestime jamais le coût restant, garantit que l'algorithme A* trouve des solutions optimales. Si l'heuristique est également monotone (cohérente), elle assure un coût croissant le long des chemins explorés et réduit efficacement le nombre de nœuds à visiter, rendant l'algorithme encore plus performant.