Wie kann ich einen 20-Fragen-Algorithmus implementieren?

Seit meiner Kindheit habe ich mich gefragt, wie das elektronische 20Q- Spiel funktioniert. Sie denken an einen Gegenstand, ein Ding oder ein Tier (z. B. Kartoffel oder Esel ). Das Gerät stellt Ihnen dann eine Reihe von Fragen wie:

• Ist es größer als ein Brot?
• Wird es draußen gefunden?
• Wird es zur Erholung genutzt?

Für jede Frage können Sie " Ja" , " Nein" , " Vielleicht" oder " Unbekannt" beantworten . Ich habe mir immer vorgestellt, dass es mit immensen, verschachtelten Bedingungen ( if-Anweisungen) funktioniert. Ich denke jedoch, dass dies aufgrund seiner Komplexität für den Programmierer eine unwahrscheinliche Erklärung ist.

Wie würde ich ein solches System implementieren?

Ich weiß nicht, wie es 20Q konkret gemacht hat, aber es gibt viele Informationen darüber, wie man ein Spiel mit 20 Fragen umsetzt .

Es gibt viele Möglichkeiten, dies zu lösen, aber ich beschreibe einen Weg. Diese Spiele können eine Art Entscheidungsbaum implementieren . Für ein elektronisches Spiel wie 20Q wäre dieser Baum vorberechnet und ziemlich einfach zu durchlaufen. Es gibt Methoden zum Verwenden von Lernentscheidungsbäumen, bei denen das Spiel am Ende seiner Fragen neue Objekte akzeptieren kann, wenn es nicht in der Lage ist, die Fragen des Benutzers zu erraten.

Wenn es sich bei den Fragen um eine Reihe von Ja- oder Nein-Antworten handelt, erhalten Sie einen Binärbaum. Jeder Knoten ist eine Frage und die Blätter sind Antworten. Wenn Fragen mit unbekannt oder nicht sicher beantwortet werden, können die untergeordneten Knoten kombiniert und ihre Fragen in Reihe gestellt werden, um die möglichen Antworten weiter zu ermitteln.

Grundsätzlich ist dies der Prozess:

1. Beginnen Sie mit einer vollständigen Liste der Objekte. Diese können alle mit gleicher Wahrscheinlichkeit beginnen oder nach der Wahrscheinlichkeit sortiert werden, mit der das Objekt beim Testen ausgewählt wurde.
2. Beginnen Sie mit der ersten Frage im Entscheidungsbaum. Schieben Sie es in die Fragenwarteschlange.
3. Stellen Sie die Frage oben in der Warteschlange.
4. Prozessantwort:
   1. Ja / Nein-Antworten entfernen / addieren eine vorgegebene Wahrscheinlichkeitsmenge aus jeder Antwort basierend auf der Frage.
   2. Die Antwort "Vielleicht" entfernt / fügt einen Bruchteil der vorgegebenen Menge eines "Ja" hinzu.
   3. "Unbekannt" ändert die Wahrscheinlichkeiten nicht
5. Eine "Unbekannte" oder "Vielleicht" Antwort schiebt beide Fragen des nächsten Knotens in die Fragenwarteschlange. Eine "Ja" - oder "Nein" -Antwort fügt nur den einen entsprechenden Ja / Nein-Knoten in die Fragenwarteschlange ein.
6. Fahren Sie mit Schritt 3 fort, bis keine Fragen mehr vorliegen oder die Wahrscheinlichkeit einer einzelnen Antwort einen vordefinierten "Sicherheitsschwellenwert" überschreitet.
7. Geben Sie die wahrscheinlichste Antwort.

Das Generieren des Baums ist wahrscheinlich das Thema einer anderen Frage. Aber im Grunde geht es darum, Fragen zu wählen, die die Antworten so weit wie möglich aufteilen. Platzieren Sie die Fragen, die die Fragen am gleichmäßigsten aufteilen, am Anfang, damit die meisten Fragen am schnellsten geklärt werden können.

Die einfache Antwort lautet, dass das Handheld-Spiel 20Q aus der künstlichen Intelligenz von http://20Q.net erstellt wurde . Auf 20Q.net können Sie verschiedene Versionen des Spiels Twenty Questions spielen, ähnlich dem Spielzeug, außer dass das Spiel von jedem gespielten Spiel lernt. Das Handspielzeug verwendet dieselben neuronalen Netzwerkalgorithmen. Das neuronale Netzwerk wählt die zu stellenden Fragen aus und macht Vermutungen. Dieser Ansatz bedeutet, dass die KI häufig richtig errät, auch wenn Sie eine andere Frage beantworten als die, die der KI beigebracht wurde. Ein weiterer Vorteil ist, dass das Spiel bei jedem Spiel andere Fragen stellt, auch wenn Sie an dasselbe denken.

Die Algorithmen und das neuronale Netz des klassischen englischen Spiels (Animal, Vegetable, Mineral) wurden 1988 von Robin Burgener entwickelt. . . mir.

Danke für die Frage.

Ich habe "20q code" gegoogelt und Folgendes gefunden: http://mosaic.cnfolio.com/B142LCW2008A197

Diese Version ist nur für Tiere, aber die eigentlichen 20 Fragen haben wahrscheinlich einen ähnlichen Algorithmus.

Hier ist ein kurzer Überblick über den Code, den ich verlinkt habe:
Es gibt verschiedene Antworten, die im Programm fest programmiert sind. Ihnen werden dann mehrere TRUE- oder FALSE-Attribute zugewiesen:

#define ANIMALS_LIST      "daddylonglegs bee penguin eagle giraffe octopus tiger elephant jellyfish bull \nparrot dolphin python crocodile cat leopard monkey zebra sheep rat \nowl spider frog polarbear snail tortoise rabbit salmon rhino fox"
#define MAMMALS                    "0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1"
#define FLYING_ANIMALS             "1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
#define WATER_ANIMALS              "0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0"
#define BEAK                       "0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0"
...

Wie Sie sehen, ist eine Biene kein Säugetier, sondern fliegt usw.

Für jede Gruppe gibt es ein Array:

int   mammals[ TOTAL_ANIMALS ] = { 0 };
int   flying_animals[ TOTAL_ANIMALS ] = { 0 };
int   water_animals[ TOTAL_ANIMALS ] = { 0 };
...

Wenn jede Frage gestellt wird:

  askUserQuestion( guesses, "\nQuestion %d: Is your animal a mammal? \n", mammals );

Das Programm überprüft die Definition der entsprechenden Kategorie und ermittelt anhand der WAHR- oder FALSCH-Werte und der von Ihnen eingegebenen Ja- oder Nein-Antwort auf die Frage, welches Tier am wahrscheinlichsten dasjenige ist, an das Sie denken.

Dies geschieht in:

void askUserQuestion( int guessNumber, char* question, int* animalData );

Es ist kein massiver Entscheidungsbaum oder eine Reihe von hartcodierten if / else-Anweisungen. Der Erfinder Robin Burgener hat seinen Algorithmus in seiner Patentanmeldung von 2005 vollständig dokumentiert . Es ist genial einfach.