Название говорит само за себя. Вот Акинатор и 20Q .
Принцип этих игр состоит в том, чтобы задавать пользователю ряд вопросов, касающихся некоторой сущности, выбранной пользователем. А потом выясните, что это за сущность. Суть алгоритма состоит в том, чтобы находить «самый полезный вопрос» в каждом раунде, имея дело с пользователем, который может не отвечать на все вопросы правильно.
«Самый полезный вопрос» определяется как вопрос, который дает больше информации, в оптимальном случае, разделяя аудиторию (или количество?) кандидатов на две равные половины.
Я нашел статью, в которой описаны некоторые алгоритмы (хорошо, слово «алгоритм» не использовалось, но доказательства можно превратить в алгоритмы). К сожалению, я не могу найти этот документ снова :(. В документе описана проблема с концепциями теории игр, с некоторыми уровнями лжи, разрешенными для пользователя (обсуждались 3 уровня лжи). Пожалуйста, напишите, если вы думаете, что знаете статью.
источник
Ответы:
Я думаю, что вы, вероятно, ищете «Об игре в« Двадцать вопросов »с лжецом», Дагат, Гакс и Винклер, SODA 1992, http://portal.acm.org/citation.cfm?id=139404.139409
На многих других документах , которые цитируют эту , вероятно , включать дополнительные соответствующие хиты.
источник