Bagaimana saya bisa menerapkan algoritma "20 Pertanyaan"?

Sejak kecil, saya bertanya-tanya bagaimana permainan elektronik 20Q bekerja. Anda memikirkan suatu benda, benda, atau binatang (misalnya kentang atau keledai ). Perangkat kemudian menanyakan serangkaian pertanyaan seperti:

• Apakah lebih besar dari sepotong roti?
• Apakah itu ditemukan di luar ruangan?
• Apakah ini digunakan untuk rekreasi?

Untuk setiap pertanyaan, Anda dapat menjawab ya , tidak , mungkin , atau tidak dikenal . Saya selalu membayangkan itu bekerja dengan kondisional ( if-pernyataan) besar, bersarang . Namun, saya pikir itu penjelasan yang tidak mungkin karena kerumitannya untuk programmer.

Bagaimana saya menerapkan sistem seperti itu?

Saya tidak tahu bagaimana 20Q melakukannya secara khusus, tetapi ada banyak informasi tentang cara menerapkan permainan 20 pertanyaan .

Ada banyak cara untuk menyelesaikan ini, tetapi saya akan menjelaskan satu cara. Game-game ini dapat menerapkan semacam pohon keputusan . Untuk permainan elektronik seperti 20Q, pohon ini akan dikomputasi dan cukup mudah untuk dilintasi. Ada metode untuk menggunakan pohon keputusan pembelajaran di mana permainan dapat menerima objek baru di akhir pertanyaan itu jika tidak dapat menebak apa yang ditanyakan pengguna.

Ketika pertanyaan adalah serangkaian jawaban ya atau tidak, Anda berakhir dengan pohon biner. Setiap node adalah pertanyaan dan daunnya adalah jawaban. Ketika pertanyaan dijawab dengan tidak diketahui atau tidak yakin, simpul anak dapat digabungkan dan pertanyaan mereka diajukan secara seri untuk lebih lanjut memilih jawaban yang mungkin.

Pada dasarnya ini adalah proses:

1. Mulai dengan daftar objek yang lengkap. Ini semua dapat dimulai pada kemungkinan yang sama, atau mereka dapat diurutkan berdasarkan seberapa besar kemungkinan objek akan dipilih dalam pengujian.
2. Mulailah dengan pertanyaan pertama di pohon keputusan. Dorong ke antrian pertanyaan.
3. Ajukan pertanyaan di atas antrian.
4. Tanggapan proses:
   1. Ya / Tidak jawaban menghapus / menambah jumlah probabilitas yang telah ditentukan dari setiap jawaban berdasarkan pertanyaan.
   2. Jawaban "Mungkin" menghapus / menambahkan sebagian kecil dari jumlah "ya" yang telah ditentukan.
   3. "Tidak Tahu" tidak mengubah probabilitas
5. Respons "Tidak Diketahui" atau "Mungkin" mendorong kedua node pertanyaan berikutnya ke antrian pertanyaan. Respons "Ya" atau "Tidak" hanya menambahkan simpul masing-masing ya / tidak ke antrian pertanyaan.
6. Lanjutkan ke langkah 3 hingga keluar dari pertanyaan atau probabilitas satu jawaban di luar ambang batas "kepastian" yang telah ditentukan.
7. Berikan jawaban yang paling memungkinkan.

Menghasilkan pohon mungkin merupakan topik dari pertanyaan lain. Tetapi pada dasarnya itu memilih pertanyaan yang membagi jawaban sebanyak mungkin. Letakkan pertanyaan-pertanyaan yang membagi pertanyaan-pertanyaan dengan paling dekat di awal sehingga jumlah pertanyaan terbanyak dapat diambil dengan tercepat.

Jawaban sederhananya adalah bahwa game genggam 20Q diciptakan dari kecerdasan buatan yang hidup di http://20Q.net . Di 20Q.net Anda dapat memainkan versi berbeda dari game Twenty Question, mirip dengan mainannya kecuali bahwa game itu dipelajari dari setiap game yang dimainkan. Mainan genggam menggunakan algoritma jaringan saraf yang sama. Jaringan saraf mengambil pertanyaan untuk diajukan serta membuat tebakan. Pendekatan ini berarti bahwa AI akan sering menebak dengan benar bahkan jika Anda menjawab pertanyaan secara berbeda dari apa yang telah diajarkan AI. Keuntungan lain adalah bahwa gim akan mengajukan pertanyaan secara berbeda pada setiap gim bahkan jika Anda memikirkan hal yang sama.

Algoritma dan jaringan saraf dari permainan bahasa Inggris klasik (Animal, Vegetable, Mineral) diciptakan pada tahun 1988 oleh Robin Burgener. . . saya.

Terima kasih untuk bertanya.

Saya googled "kode 20q" dan menemukan ini: http://mosaic.cnfolio.com/B142LCW2008A197

Versi ini hanya untuk hewan tetapi 20 Pertanyaan yang sebenarnya mungkin memiliki algoritme yang sama.

Berikut ini adalah ikhtisar singkat dari kode yang saya tautkan:
Ada beberapa jawaban berbeda yang dikodekan dengan keras ke dalam program. Beberapa atribut TRUE atau FALSE kemudian ditugaskan kepadanya:

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

Seperti yang Anda lihat, lebah bukan mamalia tetapi ia terbang, dll.

Ada larik untuk setiap grup:

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

Ketika setiap pertanyaan diajukan:

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

Program ini melihat definisi dari kategori yang sesuai dan melacak hewan mana yang paling mungkin Anda pikirkan berdasarkan nilai-nilai BENAR atau SALAH dan Anda menjawab ya atau Tidak yang dimasukkan untuk pertanyaan.

Ini dilakukan di:

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

Ini bukan pohon keputusan besar-besaran atau sekelompok pernyataan if / else yang dikodekan dengan keras. Robin Burgener, sang penemu, sepenuhnya mendokumentasikan algoritmanya dalam pengajuan paten 2005. Sederhana sekali.