Struktury danych dla gier logicznych / Zasady dedukcji / Wystarczający zestaw wskazówek?

11

Zastanawiałem się nad stworzeniem gry logicznej podobnej do Puzzle Einsteina , która zawierałaby różne zestawy wskazówek dla każdej nowej gry.

Jakich struktur danych użyłbyś do obsługi różnych podmiotów (zwierzęta domowe, kolory domów, narodowości itp.), Zasady odliczeń itp., Aby zagwarantować, że podane wskazówki wskazują na unikalne rozwiązanie?

Trudno mi myśleć o tym, jak uzyskać zasady dedukcji, aby grać wraz z możliwymi wskazówkami; każdy wgląd byłby mile widziany.

logic data-structure puzzle Taserian
źródło
1
Nie sądzę, żeby gra była bardzo interesująca. Po rozwiązaniu go raz , zrobienie tego ponownie przy użyciu innych zasad nie będzie niczym innym niż granie w sudoku.
o0 ”.
4
Z drugiej strony ludzie wykonują setki sudoku, zanim się nimi nudzą. A jeśli powiążesz odpowiedzi z jakimś działaniem w świecie zamiast wpisywać tylko numer lub imię, ludzie nawet nie będą narzekać, że to sudoku.
To przypomina mi tę grę: nick.com/games/series.html
CeeJay
3
Proponuję rzucić okiem na gry Everetta Kasera - stworzył mnóstwo tego rodzaju gier, w szczególności Sherlocka, który był zainspirowany tą układanką, ale także niektóre inne gry, takie jak Honeycomb Hotel lub jego najnowsza gra , Pani Hudson . Pomoże ci to zobaczyć coś takiego w akcji.
Michael Madsen
@Joe: to, co mówisz, jest technicznie właściwe, ale ważne jest, aby wiedzieć, co robisz (on) robi. Robienie gry podobnej do sudoku jest w porządku, jeśli masz świadomość, że to robisz, a prawie na pewno doprowadzi do bzdurnych rezultatów, jeśli uważasz, że robisz coś innego.
o0 ”.

Odpowiedzi:

4

Łał. To faktycznie wydaje się być sytuacją, w której przydatne byłyby old-schoolowe semantyczne sieci AI, takie jak Richard Bartle, które będą miały znaczenie dla przyszłości gier, gdy pisał Sztuczną inteligencję i gry komputerowe . Zasadniczo masz kilka list danych (tabele bazy danych, cokolwiek), z których pierwsza określa reguły dotyczące tego, jak rzeczy mogą się ze sobą odnosić, takie jak:

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

Następnie masz wystąpienia kategorii:

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

Te struktury danych nie uwzględniają całkowicie sytuacji - potrzebujesz ograniczeń unikatowości, a niektóre kategorie wymagają meta-reguł, takich jak POSITIONobsługa „po prawej stronie”, „po lewej stronie” i „dalej” na przykład, ale struktura problemu wydaje się je zdecydowanie sugerować.

Nie wiem, czy to zaprowadzi cię bardzo daleko, ale mam nadzieję, że to pomoże.

chaos
źródło
4

Moje zalecenie to przyjrzenie się kodowi Python dla problemów z ograniczeniami związanymi z ograniczeniami (CSP) dostarczonego z projektem AIMA . Używają słownika (tablica asocjacyjna / tablica skrótów) do śledzenia poprawnych ograniczeń. Ponadto istnieją implementacje kilku algorytmów używanych do rozwiązywania CSP, takich jak min-konflikty i AC3.

Kod zawiera przykładowy problem Zebry jako przykład, taki jak ten, z którym się łączysz.

Brandon
źródło
1

To naprawdę idzie bardzo głęboko. Dziwne, że Wikipedia nigdy o tym nie wspomina.

To, czego szukasz, to bardzo twarde dowody, które prawdopodobnie można uzyskać za pomocą takich rzeczy, jak dowody Fitch . Więc staramy się odjąć rzeczy z naszych danych. Istnieje wiele konstruktorów Fitch, którzy wykonują dla ciebie dużo pracy. Ale niektóre ćwiczenia nie mają tego udowodnić.

Nie wiem, czy użytkownik powinien wykonać obliczenia. Jeśli tak, pamiętaj o takich rzeczach jak 3SAT , które są nierozwiązywalnym problemem dla czasu wielomianowego.

Jeśli chodzi o struktury danych, których chcesz użyć, myślę, że chcesz mieć jakąś Ruleklasę. Reguła może być dowolna, w zależności od typu. W logice predykatów nie ma wielu reguł , więc można to obejść przez dziedziczenie (if, iff i, lub, nie ...). Zasady te należy jedynie ocenić. Jedyne, co może zrobić reguła, to zwrócenie wartości prawda lub fałsz. Ponieważ to właśnie robisz z logiką predykatów. Na uniwersytecie John Kelly polecił mi przeczytać tę książkę .

