À quoi servent les valeurs minimales sur les arbres minimax?

8

Considérons un arbre minimax pour un problème de recherche contradictoire. Par exemple, dans cette image (élagage alpha-bêta):

entrez la description de l'image ici

Lorsque nous marquons l'arbre avec des valeurs bas en haut, nous traversons d'abord le nœud 3 et attribuons B. \ max = 3 . Ensuite, nous parcourons 12 et 8 dans cet ordre, il s'assurera que B.max = 3 .[min,max]3B.max=3128B.max=3

Mais pourquoi B.min=3 ? Quelle est l'utilité de cette valeur?

sam
la source
D'où vient la photo? Est-ce un exemple artificiel?
uli
Oui, c'est juste un exemple de cas particulier, je modifie également l'image pour ajouter le texte des min et max. S'il apparaît des erreurs, n'hésitez pas à le dire. Merci ~
sam
1
D'après l'article (horrible) de Wikipédia, l'arbre que vous donnez ne semble pas être un arbre min-max. En particulier, devrait être ; , d'autre part, semble complètement à droite. Alors, quelle est la question ici, vraiment? Êtes-vous confus par l'exemple ou voulez-vous des applications d'arbres min-max? Dans tous les cas, veuillez inclure une définition précise (!) Des arbres min-max et / ou une référence à celui-ci. B.max12B.min
Raphael
1
Veuillez inclure une référence pour l'image; J'ai des raisons de croire que vous ne l'avez pas créé. Les diapositives liées peuvent également répondre à certaines de vos questions; ils semblent utiliser des arbres différents de vous.
Raphael
1
L'image semble trompeuse ..
Strin

Réponses:

7

Cette figure (qui est en fait correcte) est utilisée dans l'explication de l'algorithme d'élagage alpha-bêta sur un arbre minimax. L'élagage alpha-bêta est une méthode utilisée pour tailler des parties de l'arbre minimax dans un problème de recherche contradictoire. Dans le cadre d'un jeu tic-tac-toe, les arbres minimax sont destinés à permettre à l'ordinateur de parcourir l'espace de tous les plateaux de jeu possibles (configurations de x et o) en supposant que les mouvements du joueur sont optimaux. Cela permet à l'ordinateur de proposer un mouvement qui donne les meilleurs résultats (c'est pourquoi le jeu connect-four sur votre ordinateur est incroyablement difficile à battre!). Pour une description plus complète, je suggère fortement "AI a Modern Approach" par Stuart et Norvig (p. 162-170 ish dans la 2e éd.).

Maintenant que nous avons dissipé une certaine confusion sur l'algorithme. L'élagage alpha-bêta tente d'éviter l'expansion des sous-arbres en fonction du fonctionnement de l'algorithme minimax. Nous savons que le nœud max au niveau supérieur prendra la plus grande valeur de tous ses enfants. Ainsi, le nœud trouve la valeur , et jusqu'à présent, c'est la valeur maximale qu'il est prêt à transmettre à son parent, il place donc cette valeur dans l'emplacement MAX. Ensuite, il trouve . N'oubliez pas que est un nœud MIN, il souhaite donc minimiser la valeur qu'il transmet à son parent, il conserve donc la valeur dans l'emplacement MAX. Encore une fois pour . Lorsque a recherché tous ses enfants, il connaît la limite inférieure maximale (B312B38Bα) et la solution de limite supérieure ( ) minimale de son sous-arbre et conserve ces valeurs dans MIN ( ) et MAX ( ) (comme [3, 3]).βαβ

Remarque: min et max étiquetés sur la figure NE SONT PAS les valeurs minimum et maximum du sous-arbre! Ils sont (assez confusément étiquetés) les limites alpha-bêta des solutions du sous-arbre (rappelez-vous que c'est un problème de recherche contradictoire).

Nous passons ensuite au noeud . Ici, nous rencontrons un en première position. Le nœud , voulant sélectionner la valeur la plus basse de son sous-arbre, SAIT maintenant que son parent ne choisira pas sa valeur puisque le nœud trouvé une valeur plus grande. Par conséquent, nous pouvons élaguer le reste de la sous - arborescence et continuer à .C2CBD

Enfin, pour répondre à la question spécifique: pourquoi .min = 3? Une valeur pour (la limite inférieure maximale des solutions à ce nœud) et (la limite supérieure minimale des solutions à ce nœud) est maintenue à chaque nœud afin d'effectuer l'élagage. Ces valeurs ont limité les cas possibles dans lesquels la valeur d'un nœud (ou de son sous-arbre) peut faire partie de la solution.Bαβ

Dans cet exemple, il ne semble pas jouer de rôle, cependant, essayez de regarder des exemples plus compliqués (c'est-à-dire des arbres d'une hauteur> 3) comme celui-ci et voyez si vous pouvez le comprendre.

Je ne peux pas rendre justice à l'élagage minimax ou alpha-bêta ici (principalement parce que je ne les ai pas utilisés depuis des années), donc si vous voulez vraiment comprendre cela, veuillez consulter un livre sur l'IA comme celui de Stuart et Norvig (le la page wikipedia n'a étonnamment aucune visualisation non plus).

pseudo
la source
Ouais, comme vous l'avez dit, je pense que vous êtes totalement d'accord sur l'exactitude de l'image, non? Merci de partager le processus si détaillé de l'élagage AlphaBeta, et ma question est à quoi sert la valeur minimale? Les valeurs minimales sont-elles toujours les mêmes que les valeurs maximales? Dans ce cas est le premier 3 de [3,3].
sam
@sam, oui, l'image est définitivement correcte. J'ai modifié ma réponse pour répondre (partiellement) à votre question spécifique. J'espère que cela t'aides.
Nick
"Lorsque B a recherché tous ses enfants, il connaît les valeurs minimale et maximale de son sous-arbre et conserve ces valeurs en MIN et MAX (comme [3, 3])" - mais ce n'est évidemment pas ce qui se passe (il devrait être , alors). Votre explication plus tard est plus logique. [3,12]
Raphael
@Raphael, j'aurais dû être plus clair. Ce ne sont pas les valeurs min et max de la sous-arborescence, ce sont la limite inférieure maximale et la limite supérieure minimale que le nœud peut propager à son parent.
Nick
@ Nick: C'est aussi ainsi que j'ai compris minimax. Comme l'OP confond initialement minimax et min-max, vous devriez peut-être le préciser très clairement dans votre réponse et inclure un exemple non trivial (autre que lié).
Raphael