Comments 4
Интересный материал. Я думала, робототехника уже вовсю движется в сторону reinforcement learning
А я использую деревья принятия решений в своей небольшой самописной авторской игре на Андроид. Однажды жена показала мне Акинатора и… я… загорелся! В результате принял решение сделать подобную игру, но маг угадывает не персонажей, а существительные, задавая наводящие вопросы. Я взял самые объёмные сайты со словарями русского языка и на-дата-майнил порядка 200000 существительных. Потом я написал на плюсах прогу, которая находит все простые лексические признаки слов. Под признаком я понимаю вопрос-предикат, на который однозначно можно ответить «да» или «нет», зная написание слова. Например, признаками являются: «в слове встречается буква ж», «слово состоит из 8 букв», «5-я буква в слове у», «в слове есть сочетание ка перед ро» и так далее. Получилось огромное множество признаков. Потом эта программа с использованием этих признаков построила оптимальное дерево задания вопросов, чтобы поскорей добраться до ответа. В результате маг угадывал любое слово за 10-15 вопросов, но это было скучно, ибо вопросы часто были одного и того же «типа». И я запретил алгоритму построения решающего дерева использовать подряд два однотипных вопроса. В результате игра получилась куда более увлекательной и интересной. Теперь маг (Wordeuz кому интересно) пытается угадать любое ваше слово за 20 вопросов, и если у него это не выходит — победный балл ваш! Разумеется, так как алгоритм поиска решающего дерева опирается на выявление таких предикатов, которые делят множество решений максимально пополам, можно эксплуатировать эту уязвимость в игре, загадывая магу слова с максимально необычным написанием для русского языка, например, «гжель» или «пьянь». На них он проигрывает. Дерево я не балансировал. Чтобы Вордеуз не задавал одинаковые вопросы из игры в игру, я построил не одно, а несколько решающих деревьев, беря в качестве предикатов не только топовые (лучшие), а вторые/третьи и так далее. База получилась огромной (20 мб на решающее дерево), но я написал собственный алгоритм архивации, основанный на частотном распределении фрагментов слов, и умудрился впихнуть даже несколько решающих деревьев в apk. Плюс само сжатие при билде и в итоге — в оффлайн (!!!) версии приложения 200000 существительных в нескольких решающих деревьях и игре вообще не нужен интернет!!! Чудеса! Далее я запрограммировал андроид-приложение, нарисовал (художник из меня от слова «худо») персонажа и выпустился. Ссылок никаких не привожу, ибо реклама и всё такое.
Может… Стоило бы это всё-таки в виде статьи оформить? С примерами там, разбором полётов?..
Only those users with full accounts are able to leave comments. Log in, please.
Information
Founded

15 September 2008

Location

Россия

Employees

201–500 employees

Registered

12 May 2010