Установка ограничения памяти для моего алгоритма ИИ?

Question

Я работаю над реализацией Tetris AI. Это приложение с графическим интерфейсом, которое играет в игру самостоятельно. Пользователь может манипулировать несколькими параметрами, которые влияют на решения, принимаемые ИИ. Основной алгоритм выглядит следующим образом:

• Начните новый поток и клонируйте текущее состояние игры, чтобы избежать чрезмерной блокировки.
• Создайте список всех возможных будущих состояний игры. Они становятся дочерними узлами текущего игрового состояния.
• Для каждого дочернего узла генерировать свои будущие игровые состояния.
• Продолжайте делать это рекурсивно, пока не будет достигнута заранее заданная глубина.
• Как только запрошенная глубина достигнута, найдите лучший конечный узел и рекурсивно найдите его родительский узел, пока у вас не появится дочерний элемент первого уровня.
• Удалите все дочерние узлы, которые не находятся на пути между дочерним узлом и конечным узлом.
• Этот путь теперь является списком предварительно рассчитанных ходов.
• Основная игра выполняет список предварительно рассчитанных ходов (с некоторой причудливой анимацией).

Это работает довольно хорошо вплоть до глубины поиска 4. После этого у меня начинают появляться проблемы с памятью. Количество возможных игровых состояний может быть от 9 до 34. Таким образом, наихудший сценарий поиска уровня 4 будет 34 ^ 4 игровых состояния. Похоже, что Windows XP не справляется с поиском на уровне 5 (она висит на 2+ ГБ).

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

Я решил использовать пул памяти и использовать «размещение нового» для создания моих объектов в сегментах памяти пула. Однако игровая сетка реализована в виде вектора STL. Поэтому, чтобы распределить его по пулу, мне нужно реализовать собственный распределитель.

Это кажется довольно сложной задачей, и, возможно, я пропускаю более простое решение. Поэтому я хотел бы, чтобы вы поделились своими соображениями о том, как лучше всего с этим справиться.

Может ли boost или другая библиотека предоставить мне некоторые из этих возможностей? (Я уже нашел Poco MemoryPool .) Есть ли хорошие онлайн-ресурсы, которые помогут мне начать работу?

К вашему сведению: вот исходный код и пример двоичного файла для Windows .

Answer 1

Вы можете создать пул памяти и т. Д., Но это на самом деле не сделает процесс подсчета игровых состояний проще или сложнее. Вам необходимо убедиться, что вы не используете определенное количество активных состояний в дереве решений с пулом или без него. И Boost имеет один: http://www.boost.org/doc/libs/1_44_0/libs/pool/doc/index.html

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

Answer 2

Несмотря на отсутствие контекста [какую проблему поиска вы делаете? Глубина первая, ширина первая, A *? ....] Мое предложение:

Используйте семафоры, чтобы ограничить объем обработки, выполняемой за один раз, а затем отпустите ее после оценки обработки. Я не могу порекомендовать конкретную библиотеку, которая включает в себя семафоры, так как эта многопоточность не встроена в C ++, однако сверьтесь с документацией вашей платформы.