Как хранить редкое дерево решений (список перемещений) в базе данных? - PullRequest
Новая
       42

Как хранить редкое дерево решений (список перемещений) в базе данных?

8 голосов
/ 07 августа 2011

Я давно думал о создании ИИ для настольной игры, и недавно я начал собирать ресурсы и алгоритмы.Игра неслучайная, и в большинстве случаев для игрока <3 хода, иногда> 20 ходов.Я хотел бы хранить критические ходы или неоднозначные ходы, чтобы ИИ учился на своих ошибках и не повторил бы такую ​​же ошибку в следующий раз.Ходы, которые несомненно выигрывают или проигрывают, не должны быть сохранены.Так что у меня фактически есть разреженное дерево решений для начала игр.Я хотел бы знать, как я должен хранить это дерево решений в базе данных?База данных не обязательно должна быть SQL, и я не знаю, какая база данных подходит для этой конкретной проблемы.

РЕДАКТИРОВАТЬ: Пожалуйста, не говорите мне, чтобы проанализировать дерево решений в памяти, просто представьте игру так сложно, как шахматы.

Ответы [ 10 ]

1 голос
/ 22 августа 2011

Поскольку вы будете обходить дерево, neo4j кажется мне хорошим решением. SQL не является хорошим выбором из-за множества соединений, которые вам понадобятся для запросов. Как я понимаю вопрос, вы спрашиваете о способе сохранения некоторого графа в базе данных, а neo4j - это база данных для графов. Для разреженности вы можете прикрепить массивы примитивов или строк к краям вашего графа для кодирования последовательностей ходов, используя PropertyContainers (верно, что из-за разреженности и пропуска узлов вы имеете в виду, что ребра дерева - это последовательности движений, а не одиночные движется?).

0 голосов
/ 17 декабря 2011

Я бы подошел к этому традиционным способом обработки начальной книги в шахматных движках:

  1. Генерация всех возможных ходов
  2. Для каждого хода:
    1. Сделатьэтот ход
    2. Посмотрите получившуюся позицию вверх в вашей базе данных
    3. Отмените ход
  3. Сделайте ход с самым высоким счетом в вашей базе данных

Поиск хода

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

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

Как шахматные движки делают это

Большинство шахматных движков используют статические вводные книги, которые составлены из записанных игр и, следовательно, используют сиmple двоичный файл, который отображает эти хэши на счет;например, 

struct book_entry {
    uint64_t hash
    uint32_t score
}

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

Обновление баллов

Однако, если вы хотите, чтобы движок постоянно учился, вам понадобится более сложная структура данных;на этом этапе это обычно не стоит делать самостоятельно, и вы должны использовать доступную библиотеку.Я бы, вероятно, использовал LevelDB , но все, что позволяет хранить пары ключ-значение, подходит (Redis, SQLite, GDBM и т. Д.)

Обучение счетам

КакТочное обновление результатов зависит от вашей игры.В играх с большим количеством доступных данных работает простой подход, такой как просто сохранение процента игр, выигранных после хода, результатом которого стала позиция;если у вас меньше данных, вы можете сохранить результат поиска по игровому дереву из рассматриваемой позиции как счет.Методы машинного обучения, такие как Q learning , также возможны, хотя я не знаю программы, которая фактически делает это на практике.

0 голосов
/ 11 декабря 2011

Я не могу ясно представить себе ни структуры данных, которые вы обрабатываете в своем дереве, ни их сложность.

Но вот некоторые мысли, которые могут вас заинтересовать:

  • Отобразите ваше дерево решений в разреженную матрицу, ведь дерево - это граф, в конце концов
  • Разработка стратегии хранения / извлечения с использованием преимуществ разреженных свойств матрицы.
0 голосов
/ 23 августа 2011

Знаете ли вы Чинук - ИИ, который решает шашки?Это достигается путем составления базы данных всех возможных эндшпилей.Хотя это не совсем то, что вы делаете, вы можете извлечь из этого уроки.

0 голосов
/ 23 августа 2011

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

0 голосов
/ 22 августа 2011

Начните с простого проектирования таблицы базы данных.

Решения: CurrentState BINARY (57) |NewState BINARY (57) |Счет INT

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

Рэндзю, использует доску 15x15, каждая локация может быть либо черной, белойили пустой, так что вам нужно Ceiling ((2bit * 15 * 15) / 8) байтов для сериализации платы.В SQL это будет BINARY (57) в T-SQL

Ваш ИИ выберет текущие ходы, которые он сохранил, например ... 

SELECT NewState FROM Decisions WHERE CurrentState = @SerializedState ORDER BY Score DESC

Вы получите списоквсе сохраненные последующие ходы из текущего игрового состояния в порядке от лучшего к наименьшему количеству очков.

В вашей структуре таблицы будет составной уникальный индекс (первичный ключ) для (CurrentState, NewState), чтобы упростить поиск и избежать дубликатов..

Это не лучшее / самое оптимальное решение, но из-за недостатка знаний о БД, я полагаю, его будет проще всего реализовать и дать хорошее начало.

0 голосов
/ 22 августа 2011

Вы можете использовать отображенный в памяти файл в качестве хранилища. Сначала создайте «компилятор». Этот компилятор проанализирует текстовый файл и преобразует его в компактное двоичное представление. Главное приложение отобразит этот двоичный оптимизированный файл в память. Это решит вашу проблему с ограничением размера памяти

0 голосов
/ 22 августа 2011

Я бы использовал базу данных документов (NOSQL), например RavenDB , потому что вы можете хранить любую структуру данных в базе данных.

Документы не плоские, как в обычной базе данных SQL, и этопозволяет вам хранить иерархические данные, например, деревья напрямую: 

{ 
   decision: 'Go forward', 
   childs: [ 
      { decision: 'Go backwards' },
      { 
         decision: 'Stay there',
         childs: [
            { decision: 'Go backwards' }
         ]
      }
   ]
}

Здесь вы можете увидеть пример дерева JSON, которое может храниться в RavenDB.

RavenDB также имеетвстроенная функция для запроса иерархических данных: http://ravendb.net/faq/hierarchies

Пожалуйста, посмотрите документацию , чтобы получить больше информации о том, как работает RavenDB.

Ресурсы:

0 голосов
/ 22 августа 2011

Во-первых, то, что вы пытаетесь сделать, звучит как проблема, основанная на рассмотрении дела (см. CBR), см. http://en.wikipedia.org/wiki/Case-based_reasoning#Prominent_CBR_systems.У ЦБ РФ будет база данных о решениях, ваша система теоретически выберет наилучшие доступные результаты.

Поэтому я бы предложил использовать neo4j, который является базой данных графа nosql.http://neo4j.org/

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

0 голосов
/ 07 августа 2011

Я предполагаю, что ваш вопрос спрашивает о том, как преобразовать дерево решений в последовательный формат, который можно записать в местоположение, а затем использовать для восстановления дерева.

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

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

...