Структуры данных для логических игр / Правила дедукции / Достаточный набор подсказок?

11

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

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

Мне трудно думать о том, как заставить правила дедукции подойти к возможным подсказкам; Любое понимание будет оценено.

logic data-structure puzzle taserian
источник
1
Я не думаю, что было бы очень интересно играть. После того, как вы решите это один раз , выполнение этого снова с другими правилами не будет сильно отличаться от игры в судоку.
о0 '.
4
С другой стороны, люди делают сотни судоку, пока им не надоест. И если вы привязываете ответы к какому-то действию в мире, а не просто вводите число или имя, люди даже не будут жаловаться, что это судоку.
Это напоминает мне об этой игре: nick.com/games/series.html
CeeJay
3
Я хотел бы предложить взглянуть на Эверетт Käser игры «s - он сделал тонну игр такого рода, в частности , Шерлок который был вдохновлен этой самой головоломки, но и некоторые из других игр, как Honeycomb отеля или его последней игре , миссис Хадсон . Это может помочь вам увидеть подобные вещи в действии.
Майкл Мэдсен
@Joe: то, что вы говорите, технически правильно, но здесь важно знать, что вы (он) делаете. Игра в стиле судоку - это хорошо, если вы знаете, что делаете это, хотя это почти наверняка приведет к дерьмовым результатам, если вы думаете, что делаете что-то еще.
о0 '.

Ответы:

4

Вау. Это на самом деле похоже на ситуацию, когда семантические сети ИИ старой школы, как полагал Ричард Бартл, будут важны для будущего игр, когда он писал « Искусственный интеллект и компьютерные игры» , которые были бы полезны. В основном у вас есть пара списков данных (таблиц базы данных и т. Д.), Первый из которых определяет правила о том, как вещи могут относиться друг к другу, например:

a PERSON must LIVE IN a DOMICILE
a PERSON must OWN an ANIMAL
a PERSON must DRINK a BEVERAGE
a PERSON must SMOKE a CIGARETTE BRAND
a PERSON must BE OF a NATIONALITY
a DOMICILE must BE IN a POSITION
a DOMICILE must BE OF a COLOR

Тогда у вас есть экземпляры категорий:

ANIMAL: dog snail zebra fox horse
BEVERAGE: milk tea OJ coffee water
CIGARETTE BRAND: Kools Parliaments Luckies OldGold Chesterfields
NATIONALITY: Englishman Spaniard Ukrainian Japanese Norwegian
POSITION: first second third fourth fifth
COLOR: red green yellow ivory blue

Эти структуры данных не полностью инкапсулируют ситуацию - вам нужны ограничения уникальности, а некоторым категориям нужны мета-правила, такие как POSITIONобработка «справа от», «слева от» и «следующий» к «понятиям», например - но структура проблемы, кажется, настоятельно рекомендует их.

Не знаю, если это приведет вас очень далеко, но я надеюсь, что это поможет.

хаос
источник
4

Моя рекомендация состоит в том, чтобы взглянуть на код Python для проблем удовлетворения ограничений (CSP), предоставляемый с проектом AIMA . Они используют словарь (ассоциативный массив / хэш-таблицу), чтобы отслеживать действительные ограничения. Также есть реализации нескольких алгоритмов, используемых для решения CSP, таких как минимальные конфликты и AC3.

Код включает в себя пример задачи Zebra в качестве примера, например, тот, на который вы ссылаетесь.

Brandon
источник
1

Это идет очень глубоко на самом деле. Странно, что Википедия никогда не упоминает о нем.

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

Я не знаю , если пользователь должен делать расчеты. Если да, то знать о таких вещах , как 3SAT , которые невыполнимая задача для полиномиального времени.

Что касается структур данных , которые вы хотите использовать, я думаю , что вы хотите иметь какой - то Ruleкласс. Правило может быть что угодно, в зависимости от типа. Есть не много правил в предикатных логик , так что это может быть преодолена путем наследования (если, тогда и только тогда, и, или, не ...). Эти правила должны быть оценены только. И единственное правило может сделать, это вернуть истинным или ложным. Потому что это то , что вы делаете с предикатных логик. В университете я рекомендовал читать эту книгу Джона Келли .

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

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

Marnix
источник
Проблема заключается не просто в доказательствах в логике предикатов в конечной (и крошечной!) Модели, иначе я бы ответил, а не увеличил вознаграждение. Цель состоит в том, чтобы не решить эту проблему - цель состоит в том, чтобы автоматически сделать эту проблему, и в занимательной форме.
@Joe Проблемы, даже для крошечного набора, все равно будет проблема 3SAT. Если вы создаете только «И» и «ИЛИ», это может привести к вещам, которые не могут быть удовлетворены, поэтому я думаю, что было бы очень сложно просто создать случайную головоломку. Головоломка должна содержать , по крайней мере , некоторые ограничения. Иногда назад рассуждения может быть ответом (есть решение, оставить вещи из)
Марниксплатс
Общая логика предикатов на самом деле сложнее, чем 3SAT; однако современные алгоритмы проверки действительно хороши на практике. Кроме того, простое создание модели, головоломки и проверка решения могут быть выполнены за линейное время - хитрость заключается в том, чтобы предоставляемые ограничения создавали уникальное обнаруживаемое решение.
@ Джо, так есть ли какие-то ограничения, с которыми мы можем быть уверены в создании этой головоломки? Вопрос все еще был: какую структуру данных использовать. Поэтому я все еще думаю, что Ruleкласс - хорошая идея. Я думаю, что моделирование этих ограничений все еще выполняется логикой предикатов.
Marnix
0

У меня нет хорошего ответа, но, ища подсказки по той же проблеме, я нашел этот репозиторий на github:

https://github.com/nateinaction/Zebra-Puzzle

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

Vegar
источник
-1

Есть это на решение этого.

Конечно, я думаю, что не было бы слишком сложно работать задом наперед; то есть список как это:

  • Фред Ред Дог

  • Стив Блю Кэт

  • Билл Фиолетовый Кит

  • Эрик Сайан Дельфин

Которые могут быть легко сгенерированы, а затем составить набор правил из этого.

Что касается хранения, почему бы не набор каждой отдельной вещи, поэтому [Фред, Стив, Билл, Эрик] и набор ответов [Фред, Ред, Дог]. Затем имейте «ИМЯ (не) ДЕЙСТВИТЕЛЬНЫЙ ОБЪЕКТ».

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

Коммунистическая утка
источник
2
Хитрость в том, что вы хотите, чтобы проблема все еще была сложной. Если сгенерированные вами правила допускают 90% возможных комбинаций в качестве правильных ответов, это уже не интересная головоломка.
Я полагаю, что это верный момент - но не является ли решение просто снизить количество подсказок?
Коммунистическая утка
1
Нет. Недооценка, скорее всего, приведет ко многим обоснованным выводам. Чрезмерное уточнение может привести к одному очень очевидному выводу. Хорошая логическая головоломка избегает обоих.
Ах да, я как-то пропустил это. Я постараюсь добавить лучшее решение, если смогу придумать.
Коммунистическая утка
Джо. Совершенно верно с вашим первым комментарием. Головоломка, которая позволяет вам смешно разгадывать подсказки, - не столько загадка, сколько детский проект.
taserian