Problèmes d'invalidation de l'arbre min-max en place

Question

J'essaye de construire une implémentation parallèle d'un min-max search. Mon approche actuelle consiste à matérialiser l'arbre à une petite profondeur et ensuite faire la chose normale à partir de chacun de ces nœuds.

La méthode la plus simple consiste à calculer la valeur heuristique pour chaque feuille, puis de balayer et de calculer le min/max. Le problème est que cela omet alpha/beta pruning aux niveaux supérieurs et fait un coup de performance majeur.

Ma première "solution" à cela était de pousser le min/max vers le haut après chaque feuille est calculée. Ceci donne la valeur de mise à jour pour que je puisse balayer l'arbre et vérifier si une feuille devrait être élaguée.

Le problème est que c'est complètement cassé. (2 jours de mise au point à remarquer que, zut je me sens stupide)

Maintenant pour la question:

est-il un moyen de construire un arbre min-max qui permet aux leafs à évaluer dans un ordre aléatoire et permet également l'élagage alpha/bêta?

Answer 1

Découvrez recherche de l'arbre de jeu parallèle, par ex. this paper.

Answer 2

Je pense avoir trouvé une solution mais je ne l'aime pas en quelques matière:

1. annoter l'arbre avec le nombre d'enfants inachevés.
2. Après une feuille est évaluée, mettre à jour son parent, décrémenter le nombre de parents
3. Si ce nombre juste atteint zéro, le mettre à jour son parent, décrément qui comptent
4. Lather, hausse, répéter

Alpha/L'élagage bêta fonctionne comme prévu. Les problèmes avec ceci sont qu'avec l'évaluation d'ordre aléatoire, beaucoup plus de noeuds seront évalués avant que les trucs commencent à être élagués. D'un autre côté, cela pourrait être atténué par un meilleur classement des feuilles.