Является ли тензор (многомерный массив) эффективным типом хранения для данных предпросмотра дерева?
Я исследую один игровой алгоритм и думаю, как его улучшить. Есть загадочное дерево. Это очень распространенный сценарий, как в карточных или других подобных играх. Игровая стратегия реализована в виде тензора (многомерного массива). Количество измерений = глубина просмотра. И каждый размер измерения — это МАКСИМАЛЬНО возможное количество действий, доступных на этом уровне дерева. Один узел на одном уровне может иметь только 2 доступных действия, а другой 10. Но нам нужно иметь размерность 10, если мы используем тензор. Также нам нужно сохранить другую структуру с подсчетом действий для всех узлов. С этим тензором выполняется много операций, таких как поэлементное умножение, сложение и т. Д. Общий размер этого тензора составляет пару гигабайт. Является ли этот тензор хорошей идеей или нет с точки зрения производительности? Могу ли я сделать лучше с пользовательской структурой? Приложение очень тяжелое.
Решение
Это звучит как запоминание теории игр.
К счастью, у нас нет возможности измерять каждый уровень с самого начала, используя что-то вроде этого:
class Moves {
TheMove thisMove; // A2-A3
std::vector<Moves> positions; // all possible counter moves
... add stuff
};
Как вы упомянули, это будет ужасно взрываться в размерах. Преимущество заключается в том, что вам не нужно пересчитывать, если вы наметили общее возможное количество ходов за всю игру.
Если вы не наносите на карту всю игру, вам придется отбрасывать (x-1) / x дерева каждый ход и расширять конечные узлы на уровень.
Другие решения
Других решений пока нет …