Comment prouver que chaque sous-section, la stratégie est la plus optimale dans l'algorithme minimax?

Question

La question est de savoir comme le titre le suggère.

Je sais que l'algorithme minimax ce pour 2-les gens de jeu (à supposer que l'on veut maximiser Un profit):quand c'est Un tour, on prend le max de l'enfant des valeurs parce que nous sommes à maximiser les profits, et quand il est B son tour, nous prenons le min de l'enfant des valeurs parce que nous voulons minimiser B du profit.

Cependant, je ne pense pas que la logique ci-dessus prouve que chaque sous-problème, la stratégie est la plus optimale dans l'algorithme minimax.Tous conseils ou des solutions à la question que j'ai proposé?Si la logique ci-dessus est le cas, pourriez-vous élaborer sur elle?

Answer 1

La demande minimax a est:Minimax est de donner à la stratégie optimale si l'autre joueur est également en utilisant la même stratégie.

La Base de:Pour une feuille dans l'arborescence du jeu - il y a une seule stratégie, qui minimax évidemment choisit, et il est optimal car il est le seul.
Hypothèse:minimax choisit la stratégie optimale pour un jeu de profondeur d.
La preuve:

Penchons-nous sur un jeu de profondeur d+1.Il y a évidemment des 2 scénarios possibles:

1. Il est à son tour - c'est max de phase.Dans ce cas, de tous les mouvements possibles que nous pouvons faire - minimax de manière récursive évalue le min-max de la valeur pour chaque stratégie, et nous donne le résultat optimal pour un "sous-jeu", où nous avons choisi ce mouvement.Chacun de ces subgames est de profondeur d, et , à partir de l'induction hypothèse, il est optimal.
   Puisque c'est max de phase min-max algorithme choisit le max, qui est la solution optimale pour nous.
2. C'est le tour de l'adversaire - c'est min de phase.De même pour la logique ci-dessus, minimax divise le cas de tous les mouvements possibles de l'adversaire peut le faire, et évalue leurs résultats.De l'Induction-Hypothèse, les évaluations sont optimales, et nous choisissons les minimes - qui sera ce que l'adversaire aurait choisi, et est la stratégie optimale pour lui (et supposons que l'adversaire choisit de façon optimale pour chaque étape de la voie) - ainsi, l'adversaire choisit l'une évaluation minimale, qui permettent de réduire notre bénéfice, et donc de maximiser son profit.

CQFD

Basé sur lui, vous pouvez en conclure une autre revendication de minimax - la valeur retournée par la stratégie n'est pas moins que ce que vous obtenez en fait (quel que soit le oppnent de la stratégie).Cela peut être prouvé par induction très similaire à celle ci-dessus, on.

Lignes directrices:

La Base de:Une stratégie, et vous êtes de retour, quand l'arbre est en fait une feuille.
Demande:la valeur retournée par minimax pour le jeu de profondeur d est une limite inférieure de tous les matchs de ce niveau, où vous avez choisi en fonction de minimax, et aucune restriction sur l'adversaire.
La preuve:

Regardons jeu de profondeur d+1.

1. Si c'est votre tour, vous avez choisi le maximum de toutes les feuilles, puisque vous avez le choix ici.Chaque feuille vous garantit (induciton hypothèse) au moins une certaine valeur, et en choisissant le max d'entre eux - vous avez également la garantie de la valeur choisie.
2. Si c'est le tour de l'adversaire - vous n'avez aucun contrôle sur le choix.Vous ne pouvez être certain qu'il a choisi de un mouvement, aucune idée de ce qui.Cependant, pour tous les possible, déplacez - vous d'obtenir un nouveau "subgame' de profondeur d, où l'hypothèse d'induction maintenez-la enfoncée.L'adversaire peut choisir l'un de ces mouvements, de sorte que vous pouvez garantir qu'après ce coup, vous aurez une valeur d'au moins min{game after opponent move}, qui est exactement ce que le min de la phase retour.

CQFD.

Answer 2

Vous ne pouvez pas prouver que Minimax maximise le profit du joueur, car Minimax n'essaie pas de maximiser le bénéfice du joueur.

Qu'est-ce que minimax est de minimiser le possible perte ;C'est-à-dire que ses décisions sont conservatrices et assument le pire scénario (jeu optimal de l'autre joueur).Essayez de prouver que l'un;Vous le trouverez beaucoup plus simple.