jeu arbre de recherche, ce que je dois construire l'arbre en premier?

Question

dans le jeu arbre de recherche il y a beaucoup d'algorithmes pour obtenir la solution optimale, comme algorithme Minimax. Je commence à apprendre comment résoudre ce problème avec l'algorithme Minimax, l'algorithme clair. mais je suis confus au sujet de l'arbre lui-même, dans des jeux comme numéro de tic tac toe de noeud pas très grand, mais sur d'autres comme les échecs il y a beaucoup de nœuds. Je pense que ce besoin grand espace dans la mémoire. Donc, il y a des algorithmes pour évaluer et arbre de construction dans le même temps?

Answer 1

Un arbre d'états de jeu ne sont pas normalement construit comme une structure de données complète. Au lieu de cela, les États sont évalués car ils sont créés, et la plupart sont mis au rebut dans le processus. Souvent, une liste chaînée de l'état d'être de retour évalué à l'état actuel du jeu est maintenu. Mais si un mouvement se révèle être beaucoup mieux que l'autre, la ligne entière pour les pauvres mouvement sera mis au rebut, il occupera pas d'espace dans la mémoire.

Une façon simple pour rechercher l'espace d'état pour un jeu comme les échecs est de faire la recherche récursive à une profondeur donnée. Dans ce cas, très peu d'Etats de jeu existent en réalité à un moment donné, et ceux qui existent sont simplement référencées sur la pile des appels. Des algorithmes plus sophistiqués créer un arbre plus grand, mais (surtout pour les échecs) ne maintiendront un arbre de tous les états possibles. Pour les échecs, une recherche en largeur peut être mieux, en utilisant une file d'attente plutôt que d'une pile, et cela maintiendra seuls les États à une certaine profondeur dans l'arbre. Mieux encore serait une file d'attente prioritaire dans lequel les meilleurs états sont stockés pour une évaluation plus poussée, et les pires états sont complètement mis au rebut.