Minimax Algorithm queue possible?

Question

Est-il possible de représenter un algorithme minimax dans une structure de données de file d'attente ou est-ce seulement possible dans un arbre?

Answer 1

Si vous implémentez minimax en tant que première recherche d'arbre de jeu, la nature FIFO d'une file d'attente est un ajustement naturel pour l'algorithme. Vous stockez chaque position dans la file d'attente, puis toutes les positions qui pourraient résulter de cette position. Recouvrez jusqu'à ce que vous atteigniez la profondeur de recherche finale. Mais l'inconvénient, et c'est un gros problème, c'est qu'il y a un nombre exponentiel de nœuds terminaux par rapport à la profondeur de l'arbre et que vous devriez tous les stocker dans la file d'attente pour une recherche en largeur.

Minimax est mieux implémenté comme une recherche en profondeur, qui ne nécessite qu'une quantité linéaire de mémoire par rapport à la profondeur de l'arbre. La structure de données utilisée pour cette recherche est une pile, soit par le biais d'appels de fonction récursifs, soit par une implémentation basée sur une pile directe sans l'en-tête d'appel de fonction.