База данных для настольных игр, решающих перебор

Question

Несколько лет назад исследователи объявили, что они разработали комплексное решение для шашек методом грубой силы.

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

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

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

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

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

Answer 1

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

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

1. Количество элементов в очереди, вероятно, будет расти в геометрической прогрессии по мере того, как вы исследуете дерево, причем каждый рабочий элемент вызывает в очереди еще несколько элементов. Будьте готовы к очень длинной очереди.
2. В зависимости от вашей игры может быть несколько путей к одному и тому же игровому состоянию. Вам нужно будет проверить и устранить дубликаты, и ваша база данных должна быть структурирована так, чтобы это был график (возможно, с циклами!), А не дерево.

Answer 2

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

Затем вы найдете максимально компактную кодировку для того набора игровых состояний, для которого вы хотите создать свою базу данных конечной игры; скажем, ваша кодировка занимает 20 бит. Тогда достаточно иметь массив 2 ²¹ бит на вашем жестком диске, то есть 2 ¹³ байт. Когда вы анализируете позицию в конце игры, вы сначала проверяете, установлено ли соответствующее значение в базе данных; если нет, вычислите все его преемники, вычислите их теоретико-игровые значения рекурсивно, а затем вычислите с помощью min / max теоретико-игровое значение исходного узла и сохраните в базе данных. (Примечание: если вы храните данные о выигрышах / проигрышах / ничьих в двух битах, у вас остается один битовый шаблон для обозначения «неизвестно»; например, 00 = неизвестно, 11 = ничья, 10 = игрок, который хочет переместить выигрыш, 01 = игрок, которому нужно ход теряет).

Например, рассмотрим крестики-нолики. Есть девять квадратов; каждый может быть пустым, «Х» или «О». Этот наивный анализ дает вам 3 ⁹ = 2 ^14.26 = 15 бит на состояние, поэтому у вас будет массив из 2 ¹⁶ бит.

Answer 3

Первое, что мне пришло в голову, это стиль Linda общей «доски», где разные процессы могут поглощать «проблемы» вне доски, добавлять новые проблемы на доску и добавлять «Решения» для доски.

Возможно, проект Cassandra является более современной версией Линды.

Было много попыток распараллелить проблемы в распределенных компьютерных системах; Folding @ Home предоставляет платформу, которая выполняет «ядра» двоичного двоичного объекта для решения проблем сворачивания белка. Distributed.net , возможно, начал современное воплощение распределенного решения проблем и может иметь клиентов, с которых вы можете начать.