Дерево игровых состояний обычно не строится как целостная структура данных. Вместо этого состояния оцениваются по мере их создания, и большинство из них отбрасывается в процессе. Часто поддерживается связанный список из оцениваемого состояния обратно в текущее состояние игры. Но если показано, что одно движение намного лучше другого, тогда вся строка для плохого хода будет отброшена, поэтому она не займет места в памяти.
Один простой способ поиска в пространстве состояний для такой игры, как шахматы, - это рекурсивный поиск на заданной глубине. В этом случае очень немногие игровые состояния фактически существуют одновременно, а те, которые существуют, просто ссылаются на стек вызовов. Более сложные алгоритмы создадут большее дерево, но (особенно для шахмат) ни один не будет поддерживать дерево всех возможных состояний. Для шахмат поиск в ширину может быть лучше, используя очередь, а не стек, и это будет поддерживать только состояния на определенной глубине в дереве. Еще лучше будет очередь с приоритетами, в которой лучшие состояния сохраняются для дальнейшей оценки, а худшие состояния полностью отбрасываются.