Wracając do zajęć: Powinieneś zobaczyć te problemy tak, jakbyś widział wdrożenie normalnych obliczeń za pomocą matematyki. Co to jest +operator? Zawiera dwa parametry, które mogą być nowym równaniem lub tylko liczbą. Myślę, że masz to samo z Regułami. Mogą mieć nowe reguły jako parametr lub po prostu wartość logiczną (tzw. Predykat).

Mam nadzieję, że to ci bardzo pomaga, zwłaszcza referencje. Jeśli chcesz dowiedzieć się więcej lub pójdę w złym kierunku, powiedz mi.

Marnix
źródło
Problemem nie są po prostu dowody w logice predykatów na skończony (i malutki!) Model, inaczej bym odpowiedział, niż wystawił nagrodę. Celem jest nie do rozwiązania problemu - celem jest automatycznie sprawiają problemu, w ciekawy sposób.
@Joe Problem, nawet w przypadku niewielkiego zestawu, nadal stanowiłby problem 3SAT. Jeśli tworzysz tylko AND i OR, może to prowadzić do rzeczy, które nie są zadowalające, więc myślę, że bardzo trudno byłoby wygenerować losową łamigłówkę. Łamigłówka powinna zawierać co najmniej pewne ograniczenia. Czasami odpowiedź wsteczna może być odpowiedzią (znajdź rozwiązanie, pomiń rzeczy)
Marnix
Ogólna logika predykatów jest w rzeczywistości trudniejsza niż 3SAT; jednak nowoczesne algorytmy dowodowe są naprawdę całkiem dobre w praktyce. Poza tym po prostu generowanie modelu, układanki i sprawdzenie rozwiązania można wykonać w czasie liniowym - sztuczka polega na upewnieniu się, że dostarczone ograniczenia tworzą unikalne, możliwe do wykrycia rozwiązanie.
@Joe, więc czy istnieją jakieś ograniczenia, które możemy być pewni przy tworzeniu tej układanki? Pytanie wciąż brzmiało: jakiej struktury danych użyć. Nadal uważam, że Ruleklasa to dobry pomysł. Myślę, że modelowanie tych ograniczeń nadal odbywa się za pomocą logiki predykatów.
Marnix,
0

Nie mam dobrej odpowiedzi, ale szukając wskazówek dotyczących tego samego rodzaju problemu, znalazłem to repozytorium na github:

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

Zawiera pewną logikę wybierania wskazówek i decydowania, ile wskazówek potrzebujesz, aby rozwiązać zagadkę.

Vegar
źródło
-1

Problem polega na rozwiązaniu tego.

Oczywiście myślę, że nie byłoby zbyt trudno pracować wstecz; to jest taka lista:

  • Fred Red Dog

  • Steve Blue Cat

  • Bill Purple Whale

  • Eric Cyan Dolphin

Które można łatwo wygenerować, a następnie stworzyć z tego zestaw reguł.

Jeśli chodzi o przechowywanie, dlaczego nie zestaw każdej osobnej rzeczy, więc [Fred, Steve, Bill, Eric] i zestaw odpowiedzi [Fred, Red, Dog]. Następnie „NAZWA (NIE) DZIAŁA”.

Czy gdy przyjdzie Ci do głowy, czy naprawdę ważne jest unikalne rozwiązanie? Tak długo, jak Twoja gra może podzielić je na listy i zaznaczyć „zestaw 1 nie zawiera wieloryba”.

Kaczka komunistyczna
źródło
2
Sztuka polega na tym, że chcesz, aby problem był nadal trudny. Jeśli generowane reguły dopuszczają 90% możliwych kombinacji jako prawidłowe odpowiedzi, nie jest to już interesująca łamigłówka.
Wydaje mi się, że to słuszna kwestia - ale czy nie jest to rozwiązanie tylko po to, aby zmniejszyć liczbę podanych wskazówek?
Kaczka komunistyczna
1
Nie. Nieokreślona specyfikacja może prowadzić do wielu ważnych wniosków. Przekroczenie specyfikacji może doprowadzić do jednego bardzo oczywistego wniosku. Dobra logiczna łamigłówka pozwala uniknąć obu.
Ach tak, jakoś mi tego brakowało. Spróbuję dodać lepsze rozwiązanie, jeśli mogę o tym pomyśleć.
Kaczka komunistyczna
Joe: Dokładnie tak, z twoim pierwszym komentarzem. Łamigłówka, która pozwala ci zacinać wskazówki, chcąc nie chcąc, to nie tyle układanka, co projekt artystyczny w przedszkolu.
taserian