Algoritma apa yang ada di belakang akinator atau 20q?

12

Judul berbicara sendiri. Berikut adalah Akinator dan 20Q .

Prinsip dari permainan ini adalah untuk menanyakan kepada pengguna sejumlah pertanyaan yang berkaitan dengan beberapa entitas yang dipilih oleh pengguna. Dan kemudian cari tahu apa entitas ini. Inti dari algoritma ini adalah untuk menemukan "pertanyaan paling berguna" di setiap putaran, saat berhadapan dengan pengguna yang mungkin tidak menjawab semua pertanyaan dengan benar.

"pertanyaan paling berguna" didefinisikan sebagai pertanyaan yang memberikan informasi terbanyak, dalam kasus optimal yang membagi audiens (atau jumlah?) entitas kandidat menjadi dua bagian yang sama.

Saya menemukan makalah yang menggambarkan beberapa algoritma (kata "algoritma" tidak digunakan, tetapi buktinya dapat diubah menjadi algoritma). Sayangnya saya tidak dapat menemukan makalah ini lagi :(. Makalah ini menjelaskan masalah dengan konsep teori permainan, dengan beberapa tingkat kebohongan diizinkan kepada pengguna (ini membahas 3 tingkat kebohongan). Silakan posting jika Anda pikir Anda tahu makalahnya.

ds.algorithms BenoitParis
sumber
1
stats.stackexchange.com/questions/6074/... Ini adalah diskusi tentang stats.SE
Tomek Tarczynski

Jawaban:

14

Saya pikir Anda mungkin mencari "Memainkan" Dua Puluh Pertanyaan "dengan pembohong", Dhagat, Gacs, dan Winkler, SODA 1992, http://portal.acm.org/citation.cfm?id=139404.139409

The banyak makalah lain yang mengutip satu ini mungkin termasuk tambahan hit yang relevan.

David Eppstein
sumber
Adakah yang punya sumber untuk tautan ke-2? Itu tidak tersedia lagi.
Ryan
Tautan kedua diperoleh dengan pergi ke Google sarjana, menemukan makalah pertama, dan kemudian mengklik tautan "dikutip oleh NN" yang ditampilkan untuk hasilnya (di mana NN adalah jumlah makalah yang mengutip yang satu ini). Agaknya prosedur itu masih berfungsi, meskipun Google telah mengubah format URL-nya.
David Eppstein