Сразу оговорюсь, что под «башнями» в заголовке поста подразумевается игра-головоломка «Саровские башни», расположенная на сайте bashni.org, о существовании которой я узнал из хабрапоста Как построить башню.
Если вам знакомы эта игра и этот сайт, то лишних пояснений не потребуется, если нет — можете пробежаться по обоим ссылками, чтобы понять о чем речь.
Ну или можно просто почитать о том, как одному ленивому программисту захотелось автоматизировать процесс решения головоломки, над раскладами которой порой часами бились люди с зашкаливающим IQ, и что из всего этого вышло.
Вступление
Итак, в октябре 2011 года я наткнулся на вышеупомянутую статью, и, в силу моей тяги к различными головоломкам, «подсел» на эту игру. Собирал потихоньку башни, со временем все лучше и лучше, но зачастую оказывался «бит» более опытными противниками, либо не мог повторить уже достигнутого ими результата.
Здесь самое время упомянуть о соревновательном элементе игры, если вы конечно еще не успели про него узнать из приведенных мной ссылок. Суть в том, что задачей является не просто решить головоломку, но сделать это за меньшее количество ходов, чем другие игроки. Т.к. у каждого расклада есть уникальный номер, и на сайте ведется статистика всех сборок, то все это весьма наглядно показано, и создает вполне соревновательную атмосферу.
И вот, в очередной раз не сумев перегнать, или хотя бы просто догнать заслуженных мастеров спорта по башнестроению, я решил применить «допинг», т.е. написать программу для решения головомки. В конце-концов, разве не должны роботы работать вместо людей в прогрессивном третьем тысячелетии?
Дополнительным стимулом мне служило то, что создатель игры, небезызвестный на хабре PapaBubaDiop, в комментариях к той статье неоднократно заявлял, что количество вариантов ходов в сложных раскладах очень велико, и программно перебирать их можно очень-очень долго, в то время как другой хабраюзер volerog утверждал что уже писал бота, способного решать большинство башен за какие-то считанные минуты.
В общем, не откладывая дела в долгий ящик, я приступил к написанию кода.
Т.к. мой основной рабочий инструмент — JavaScript, а игра браузерная, то естественным решением стало написание программы на этом языке. Многие конечно могут возразить, что интерпретируемый скриптовый язык не лучшим образом подходит для обработки большого объема информации, и лучше бы все это писать на С (или даже на Asm, «ибо воистину»), но мне подобные усилия для задачи Just for fun показались чрезмерными.
Я даже поленился делать из программы что-то типа подключаемого userscript для браузера, и ограничился просто копипастой кода в dev-консоль (та самая, которая вызывается кнопкой F12 в FF и Chrome). Собственно, именно Chrome, обладающий быстрейшим из известных мне движков JavaScript, и стал моим тестовым полигоном.
Если читатель до этого места до сих пор хотя бы бегло не ознакомился с правилами игры, то стоит это сделать на этой замечательной странице, где все очень доступно расписано, и даже есть наглядный анимационный пример. Благо правила эти очень просты и лаконичны.
Ознакомились? Отлично, идем дальше.
Первый блин — комом
Первая версия программы была очень примитивна, и просто проверяла все возможные варианты решений слева-направо (в порядке следования столбцов). Брался исходный расклад, искался первый столбец, который позволял сделать разрешенный правилами ход, ход делался (виртуально), дальше шел рекурсивный возврат к первому пункту алгоритма, только теперь за базу бралось не исходное положение башен, а то, что получилось после сделанного хода.
И так много-много раз, банальное дерево решений.
Если на очередном ходе головоломка решалась (т.е. все башни оказывались собранными), то решение запоминалось с указанием количества ходов, на него потраченного. По итогам работы программы использовалось решение с наименьшим количеством ходов из найденных.
Одной из базовых оптимизаций стало обрубание веток ходов, чья длина превышала уже найденные решения, что вполне очевидно, т.к. проку от таких веток никакого.
Второй оптимизацией стала проверка на «блоки-соседи», т.е. блоки одинакового цвета с соседними цифрами, напр. 3 и 4. Поскольку такие блоки после складывания объединяются и могут перемещаться одновременно, я решил что всех «соседей» надо соединять всегда, как только появляется такая возможность, и не создавать лишние ветки вариантов. В итоге, если программа видела, например, красные 3 и 4, то она всегда сначала клала тройку на четверку, и только потом продолжала перебор. Это сильно сокращало время работы скрипта, т.к. чем больше блоков «слипались» вместе, тем меньше оставалось вариантов ходов.
Скрипт довольно сносно работал на «африканских» башнях (минимальный уровень сложности), находя решение за 1-2 минуты, а иногда и меньше. Однако на «ханойских» он уже задерживался минут на 15-30, а за «саровские» мне было даже страшно браться.
Кроме того, пару раз я замечал что программа, даже перебрав все возможные варианты, не может повторить результат, достигнутый игроками, и отстает от него на 1-2 хода. Как позже выяснилось, причиной этому стала моя оптимизация на «блоки-соседи», т.к. она основывалась только на моем эмпирическом предположении (я и сам так поступал когда играл своей «головой»), а не на каких-либо объективных доводах.
Однако, если совсем отключить эту оптимизацию, то время решения головоломок зашкаливало, и даже для африканских башен превышало 15 минут.
Надо было что-то менять.
Работа над ошибками
Во-первых, нужно было разобраться с вопросом склеивания «блоков-соседей». Проблема заключалась в том, что при их слиянии мы теряли «посадочное место» для более мелких блоков. Например, имея в разных столбцах «не склеенные» 4 и 5 одного цвета, мы могли на каждый из них класть блоки со значениями от нуля до трех, и работать с этими двумя наборами параллельно. Зачастую это было критично для экономии тех 1-2х ходов, которые приводили к оптимальному решению.
После определенных умозаключений я пришел к выводу, что мы можем безусловно склеивать лишь блоки, где верхний кирпич верхнего блока равен нулю или единице. Т.к. только в данном случае мы гарантированно не пострадаем от потери «посадочных мест» (на блок с нулевым кирпичиком сверху все равно больше ничего положить нельзя, а на блок с единицей можно положить только ноль, и следовательно нет нужды сохранять 2 «посадочных места», имея только один возможный вариант «посадочного блока»).
Во-вторых, необходимо было оптимизировать порядок обхода вариантов, т.к. перебор дерева слева-направо был крайне неэффективен в случаях, когда наилучший вариант находился как раз в правой части.
После каждого хода я стал оценивать «стоимость» текущего положения башен как разницу между общим количеством сделанных ходов на данный момент и количеством «слабых» ходов. Слабыми я называю промежуточные ходы, не приводящие сразу к желаемому результату (например, когда мы кладем красную тройку на пятерку, т.к. позже нам все равно придется переложить ее на четверку). Таким образом, наилучшую оценку имели варианты, обладающие наименьшим количеством слабых ходов по отношению к общему прогрессу решения.
Варианты ставятся в очередь с учетом своей стоимости, и в первую очередь решаются варианты с наилучшей оценкой, т.к. именно они имеют наибольшую вероятность превратиться в оптимальное решение. Сама по себе эта оптимизация бессмысленна, т.к. для гарантированного нахождения лучшего результата нам все равно необходимо перебрать все варианты, но в сочетании с отбрасыванием веток решений, превышающих по длине (и по стоимости) уже найденные, это позволило на порядки сократить время поиска, т.к. короткие (хотя и не всегда наилучшие) решения находились очень быстро, обычно в первые же секунды, после чего можно было сразу отбрасывать огромные ветки «длинных» решений, сосредотачиваясь на поиске оптимума.
Ну и третьим китом успеха стало случайное наблюдение о том, что разные ветки вариантов (даже с разным количеством ходов) могут приводить к одинаковым позициям башен. Очевидно, что дальнейшее развитие этих вариантов нет никакого резона рассматривать отдельно для каждой ветки, т.к. при одинаковой исходной позиции и дерево решений будет одинаковым.
Я стал делать текстовый слепок каждой позиции после каждого хода и заносить в хэш-таблицу (которая, как известно, лежит в основе работы объектов в JS, чем я и воспользовался). Оказалось, что таких веток-дублей значительно больше, чем я предполагал, и, отбрасывая их, удалось сократить время перебора еще в несколько раз.
Был еще ряд мелких оптимизаций, о которых вряд ли стоит тут упоминать, например защита от зацикливания ходов или от перекладывания блоков с одного пустого места на другое. Все это вполне очевидно и не влияет существенно на алгоритм.
Слава Роботам! Убить всех человеков!
Итоговый результат превзошел все мои ожидания. Скрипт решал большинство африканских башен за считанные секунды (1-3 в среднем), ханойские — в пределах 10 секунд, русские (саровские) — от 30 секунд до 10 минут в большинстве случаев, и 20-30 минут на самые сложные расклады, которые мне встречались, включая первую сотню из «усложненных» раскладов.
Как выяснилось, большинство башен среднего и сложного уровня решаются людьми не оптимально, даже с учетом соревновательного элемента (т.е. после того, как игроки несколько раз пытались превзойти результат друг друга). Обычно скрипт находит решение на 1-2, а порой и на 3-5 ходов короче, чем наилучший результат у людей.
Ну и разумеется по скорости нахождения решения железные мозги значительно опережают человеческие.
Некоторое время я развлекался, изображая из себя мега-мозг, но спустя неделю-другую каждодневных побед от ранее неизвестного игрока «пчелы начали что-то подозревать», да и процесс этот стал довольно скучным, как обычно и происходит если играть с «читами».
Чтобы результат двухдневных мозговых усилий не пропадал совсем уж зря, я решил рассказать эту историю здесь, на хабре, и выложить код программы в открытый доступ.
Объясню, почему я это делаю.
Игра сама по себе замечательная, и я хочу еще раз выразить благодарность ее создателю PapaBubaDiop, за неугасающий энтузиазм. Однако тот самый соревновательный элемент, который был призван стать ее изюминкой, может стать и ее проблемой. Совершенно очевидно на данный момент, что бота, быстро находящего наилучшее решение, создать можно, причем сделать это можно за довольно короткое время, и это под силу многим (хотя конечно и не всем). Лишний раз доказывает это тот факт, что хабраюзер Rois совсем недавно создал собственного бота, ничем не хуже моего (а может и лучше по скорости работы), видимо для того чтобы понять, могу ли быть ботом я.
Я пишу эту статью и выкладываю код для того, чтобы ребята, серьезно относящиеся к соревновательному элементу в этой игре понимали, что да — я могу быть ботом, Rois может быть ботом, кто угодно может быть ботом. И вы можете об этом никогда не узнать, если владелец бота поставит себе такую цель (есть куча способов выглядеть как человек, даже если ты бот). И чисто техническими средствами вы бота никак не выявите, и не остановите.
Можно лишь пересмотреть саму концепцию соревнований или отношение к их результатам.
P.S. Код я разумеется поддерживать не буду, и если например на сайте игры что-либо поменяют для того, чтобы он не смог считывать начальную позицию башен — желающие пусть исправляют это сами.
P.P.S. Чуть не забыл :) pastebin.com/AJyR2E71 — вот и код
