Атчод о ICFPC.
На этот ICFPC наша команда имела _план_. План заключался в том, чтобы забраться в какое-нибудь весьма отдалённое шале в горах (но при этом, разумеется, с интернетом) - чтобы в течение 72 часов ничто не могло отвлечь нас от героических поступков. Шале было найдено, план осуществлён, мы уселись в кресла и стали ждать начала задания.
Задание на этот раз оказалось простым и понятным даже с первого взгляда на спецификацию, в отличие от большинства предыдущих соревнований. Речь шла о добыче в шахтах Шотландии лямбд, необходимых для функциональных языков программирования, мировые запасы которых изрядно поистощились из-за активного использования. Через две минуты стало понятно, что задача сводится к написанию AI для эдакого походового Диггера.
- Лямбда один, лямбда два, и ещё семнадцать лямбдей!
А именно: даётся карта для прохождения её роботом-диггером, типа такой:
###############
#***...R......#
#***... ...*..#
#\\\... ..\\\.#
#...... ...*..#
#.. .. ...#
#.... .... ...#
#.... .... ...#
#.. . ..#
#..*. .. .....#
#.... .. .....#
#.\.. .......*#
#.............#
#......... .#
#############L#
(где R - робот, # - стена, . - земля, * - падающий как в диггере камень, \ - лямбда, которые надо собирать, и L - лифт, то есть выход с уровня, куда надо добраться, собрав все лямбды). Задача - найти оптимальную последовательность ходов, которая позволяет собрать максимальное количество лямбд и по возможности выбраться с уровня живым.
Например, решением для вышеописанного уровня является следующая последовательность ходов (U, D, L, R - это вверх, вниз, влево и вправо соответственно):
DDDLLLLLLURRRRRRRRRRRRDDDDDDDLLLLLLLLLLLDDDRRRRRRRRRRRD
Тут сразу стали понятными несколько вещей:
- Прошедшие стэндфордский AI Class или вообще когда-либо занимавшиеся искусственным идиотизмом обладают нечестным эдвентеджом по сравнению с прочими простыми смертными;
- AI Class ваш покорный слуга таки прошёл (Win!)
- ...тем не менее, как и полагается, содержание курса я забыл чуть менее чем совсем. Было бы гораздо больше пользы, если бы этот курс сдал какой-нибудь более умный (то есть любой другой) член команды (Fail!)
Помимо этого, коварные организаторы предупредили, что за время контеста спецификация будет обновляться и дополняться минимум четыре раза с новыми условиями, и поэтому было бы неплохо не слишком-то хардкорно хардкодить.
После недолгого обсуждения произвольно выбранных ключевых слов, по которым нужно будет искать в гугле алгоритмы и пейперы, мы решили для начала накодить эвалуатор, который будет брать на вход исходную карту и последовательность ходов, и показывать, выиграли мы и с каким счётом.
- Каждый раз, когда кто-то пишет var x, ivan_gandhi убивает котёнка!
Подключив один из ноутбуков к большому телевизору, и по очереди сменяя друг друга на программистском кресле, мы сделали в скале модель мира, команды, парсинг и печать состояний мира (с достаточно наивной и неоптимизированной реализацией, которая, конечно, никак не могла справиться с обещанными картами размером 1000x1000), на славу поизвращались с sbt (кто придумал это исчадие ада и назвал его "simple build tool"?), и через T+5.5 после начала контеста (или T+4.5 после начала программирования) эвалуатор у нас был. Организаторы, конечно, не преминули именно в этот момент обновить спецификацию и ввести туда «затопление» шахты (шотландцев колбасит), но наш код оказался довольно неплох и смог быть адаптирован к изменениям буквально за полчаса.
Поскольку эвалуатор умел выводить промежуточные состояния мира на экран, появилась идея быстро сделать интерпретатор, то есть игровой интерфейс, позволяющий управлять роботом прямо кнопками WASD, и жрать лямбды наглядно. Нашли метод clearScreen в jLine, и очень быстро сделали реализацию. На радостях решили руками неколько тестовых карт, предоставленных организаторами (а что там решать - ходи да уворачивайся от булыжников, точно как в настоящем диггере), отправили решения на тестовый сервер и с удивлением обнаружили, что верные решения отправили почти все команды. То есть наверняка зубры контеста сделали аналог нашему решению за первые час-полтора и уже вовсю кодят AI. Как теперь модно говорить, OPASNO!
Мы вымотались настолько, что Женя не смог придумать ничего лучше чем сделать запускалку интерпретатора (и будущего решателя) как таск в sbt, на что убил минимум час ценного времени. Опустим занавес сострадания над этой печальной историей - авторы sbt могли бы десятки раз перевернуться в гробу, если бы он у них был.
Следующей задачей было сделать хоть какой-нибудь автоматический солвер, который Влад со свойственным ему оптимизмом назвал «недотыкомка». Высказывались самые безумные идеи, типа random walk'а с бектрегингом, и в конечном итоге мы остановились на простейшем генетическом алгоритме. А завтра, вероятно, нужно будет заняться Q-learning.
На этом ответственном моменте (T+10) я пошёл спать, а Саша с Женей остались писать генетический солвер.
День 2.
- Интегрировай!
Проснувшись, мы обнаружили, что ivan_gandhi не дремал, а, видимо, ужаснулся нашему коду и отрефакторил всё из одного огромного scala-блоба в различные файлы, и даже покрыл эвалуатор красивыми юнит-тестами. На интегрирование полученной благодати с помошью Жени, cake pattern'а и какой-то матери ушло буквально часа полтора. Сразу же после этого мы ударно навалились на генетический солвер, и успели упаковать и сдать тормозную и практически ничего не умеющую версию (но получающую какие-то очки на каких-то картах) в lightning round. За пять минут до его окончания, разумеется.
Во сне я подумал о разных OPASNOстях, подстерегающих нашего будущего искусственного идиота в решении разных хитрозакрученных карт. Например, с организаторов станется сделать принципиально недостижимую замкнутую область, наполненную лямбдами и лифтами, к которой обязательно (и бессмысленно) будет стремится наш наивный оценщик позиции, если каждый раз не использовать pathfinding (а это совершенно не уместится в отведённое время на больших картах). Помимо прочего, вожделенные лямбды могут находиться настолько далеко, что идти к ним не имеет никакого смысла (при каждом ходе очки тратятся), при этом, опять же, физически это может быть клетка совсем рядом, но к ней ведёт огромный запутанный лабиринт - и т.д. Могут существовать ловушки в виде кучки лямбд, защищённых всегда убиваюшими робота камнями, или даже достаточно одного камня, запирающего выход из области. В общем, на месте разработчиков я мог бы придумать немало гадостей, работающих даже против самых продвинутых планировщиков - и нет никаких оснований думать, что они не поступят именно так. Вооружённые этими знаниями, мы пошли встречать приехавшую к нам fea_dreams.
К этому времени стали понятны некоторые очевидные улучшения, которые можно вставить в генетический алгоритм, чтобы он работал в чуть большем количестве случаев. Например, если над нами находится камень, то ни в коем случае нельзя ходить вниз, а если мы заходим под камень, то надо обязательно проверять, что мы собираемся делать дальше, и т.д. Генетические алгоритмы начали работать пободрее и даже собирать все лямбды из задания в спецификации, но ещё не могли дойти с добычей до открывшегося лифта (сначала по причине помирания под последним камнем, потом - по причине отсутствия эвристики, показывающей маршрут к оному лифту).
Коварные организаторы ввели новый тип карт - с телепортерами (при этом исчезающими после использования, чтобы pathfinder'ам жизнь мёдом не казалась). Мы чертыхнулись и пошли кодить дальше.
ivan_gandhi в это время адаптировал алгоритмы minimum spanning tree и другие умные слова, которые мы не знаем. akuklev решил написать, наконец, pathfinder и блестяще справился с задачей. После чего нужно было начать его использовать. Решили для начала собирать максимум лямбд генетическим алгоритмом, и если они все собраны, пилить напрямую в сторону выхода. Но интеграция pathfinder'а почему-то заняла куда больше времени, чем планировалось. Не дождавшись результата, мы с xeno_by пошли спать, оставив akuklev добиваться каких-то эффектов.
Перед самым отходом ко сну у меня появилась идея оценивать gamestate эвристически, наподобие позиции в шахматах. Учитывать расстояние до ближайшей лямбды (а лучше - наличие пути к ней за максимум M ходов, что ложилось на pathfinder с довольно большой производительностью), количество оставшихся лямбд, расстояние до лифта, а в перспективе - затопленность и whatsnot. Но думать над её реализацией и применением (в Q-learning пихать?) я был уже не в состоянии.
День 3 и 3.5.
- Очень жаль. :(
Проснувшись, я обнаружил, что Куклев таки довёл свой генетический алгоритм до состояния, в котором он решает карту из спецификации на отличненько. Это плюс. Минус заключался в том, что для этой довольно скромной карты процесс решения занимал секунд сорок, не менее, поэтому решения особо больших карт мы дожидались бы до второго пришествия (if any). ivan_gandhi параллельно закоммитил свой алгоритм на A*, но он не работал.
Пришлось убеждать xeno_by, что нам нужен глобальный скоринг, описанный в окончании предыдущего дня. xeno_by довольно быстро убедился, но инициатива наказуема, поэтому писать код он посадил меня. Впрочем, если скоринг-функцию я написал довольно быстро, то на генерации дерева ходов с их перебором и отсечением мой моск забуксовал, и последние эндцать строчек я писал под Женину диктовку в режиме «конец тридцать восьмой строчки, энтер, вал икс равно...» Элементы скоринга выглядели так:
// limited path to nearest lambda
// lambdas collected
// lift is open? then distance to lift
// robot is no more :(
Мы перебирали последовательность из N ходов и выбирали ту, которая даёт в сумме максимальный score. Карту из спецификации алгоритм быстренько решил на отлично, примерно вдесятеро быстрее чем куклевский генетический алгоритм. Но уже на третьей карте робот бодро уткнулся в тупик рядом с ближайшей лямбдой, и пытался пробить лбом стенку. Пришлось выразить расстояние до ближайшей лямбды не напрямую, а через реализованный к тому времени Куклевым алгоритм Дейкстры (почему не A*? Потому что Куклев считал, что A* с динамической картой будет не киргуду, а тем более с бородами и телепортерами - убедить его отвлечься от топографии и осмыслить ситуацию как граф состояний мне так и не удалось).
К середине дня мы окончательно выбились из сил, настроение было паническое, поэтому мы ушли гулять в горы и смотреть футураму, не помню в какой последовательности. После твикинга скоринг-функции, багфиксов в Дейкстре (особо тупые баги - перепутанные ширина с высотой и невозможность подсчёта расстояния на больше чем h + w клеточек). К вечеру, наконец, всё было починено, а Влад сделал параллельный алгоритм на A*, который, увы, на тот момент не работал. Все задолбались и ушли спать. :(
Проснувшись, я осознал, что если ввести в функцию скоринга количество доступных (по Дейкстре) лямбд, робот сможет отодвигать камни от наиболее очевидных проходов. Так и вышло (ещё плюс два часа на реализацию). Влад таки пофиксал A* с поиском на графах и аспирантками калифорнийских университетов, но он зависал на шестой карте - а miscommunication и разница временных зон не дали возможности совместно починить это). Решили сдавать мой скоринг, названный почему-то в запале chess. Потом, наконец, нужно было привинтить адекватную реакцию программы на SIGINT, и с помощью Куклева это удалось - за пять минут до дедлайна. Залили, сдали, приготовили накладной фейспалм, потому что мы лохи.
Ошибки, в ретроспективе:
- Работать надо интенсивнее; отдых и сон на ICFPC are much overrated;
- Надо было сразу сказать Куклеву, что генетические алгоритмы не прокатят. Во мне взыграло естественное любопытство на тему «вдруг получится?»
- Идея со скорингом должна была прийти ко мне на первый день, а не на третий;
- Самое главное - я должен был бы вспомнить хоть что-нибудь из того, чему меня учили в ai-class, а не просто травить всех словами типа "Q-learning!" или там "MDP!".
- Если вас зовут не Дмитрий Астапов, не следует работать в одиночестве. Равно не следует оставлять членов команды, не справлясь постоянно о их статусе и не предлагая помощь.
О прохождении четверьфинала, думаю, не идёт и речи.
До встречи через год.
Задание на этот раз оказалось простым и понятным даже с первого взгляда на спецификацию, в отличие от большинства предыдущих соревнований. Речь шла о добыче в шахтах Шотландии лямбд, необходимых для функциональных языков программирования, мировые запасы которых изрядно поистощились из-за активного использования. Через две минуты стало понятно, что задача сводится к написанию AI для эдакого походового Диггера.
- Лямбда один, лямбда два, и ещё семнадцать лямбдей!
А именно: даётся карта для прохождения её роботом-диггером, типа такой:
###############
#***...R......#
#***... ...*..#
#\\\... ..\\\.#
#...... ...*..#
#.. .. ...#
#.... .... ...#
#.... .... ...#
#.. . ..#
#..*. .. .....#
#.... .. .....#
#.\.. .......*#
#.............#
#......... .#
#############L#
(где R - робот, # - стена, . - земля, * - падающий как в диггере камень, \ - лямбда, которые надо собирать, и L - лифт, то есть выход с уровня, куда надо добраться, собрав все лямбды). Задача - найти оптимальную последовательность ходов, которая позволяет собрать максимальное количество лямбд и по возможности выбраться с уровня живым.
Например, решением для вышеописанного уровня является следующая последовательность ходов (U, D, L, R - это вверх, вниз, влево и вправо соответственно):
DDDLLLLLLURRRRRRRRRRRRDDDDDDDLLLLLLLLLLLDDDRRRRRRRRRRRD
Тут сразу стали понятными несколько вещей:
- Прошедшие стэндфордский AI Class или вообще когда-либо занимавшиеся искусственным идиотизмом обладают нечестным эдвентеджом по сравнению с прочими простыми смертными;
- AI Class ваш покорный слуга таки прошёл (Win!)
- ...тем не менее, как и полагается, содержание курса я забыл чуть менее чем совсем. Было бы гораздо больше пользы, если бы этот курс сдал какой-нибудь более умный (то есть любой другой) член команды (Fail!)
Помимо этого, коварные организаторы предупредили, что за время контеста спецификация будет обновляться и дополняться минимум четыре раза с новыми условиями, и поэтому было бы неплохо не слишком-то хардкорно хардкодить.
После недолгого обсуждения произвольно выбранных ключевых слов, по которым нужно будет искать в гугле алгоритмы и пейперы, мы решили для начала накодить эвалуатор, который будет брать на вход исходную карту и последовательность ходов, и показывать, выиграли мы и с каким счётом.
- Каждый раз, когда кто-то пишет var x, ivan_gandhi убивает котёнка!
Подключив один из ноутбуков к большому телевизору, и по очереди сменяя друг друга на программистском кресле, мы сделали в скале модель мира, команды, парсинг и печать состояний мира (с достаточно наивной и неоптимизированной реализацией, которая, конечно, никак не могла справиться с обещанными картами размером 1000x1000), на славу поизвращались с sbt (кто придумал это исчадие ада и назвал его "simple build tool"?), и через T+5.5 после начала контеста (или T+4.5 после начала программирования) эвалуатор у нас был. Организаторы, конечно, не преминули именно в этот момент обновить спецификацию и ввести туда «затопление» шахты (шотландцев колбасит), но наш код оказался довольно неплох и смог быть адаптирован к изменениям буквально за полчаса.
Поскольку эвалуатор умел выводить промежуточные состояния мира на экран, появилась идея быстро сделать интерпретатор, то есть игровой интерфейс, позволяющий управлять роботом прямо кнопками WASD, и жрать лямбды наглядно. Нашли метод clearScreen в jLine, и очень быстро сделали реализацию. На радостях решили руками неколько тестовых карт, предоставленных организаторами (а что там решать - ходи да уворачивайся от булыжников, точно как в настоящем диггере), отправили решения на тестовый сервер и с удивлением обнаружили, что верные решения отправили почти все команды. То есть наверняка зубры контеста сделали аналог нашему решению за первые час-полтора и уже вовсю кодят AI. Как теперь модно говорить, OPASNO!
Мы вымотались настолько, что Женя не смог придумать ничего лучше чем сделать запускалку интерпретатора (и будущего решателя) как таск в sbt, на что убил минимум час ценного времени. Опустим занавес сострадания над этой печальной историей - авторы sbt могли бы десятки раз перевернуться в гробу, если бы он у них был.
Следующей задачей было сделать хоть какой-нибудь автоматический солвер, который Влад со свойственным ему оптимизмом назвал «недотыкомка». Высказывались самые безумные идеи, типа random walk'а с бектрегингом, и в конечном итоге мы остановились на простейшем генетическом алгоритме. А завтра, вероятно, нужно будет заняться Q-learning.
На этом ответственном моменте (T+10) я пошёл спать, а Саша с Женей остались писать генетический солвер.
День 2.
- Интегрировай!
Проснувшись, мы обнаружили, что ivan_gandhi не дремал, а, видимо, ужаснулся нашему коду и отрефакторил всё из одного огромного scala-блоба в различные файлы, и даже покрыл эвалуатор красивыми юнит-тестами. На интегрирование полученной благодати с помошью Жени, cake pattern'а и какой-то матери ушло буквально часа полтора. Сразу же после этого мы ударно навалились на генетический солвер, и успели упаковать и сдать тормозную и практически ничего не умеющую версию (но получающую какие-то очки на каких-то картах) в lightning round. За пять минут до его окончания, разумеется.
Во сне я подумал о разных OPASNOстях, подстерегающих нашего будущего искусственного идиота в решении разных хитрозакрученных карт. Например, с организаторов станется сделать принципиально недостижимую замкнутую область, наполненную лямбдами и лифтами, к которой обязательно (и бессмысленно) будет стремится наш наивный оценщик позиции, если каждый раз не использовать pathfinding (а это совершенно не уместится в отведённое время на больших картах). Помимо прочего, вожделенные лямбды могут находиться настолько далеко, что идти к ним не имеет никакого смысла (при каждом ходе очки тратятся), при этом, опять же, физически это может быть клетка совсем рядом, но к ней ведёт огромный запутанный лабиринт - и т.д. Могут существовать ловушки в виде кучки лямбд, защищённых всегда убиваюшими робота камнями, или даже достаточно одного камня, запирающего выход из области. В общем, на месте разработчиков я мог бы придумать немало гадостей, работающих даже против самых продвинутых планировщиков - и нет никаких оснований думать, что они не поступят именно так. Вооружённые этими знаниями, мы пошли встречать приехавшую к нам fea_dreams.
К этому времени стали понятны некоторые очевидные улучшения, которые можно вставить в генетический алгоритм, чтобы он работал в чуть большем количестве случаев. Например, если над нами находится камень, то ни в коем случае нельзя ходить вниз, а если мы заходим под камень, то надо обязательно проверять, что мы собираемся делать дальше, и т.д. Генетические алгоритмы начали работать пободрее и даже собирать все лямбды из задания в спецификации, но ещё не могли дойти с добычей до открывшегося лифта (сначала по причине помирания под последним камнем, потом - по причине отсутствия эвристики, показывающей маршрут к оному лифту).
Коварные организаторы ввели новый тип карт - с телепортерами (при этом исчезающими после использования, чтобы pathfinder'ам жизнь мёдом не казалась). Мы чертыхнулись и пошли кодить дальше.
ivan_gandhi в это время адаптировал алгоритмы minimum spanning tree и другие умные слова, которые мы не знаем. akuklev решил написать, наконец, pathfinder и блестяще справился с задачей. После чего нужно было начать его использовать. Решили для начала собирать максимум лямбд генетическим алгоритмом, и если они все собраны, пилить напрямую в сторону выхода. Но интеграция pathfinder'а почему-то заняла куда больше времени, чем планировалось. Не дождавшись результата, мы с xeno_by пошли спать, оставив akuklev добиваться каких-то эффектов.
Перед самым отходом ко сну у меня появилась идея оценивать gamestate эвристически, наподобие позиции в шахматах. Учитывать расстояние до ближайшей лямбды (а лучше - наличие пути к ней за максимум M ходов, что ложилось на pathfinder с довольно большой производительностью), количество оставшихся лямбд, расстояние до лифта, а в перспективе - затопленность и whatsnot. Но думать над её реализацией и применением (в Q-learning пихать?) я был уже не в состоянии.
День 3 и 3.5.
- Очень жаль. :(
Проснувшись, я обнаружил, что Куклев таки довёл свой генетический алгоритм до состояния, в котором он решает карту из спецификации на отличненько. Это плюс. Минус заключался в том, что для этой довольно скромной карты процесс решения занимал секунд сорок, не менее, поэтому решения особо больших карт мы дожидались бы до второго пришествия (if any). ivan_gandhi параллельно закоммитил свой алгоритм на A*, но он не работал.
Пришлось убеждать xeno_by, что нам нужен глобальный скоринг, описанный в окончании предыдущего дня. xeno_by довольно быстро убедился, но инициатива наказуема, поэтому писать код он посадил меня. Впрочем, если скоринг-функцию я написал довольно быстро, то на генерации дерева ходов с их перебором и отсечением мой моск забуксовал, и последние эндцать строчек я писал под Женину диктовку в режиме «конец тридцать восьмой строчки, энтер, вал икс равно...» Элементы скоринга выглядели так:
// limited path to nearest lambda
// lambdas collected
// lift is open? then distance to lift
// robot is no more :(
Мы перебирали последовательность из N ходов и выбирали ту, которая даёт в сумме максимальный score. Карту из спецификации алгоритм быстренько решил на отлично, примерно вдесятеро быстрее чем куклевский генетический алгоритм. Но уже на третьей карте робот бодро уткнулся в тупик рядом с ближайшей лямбдой, и пытался пробить лбом стенку. Пришлось выразить расстояние до ближайшей лямбды не напрямую, а через реализованный к тому времени Куклевым алгоритм Дейкстры (почему не A*? Потому что Куклев считал, что A* с динамической картой будет не киргуду, а тем более с бородами и телепортерами - убедить его отвлечься от топографии и осмыслить ситуацию как граф состояний мне так и не удалось).
К середине дня мы окончательно выбились из сил, настроение было паническое, поэтому мы ушли гулять в горы и смотреть футураму, не помню в какой последовательности. После твикинга скоринг-функции, багфиксов в Дейкстре (особо тупые баги - перепутанные ширина с высотой и невозможность подсчёта расстояния на больше чем h + w клеточек). К вечеру, наконец, всё было починено, а Влад сделал параллельный алгоритм на A*, который, увы, на тот момент не работал. Все задолбались и ушли спать. :(
Проснувшись, я осознал, что если ввести в функцию скоринга количество доступных (по Дейкстре) лямбд, робот сможет отодвигать камни от наиболее очевидных проходов. Так и вышло (ещё плюс два часа на реализацию). Влад таки пофиксал A* с поиском на графах и аспирантками калифорнийских университетов, но он зависал на шестой карте - а miscommunication и разница временных зон не дали возможности совместно починить это). Решили сдавать мой скоринг, названный почему-то в запале chess. Потом, наконец, нужно было привинтить адекватную реакцию программы на SIGINT, и с помощью Куклева это удалось - за пять минут до дедлайна. Залили, сдали, приготовили накладной фейспалм, потому что мы лохи.
Ошибки, в ретроспективе:
- Работать надо интенсивнее; отдых и сон на ICFPC are much overrated;
- Надо было сразу сказать Куклеву, что генетические алгоритмы не прокатят. Во мне взыграло естественное любопытство на тему «вдруг получится?»
- Идея со скорингом должна была прийти ко мне на первый день, а не на третий;
- Самое главное - я должен был бы вспомнить хоть что-нибудь из того, чему меня учили в ai-class, а не просто травить всех словами типа "Q-learning!" или там "MDP!".
- Если вас зовут не Дмитрий Астапов, не следует работать в одиночестве. Равно не следует оставлять членов команды, не справлясь постоянно о их статусе и не предлагая помощь.
О прохождении четверьфинала, думаю, не идёт и речи.
До встречи через год.