Como posso implementar um algoritmo de “ 20 perguntas ”?

Não sei como o 20Q fez isso especificamente, mas há muitas informações sobre como implementar um jogo de 20 questões .

Existem muitas maneiras de resolver isso, mas vou descrever uma maneira . Esses jogos podem implementar algum tipo de árvore de decisão . Para um jogo eletrônico como o 20Q, essa árvore seria pré-computada e bastante fácil de atravessar. Existem métodos para usar árvores de decisão de aprendizagem onde o jogo pode aceitar novos objetos no final de suas perguntas se não for capaz de adivinhar o que o usuário é perguntando.

Quando as perguntas são uma série de respostas sim ou não, você acaba com uma árvore binária. Cada nó é uma pergunta e as folhas são respostas. Quando as perguntas são respondidas com desconhecido ou incerto, os nós filhos podem ser combinados e suas perguntas feitas em série para selecionar ainda mais as respostas possíveis.

Basicamente, este é o processo:

1. Comece com uma lista completa dos objetos. Todos eles podem começar com a mesma probabilidade, ou podem ser classificados pela probabilidade de o objeto ter sido escolhido no teste.
2. Comece com a primeira pergunta na árvore de decisão. Coloque-a na fila de perguntas.
3. Faça a pergunta no topo da fila.
4. Resposta do processo:
   1. Respostas Sim / Não remove / adiciona uma quantidade predeterminada de probabilidade de cada resposta com base na pergunta.
   2. A resposta “Talvez” remove / adiciona uma fração da quantidade predeterminada de um “sim”.
   3. “Desconhecido” não altera as probabilidades
5. Uma resposta “Desconhecida” ou “Talvez” empurra as duas perguntas dos próximos nós para a fila de perguntas. Uma resposta “Sim” ou “Não” apenas adiciona o respectivo nó sim / não à fila de perguntas.
6. Vá para a etapa 3 até que as perguntas ou a probabilidade de uma única resposta esteja além de uma “certeza” predefinida ” limite.
7. Forneça a resposta mais provável.

Gerar a árvore é provavelmente o tópico de outra pergunta. Mas basicamente é escolher as perguntas que dividem as respostas o máximo possível. Coloque as perguntas que as dividem de forma mais uniforme perto do início, para que o maior número de perguntas possa ser eliminado o mais rápido.

A resposta simples é que o jogo portátil 20Q foi criado a partir da inteligência artificial que vive em http://20Q.net . No 20Q.net você pode jogar diferentes versões do jogo das Vinte Perguntas, semelhantes ao brinquedo, exceto que o jogo aprende com cada jogo jogado. O brinquedo portátil usa o mesmos algoritmos de rede neural. A rede neural escolhe as perguntas a serem feitas e também adivinha. Essa abordagem significa que a IA geralmente adivinha corretamente, mesmo que você responda a uma pergunta de maneira diferente da que a IA foi ensinada. Outra vantagem é que o jogo fará perguntas de maneira diferente a cada jogo, mesmo que você esteja pensando na mesma coisa.

Os algoritmos e a rede neural do clássico jogo inglês (Animal, Vegetable, Mineral) foi criada em 1988 por Robin Burgener. . . eu.

Obrigado por perguntar.

Comentários

• Olá Robin, bem-vindo ao site. Quem melhor para responder a esta pergunta do que o próprio inventor. É ‘ interessante saber o quão complexo o 20Q realmente é. Obrigado por sua contribuição para o site e mais ainda por sua contribuição para a inteligência artificial. Esperamos que você ‘ visite o site ocasionalmente e responda ao I.A. perguntas :).
• hehe, adoro quando isso acontece xD.

Pesquisei “código 20q” no Google e encontrei este: http://mosaic.cnfolio.com/B142LCW2008A197

Esta versão é apenas para animais, mas as 20 questões reais provavelmente têm um algoritmo semelhante.

Aqui está uma rápida visão geral do código vinculado:
Existem várias respostas diferentes embutidas no programa.Vários atributos TRUE ou FALSE são atribuídos a eles:

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

Como você pode ver, uma abelha não é um mamífero, mas voa, etc.

Há uma matriz para cada grupo:

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

Quando cada pergunta é feita:

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

O programa analisa a definição da categoria apropriada e rastreia qual animal é mais provavelmente aquele em que você está pensando, com base nos valores VERDADEIRO ou FALSO e sua resposta Sim ou Não à pergunta.

Isso é feito em:

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

É “s não uma enorme árvore de decisão ou um monte de declarações if / else codificadas. Robin Burgener, o inventor, documentou completamente seu algoritmo em seu pedido de patente de 2005. “é engenhosamente simples.

Comentários

• Em vez de cutucar as outras respostas, você pode dar uma breve descrição do algoritmo em vez de apenaspostando um link para ele.
• caso você tenha perdido as outras respostas, ele comentou acima! talvez @ user22025 também possa dar uma breve explicação aqui: D