Простые онлайн-игры из 20 вопросов с невероятно точным ИИ.
Как они так хорошо догадываются?
algorithm
artificial-intelligence
Папа варбокс
источник
источник
Ответы:
Вы можете думать об этом как об алгоритме двоичного поиска. На каждой итерации мы задаем вопрос, который должен исключить примерно половину возможных вариантов слов. Если всего N слов, то можно ожидать ответа после log2 (N) вопросов.
С 20 вопросами мы должны оптимально найти слово среди 2 ^ 20 = 1 миллион слов.
Один из простых способов устранить выбросы (неправильные ответы) - это, вероятно, использовать что-то вроде RANSAC . Это означало бы, что вместо того, чтобы принимать во внимание все вопросы, на которые были даны ответы, вы случайным образом выбираете меньшее подмножество, которого достаточно, чтобы дать вам единственный ответ. Теперь вы повторяете это несколько раз с разными случайными подмножествами вопросов, пока не увидите, что в большинстве случаев вы получаете один и тот же результат. тогда вы знаете, что имеете правильный ответ.
Конечно, это лишь один из многих способов решения этой проблемы.
источник
code
ссылку, чтобы увидеть ее: openbookproject.net/py4fun/animal/animal.htmlДерево решений напрямую поддерживает этот вид приложений. Деревья решений обычно используются в искусственном интеллекте.
Дерево решений - это двоичное дерево, которое задает «лучший» вопрос в каждой ветви, чтобы различать коллекции, представленные его левыми и правыми дочерними элементами. Лучший вопрос определяется некоторым алгоритмом обучения, который используют создатели приложения «20 вопросов» для построения дерева. Затем, как указывают другие плакаты, дерево глубиной в 20 уровней дает вам миллион вещей.
Простой способ определить «лучший» вопрос в каждой точке - это поискать свойство, которое наиболее равномерно делит коллекцию на две части. Таким образом, когда вы получите ответ да / нет на этот вопрос, вы избавитесь примерно от половины коллекции на каждом этапе. Таким образом вы можете приблизить двоичный поиск.
Википедия дает более полный пример:
http://en.wikipedia.org/wiki/Decision_tree_learning
И немного общей предыстории:
http://en.wikipedia.org/wiki/Decision_tree
источник
Рекомендую прочитать об игре здесь: http://en.wikipedia.org/wiki/Twenty_Questions
В частности раздел Компьютеры:
источник
Он позиционирует себя как «нейронная сеть в Интернете», и в этом заключается ключ. Вероятно, он хранит вероятности вопроса / ответа в запасной матрице. Используя эти вероятности, он может использовать алгоритм дерева решений, чтобы определить, какой вопрос задать, чтобы сузить следующий вопрос. Как только он сузит число возможных ответов до нескольких десятков или если уже достиг 20 вопросов, он начинает считывать наиболее вероятные.
По-настоящему интригующий аспект 20q.net заключается в том, что в отличие от большинства известных мне алгоритмов дерева решений и нейронных сетей, 20q поддерживает разреженную матрицу и инкрементные обновления.
Изменить: оказывается, ответ был в сети все это время. Робин Бургенер, изобретатель, подробно описал свой алгоритм в своей патентной заявке 2005 года .
источник
Он использует алгоритм обучения.
k-NN - хороший пример одного из них.
Википедия: алгоритм k-ближайшего соседа
источник