Datenstrukturen für Logikspiele / Abzugsregeln / ausreichende Hinweise?

11

Ich habe darüber nachgedacht, ein Logikspiel zu entwickeln, das Einsteins Puzzle ähnelt und bei jeder neuen Spielwiederholung unterschiedliche Hinweise enthält.

Welche Datenstrukturen würden Sie verwenden, um mit den verschiedenen Entitäten (Haustiere, Hausfarben, Nationalitäten usw.), Abzugsregeln usw. umzugehen, um sicherzustellen, dass die von Ihnen angegebenen Hinweise auf eine einzigartige Lösung hinweisen?

Es fällt mir schwer darüber nachzudenken, wie ich die Abzugsregeln dazu bringen kann, mit den möglichen Hinweisen zu spielen. Jeder Einblick wäre dankbar.

logic data-structure puzzle taserian
quelle
1
Ich denke nicht, dass es sehr interessant wäre zu spielen. Nachdem Sie es einmal gelöst haben , unterscheidet sich das erneute Ausführen mit anderen Regeln nicht wesentlich vom Sudoku-Spielen.
o0 '.
4
Auf der anderen Seite machen die Leute Hunderte von Sudoku, bevor sie sich langweilen. Und wenn Sie die Antworten an eine Art Aktion in der Welt binden, anstatt nur eine Zahl oder einen Namen einzugeben, werden sich die Leute nicht einmal darüber beschweren, dass es sich um Sudoku handelt.
Das erinnert mich an dieses Spiel: nick.com/games/series.html
CeeJay
3
Ich würde vorschlagen, einen Blick auf Everett Kasers Spiele zu werfen - er hat eine Menge Spiele dieser Art gemacht, insbesondere Sherlock, der von diesem Rätsel inspiriert wurde, aber auch einige der anderen Spiele, wie Honeycomb Hotel oder sein neuestes Spiel , Frau Hudson . Es könnte Ihnen helfen, solche Dinge in Aktion zu sehen.
Michael Madsen
@ Joe: Was du sagst, ist technisch richtig, aber das Wichtigste hier ist zu wissen, was du (er) tust. Ein Sudoku-ähnliches Spiel zu machen ist in Ordnung, wenn Sie sich dessen bewusst sind, während es mit ziemlicher Sicherheit zu Mistergebnissen führt, wenn Sie glauben, etwas anderes zu tun.
o0 '.

Antworten:

4

Beeindruckend. Dies scheint tatsächlich eine Situation zu sein, in der semantische KI-Netze der alten Schule, wie Richard Bartle dachte, dass sie für die Zukunft von Spielen wichtig sein würden, als er Künstliche Intelligenz und Computerspiele schrieb , nützlich wären. Grundsätzlich haben Sie ein paar Datenlisten (Datenbanktabellen, was auch immer), von denen die erste Regeln festlegt, wie Dinge miteinander in Beziehung stehen können, wie zum Beispiel:

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

Dann haben Sie Instanzen der Kategorien:

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

Diese Datenstrukturen kapseln die Situation nicht vollständig - Sie benötigen die Eindeutigkeitsbeschränkungen, und einige der Kategorien benötigen Metaregeln, z. B. POSITIONdie Behandlung von "rechts von", "links von" und "next" zu "Konzepten zum Beispiel - aber die Struktur des Problems scheint sie stark zu suggerieren.

Keine Ahnung, ob dies Sie sehr weit bringen wird, aber ich hoffe, es hilft.

Chaos
quelle
4

Ich empfehle, den Python-Code für Constraint Satisfaction Problems (CSPs) zu lesen, der im AIMA-Projekt enthalten ist . Sie verwenden ein Wörterbuch (assoziative Array- / Hash-Tabelle), um gültige Einschränkungen zu verfolgen. Es gibt auch Implementierungen mehrerer Algorithmen, die zur Lösung von CSPs verwendet werden, wie z. B. Min-Konflikte und AC3.

Der Code enthält als Beispiel ein Beispiel für ein Zebra-Problem, wie das, mit dem Sie verknüpft haben.

Brandon
quelle
1

Das geht eigentlich sehr tief. Seltsam, dass Wikipedia es nie erwähnt.

Was Sie suchen, sind sehr harte Beweise, die wahrscheinlich mit Dingen wie Fitch-Beweisen erreicht werden können . Wir versuchen also, Dinge aus unseren gegebenen Daten abzuleiten. Es gibt viele Fitch Proof Builder , die viel Arbeit für Sie erledigen. Aber einige Übungen sind einfach nicht zu beweisen.

Ich weiß nicht, ob der Benutzer die Berechnungen durchführen soll. Wenn ja, beachten Sie Dinge wie 3SAT , die für die Polynomzeit unlösbare Probleme darstellen.

Was die Datenstrukturen betrifft, die Sie verwenden möchten, möchten Sie eine Art RuleKlasse haben. Die Regel kann je nach Typ beliebig sein. Es gibt nicht viele Regeln in Prädikatenlogiken , daher kann dies durch Erben überwunden werden (if, iff und oder, not ...). Diese Regeln müssen nur ausgewertet werden. Und das einzige, was eine Regel tun kann, ist, wahr oder falsch zurückzugeben. Denn genau das machen Sie mit Prädikatenlogiken. An der Universität wurde mir empfohlen, dieses Buch von John Kelly zu lesen .

