Сальвадор Дали. Искушение св. Антония. 1946. (Фрагмент).
Бельгийский Королевский музей изящных искусств (Брюссель).
Неужели эта задача требует столь сложного решения? Может, это задача ИИ? – Исхожу из определения:
к ИИ относятся задачи, которые компьютер решает заметно хуже человека.
(О применении генетических алгоритмов в ИИ см. книгу: Д. Рутковская, М. Пилиньский, Л. Рутковский, Нейронные сети, генетические алгоритмы и нечеткие системы, М.: Горячая линия – Телеком, 2006).
Однако ларчик открывается довольно просто. Пусть длина каждого из заданных слов . Из словаря существительных выписываем все слова длиной . Число найденных слов обозначим . Эти слова будут метками вершин неориентированного графа. Каждую пару вершин, метки которых отличаются на одну букву, соединяем ребром. Для этого перебираем все пары вершин, сравнивая их метки – число пар , число побуквенных сравнений . Далее решаем типовую задачу поиска кратчайшего пути между указанными вершинами графа.
Словарь существительных взял с CD-ROM к книге Сергея Мельникова, Delphi и Turbo Pascal на занимательных примерах, СПб.: БХВ – Петербург, 2006 (к слову сказать, в этой книге можно найти много остроумных и простых решений подобных, казалось бы, сложных задач со словами):
В словаре перечислены все имена существительные «Орфографического словаря»
(106000 слов, 28-е издание, 1990 г.). [...] Набор текста осуществлён в 1996-98 годах игроками команды «Пузляры» (http://puzzle.ezakaz.ru) — Константином Кнопом, Яковом Зайдельманом, Валерием Тимониным, Виктором Кабановым, Дмитрием Филимоненковым.
Получил:
Число загруженных слов (число вершин графа): 1501
Число ребер: 2402
Решение: (8 слов) муха-мула-кула-кила-килт-киот-клот-клон-слон
Затрачено времени: 4.59 сек.
Вряд ли обычный человек сообразит быстрее. Более того, так как используются алгоритмы, корректность которых строго доказана, то очевидно, что программа гарантированно находит самое короткое решение, если оно существует в рамках данного словаря. А вот человек не сможет доказать, что его решение самое короткое, как и то, что решения не существует. Таким образом, тут компьютер вне конкуренции с человеком, и эта задача — не задача ИИ.
А вот некоторые другие метаграммы:
муха-мура-бура-бора-кора-корн-коан-клан-улан-улар-удар-удав
мышка-мошка-кошка-корка-горка
шило-кило-коло-соло-сало-рало-рыло-мыло
баран-барон-басон-басок-бачок-бочок-борок-порок-порог-ворог-ворот
Над последним решением программа думала уже 25.21сек. Интересно, что граф оказывается несвязным. Так, например, не удалось найти решения для пешка – ферзь.
Можно расширить задачу. Пусть программа находит самые длинные цепочки с заданным числом букв, то есть генерирует головоломки. Для решения этой задачи нужно принять длину ребра нашего графа равной единице и вычислить матрицу расстояний между вершинами. Это можно сделать, например, с помощью алгоритма Флойда-Уоршелла. Так, для слов в 11 букв получим:
Число загруженных слов: 3391
Число ребер: 223
Максимальное расстояние: 9
Пары на максимальном расстоянии: закатывание-запихивание, запихивание-наматывание, обсаживание-отматывание, отматывание-отсиживание
Затрачено времени: 3821.45 сек.Найдем решение для пары запихивание – наматывание:
Решение: (9 слов) запихивание-запахивание-запаривание-заваривание-заваливание-закаливание-накаливание-накалывание-накатывание-наматывание
Затрачено времени: 62.12 сек.
В заключение этой небольшой заметки стоит отметить, что совершенно справедливо программист, приступая к решению новой задачи, пытается использовать похожее известное решение. С ростом популярности методов ИИ они будут все чаще применяться к различным задачам. Но тут требуется особая осторожность – иначе из мелкой алгоритмической мухи может получиться громадный слон.
При этом все сказанное ни в коей мере не стоит воспринимать как критику указанной статьи с генетическим алгоритмом. Автор любой работы имеет безусловное право исследовать любой алгоритм на любой задаче. И такое исследование приносит свою пользу. В частности, благодаря ему стало возможным сравнение, приведенное в этой заметке.
Комментарии (27)
DmitryKogan
24.09.2017 22:46+1Определение ИИ неверное. Вчера компьютер играл в Го хуже человека, а сегодня лучше — и что, характер задачи изменился? На самом деле, задачи ИИ — творческие, т.е. те, для решения которых недостаточно формальной логики.
third112 Автор
24.09.2017 23:01Если я не в курсе последних достижений по Го, то, пожалуйста, поправьте меня, но, насколько мне известно, комп играет в Го хуже многих чемпионов. Такая пробуксовка наблюдается многие годы — вычислительные мощности многократно возрастают, а играть, доказывать теоремы, писать стихи как Пушкин, комп так и не выучился. Когда научится — вот тогда и можно будет пересмотреть определение.
Про формальную логику. В ИИ (и не только там) используют и эвристические алгоритмы, где не только формальная логика.DmitryKogan
24.09.2017 23:10Проблема Го решена в прошлом году: ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B3%D0%BE
Естественно, ИИ использует эвристики, как подпорку — именно потому, что не способен к творчествуthird112 Автор
24.09.2017 23:27Не увидел там утверждения, что проблема решена полностью. Про эвристики. Скорее человек использует их «как подпорку», когда не может найти строго доказуемого решения. Творчество — понятие эвристическое и во многом от вкуса зависит. Есть«творцы», которые холст экскрементами мажут и называют это творчеством, а разные именитые критики до хрипоты перманентно и инфинитно спорят, творчество это или не творчество.
vics001
25.09.2017 01:56-1В мае 2017 года на саммите «Future of Go Summit» AlphaGo выиграла три партии из трёх в мини-матче с одним из сильнейших игроков в мире, лидером мирового рейтинга Эло Кэ Цзе[31]
Пробуксовки в развитии ИИ не заметил. Вычислительные мощности не являются тупиком развития, алгоритмы обучения, структуры нейронных сетей. Так как искусство субъективно, то прогресс там не настолько общественно значим и поэтому не настолько большой, как в игре го или вождении автомобиля.
P.S. теоремы доказывать компьютер еще в 80-х годах научился. Теорема о 4-х красках или основная теорема теории групп (http://www.ega-math.narod.ru/Nquant/Groups.htm).third112 Автор
25.09.2017 13:12-2Думаю, что успех программы в трех партиях не дает основания для вывода, что проблема решена. Нпр., в крестики и нолики 3х3 у программы выиграть невозможно. М.б. и здесь какой-то финт: программа сводит партию к комбинациям, когда становится возможным полный перебор. Интересно, что на следующих строчках указанной вики-статьи говорится о проблеме игры программы с программой.
Конечно, у ИИ есть скромные успехи, однако роботы в фонтанах топятся…
Что касается задачи 4х красок, то ИИ здесь ни при чем. Было сделано утверждение, что достаточно перебрать всего ок. 2000 тысяч вариантов. Этот перебор был сделан на компьютере. Однако вникнуть во все детали ни один человек не в состоянии. Поэтому почти 30 лет ряд несогласных специалистов искали контрпример. Среди не признавших был такой известный математик, как Александр Гротендик, правда, в поисках контрпримера он не участвовал. До сих пор делаются попытки найти человеческое, а не машинное доказательство. См. нпр., В.В. Родионов, Методы четырехцветной раскраски вершин плоских графов, М.: URSS, 2005. Там довольно подробно изложена и история проблемы 4х красок. Т.о., задача 4-х красок это особый случай, а с другими теоремами, за исключением достаточно тривиальных и практически никому не нужных, комп справится пока не может.vics001
25.09.2017 19:35-1Какая проблема не решена? Люди тоже топятся в фонтанах. Называйте вещи своими именами, непонятно, что вы хотите сказать.
third112 Автор
25.09.2017 21:06Какая проблема не решена?
Я точно указал:
на следующих строчках указанной вики-статьи говорится о проблеме игры программы с программой.
Читаем здесь эти строчки:
Когда два компьютера играют в го друг с другом, то в идеале должна получиться картина игры, свойственная игре человека с человеком. Однако этого трудно добиться, особенно в конце игры. Основная проблема заключается в том
и т.д.
Люди тоже топятся в фонтанах.
Нормальные люди и подавляющее большинство ненормальных, склонных к суициду, в фонтанах не топятся. М.б. Вы считаете особым прогрессом ИИ имитацию личности на крайней стадии ее распада?
Infro-Storm
25.09.2017 12:03Хорошая статья, но тут говорится о сравнении, а сравнения я не нашел. Только с человеком. Если сравнивать скорость нахождения(пусть не оптимальных) решений этой задачи ИИ по скорости и данного алгоритма. Что-то мне подсказывает что достаточно хорошо обученный ИИ будет находить решения в разы быстрее так как ему не придется пролистывать весь словарь по нескольку раз. Возможно ли добавить в статью такие результаты тестирования?
third112 Автор
25.09.2017 13:52+1Мой алгоритм: муха-мула-кула-кила-килт-киот-клот-клон-слон 4.59 сек.
Генетический алгоритм: «муха» — «мура» — «фура» — «фора» — «кора» — «корн» — «коан» — «клан» — «клон» — «слон» 137 сек.
Но это очень грубое сравнение на разном железе. И это не главное. Я не оптимизировал программу, считая время в несколько секунд (и даже больше) вполне приемлемым. Главное, что мой алгоритм гарантирует нахождение кратчайшего решения, если оно существует в рамках выбранного словаря. А ИИ вряд ли сможет такое гарантировать. И м.б., что не достаточно хорошо обученный ИИ не сможет сделать из мухи слона.
PapaBubaDiop
А что это за язык? Ru++?
third112 Автор
Где Вы нашли такой язык?
PapaBubaDiop
Это вы нашли.
У меня их даже MSWORD подчеркивает как нерусские)
third112 Автор
Гугл в помощь:
борок
басон
рало
и т.д.
А Микрософту стоило бы лучше выучить язык, прежде чем чекеры для него писать.
PapaBubaDiop
Без гугла значит никак…
third112 Автор
Не понял. Гугл — достижение прогресса, как огонь или колесо. Не нравится гугл — пользуйтесь яндексом. Или м.б. в пещеры вернуться? Забыть все науки и искусства, а просто охотиться с кирпичом на мамонта? — так ведь мамонты перевелись.
А Даля надо знать…
PapaBubaDiop
Мы в эту игру в детстве во дворе играли. За такие слова меня бы высмеяли и прогнали… А так да, Даль — наше все. У меня просьба, может вам интересно будет — решить эту задачу на живом языке. Интересно было бы сравнить с каноническим решением из «Наука и жизнь». Разговорный русский словарь есть в гугле))
third112 Автор
Если бы я сказал на нашей улице «ИИ», то не высмеяли бы, как не смели смеяться, когда трубку от телевизора я, начитавшись детской энциклопедии, называл Кинескопом. Но не поняли бы. Однако Вы правы — результат работы программы зависит от словаря. Если Вас интересуют конкретные решения, то могу выслать Вам программу — хотите в исходном коде на Дельфи-7, хотите исполняемым файлом. Если не только Вас это заинтересует — выложу в открытый доступ.
PapaBubaDiop
Спасибо, но я не смогу воспользоваться вашим кодом или исполняемым файлом. Я в другом мире)
За кинескоп и меня не побьют. Но вот за «рало» схлопочу в морду, век воли не видать.
third112 Автор
Детские коллективы не показатель. У детей могут быть разные не совпадающие знания. Нпр., помню как в 4ом классе на перемене повторил фразу, услышанную в научпоп. передаче по радио: всё состоит из атомов. Надо мной стали смеяться, но стоявший рядом семиклассник, брат одного из моих оппонентов, прекратил этот спор, авторитетно заявив, что я прав.
Но в общем случае многие игры в компании зачастую требуют уточнения правил. Это не всегда просто сделать. В случае игр в слова проще всего взять какой-либо словарь — можно не в 100К слов, а меньше и договорится использовать только те слова, что есть в данном словаре.
PapaBubaDiop
Правило для словаря очень простое — хотя бы один кент из компании должен верифицировать ваше слово и привести пример использования. В этом случае слово считается в словаре.
Кстати, это повышает общий кругозор двора.
third112 Автор
Сейчас инет есть наверное в каждом дворе — в качестве инструмента верификации запросто можно использовать гугл. Раньше, когда не было сетки, в спорных случаях можно было пробежаться до районной или до школьной библиотеки.
Но никто не препятствует сделать компании свой словарь. Такое дело безусловно повысит общий кругозор двора. При этом в словаре могут оказаться слова, которые возникли только в этом дворе и никем кроме не используются.
third112 Автор
Ошибка: не та ветка
Zenitchik
Уменьшительно-ласкательный суффикс. Неспортивно.
С клотом тоже вопрос. Используется ли как самостоятельное слово, а не часть составного термина?
third112 Автор
Вообще-то статья не о том. Алгоритм не оценивает словарь (Орфографический, 106000 слов, 28-е издание, 1990 г.). Думаю, что подобные претензии нужно адресовать составителям словаря. Выше я уже предложил выслать код, тогда Вы сами сможете получить желаемый результат.
Zenitchik
Я имею в виду, что в эту игру играют по определённым правилам. Допустимы только существительные и только в стандартной форме. Именно поэтому применение в игре подобных приколов — читерство и законный повод получить по морде от соперника.
third112 Автор
Я не спорю, замечу только, что игроки команды «Пузляры», видимо, сочли данное слово допустимым, раз оставили его в своем словаре. Думаю, что, прежде чем играть, надо договориться, какой словарь использовать.