Jak zaimplementować algorytm “ 20 pytań ”?

Nie wiem, jak to zrobiono w 20Q, ale jest mnóstwo informacji na temat implementacji gry 20 pytań .

Jest wiele sposobów rozwiązania tego problemu, ale opiszę tylko jeden . Te gry mogą implementować pewnego rodzaju drzewo decyzyjne . W przypadku gry elektronicznej, takiej jak 20Q, drzewo to byłoby wstępnie obliczone i dość łatwe do przejścia. Istnieją metody używania drzew decyzyjnych uczenia się , w których gra może akceptować nowe obiekty na końcu swoich pytań, jeśli nie jest w stanie odgadnąć, kim jest użytkownik zadawanie pytań.

Kiedy pytania są serią odpowiedzi „tak” lub „nie”, otrzymujesz drzewo binarne. Każdy węzeł to pytanie, a liście to odpowiedzi. W przypadku odpowiedzi na pytania jako nieznane lub niepewne, węzły potomne można łączyć, a ich pytania zadawać szeregowo, aby uzyskać dalsze możliwe odpowiedzi.

Zasadniczo jest to proces:

1. Zacznij od pełnej listy obiektów. Mogą one zaczynać się od równie prawdopodobnego, albo można je sortować według prawdopodobieństwa wyboru obiektu podczas testowania.
2. Zacznij od pierwszego pytania w drzewie decyzyjnym. Przenieś go do kolejki pytań.
3. Zadaj pytanie na górze kolejki.
4. Odpowiedź procesu:
   1. Tak / Nie odpowiedzi usuwa / dodaje z góry określoną ilość prawdopodobieństwa z każdej odpowiedzi opartej na pytaniu.
   2. Odpowiedź „Może” usuwa / dodaje ułamek z góry określonej kwoty „tak”.
   3. „Nieznana” nie zmienia prawdopodobieństwa
5. Odpowiedź „Nieznane” lub „Może” wypycha oba kolejne pytania dotyczące węzłów do kolejki pytań. Odpowiedź „Tak” lub „Nie” po prostu dodaje jeden odpowiedni węzeł tak / nie do kolejki pytań.
6. Przejdź do kroku 3, dopóki brak pytań lub prawdopodobieństwo pojedynczej odpowiedzi nie przekroczy wstępnie zdefiniowanej „pewności” „próg.
7. Podaj najbardziej prawdopodobną odpowiedź.

Generowanie drzewa jest prawdopodobnie tematem innego pytania. Ale zasadniczo chodzi o wybieranie pytań, które dzielą odpowiedzi tak bardzo, jak to tylko możliwe. Pytania, które dzielą pytania, należy umieścić na początku, tak aby jak najwięcej pytań można było usunąć najszybciej.

Prosta odpowiedź jest taka, że przenośna gra 20Q została stworzona ze sztucznej inteligencji, która żyje w http://20Q.net . W 20Q.net możesz grać w różne wersje gry Dwudziestu pytań, podobnie jak w zabawce, z tym wyjątkiem, że gra uczy się z każdej rozegranej gry. te same algorytmy sieci neuronowej. Sieć neuronowa wybiera pytania, które należy zadać, a także dokonuje przypuszczeń. Takie podejście oznacza, że sztuczna inteligencja często odgadnie poprawnie, nawet jeśli odpowiesz na pytanie inaczej niż sztuczna inteligencja. Kolejną zaletą jest będzie zadawać pytania inaczej w każdej grze, nawet jeśli myślisz o tym samym.

Algorytmy a sieć neuronowa klasycznej angielskiej gry (Animal, Vegetable, Mineral) została stworzona w 1988 roku przez Robina Burgenera. . . ja.

Dziękuję za pytanie.

Komentarze

• Witaj Robin, witaj na stronie. Kto lepiej odpowie na to pytanie niż sam wynalazca. ' jest interesujące wiedzieć, jak skomplikowany jest w rzeczywistości 20Q. Dziękuję za wkład w tworzenie strony i więcej, za wkład w sztuczną inteligencję. Mamy nadzieję, że ' odwiedzisz tę witrynę od czasu do czasu i odpowiesz A.I. pytania :).
• hehe, uwielbiam, kiedy to się dzieje xD.

Wyszukałem w Google „kod 20q” i znalazłem to: http://mosaic.cnfolio.com/B142LCW2008A197

Ta wersja jest tylko dla zwierząt, ale rzeczywiste 20 pytań ma prawdopodobnie podobny algorytm.

Oto krótki przegląd kodu, który połączyłem:
Istnieje kilka różnych odpowiedzi zakodowanych na stałe w programie.Następnie przypisuje się im kilka atrybutów TRUE lub FALSE:

#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" ... 

Jak widać, pszczoła nie jest ssakiem, ale lata itd.

Dla każdej grupy istnieje tablica:

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

Gdy zadawane jest każde pytanie:

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

Program sprawdza definicję odpowiedniej kategorii i śledzi, które zwierzę jest najprawdopodobniej tym, o którym myślisz, na podstawie wartości PRAWDA lub FAŁSZ oraz wprowadzonej odpowiedzi Tak lub Nie na pytanie.

Odbywa się to w:

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

To jest nie jest ogromnym drzewem decyzyjnym ani zbiorem zakodowanych na stałe stwierdzeń if / else. Robin Burgener, wynalazca, całkowicie udokumentował swój algorytm w swoim zgłoszeniu patentowym w 2005 r. To „jest genialnie proste.

Komentarze

• Zamiast szturchać inne odpowiedzi, możesz podać krótki opis algorytmu zamiast tylkozamieszczając link do niego.
• gdybyś przegapił inne odpowiedzi, skomentował powyżej! może @ user22025 mógłby również podać tutaj krótkie wyjaśnienie: D