Zurück zu den Klassen: Sie sollten diese Probleme so sehen, als würden Sie normale Berechnungen mit Mathematik implementieren. Was ist ein +Operator? Es enthält zwei Parameter, die eine neue Gleichung für sich oder nur eine Zahl sein können. Ich denke, Sie haben das gleiche mit Regeln. Sie können neue Regeln als Parameter oder nur einen Booleschen Wert (sogenanntes Prädikat) haben.

Ich hoffe das hilft dir sehr, besonders die Referenzen. Wenn Sie mehr wissen wollen oder wenn ich in die falsche Richtung gehe, sagen Sie es mir bitte.

Marnix
quelle
Das Problem sind nicht nur Beweise in Prädikatenlogik über ein endliches (und winziges!) Modell, oder ich hätte eher geantwortet, als ein Kopfgeld aufzubringen. Das Ziel ist nicht , das Problem zu lösen - das Ziel ist es , das Problem automatisch und auf interessante Weise zu lösen .
@ Joe Das Problem, selbst für ein winziges Set, wäre immer noch das 3SAT-Problem. Wenn Sie nur UNDs und ODERs erstellen, könnte dies zu Dingen führen, die nicht zufriedenstellend sind. Ich denke, es wäre sehr schwierig, nur ein zufälliges Puzzle zu generieren. Das Puzzle sollte zumindest einige Einschränkungen enthalten. Manchmal könnte Rückwärtsdenken die Antwort sein (eine Lösung haben, Dinge weglassen)
Marnix
Die allgemeine Prädikatenlogik ist tatsächlich schwieriger als 3SAT. Moderne Proof-Algorithmen sind jedoch in der Praxis ziemlich gut. Abgesehen davon kann das einfache Generieren eines Modells, eines Puzzles und das Überprüfen einer Lösung in linearer Zeit erfolgen. Der Trick besteht darin, sicherzustellen, dass die bereitgestellten Einschränkungen eine einzigartige, auffindbare Lösung ergeben.
@ Joe, gibt es also irgendwelche Einschränkungen, bei denen wir sicher sein können, dass wir dieses Puzzle erstellen? Die Frage war immer noch: Welche Datenstruktur soll verwendet werden? Daher denke ich immer noch, dass der RuleUnterricht eine gute Idee ist. Die Modellierung dieser Einschränkungen erfolgt meiner Meinung nach immer noch durch Prädikatenlogik.
Marnix
0

Ich habe keine gute Antwort, aber auf der Suche nach Hinweisen zu der gleichen Art von Problem habe ich dieses Repository auf github gefunden:

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

Es enthält eine Logik zum Auswählen von Hinweisen und zum Entscheiden, wie viele Hinweise Sie benötigen würden, um das Rätsel lösbar zu machen.

Vegar
quelle
-1

Es gibt dies beim Lösen.

Natürlich denke ich, dass es nicht allzu schwierig wäre, rückwärts zu arbeiten. Das heißt, Sie haben eine Liste wie diese:

  • Fred Red Dog

  • Steve Blue Cat

  • Bill Purple Whale

  • Eric Cyan Dolphin

Welches könnte leicht generiert werden, und dann eine Reihe von Regeln daraus bilden.

Was die Aufbewahrung betrifft, warum nicht eine Reihe von einzelnen Dingen, also [Fred, Steve, Bill, Eric] und eine Reihe der Antworten [Fred, Red, Dog]. Dann haben Sie 'NAME macht (nicht) ACTION OBJECT'.

Ist eine einzigartige Lösung wirklich wichtig, wenn Sie sich darauf konzentrieren? Solange Ihr Spiel sie in die Listen aufteilen kann und aktivieren Sie "Set 1 enthält keinen Wal".

Die kommunistische Ente
quelle
2
Der Trick ist, dass das Problem immer noch schwierig sein soll. Wenn die von Ihnen generierten Regeln 90% der möglichen Kombinationen als gültige Antworten zulassen, ist dies kein interessantes Rätsel mehr.
Ich denke, das ist ein gültiger Punkt - aber ist die Lösung nicht nur, um die Anzahl der gegebenen Hinweise zu verringern?
Die kommunistische Ente
1
Nein. Eine zu geringe Spezifikation führt eher zu vielen gültigen Schlussfolgerungen. Eine Überspezifikation führt wahrscheinlich zu einer sehr offensichtlichen Schlussfolgerung. Ein gutes Logik-Puzzle vermeidet beides.
Ah ja, das habe ich irgendwie verpasst. Ich werde versuchen, eine bessere Lösung hinzuzufügen, wenn mir eine einfällt.
Die kommunistische Ente
Joe: Genau richtig mit deinem ersten Kommentar. Ein Puzzle, mit dem Sie wohl oder übel Hinweise zusammenfügen können, ist weniger ein Puzzle als ein Kunstprojekt für Kindergärten.
Taserian