Популярно об ИИ/Lua для игр и не только
Например, в последнее время, если речь идет о чем-то казуальном, весь математический аппарат я делаю только и сразу на Lua, а к чему он (какому движку или платформе) будет прикручен в дальнейшем (для iPhone, Android, Windows) — это уже вопрос интеграции. В арсенале Lua есть все, что необходимо, включая стандартный математический аппарат, мусороуборщик, coroutines (многопоточность) и такой удобный тип данных, как table. Отсутствие явного ООП может испугать разве что программистов нового поколения. Но многим такой вариант нравится даже больше, потому как меньше всевозможного языкового хлама. Основные идеи, реализованные в Lua, фактически идентичны тем, за которые я некогда обратил внимание на С#, но тот в силу своей тяжкой наследственности:) в очередной раз «начал прокладывать свою трассу». Lua ругают за отсутствие строгой типизации, но динамическое приведение типов, а также реализация типа table, который может хранить в себе данные различных типов — это очень удобные инструменты. Да, в руках новичка код может быстро превратиться в кашу, но это уже культура написания — я видел немало кода на С++, в котором не мог разобраться даже его написавший. И это мы обсудили только внутреннее убранство.
Использование Lua в качестве языка сценариев (а я его использую и вообще как главный блок кода в обход основного, и как организацию хранилища данных) очень удобно — все исправления можно вносить на лету, не нужно ничего компилировать и т.п. В результате высокая скорость итераций.
«МУХА» -> «СЛОН». Продолжение…
Интересные события произошли после публикации предыдущего материала этой серии, в котором мы начали писать программу превращения слова «МУХА» в слово «СЛОН» по правилам известной головоломки, когда можно менять только одну букву, при этом каждый промежуточный вариант должен быть осмысленным. Автор этих строк взял такой пример для старта написания алгоритма по автоматическому созданию кроссвордов.
И удивило даже не то, что из всех читателей, откликнулся только один, приславший свой вариант решения «МУХА» —> «СЛОН», написанный именно на Lua. Он использовал стандартный вариант, о чем мы расскажем чуть позже.
Довольно необычным было получение писем от двух разработчиков коммерческих программ-генераторов кроссвордов, общую мысль которых можно описать как: «Не нужно давать «копипастерам» готовые алгоритмы!». Не подумайте, что это звучало как-то угрожающе, просто я понимаю проблему этих людей, причем, как и они, до «внутренностей» алгоритма когда-то тоже дошел самостоятельно. И сложного там не много, на самом деле. Поэтому мы и остановились на примере с «МУХА» —> «СЛОН», благодаря которому вы сможете понять, как делать более сложные вещи.
Напомню, что в прошлой части материала мы сделали основную «рыбу», в рамках которой имелась функция чтения словаря из текстового файла и загрузка всей базы слов в таблицу. Затем мы реализовали функцию перебора, меняющую буквы и находящую все осмысленные результаты, сверяясь со словарем. На базе всего этого были найдены все варианты слов, которые могут быть сформированы из «МУХА», коих оказалось 11. Далее я вам предложил самостоятельно подумать об алгоритме перебора, который позволит выявить цепочку «МУХА» — «СЛОН».
Несколько слов о выборе алгоритмов
Выбор оптимального алгоритма применительно к задаче — это очень интересный этап, потому как сама задача в нашем случае, как и в множестве других, является конкретной, а не абстрактной.
Вариантов может быть довольно много, поэтому давайте рассмотрим ключевые из них.
Самое неэффективное — полный перебор
Алгоритм следующий: для каждого полученного слова мы находим те, которые могут быть сформированы от него, и так далее, пока не получим «СЛОН». Дерево поиска растет семимильными шагами.
Полный перебор с отсечениями родительских узлов
Для того чтобы сделать полный перебор более эффективным, нужно отсечь те ветки, которые имеют встречающиеся элементы, чтобы мы не обрабатывали циклически повторяющиеся состояния. Например: «МУХА» -> «МУКА» -> «МУХА» или же «МУХА» -> «МУКА» -> «МУЗА» -> «МУХА». Для этого нужно внедрить функцию сравнения результата со всеми родительскими элементами ветки.
В принципе, при выполнении этой задачи главное — сделать вариант отсечения максимально оптимальным, причем, как вы понимаете, нужно запоминать все предыдущие состояния каждой ветки.
Поиск в ширину, или с каким порядком цифр мы сталкиваемся
Среди множества вариантов поиска можно выделить со стороны кажущийся ресурсоемким и близким к полному перебору, но при этом и наиболее полно отображающий общую картину — поиск в ширину. Именно в его рамках мы можем найти оптимальный ответ, но какими ресурсами этого можно достичь? Несмотря на то, что наиболее часто используемыми являются поиск в глубину, а также смешанный (и в глубину, и в ширину), для общей информативности статьи я сделал небольшое отклонение от программы из прошлой статьи и заставил ее посчитать количество слов в каждом поколении. При этом родительские узлы я просто отсекал, удаляя эти слова из словаря (нашей таблицы). Иначе говоря, от «МУХА» образовалось 11 слов, «МУХА» было удалено из общей базы, затем из этих 11-ти было сформировано новое поколение, после чего эти 11 были удалены.
Примечание: точнее сказать, я не удалял, поскольку удаление в рамках таблицы — это тоже ресурсоемкая операция, я просто заменял слова на «». Таким образом, мы грубо отсекаем любые циклические ветви. Напомню, что сам словарь у нас включает чуть меньше 4000 слов. А приведенные ниже цифры демонстрируют не что иное, как размеры популяций поколений.
Итак, вот что выдала программа от слова МУХА:
11
71
314
702
699
333
235
228
Причем сами расчеты велись довольно долго, поскольку, напоминаю, что каждое слово мы разбиваем на символы, формируем от него его потомков (коих 33*4=132, то есть предусматриваем варианты замены по одному символу на каждой позиции), потом производим сверку со словарем, и если есть совпадение, то получаем дочернее слово. Если у нас таких слов 11, то мы в итоге получаем 132*11=1452 неявных потомка, которые нужно сравнить со словарем. От 11-ти, как вы увидели, с ним сошлось 72 дочерних варианта, и так далее. В случае с приведенными цифрами, и поскольку мы сделали ощутимое отсечение с удалением слов всех родительских поколений, можем наблюдать всплеск на 4-м и 5-м преобразованиях.
А теперь давайте посмотрим, что будет в случае, если мы будем двигаться в обратном направлении, от «СЛОН» к «МУХА», причем изначально слово «СЛОН» имеет всего пять потомков. Выгодно ли двигаться от «СЛОНА» к «МУХЕ»? Давайте посмотрим:
5
27
98
200
355
573
840
683
Здесь мы получаем гораздо худшую картину в итоге. В действительности, само слово «СЛОН» обладает большей жизнеспособностью, хотя в первых поколениях имеет меньше потомков по сравнению с «МУХА».
Выборочный поиск
В данном случае нужно внести оценочную функцию того или иного слова и рассчитывать в первую очередь наиболее выгодные ветки. Например, в качестве оценочной функции можно учесть следующие параметры:
. За каждую гласную букву начисляется 1 балл.
. Если место расположения гласной буквы в найденном слове совпадает с местом расположения гласной буквы в искомом слове, начисляется 2 балла. . Если буква найденного слова совпадает с искомым по положению и значению, то начисляется 3 балла.
Таким образом, конечное слово всегда будет иметь оценку в 12 баллов. Нужно сказать, что это один из самых часто встречающихся вариантов распределения оценок применительно к данной задаче.
Это близко и к понятию генетических алгоритмов, в рамках которых из популяции производится селекция по определенным критериям, именуемым хромосомами. А в шахматных алгоритмах все это называется несколько по-другому и прячется за большим количеством вариантов альфа-бета переборов.
Выборочный поиск в глубину
Именно такой вариант и прислал единственный откликнувшийся читатель. Причем, как он написал, сначала попробовал сделать все с помощью рекурсивного метода, в результате чего, естественно, начал бороться с проблемами переполнения стека, после чего (как и всегда бывает в таких случаях:)), плюнул на все и реализовал подобные алгоритмы с помощью циклов.
Вообще, я уже много раз писал, что в большинстве случаев рекурсия оправдана только емким кодом, не более того.
Поскольку присланный листинг довольно объемен, опишу его словами.
В общем, читатель (а это Николай С. из Минска) пошел изначально по пути реализации поиска в глубину. То есть из слова МУХА у нас получилось 11 слов, затем берется первое (или последнее) из них, и теперь уже от него ищутся по словарю следующие варианты преобразования, из которых опять же выбирается определенный, от которого снова ищутся следующие слова, и так до определенной глубины. Если искомый результат не был найден, то идет переход на соседнюю ветвь.
В коде Николая на первом этапе дополнительно к представленному мною коду появились новые функции:
1. Функция перебора слов и поиска в глубину.
2. Исключения родительских элементов для устранения из области поиска циклически повторяющихся ветвей.
3. Сравнения результатов со «СЛОН».
4. Плюс к этому у него было ограничение по глубине.
Причем изначально, как признался Николай, он об оценочной функции не думал, потому как «с треском», но получал результат, а именно цепочку (мы к ней потом присмотримся внимательно): МУХА МУКА МУЗА ЛУЗА ЛОЗА КОЗА КОЛА КИЛА КИЛТ КИОТ КРОТ ШРОТ ШКОТ СКОТ СЛОТ СЛОН.
После Николай просмотрел старые статьи из серии «Популярно об ИИ», а также обратил внимание на то, что я упомянул о генетических алгоритмах, поэтому решил модифицировать код, посмотрев на формируемые поколения как на «популяцию», к которой нужно применять «селекцию»:). В принципе, в тех же шахматных программах вы не встретите подобной терминологии, хотя алгоритмы, используемые в их рамках, очень близки к генетическим. Например, по выбору лучшего хода.
Итак, Николай сделал свою оценочную функцию, очень похожую на ту, что описана в предыдущем подразделе, а также ввел ограничения по размеру популяции — она не должна была превышать какого-либо размера.
В результате таких нововведений расчеты стали происходить гораздо быстрее. То есть Николай ввел дополнительно:
1. Оценочную функцию для выбора наиболее перспективных ветвей для расчета.
2. Ограничение по размеру популяции.
Мы списались с Николаем, и я сказал, что сделанный им алгоритм является фактически классикой, с чем и поздравил (и по коду, и по описанию в письме было очевидно, что до всего человек додумался сам). Но есть у такого подхода, как, впрочем, и вообще у поиска в глубину, и изъяны. Какие? Посмотрите внимательно на результат, а именно на три первых элемента: МУХА МУКА МУЗА. Заметили? Дело в том, что МУЗА так же формируется от исходного слова изменением одной буквы, как и МУКА. И на самом деле, слово МУКА в его цепочке является лишним, но алгоритм выстроил верную цепочку от него. Таким образом, вы и сами убеждаетесь в том, что вариант поиска в глубину выдает искомый результат, но не оптимальный — все зависит от направления движения поиска.
Если говорить о варианте поиска в ширину, то улучшение его алгоритма за счет введения оценочной функции также может значительно увеличить скорость расчетов, но в то же время ограничение размера популяции повредит качеству алгоритма.
Самыми ресурсоемкими для всех вариантов алгоритмов в программе являются: функция сравнения со словарем, а также разбиение/конкатенация. Очень многое зависит от оценочной функции, качества ее настройки.
Встречный поиск применительно к данной задаче
Вообще, нашу задачу можно представлять не в виде дерева, а в виде графа, в рамках которого известны начальный и конечный пункты. Поэтому можно открыть двухстороннее движение, сделав своеобразные «качели», когда поколения от двух исходных слов направляются друг к другу. Для этого нужна еще одна функция сравнения поколений. То есть от слова «МУХА» сформировалось 11 вариантов, они сравниваются со «СЛОН», затем от «СЛОН» формируется 5 и сравнивается с 11-ю от «МУХА», и так далее.
Для решения нашей задачи данный метод неэффективен, но в ряде случаев является самым оптимальным. О нем просто нужно знать, что есть такой.
Вместо завершения
Реализацию всего написанного выше вы можете без особого труда воспроизвести на базе кода из предыдущей статьи, потому как для газеты это будет довольно объемный листинг, если его приводить.
Для понимания специфики Lua при выполнении этого задания также рекомендую самостоятельно найти наиболее ресурсоемкие операции. А также, что может вам сильно пригодиться в рамках реальных проектов, сделайте вариант, когда таблицы с базой как таковой у вас нет, а поиск по словарю производится внутри внешнего файла (того самого *.txt, где у нас изначально хранился словарь).
Кристофер http://itcs.3dn.ru
Компьютерная газета. Статья была опубликована в номере 17 за 2011 год в рубрике программирование
