Wie kann ich einen “ 20 Fragen ” -Algorithmus implementieren?

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

Es gibt viele Möglichkeiten, dies zu lösen, aber ich werde einen Weg beschreiben . Diese Spiele können eine Art Entscheidungsbaum implementieren. Für ein elektronisches Spiel wie 20Q wäre dieser Baum vorberechnet und ziemlich leicht zu durchqueren. Es gibt Methoden zur Verwendung von Lernentscheidungsbäumen , bei denen das Spiel am Ende seiner Fragen neue Objekte akzeptieren kann, wenn es nicht erraten kann, was der Benutzer ist Fragen.

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 auszusortieren.

Grundsätzlich ist dies der Prozess:

1. Beginnen Sie mit einer vollständigen Liste der Objekte. Diese können alle gleich wahrscheinlich 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 / fügen eine vorgegebene Menge von hinzu Wahrscheinlichkeit aus jeder Antwort basierend auf der Frage.
   2. Die Antwort „Vielleicht“ entfernt / fügt einen Bruchteil des vorgegebenen Betrags eines „Ja“ hinzu.
   3. „Unbekannt“ ändert die Wahrscheinlichkeiten nicht
5. Eine Antwort „Unbekannt“ oder „Vielleicht“ verschiebt die Fragen der beiden nächsten Knoten in die Fragenwarteschlange. Bei einer Antwort mit „Ja“ oder „Nein“ wird lediglich der jeweilige Ja / Nein-Knoten zur Fragenwarteschlange hinzugefügt.
6. Fahren Sie mit Schritt 3 fort, bis keine Fragen mehr vorliegen oder die Wahrscheinlichkeit einer einzelnen Antwort über einer vordefinierten „Gewissheit liegt „Schwelle.
7. Geben Sie die wahrscheinlichste Antwort.

Das Generieren des Baums ist wahrscheinlich das Thema einer anderen Frage. Aber im Grunde ist es die Auswahl von Fragen, die die Antworten so weit wie möglich aufteilen. Stellen Sie die Fragen, die die Fragen am gleichmäßigsten aufteilen, am Anfang so, dass die meisten Fragen am schnellsten geklärt werden können.

Die einfache Antwort lautet, dass das Handheld-Spiel 20Q aus der künstlichen Intelligenz erstellt wurde, die unter http://20Q.net Bei 20Q.net können Sie verschiedene Versionen des Spiels der zwanzig Fragen spielen, ähnlich dem Spielzeug, außer dass das Spiel aus jedem gespielten Spiel lernt. Das Handheld-Spielzeug verwendet das Gleiche neuronale Netzwerkalgorithmen. Das neuronale Netzwerk wählt die zu stellenden Fragen aus und macht Vermutungen. Dieser Ansatz bedeutet, dass die KI oft richtig rät, selbst wenn Sie eine Frage anders beantworten als die KI gelehrt wurde. Ein weiterer Vorteil ist, dass das Spiel stellt in jedem Spiel andere Fragen, auch wenn Sie an dasselbe denken.

Die Algorithmen und das neuronale Netzwerk des klassischen englischen Spiels (Animal, Vegetable, Mineral) wurde 1988 von Robin Burgener erstellt. . . Ich.

Danke, dass Sie gefragt haben.

Kommentare

• Hallo Robin, willkommen auf der Website. Wer könnte diese Frage besser beantworten als der Erfinder selbst? ‚ ist interessant zu wissen, wie komplex der 20Q tatsächlich ist. Vielen Dank für Ihren Beitrag zur Website und vor allem für Ihren Beitrag zur künstlichen Intelligenz. Hoffentlich besuchen Sie ‚ gelegentlich die Website und antworten A.I. Fragen :).
• hehe, liebe es, wenn dies passiert xD.

Ich habe „20q-Code“ gegoogelt und Folgendes gefunden: http://mosaic.cnfolio.com/B142LCW2008A197

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

Hier ist eine kurze Übersicht über den Code, den ich verlinkt habe:
Es gibt verschiedene Antworten, die fest im Programm codiert 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 können, 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 untersucht die Definition der entsprechenden Kategorie und verfolgt anhand der TRUE- oder FALSE-Werte und Ihrer eingegebenen Ja- oder Nein-Antwort auf die Frage, welches Tier höchstwahrscheinlich 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 fest codierter if / else-Aussagen. Robin Burgener, der Erfinder, hat seinen Algorithmus in seiner Patentanmeldung von 2005 vollständig dokumentiert „s genial einfach.

Kommentare

• Anstatt auf die anderen Antworten zu stöbern, möchten Sie möglicherweise eine kurze Beschreibung des Algorithmus geben, anstatt nureinen Link dazu posten.
• falls du die anderen Antworten verpasst hast, hat er oben einen Kommentar abgegeben! Vielleicht könnte @ user22025 hier auch eine kurze Erklärung geben: D