TechCodeview

La recherche contradictoire est une recherche dans laquelle nous examinons le problème qui se pose lorsque nous essayons de planifier à l'avance le monde et que d'autres agents planifient contre nous.

• Dans les sujets précédents, nous avons étudié les stratégies de recherche qui ne sont associées qu'à un seul agent visant à trouver la solution qui s'exprime souvent sous la forme d'une séquence d'actions.
• Mais il peut y avoir des situations dans lesquelles plusieurs agents recherchent la solution dans le même espace de recherche, et cette situation se produit généralement lors d'un jeu.
• L’environnement avec plus d’un agent est appelé environnement multi-agents , dans lequel chaque agent est l'adversaire d'un autre agent et joue les uns contre les autres. Chaque agent doit prendre en compte l'action d'un autre agent et l'effet de cette action sur ses performances.
• Donc, Les recherches dans lesquelles deux joueurs ou plus ayant des objectifs contradictoires tentent d'explorer le même espace de recherche pour trouver la solution sont appelées recherches contradictoires, souvent appelées jeux. .
• Les jeux sont modélisés comme un problème de recherche et une fonction d'évaluation heuristique, et ce sont les deux principaux facteurs qui aident à modéliser et à résoudre des jeux en IA.

Types de jeux en IA :

Informations parfaites :Un jeu avec des informations parfaites est celui dans lequel les agents peuvent consulter le tableau complet. Les agents disposent de toutes les informations sur le jeu et peuvent également se voir dans leurs mouvements. Les exemples sont les échecs, les dames, le Go, etc.Informations imparfaites :Si, dans un jeu, les agents n'ont pas toutes les informations sur le jeu et ne sont pas au courant de ce qui se passe, ce type de jeux est appelé jeu avec des informations imparfaites, comme le tic-tac-toe, le cuirassé, l'aveugle, le pont, etc.Jeux déterministes :Les jeux déterministes sont des jeux qui suivent un modèle et un ensemble de règles stricts pour les jeux, et aucun caractère aléatoire n'y est associé. Les exemples sont les échecs, les dames, le Go, le tic-tac-toe, etc.Jeux non déterministes :Les jeux non déterministes sont ceux qui comportent divers événements imprévisibles et comportent un facteur de hasard ou de chance. Ce facteur de hasard ou de chance est introduit soit par les dés, soit par les cartes. Celles-ci sont aléatoires et chaque réponse à l'action n'est pas fixe. De tels jeux sont également appelés jeux stochastiques.
Exemple : Backgammon, Monopoly, Poker, etc.

Remarque : Dans cette rubrique, nous discuterons des jeux déterministes, de l'environnement entièrement observable, de la somme nulle et du cas où chaque agent agit alternativement.

Jeu à somme nulle

• Les jeux à somme nulle sont des recherches contradictoires qui impliquent une pure concurrence.
• Dans le jeu à somme nulle, le gain ou la perte d'utilité de chaque agent est exactement équilibré par les pertes ou les gains d'utilité d'un autre agent.
• Un joueur du jeu essaie de maximiser une seule valeur, tandis que l’autre joueur essaie de la minimiser.
• Chaque mouvement d'un joueur dans le jeu est appelé pli.
• Les échecs et le tic-tac-toe sont des exemples de jeu à somme nulle.

Jeu à somme nulle : réflexion intégrée

Le jeu à somme nulle impliquait une réflexion intégrée dans laquelle un agent ou un joueur essayait de comprendre :

chaîne et sous-chaîne

• Ce qu'il faut faire.
• Comment décider du déménagement
• Doit aussi penser à son adversaire
• L'adversaire pense aussi quoi faire

Chacun des joueurs essaie de connaître la réponse de son adversaire à ses actions. Cela nécessite une réflexion intégrée ou un raisonnement rétrospectif pour résoudre les problèmes de jeu en IA.

Formalisation du problème :

Un jeu peut être défini comme un type de recherche en IA qui peut être formalisé des éléments suivants :

Etat initial:Il précise comment le jeu est mis en place au départ.Joueurs):Il précise quel joueur s'est déplacé dans l'espace d'état.Actions):Il renvoie l'ensemble des mouvements juridiques dans l'espace d'état.Résultat(s, a) :C'est le modèle de transition, qui spécifie le résultat des mouvements dans l'espace des états.Test(s) terminal(s) :Le test du terminal est vrai si le jeu est terminé, sinon il est faux dans tous les cas. L’état dans lequel le jeu se termine est appelé état terminal.Utilitaires, p :Une fonction utilitaire donne la valeur numérique finale d'un jeu qui se termine dans les états terminaux s pour le joueur p. On l'appelle également fonction de paiement. Pour les échecs, les résultats sont une victoire, une défaite ou un match nul et les valeurs de gain sont +1, 0, ½. Et pour le tic-tac-toe, les valeurs utilitaires sont +1, -1 et 0.

Arbre de jeu :

Un arbre de jeu est un arbre dont les nœuds sont les états du jeu et les bords de l'arbre sont les mouvements des joueurs. L'arbre de jeu implique l'état initial, la fonction d'actions et la fonction de résultat.

Exemple : arbre de jeu Tic-Tac-Toe :

méthode tostring en java

La figure suivante montre une partie de l'arbre de jeu du jeu de tic-tac-toe. Voici quelques points clés du jeu :

• Il y a deux joueurs MAX et MIN.
• Les joueurs ont un tour alternatif et commencent par MAX.
• MAX maximise le résultat de l'arbre de jeu
• MIN minimise le résultat.

Exemple d'explication :

• Depuis l'état initial, MAX a 9 mouvements possibles lorsqu'il démarre en premier. MAX place x et MIN place o, et les deux joueurs jouent alternativement jusqu'à ce que nous atteignions un nœud feuille où un joueur en a trois d'affilée ou que toutes les cases sont remplies.
• Les deux joueurs calculeront chaque nœud, minimax, la valeur minimax qui est la meilleure utilité réalisable contre un adversaire optimal.
• Supposons que les deux joueurs connaissent bien le tic-tac-toe et jouent le meilleur jeu. Chaque joueur fait de son mieux pour empêcher un autre de gagner. MIN agit contre Max dans le jeu.
• Donc dans l'arbre du jeu, nous avons une couche de Max, une couche de MIN, et chaque couche est appelée comme Pli . Max place x, puis MIN met o pour empêcher Max de gagner, et ce jeu continue jusqu'au nœud terminal.
• Dans ce cas, soit MIN gagne, soit MAX gagne, soit c'est un match nul. Cet arbre de jeu est tout l'espace de recherche des possibilités que MIN et MAX jouent au tic-tac-toe et se relaient alternativement.

La recherche contradictoire de la procédure minimax fonctionne donc comme suit :

• Il vise à trouver la stratégie optimale pour que MAX gagne la partie.
• Il suit l’approche de la recherche en profondeur.
• Dans l'arbre du jeu, le nœud feuille optimal peut apparaître à n'importe quelle profondeur de l'arbre.
• Propagez les valeurs minimax jusqu'à l'arborescence jusqu'à ce que le nœud terminal soit découvert.

Dans un arbre de jeu donné, la stratégie optimale peut être déterminée à partir de la valeur minimax de chaque nœud, qui peut s'écrire MINIMAX(n). MAX préfère passer à un état de valeur maximale et MIN préfère passer à un état de valeur minimale alors :