Кто такой Акинатор? Это древний джинн, каким-то чудом оказавшийся на воле после многих тысяч лет, проведенных в лампе. Конечно, за это время привычный ему мир порядком изменился. Но Акинатор не стал удивляться, а быстренько научился пользоваться интернетом, скачал оттуда информацию обо всем на свете и даже создал для себя специальное приложение, в котором мог бы похвастаться своими знаниями. Всем, кто заходит на его сайт, Акинатор предлагает сыграть в свою любимую игру.
Для этого тебе необходимо загадать любого персонажа – например, Кота Леопольда, певицу Уитни Хьюстон, актера Тома Круза – которого джинну надо будет угадать, задавая тебе уточняющие вопросы. Например, существует ли твой персонаж на самом деле, жив ли он еще или умер, мужчина это или женщина. Некоторые вопросы могут показаться весьма странными. Например, носит ли твой персонаж обувь или есть ли у него мобильный телефон. Но все это дает Акинатору необходимые крупицы информации, чтобы собрать из них цельный образ. Джинн располагает огромной базой имен, среди которых ему за ограниченное количество попыток нужно выбрать правильный вариант. И это у него получается далеко не всегда. Некоторых персонажей Акинатору приходится отгадывать с двух, а то и с трех раз. А кого-то он может попросту не знать. Но у тебя всегда есть возможность добавить неизвестное Акинатору имя в его список, тем самым сделав джинна еще умнее. В последней версии была добавлена опция загадывания не только людей, но и предметов. Так что теперь играть с Акинатором стало еще увлекательнее! Проверь, со скольки попыток джинн угадает такие простые вещи, как телевизор или подушка!
На Хабре уже несколько раз всплывала тема Акинатора, в том числе и с тегом не знаю как оно работает. Я на него наткнулся недавно и, разумеется, был восхищен. Затем, как вероятно и многим другим, мне в голову пришла мысль: «А как же это работает?» Ответа на этот вопрос я нигде не нашел, а потому задался целью написать аналогичную по функциональности программу, разобравшись по ходу дела что к чему.
Содержание
Функциональные требования
Первым делом стоит разобраться, что в действительности означают слова «аналогичная по функциональности программа». Подумав немного, я выделил следующие требования:
- Программа должна обучаться. Совершенно очевидно, что нельзя научить программу распознавать несколько сотен тысяч персонажей путем ручного ввода ответов на вопросы для каждого из них. Вернее, теоретически это возможно, но мы будем искать более красивые решения. Очевидная альтернатива этому подходу — учиться на ходу, пользуясь ответами пользователей. Это наша программа должна уметь.
- Программа должна прощать ошибки. Очевидно, мнение пользователей по поводу ответов на некоторые вопросы может значительно разниться. Простой пример: отчаянный гомофоб и простой человек загадывают Брэда Питта. На вопрос «Ваш персонаж сексуален?» первый, вероятно, ответит отрицательно, в то время как большинство людей — иначе. Однако это небольшое расхождение никак не должно помешать нашей программе выяснить истину.
- Программа должна с умом выбирать вопросы. Есть много стратегий, определяющих вопросы, которые нужно задавать. Например, можно задать вообще все вопросы (вот только их довольно много). Можно задавать случайные вопросы, но и тогда, скорее всего, к ответу придется идти очень долго. А можно стараться выбирать очередной вопрос так, чтобы узнать при ответе на него как можно больше информации. Именно это мы и будем пытаться делать.
Алгоритмы
Если бы не прощение ошибок, добиться желаемого можно было бы довольно просто. Например, можно было бы хранить дерево ответов на вопросы, в котором внутренние вершины соответствовали бы вопросам, а листы — ответам. Процесс игры тогда выглядел бы как спуск от корня к одному из листов. Тем не менее, с прощением ошибок этот алгоритм справляться не будет. Да и вопросы балансировки дерева возникают.
В каком-то смысле дерево — это очень «механистический», «машинный» способ игры, крайне неустойчивый к малейшим неточностям. Нам же нужно играть так, как стал бы играть рациональный человек. Тем, кто более-менее знаком с теорией вероятности, должно быть известно, что у нее существует так называемая Байесовская интерпретация, а также основанный на ней Байесовский подход. В основе этого подхода лежит описание знаний с помощью распределений случайных величин с последующим преобразованием априорных знаний в апостериорные на основе наблюдений при помощи знаменитой формулы Байеса. Более того, такой подход является единственным обобщением классической алгебры логики на случай неопределенности (об этом можно прочитать, например, ). Это наводит многих ученых на мысль, что Байесовский подход является эталоном рационального мышления. Что же, нам только этого и нужно. Попробуем применить его к нашей задаче.
Байесовская модель
Итак, вспоминаем формулу Байеса: P(A|B) = P(B|A)P(A)/P(B). А теперь словами. Пусть нам нужно оценить вероятность того, что произошло событие A, при условии, что событие B точно произошло (то есть мы его гарантированно пронаблюдали; именно поэтому B часто называют наблюдением). По формуле Байеса эта вероятность пропорциональна произведению двух других. Первая из них, P(B|A), называется правдоподобием и показывает, с какой вероятностью событие B происходит при условии, что произошло A. Второй множитель, P(A), — это так называемая априорная вероятность события A, то есть вероятность, что оно в принципе произойдет (вне зависимости от B). По сути, эта вероятность отражает информацию, которую мы знали об A до того, как узнали о том, что произошло B. В знаменателе формулы также присутствует величина P(B), которая в данном случае просто играет роль нормировочного коэффициента и может быть проигнорирована.
Использовать эту формулу в контексте игры в вопросы довольно легко. Давайте считать, что Ai — это событие вида «вы загадали объект i», где i может быть как Споком, так и Девой Марией. Поскольку B — это наблюдение относительно Ai, то естественно было бы считать, что B состоит из ответов на вопросы. Единственный вариант, который я тут вижу, — это представить B в виде совместного события «На вопрос Q1 был дан ответ A1, …, на вопрос Qk был дан ответ Ak». Тогда P(Ai|B) будет для объекта i показывать вероятность того, что был загадан именно он (с учетом того, что пользователь дал ответы на k вопросов). Это именно та величина, которая нас интересует. Выбрав объект с максимальным значением P(Ai|B), можно, если значение P(Ai|B) достаточно велико, попробовать использовать его в качестве догадки.
Априорную вероятность P(Ai) можно рассматривать как частный случай P(Ai|B) при k=0. Иначе говоря, это вероятность, что игрок загадал объект i при условии, что вопросов задано не было, и мы вообще ничего не знаем. С одной стороны, можно было бы дать всем объектам равные P(Ai), т.к. это честно. С другой стороны, Барака Обаму наверняка будут загадывать намного чаще, чем Холдена Колфилда. Поэтому при прочих равных (то есть когда мы не можем различить объекты), следует выбирать именно Обаму. Следовательно, естественной оценкой P(Ai) будет отношение числа игр, когда был загадан X, к общему их числу.
Правдоподобие P(B|Ai) тоже получает удобную интерпретацию. Только прежде нужно воспользоваться одним небольшим трюком — предположить условную независимость ответов на вопросы при условии Ai (несколько грубое, но очень удобное для нас упрощение). В переводе на русский это значит, что по предположению вероятность P(B|Ai) может быть записана в виде произведения (по j) вероятностей P(Bj|Ai), где Bj — событие вида «На вопрос Qj был дан ответ Aj». P(Bj|Ai) в этом случае будет отношением числа раз, когда при загаданном объекте i на вопрос Qj был дан ответ Aj к числу раз, когда при загаданном объекте i в принципе был задан вопрос Qj. В целях избежания нулевых и неопределенных вероятностей предлагаю дополнительно считать, что изначально на каждый из вопросов каждый из вариантов ответов был дан по разу. То есть в случае, если вопрос Qj еще ни разу не задавался об объекте i, P(Bj|Ai) будет равно 1/Nj, где Nj — число вариантов ответа на вопрос Qj (я, к слову, использовал для всех вопросов одни и те же 4 варианта ответа: «да», «нет», «не знаю» и «вопрос не имеет смысла»).
Подведем промежуточный итог. Мы нашли простую формулу, которая отображает набор пар вопрос/ответ и некоторую сущность в вероятность, что при данных ответах на вопросы была загадана именно эта сущность. Пересчитав эту вероятность для всех объектов в нашей базе данных после ответа на новый вопрос можно видеть, какие из них больше похожи на загаданный объект на настоящий момент. Более того, обучение нашей модели реализуется довольно просто: нужно просто для каждой сущности в базе хранить информацию о том, какие вопросы про нее задавались и сколько ответов каждого из типов дали пользователи. После каждой игры эту информацию можно обновлять, основываясь на ответах пользователя. Также, для учета «популярности» персоны в базе нужно хранить число раз, которое персона была загадана.
Выбор вопросов, информация и энтропия
Ну что же, осталось только понять, какие вопросы лучше задавать. Естественно, задавать нужно те вопросы, которые дают больше информации. Но разве мы можем как-то эту информацию измерить? Оказывается, что да. Для этого можно воспользоваться понятием информационной энтропии. Если говорить грубо, но понятно, то информационная энтропия — это такая характеристика распределения случайной величины (измеряемая, как и информация, в битах), которая показывает, насколько мы не уверены в том, какое значение эта случайная величина примет. Например, если случайная величина принимает значение 1 с вероятностью 0.99, и значение 0 — с вероятностью 0.01, то энтропия такого распределения будет очень близка к нулю. Если же случайная величина принимает, к примеру, значения 0 и 1 с равными вероятностями 0.5 (орел или решка), то энтропия такой случайной величины будет равна 1 биту (это как раз то количество информации, которое мы должны получить, чтобы устранить неопределенность).
Ладно, давайте выбирать каждый раз тот вопрос, ответ на который сильнее всего уменьшит энтропию распределения P(Ai|B), которое как раз и отвечает за наши знания о том, кого загадал игрок. Тут сразу возникает еще одна проблема: вообще говоря, разные ответы на один и тот же вопрос могут уменьшать энтропию по разному. Что же делать? Предлагается находить тот вопрос, для которого ожидаемое уменьшение энтропии будет максимальным. Ожидаемое уменьшение энтропии показывает, насколько «в среднем» уменьшится энтропия, если мы зададим некоторый вопрос. Чтобы не писать здесь еще несколько абзацев текста, приведу формулу, по которой эту величину можно посчитать. Желающие без труда поймут, почему она имеет такой вид. Итак, нужно каждый раз задавать такой вопрос j, для которого величина HP(<Qj,Yes>) +… + HP(<Qj,No>) минимальна. Через H тут обозначена энтропия распределения вероятности P, а через «<Qj,Ans>» — событие «на вопрос Qj дан ответ Ans». Величину P(<Qj,Ans>) можно легко найти по формуле полной вероятности, просуммировав ее, обусловленную по всем известным объектам. То есть P(<Qj,Ans>) = sum(i) P(<Qj,Ans>|Ai) P(Ai|B).
Оказывается, что такой подход позволяет очень быстро отбрасывать нерелевантные вопросы, сосредотачиваясь на самом главном. В каком-то смысле этот метод является обобщением метода «деления пополам» в вероятностной постановке. Посмотреть, как все это работает вместе, можно на видео ниже.
Итог
Надеюсь, информация из этой небольшой статьи показалась кому-нибудь из вас интересной. На самом деле, прежде всего эта статья должна обратить ваше внимание на мощь (пусть и простейшей) математики в решении плохо формализуемых задач. Использование Байесовского подхода к теории вероятности и теории информации в ваших программах может сделать их более рациональными, но в то же время и более человечными 🙂
Павел Крижепольский
Facebook Twitter Вконтакте
Akinator — всемирно известный джинн, способный отгадать любого загаданного персонажа, задав вам всего несколько простых вопросов. Иногда возникает ощущение, что он просто читает мысли. Вы еще не знакомы? Тогда прошу под кат
Сразу отмечу, что приложение платное, стоит около 65 рублей. Формально, у него есть и бесплатная версия, но из-за сильно урезанных возможностей особого интереса она не представляет. Так же стоит учесть, что для работы приложению требуется доступ в интернет.
Кроме того, играть можно и на сайте программы — http://ru.akinator.com. Там же можно прочесть небольшой FAQ и больше узнать о разработчиках программы. Стоит отметить, что игра доступна на 12 (!) различных языках.
От Дарт Вейдера до королевы Англии
Вассерман всегда знает «Что», «Где» и «Когда»,
но только Акинатор всегда знает «Кто»
Интернет мем
Как вы уже наверное поняли, суть игры заключается в следующем — вы загадываете любого персонажа (как выдуманного, так и реально существующего), а дальше отвечаете на поставленные программой вопросы. Вариантов ответа всего пять: «Да», «Нет», «Не знаю», «Возможно \ Частично», «Скорее нет \ Не совсем». Максимальное кол-во вопросов, которое может задать вам джинн — 40 штук. Однако, в большинстве случаев, ответ у него готов намного раньше. Если Акинатор неверно угадал задуманного вами персонажа, то вы можете дать ему еще один шанс. В этом случае он задаст вам еще несколько уточняющих вопросов и попробует угадать со второй попытки.
Как видите, сама идея игры довольно проста и не слишком оригинальна. Тем не менее, Акинатор затягивает не меньше чем первые Angry Birds. Бывает, что открываешь приложение на пару минут, а когда смотришь на часы — прошло уже полчаса. Да и популярности приложению не занимать — у одной только бесплатной версии под Android на счету несколько миллионов загрузок. Причина такого успеха проста — Акинатор действительно способен отгадать практически любого персонажа. Это может быть кто угодно, от Владимира Путина и Майкла Джексона до Лары Крофт и ослика Иа-Иа. Певец, философ, телевизионный ведущий, персонаж книги или японской манги — Акинатору все равно.
Это может быть Сократ… |
… или Spider-Man … |
… или герой Союзмультфильма |
Знаете ли вы, что… С недавнего времени Акинатор может отгадывать предметы, понятия, животных (в общем, практически все, что не является персонажем). Для игры в этом режиме раньше нужно было зайти на сайт и выберать в меню «игра > объекты». Но в настоящее время, насколько я вижу, разделения на режимы больше нет.
Еще раз отмечу, что у бесплатной версии возможностей гораздо меньше — в ней доступны только самые известные персонажи. Во всех остальных случаях вы получите только садистское сообщение «Я знаю, кого вы загадали. Купите платную версию, тогда скажу». И это, на мой взгляд, полностью убивает весь смысл игры. И превращает уникальную разработку в демо-версию поисковика Google, способного обработать только десять простых поисковых запросов.
Так как у игрока есть возможность загадать совершенно кого угодно, то возможных вариантов ответа для Акинатора очень много. Вопросов, соответственно, не меньше. Первые вопросы обычно стандартные — «Ваш персонаж существует на самом деле?», «Ваш персонаж мужчина?» и пр. А вот следующие вопросы могут быть абсолютно любыми. Особенно, когда Акинатор начинает подозревать что знает ответ, и задает уточняющие вопросы.
«Любят ли слонопотамы поросят, а если любят — то как любят?» (с) Пяточек |
Ответ «Да» на прошлый вопрос означал вовсе не это ! |
Да целыми днями… то кровь пьет, то на нервах играет |
Если ваш ответ на вопрос приближает джина к разгадке, то он поднимается вверх. Если же ответ, наоборот, только смешал ему все карты, то он опускается вниз. На левой стороне экрана даже нарисована своеобразная шкала, по которой можно определить, насколько близко джин подошел к разгадке.
Элементарно, Ватсон!
— Холмс, мы, кажется, докопались до истины!
— Да, Ватсон, теперь попробуем выбраться из ямы.
Бородатый анекдот
После того, как Акинатор подряд отгадал мне Лару Крофт, Ленина, Оби-Вана Кеноби, Сократа и ослика Иа-Иа, я решил, что для обзора мне будет нужен скриншот проигранной джином игры. Загадывать персонажей фильмов или книг я после этого не рискнул, каких-то реально существующих актеров, певцов или исторических личностей — тоже. Но просто так случайным образом тыкать на кнопки ответов мне тоже было не интересно. Окей, подумал я, пусть это будет просто первый пришедший на ум человек — например, Эльдар Муртазин.
Знаете ли вы, что… Для любителей постоянно давать расплывчатые ответы или все время бездумно нажимать «Скорее нет \ Не совсем» у тоже Акинатора есть свой ответ.
Впервые я забеспокоился, когда Акинатор стал допытываться у меня, есть ли у загаданного персонажа мобильный телефон. Затем — когда он стал спрашивать, носит ли мой персонаж очки и не полноват ли он. Потом немного расслабился, когда джин стал узнавать, не является ли он красивой и талантливой русско-французской певицей и нет ли у него, случаем, клешней.
Вопросы про мумии… |
… и поцелуи. |
И логический вывод |
Но ответ меня все равно удивил — Акинатор решил, что это Андрей Соловьев, обзорщик мобильной техники. Очень, очень близко! При том, что не одного вопроса «в лоб» (является ли ваш персонаж журналистом, связан ли он с мобильной индустрией, пишет ли он обзоры устройств и пр.) он мне даже не задавал. Мистика, не иначе. Впрочем, ответ в любом случае оказался неверен. Но, как вы помните, даже если Акинатор не правильно угадал задуманного персонажа с первого раза, можно дать ему еще один шанс, продолжив игру. Именно это я и решил сделать.
На этот раз джин решил не ходить вокруг да около и сразу стал задавать вопросы по существу. «Ваш персонаж родился не в Белоруссии?», «Имеет ли он отношение к технике?», «Ваш персонаж писатель?», «Он имеет отношение к мобильным телефонам?» Всего четыре дополнительных вопроса и у Акинатора уже готов ответ: «Я думаю это… Эльдар Муртазин, журналист».
|
Вторая попытка |
Верный ответ |
Эльдар явно популярен =) |
Вот такие дела. Даже специально решив «завалить» джина и выбрав, как мне казалось, совершенно беспроигрышный вариант, я все равно проиграл. Особо недоверчивые читатели могут повторить эксперимент сами. Вопросы, скорее всего, будут другие, но сам результат вряд ли изменится — верный ответ со второй попытке.
Персонализация и настройки
— Я попыталась настроить дома телевизор.
— Получилось?
— Не знаю… Кажется, я его настроила против себя.
Разговор двух блондинок
После окончания игры, когда Акинатор (не)отгадал вашего персонажа, у вас появится доступ к дополнительным функциям. Во-первых, это кастомизация текущего персонажа — персонажу можно изменить как имя, так и фотографию. Это может быть отличным способом удивить знакомых — Акинатор не просто ответит «это ваш учитель», но еще и назовет его по имени и покажет фотографию.
|
Меняем имя |
Ставим свою картинку |
Готовый вариант |
Кроме того, можно добавить в программу дополнительные вопросы про вашего персонажа. Причем, в отличие от кастомизации, эти вопросы будут внесены в базу данных самой программы и после проверки модератором станут доступны всем игрокам. Правда у меня протестировать эту функцию не получилось — каждый раз выскакивала какая-то ошибка. Ниже я приведу те скриншоты, которые смог сделать.
|
Поиск похожих вопросов |
Вводим сам вопрос |
Указываем правильный вариант ответа |
Как видите, вначале мы проверяем наличие схожего запроса по ключевым словам, затем вводим сам вопрос и выбираем правильный вариант ответа для каждого персонажа.
|
Детский режим |
Два разных варианта… |
… одного вопроса |
Настройки программы довольно просты. Есть возможность выбрать один из 12 доступных языков, включить \ отключить музыку и звуки, защиту от детей, персонализацию. Кроме того, можно выбрать фоновое изображение. Доступных вариантов, к сожалению, всего два.
|
Выбор фона |
Первый вариант |
Второй вариант |
Вместо послесловия
Игра оставила после себя самые приятные впечатления — интересная задумка, качественная реализация, красивое оформление. Жаль только, что свои вопросы добавить с телефона не получилось.
Akinator довольно популярная программа, вполне возможно, что многие из вас уже давно с ней знакомы. Тем не менее, за всеми хорошими программами не уследишь. И мне кажется, что не будет ничего плохого, если на AMR будут появляться обзоры некоторых из них.
Надеюсь, обзор оказался для кого-то интересным. Спасибо за внимание.
