À quoi servent les valeurs minimales sur les arbres minimax?

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

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]$$3$$B.\max = 3$$12$$8$$B.max = 3$

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

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 ($B$$3$$12$$B$$3$$8$$B$$\alpha$) et la solution de limite supérieure ( ) minimale de son sous-arbre et conserve ces valeurs dans MIN ( ) et MAX ( ) (comme [3, 3]).$\beta$$\alpha$$\beta$

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 à .$C$$2$$C$$B$$D$

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$$\alpha$$\beta$

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