Un arbre d'états de jeu n'est normalement pas construit comme une structure de données complète. Au lieu de cela, les états sont évalués au fur et à mesure de leur création et la plupart sont rejetés dans le processus. Souvent, une liste liée de l'état en cours d'évaluation à l'état actuel du jeu est maintenue. Mais si un mouvement est montré être beaucoup mieux qu'un autre, alors la ligne entière pour le mouvement pauvre sera écartée, ainsi elle n'occupera aucun espace dans la mémoire.
Une manière simple de rechercher l'espace d'état d'un jeu comme les échecs consiste à effectuer une recherche récursive à une profondeur donnée. Dans ce cas, très peu d'états de jeu existent réellement en même temps, et ceux qui existent sont simplement référencés sur la pile d'appel. Des algorithmes plus sophistiqués créeront un arbre plus grand, mais (en particulier pour les échecs) aucun ne maintiendra un arbre de tous les états possibles. Pour les échecs, une recherche en largeur peut être meilleure, en utilisant une file d'attente plutôt qu'une pile, et cela ne conservera que les états à une certaine profondeur dans l'arbre. Mieux encore, il y aurait une file d'attente prioritaire dans laquelle les meilleurs états seraient stockés pour une évaluation plus poussée, et les états les plus mauvais seraient complètement éliminés.