Minimax utilisation arbre déjà évalué. Où est mon défaut?

Question

Je viens de commencer à essayer d'utiliser le Minimax / negamax algorithme et je suis venu avec une idée qui sonne bien pour moi, mais comme personne ne l'utilise, il est peut-être une logique erronée.

Pourquoi ne pas le faire:

Créez trois avec profondeur = x, savoir qui se déplacent à faire, et attendre notre adversaire. Après avoir fait son déménagement nous pouvons simplement prendre le sous-arbre des mouvements que nous avons déjà évalué et continuer à construire plus profond tout en utilisant les anciens nœuds. Nous pourrions utiliser les valeurs déjà évaluées des nœuds et les peser avec les nouvelles valeurs de nouveaux nœuds plus profonds.

Altough les nouvelles valeurs pourraient ne pas être aussi exacte que la méthode habituelle, nous pourrions obtenir beaucoup plus profond et tirer profit de cela.

Je présente mes excuses pour mon et une mauvaise question écrite et non structurées, mais je l'espère vous mon idée.

Answer 1

Je pense que ce que vous êtes absent ici est comment fonctionne Minimax. Minimax énumère toutes les possibilités à une profondeur D spécifiée, attribue ensuite un score aux nœuds (états de jeu) à D, et en décalant l'arbre, retourne le nœud MAX ou MIN à chaque profondeur selon que je suis la maximisation joueur ou le joueur de réduction au minimum.

Votre proposition de le faire de haut en bas voudrait dire que vous devez attribuer un score aux nœuds à des profondeurs plus faible profondeur, entraînant une évaluation moins bonne.

Answer 2

L'idée est utilisée, mais d'une manière différente. Au lieu de garder l'arbre de recherche autour, ce qui serait prohibitif mémoire, les résultats d'évaluation sont conservés dans le tableau de transposition et réutilisés. Cela peut faire gagner du temps lors approfondissement itératif , car de nombreux postes seront mis en cache scores des recherches précédentes . Ainsi, en réutilisant les anciens résultats de recherche peuvent aider certaines des recherches intermédiaires et accélérer la commande de déplacement, mais les nœuds feuilles devront encore être évalués à quelque profondeur de recherche du moteur de terminal utilise.