Jak mogę wdrożyć algorytm „20 pytań”?

Od dzieciństwa zastanawiałem się, jak działa gra elektroniczna 20Q . Myślisz o przedmiocie, rzeczy lub zwierzęciu (np. Ziemniak lub osioł ). Następnie urządzenie zadaje serię pytań, takich jak:

• Czy jest większy niż bochenek chleba?
• Czy znaleziono go na zewnątrz?
• Czy służy do rekreacji?

Na każde pytanie możesz odpowiedzieć tak , nie , może lub nieznane . Zawsze wyobrażałem sobie, że działa z ogromnymi, zagnieżdżonymi warunkami warunkowymi ( if-statements). Myślę jednak, że jest to mało prawdopodobne wyjaśnienie ze względu na złożoność dla programisty.

Jak mógłbym wdrożyć taki system?

Nie wiem, jak dokładnie zrobiło to 20Q, ale jest mnóstwo informacji na temat implementacji gry złożonej z 20 pytań .

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

Kiedy pytania są serią odpowiedzi tak lub nie, powstaje drzewo binarne. Każdy węzeł jest pytaniem, a liście są odpowiedziami. Gdy odpowiedzi na pytania są nieznane lub nie są pewne, węzły potomne można łączyć, a ich pytania zadawać szeregowo, aby dodatkowo wyeliminować możliwe odpowiedzi.

Zasadniczo jest to proces:

1. Zacznij od pełnej listy obiektów. Wszystkie mogą rozpocząć się z jednakowym prawdopodobieństwem lub można je posortować według prawdopodobieństwa, że ​​obiekt zostanie wybrany podczas testowania.
2. Zacznij od pierwszego pytania w drzewie decyzyjnym. Wciśnij w kolejkę pytań.
3. Zadaj pytanie na górze kolejki.
4. Odpowiedź procesu:
   1. Tak / Brak odpowiedzi usuwa / dodaje z góry określoną wartość prawdopodobieństwa dla każdej odpowiedzi na podstawie pytania.
   2. Odpowiedź „Być może” usuwa / dodaje ułamek z góry określonej liczby „tak”.
   3. „Unknow” nie zmienia prawdopodobieństw
5. Odpowiedź „Nieznany” lub „Być może” wypycha pytania z kolejnych węzłów do kolejki pytań. Odpowiedź „Tak” lub „Nie” dodaje tylko jeden odpowiedni węzeł tak / nie do kolejki pytań.
6. Przejdź do kroku 3, aż liczba pytań lub prawdopodobieństwa pojedynczej odpowiedzi nie przekroczy ustalonego progu „pewności”.
7. Podaj najbardziej prawdopodobną odpowiedź.

Generowanie drzewa jest prawdopodobnie tematem innego pytania. Ale w zasadzie to wybór pytań, które dzielą odpowiedzi tak bardzo, jak to możliwe. Umieść pytania, które dzielą pytania w jednakowy sposób na początku, aby jak najwięcej pytań można było szybko usunąć.

Prosta odpowiedź jest taka, że ​​przenośna gra 20Q została stworzona ze sztucznej inteligencji, która żyje pod adresem http://20Q.net . Na 20Q.net możesz grać w różne wersje gry Dwadzieścia pytań, podobne do zabawki, z tą różnicą, że gra uczy się z każdej gry. Przenośna zabawka wykorzystuje te same algorytmy sieci neuronowej. Sieć neuronowa wybiera pytania i zgaduje. Takie podejście oznacza, że ​​AI często poprawnie zgaduje, nawet jeśli odpowiesz na pytanie inaczej niż to, czego nauczyłem AI. Kolejną zaletą jest to, że gra będzie zadawać pytania inaczej w każdej grze, nawet jeśli myślisz o tym samym.

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

Dzięki, że pytasz.

Poszukałem „kodu 20q” i znalazłem to: http://mosaic.cnfolio.com/B142LCW2008A197

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

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

#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, itp.

Dla każdej grupy istnieje tablica:

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

Kiedy zadawane jest każde pytanie:

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

Program analizuje 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 nie jest ogromne drzewo decyzyjne ani wiązka zakodowanych instrukcji if / else. Robin Burgener, wynalazca, całkowicie udokumentował swój algorytm w swoim zgłoszeniu patentowym z 2005 roku. To genialnie proste.