Лучшая структура данных для N-арного дерева - PullRequest
Новая
       73

Лучшая структура данных для N-арного дерева

0 голосов
/ 30 мая 2019

Мне нужно представить дерево с несколькими ветвями на узел.Какую структуру я должен использовать?Это для вычисления состояний игры в шахматы.Он взрывается экспоненциально, поэтому память будет проблемой.Я использую C ++ 11, но я открыт для других стандартов.Кроме того, обрезка должна быть O (1).

EDIT1 Чтобы расширить, я собираюсь провести соревнование по шахматному ИИ.Основная PvP-игра уже завершена, и я программирую AI API.Конкурсанты напишут свой ИИ, и тогда мы заставим их участвовать в турниреИИ победителя будет использован в Player vs Computer games.Я просто думаю о лучшей структуре для хранения моих состояний игры и мыслей ИИ.

Я читал о Deep Blue, и он думает, что от 5 до ~ 25 шагов вперед.Я могу представить себе большинство компьютеров, способных обрабатывать 5 ходов на глубину с помощью BFS, но что-то более глубокое, и я считаю, что мне придется использовать DFS.

AI будут синхронизированы, а конкурирующие AI будут воспроизводиться только локально, так что нет.чтобы представить преимущества в мощности процессора.

Я читаю о поисках Монте-Карло и Альфа-бета.

Мои первоначальные мысли о структуре данных следующие: 

union CHESS_MOVE {
   unsigned short m;
   ChessPosT pos[2];
   ///...
};

class ChessMoveNode {
   CHESS_MOVE move;
   std::set<ChessMoveNode> nextmoves;
};

class ChessMoveTree {
   std::set<ChessMoveNode> next;
};

Плата может быть рассчитана в любое время путем объединения пути от корня до листа.Хотя пересчет платы может стать очень дорогим со временем.Идеи?Должен ли я хранить доску?Доска хранится в виде массива из 64 индексов, содержащих номер фигуры.Таким образом, это 16 байтов, по сравнению с 2, но использование памяти сэкономило бы много пересчета состояния платы.

Для моего личного ИИ я буду реализовывать функцию оценки доски, которая будет ранжироватьигровые состояния, а затем все не максимальные игровые состояния будут отбрасываться, а также обрезать игровые состояния, которые становятся недействительными при выборе хода.

1 Ответ

1 голос
/ 30 мая 2019

Один простой способ сделать это, который хорошо работает для поиска по дереву Монте-Карло (MCTS), - это использовать vector некоторого пользовательского класса.Внутри класса у вас есть любая необходимая информация о состоянии в дополнение к информации о детях - число детей и их индекс в векторе.Это позволяет избежать хранения отдельного указателя для каждого дочернего элемента, что может привести к значительным накладным расходам.

Таким образом, корень находится в индексе 0.Внутри этого индекса будет два целых числа, указывающих, что дочерние элементы начинаются с индекса 1 и что есть k дочерние элементы.(От индекса 1 до k.) При индексе 1 дочерние элементы начинаются с индекса k+1 с общим числом дочерних элементов l и т. Д. По всему дереву.

Это работает очень хорошоисходя из предположения, что (1) число дочерних элементов фиксировано, (2) что они все добавляются одновременно, и (3) состояния не удаляются из дерева.

Если вы пытаетесь обрезать состояния из дерева, это не сработает, потому что вы оставите пробелы в дереве, если уберете их.Использование явных указателей для хранения каждого дочернего элемента стоит дорого, поэтому на практике что-то еще делается.

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

Однако обратите внимание, что хеш-таблицы (называемые таблицами транспонирования в контексте поиска по игровому дереву)обычно не используется глубоко в дереве, потому что существует много состояний и стоимость хранения возрастает, а польза от удаления дубликатов уменьшается.

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

...