ICFPC 2012. Как мы дерево из массива вырастили!
Итак, после первого раунда мы, hack the loop, 15-ые! Значит все таки надо написать отчёт. Впрочем впереди нас ждет ещё один отборочный тур, в котором отсеют ещё половину участников, а потом финальный тур, результаты которого мы узнаем лишь осенью во время конференции ICFP 2012.
Team
В этот раз играли большой толпой в 6 человек, очно в Контуровском офисе на Радищева, на территории проекта Диадок. В команде было 5 контуровцев и 2 экс-контуровца:
Я - @xoposhiy - визуализатор, поиск путей, перебор вариантов.
Леша @mogilnikov - генератор карт, надмозг - высокоуровневый перебор вариантов.
Андрей @AndrewKostousov - тестирование корректности, квадродерево (читай ниже), отладка всего.
Саша @AlexFetisov - логика игры, квадродерево.
Миша @Michael_Khr - логика игры, толкание камней, бритьё бород и прочие хитрости.
Дима Титаренко - взаимодействие с официальным эмулятором, борьба с наводнениями.
Ваня @i_komarov - мужественная борьба с ангиной у себя дома :(
Получилось очень слажено - почти никогда никто не бездействовал, почти ничего не написали “в стол” - все использовалось.
На заметку последователям: собирать большую команду лучше сильно заранее - хотя бы за месяц до. Иначе у всех внезапно оказываются планы на выходные.
Rules
Для тех, кто ещё не в курсе, в этот раз надо было написать искусственный интеллект для игры, очень похожую на Boulder dash / диггер (кушаем землю, собираем ништяки, роняем и толкаем камушки, сбегаем после всего этого в лифт). Причем организаторы обещали запускать все это на очень больших картах, так что игра была скорее про быстро работающие эвристики, а не про полный перебор.
Отдельный хардкор был в том, что четырежды к спецификации игры были дополнения, вводящие в игру новые активные элементы - потопы, телепорты, бороды/бритвы и камнелямбды. Иногда приходилось изо всех сил бежать, чтобы только оставаться на месте.
Поиграться самостоятельно в эту игру по всем правилам можно на неофициальном симуляторе
Action
Но правила игры - это вторично! Какие бы они ни были, в ICFPC вам в любом случае нужно будет написать следующие компоненты:
1. Эмулятор чего-то, что описано в спецификации.
2. Визуализатор, чтобы вы могли смотреть на поведение вашего AI глазками (Без этого никак! И если вы думаете, что это не так, знайте - это так! (с))
3. Тесты, проверяющие корректность вашего эмулятора (баги будут обязательно!)
4. Тест, измеряющий эффективность вашего AI (чтобы в последний момент не сделать смертельное “ещё одно маленькое улучшение”)
5. И собственно сам AI.
На этот раз в рамках п.4 мы написали ещё и
6. Генератор чего-то, с чем ваш AI будет сражаться (в нашем случае - генератор карт)
Но в этой части отчетика я расскажу лишь про одну забавную и поучительную компоненту нашего решения!
Карта, Билли, нам нужна карта!
Эмулятор в нашем случае представлял собой класс Map - игровое поле и по совместительству нечто, знающее все правила игры. Map - это что-то с методом Cell Get(x, y), методом void ApplyMove(lifterMove) и прочими менее важными штуками.
Для людей не зараженных идеями функционального программирования, должно казаться очевидным, что Map - это что-то с двумерным массивом ячеек внутри, а метод ApplyMove просто меняет значения затронутых ячеек.
Так было и у нас до тех пор, пока я не понес свет в массы ;-) Под действием света массив мутировал... во что же он мутировал? Читайте далее после рекламы!
Mutability sucks!
Проблема этого императивного подхода в том, что для реализации AI нужно так или иначе устраивать перебор ходов. А перебор состоит не только из применения ходов, но и из их откатов! А откатывать ходы при такой реализации довольно муторно - нужно запоминать что и как мы изменили на каждом шагу и как это что-то откатить. По факту, это много кода, подверженного трудноуловимым ошибкам + необходимость при переборах не забывать откатывать кому надо сделанные ходы. Ну и вообще! Откаты это плохо!
Подход функционального программирования ближе к тому, что делают в своих доказательствах математики. Давайте сделаем ApplyMove “математической” функцией, которая не будет иметь побочных эффектов, а будет просто возвращать новую версию карты. Например, просто скопировав тот большой двумерный массив ячеек и сделав в нем нужные изменения.
Вы скажете, медленно? Да! Но давайте пока забудем про скорость и посмотрим на плюсы.
А главный плюс в том, что больше не нужен код для отката ходов. Более того, не нужно нигде помнить про то, что что-то где-то нужно откатывать. Достаточно просто сохранять карты, к которым потом захочется ещё раз вернуться. Структуры данных, которые не изменяются в результате операций над ними и, как следствие кроме своего текущего состояния способные помнить всю свою историю, принято называть то ли persistent, то ли pure functional, то ли immutable. Честно говоря я в тонкостях этих терминов не очень разбираюсь, так что скажем просто - immutable pure functional persistent data structure :) Кстати, если кто-то чувствует тонкости различия этих терминов - буду благодарен за разъяснения в комментах!
ОК, но как же сделать ApplyMove быстрым?
Первая идея была такая: давайте ApplyMove не будет копировать всю карту, а будет хранить ссылку на предыдущий map и patch к нему. После того, как накопилось уже много патчей, разом их применять. Когда я эту идею попытался озвучить, меня быстро убедили, что это а) слишком сложно, б) с непонятной асимптотикой в) и вообще, блин! Последний аргумент подействовал и я уже почти было смирился с mutable-реализацией Map, но на следующее утро...
Сорока на хвосте принесла
На следующее утро, на пути в офис я читал твиттер по хештегу #icfpc. И успел дочитать до твита “Вау! Я за пару строк кода добавил супербыструю возможность откатывать карту на сколько угодно ходов назад!”.
“Вот блин!”, подумал я! “Ведь не иначе чел таки взял и реализовал карту как immutable pure functional persistent data structure!” Это был вызов! Буквально через минуту после которого, на ум пришла так называемая корневая оптимизация, а потом уже и логарифмическое квадродерево не заставило себя ждать!
Итак, корневая оптимизация
Идея очень простая. Пусть карта размера N*N. Разобьем ее на квадратики размером sqrt(N) х sqrt(N). Тогда карта - это двумерный массив sqrt(N) x sqrt(N) таких квадратиков. И если после хода некоторые квадратики не изменились, то их можно не копировать в новую карту, а просто сохранить в ней ссылки на те же самые квадратики. И если отталкиваться от того, что каждый ход в среднем меняется очень мало ячеек, то копирований придется сделать всего порядка O(sqrt(N) х sqrt(N)), вместо O(N x N).
На сколько я знаю, “корневая оптимизация” - это сленг ACM-щиков (опять же заранее спасибо тем, кто меня в этом разубедит в комментах, раскрыв правильный первоисточник). Так называют любой подход, в котором большая (N) задача делится на корень из N задач, каждая размером корень из N. Этим достигается снижение сложности алгоритма в корень из N раз. Как правило, любая такая оптимизация может быть развита до логарифмической, но на ACM-соревнованиях иногда быстро написать простую корневую правильнее, чем долго писать сложную логарифмическую.
Корень дереву голова!
Переход к логарифмической оптимизации тоже очень прост. Давайте мы будем бить карту не на sqrt(N) x sqrt(N) квадратиков, а всего на 4 квадратика размером N/2 x N/2. Но только каждый такой квадратик мы разобьем ещё на 4. А те ещё на 4. И так до тех пор, пока очередной квадратик не окажется единичного размера - в таком узле мы и будем хранить собственно информацию о том, что находится в этой ячейке. Получится дерево, у каждого узла которого может быть до 4-х детей, а вся реальная информация хранится в листьях. Как-то примерно вот так:
А дальше все то же самое - при применении хода, будем заменять только те квадратики, в составе которых хоть что-то поменялось. В принципе эта техника - не менять, а создавать новые узлы дерева, если что-то поменялось - применима к любым деревьям и хорошо иллюстрируется картинкой по типу вот этой из википедии:
Из картинки должно быть понятно, что при изменении одной ячейки карты, поменяется лишь O(высота дерева) = O(log N) узлов дерева. Win!
Получается очень забавная структура данных по семантике как двумерный массив, но хранящая историю всех состояний этого массива.
Поскольку тем же утром Андрей уж очень хотел тотально отрефакторить наш Map, в котором постоянно всплывали какие-то мелкие ошибки, то под шумок вкрутить туда квадродерево.
Но понятно, что дерево, каким бы логарифмическим оно ни было, медленнее простого массива. Квадродерево замедлило наше решение на разных картах в полтора - три раза по сравнению с mutable версией с двумерным массивом и откатами. Но мы всей командой сказали твердое “нет” откатам! :-) По факту, после перехода на квадродерево у нас разом пропали все многочисленные мелкие баги с откатами наводнений и прочих телепортов, а также убилось довольно много кода, в котором, видимо, эти баги и жили.
Такая вот поучительная история. А если мы пройдем в следующий тур - напишу ещё какую-нибудь поучительную историю из нашего участия :)
Ссылки для детального изучения:
* ICFPC 2012 Task
* Наша версия QTree на github.com
* Immutable data structures in C#
Team
В этот раз играли большой толпой в 6 человек, очно в Контуровском офисе на Радищева, на территории проекта Диадок. В команде было 5 контуровцев и 2 экс-контуровца:
Я - @xoposhiy - визуализатор, поиск путей, перебор вариантов.
Леша @mogilnikov - генератор карт, надмозг - высокоуровневый перебор вариантов.
Андрей @AndrewKostousov - тестирование корректности, квадродерево (читай ниже), отладка всего.
Саша @AlexFetisov - логика игры, квадродерево.
Миша @Michael_Khr - логика игры, толкание камней, бритьё бород и прочие хитрости.
Дима Титаренко - взаимодействие с официальным эмулятором, борьба с наводнениями.
Ваня @i_komarov - мужественная борьба с ангиной у себя дома :(
Получилось очень слажено - почти никогда никто не бездействовал, почти ничего не написали “в стол” - все использовалось.
На заметку последователям: собирать большую команду лучше сильно заранее - хотя бы за месяц до. Иначе у всех внезапно оказываются планы на выходные.
Rules
Для тех, кто ещё не в курсе, в этот раз надо было написать искусственный интеллект для игры, очень похожую на Boulder dash / диггер (кушаем землю, собираем ништяки, роняем и толкаем камушки, сбегаем после всего этого в лифт). Причем организаторы обещали запускать все это на очень больших картах, так что игра была скорее про быстро работающие эвристики, а не про полный перебор.
Отдельный хардкор был в том, что четырежды к спецификации игры были дополнения, вводящие в игру новые активные элементы - потопы, телепорты, бороды/бритвы и камнелямбды. Иногда приходилось изо всех сил бежать, чтобы только оставаться на месте.
Поиграться самостоятельно в эту игру по всем правилам можно на неофициальном симуляторе
Action
Но правила игры - это вторично! Какие бы они ни были, в ICFPC вам в любом случае нужно будет написать следующие компоненты:
1. Эмулятор чего-то, что описано в спецификации.
2. Визуализатор, чтобы вы могли смотреть на поведение вашего AI глазками (Без этого никак! И если вы думаете, что это не так, знайте - это так! (с))
3. Тесты, проверяющие корректность вашего эмулятора (баги будут обязательно!)
4. Тест, измеряющий эффективность вашего AI (чтобы в последний момент не сделать смертельное “ещё одно маленькое улучшение”)
5. И собственно сам AI.
На этот раз в рамках п.4 мы написали ещё и
6. Генератор чего-то, с чем ваш AI будет сражаться (в нашем случае - генератор карт)
Но в этой части отчетика я расскажу лишь про одну забавную и поучительную компоненту нашего решения!
Карта, Билли, нам нужна карта!
Эмулятор в нашем случае представлял собой класс Map - игровое поле и по совместительству нечто, знающее все правила игры. Map - это что-то с методом Cell Get(x, y), методом void ApplyMove(lifterMove) и прочими менее важными штуками.
Для людей не зараженных идеями функционального программирования, должно казаться очевидным, что Map - это что-то с двумерным массивом ячеек внутри, а метод ApplyMove просто меняет значения затронутых ячеек.
Так было и у нас до тех пор, пока я не понес свет в массы ;-) Под действием света массив мутировал... во что же он мутировал? Читайте далее после рекламы!
Mutability sucks!
Проблема этого императивного подхода в том, что для реализации AI нужно так или иначе устраивать перебор ходов. А перебор состоит не только из применения ходов, но и из их откатов! А откатывать ходы при такой реализации довольно муторно - нужно запоминать что и как мы изменили на каждом шагу и как это что-то откатить. По факту, это много кода, подверженного трудноуловимым ошибкам + необходимость при переборах не забывать откатывать кому надо сделанные ходы. Ну и вообще! Откаты это плохо!
Подход функционального программирования ближе к тому, что делают в своих доказательствах математики. Давайте сделаем ApplyMove “математической” функцией, которая не будет иметь побочных эффектов, а будет просто возвращать новую версию карты. Например, просто скопировав тот большой двумерный массив ячеек и сделав в нем нужные изменения.
Вы скажете, медленно? Да! Но давайте пока забудем про скорость и посмотрим на плюсы.
А главный плюс в том, что больше не нужен код для отката ходов. Более того, не нужно нигде помнить про то, что что-то где-то нужно откатывать. Достаточно просто сохранять карты, к которым потом захочется ещё раз вернуться. Структуры данных, которые не изменяются в результате операций над ними и, как следствие кроме своего текущего состояния способные помнить всю свою историю, принято называть то ли persistent, то ли pure functional, то ли immutable. Честно говоря я в тонкостях этих терминов не очень разбираюсь, так что скажем просто - immutable pure functional persistent data structure :) Кстати, если кто-то чувствует тонкости различия этих терминов - буду благодарен за разъяснения в комментах!
ОК, но как же сделать ApplyMove быстрым?
Первая идея была такая: давайте ApplyMove не будет копировать всю карту, а будет хранить ссылку на предыдущий map и patch к нему. После того, как накопилось уже много патчей, разом их применять. Когда я эту идею попытался озвучить, меня быстро убедили, что это а) слишком сложно, б) с непонятной асимптотикой в) и вообще, блин! Последний аргумент подействовал и я уже почти было смирился с mutable-реализацией Map, но на следующее утро...
Сорока на хвосте принесла
На следующее утро, на пути в офис я читал твиттер по хештегу #icfpc. И успел дочитать до твита “Вау! Я за пару строк кода добавил супербыструю возможность откатывать карту на сколько угодно ходов назад!”.
“Вот блин!”, подумал я! “Ведь не иначе чел таки взял и реализовал карту как immutable pure functional persistent data structure!” Это был вызов! Буквально через минуту после которого, на ум пришла так называемая корневая оптимизация, а потом уже и логарифмическое квадродерево не заставило себя ждать!
Итак, корневая оптимизация
Идея очень простая. Пусть карта размера N*N. Разобьем ее на квадратики размером sqrt(N) х sqrt(N). Тогда карта - это двумерный массив sqrt(N) x sqrt(N) таких квадратиков. И если после хода некоторые квадратики не изменились, то их можно не копировать в новую карту, а просто сохранить в ней ссылки на те же самые квадратики. И если отталкиваться от того, что каждый ход в среднем меняется очень мало ячеек, то копирований придется сделать всего порядка O(sqrt(N) х sqrt(N)), вместо O(N x N).
На сколько я знаю, “корневая оптимизация” - это сленг ACM-щиков (опять же заранее спасибо тем, кто меня в этом разубедит в комментах, раскрыв правильный первоисточник). Так называют любой подход, в котором большая (N) задача делится на корень из N задач, каждая размером корень из N. Этим достигается снижение сложности алгоритма в корень из N раз. Как правило, любая такая оптимизация может быть развита до логарифмической, но на ACM-соревнованиях иногда быстро написать простую корневую правильнее, чем долго писать сложную логарифмическую.
Корень дереву голова!
Переход к логарифмической оптимизации тоже очень прост. Давайте мы будем бить карту не на sqrt(N) x sqrt(N) квадратиков, а всего на 4 квадратика размером N/2 x N/2. Но только каждый такой квадратик мы разобьем ещё на 4. А те ещё на 4. И так до тех пор, пока очередной квадратик не окажется единичного размера - в таком узле мы и будем хранить собственно информацию о том, что находится в этой ячейке. Получится дерево, у каждого узла которого может быть до 4-х детей, а вся реальная информация хранится в листьях. Как-то примерно вот так:
А дальше все то же самое - при применении хода, будем заменять только те квадратики, в составе которых хоть что-то поменялось. В принципе эта техника - не менять, а создавать новые узлы дерева, если что-то поменялось - применима к любым деревьям и хорошо иллюстрируется картинкой по типу вот этой из википедии:
Из картинки должно быть понятно, что при изменении одной ячейки карты, поменяется лишь O(высота дерева) = O(log N) узлов дерева. Win!
Получается очень забавная структура данных по семантике как двумерный массив, но хранящая историю всех состояний этого массива.
Поскольку тем же утром Андрей уж очень хотел тотально отрефакторить наш Map, в котором постоянно всплывали какие-то мелкие ошибки, то под шумок вкрутить туда квадродерево.
Но понятно, что дерево, каким бы логарифмическим оно ни было, медленнее простого массива. Квадродерево замедлило наше решение на разных картах в полтора - три раза по сравнению с mutable версией с двумерным массивом и откатами. Но мы всей командой сказали твердое “нет” откатам! :-) По факту, после перехода на квадродерево у нас разом пропали все многочисленные мелкие баги с откатами наводнений и прочих телепортов, а также убилось довольно много кода, в котором, видимо, эти баги и жили.
Такая вот поучительная история. А если мы пройдем в следующий тур - напишу ещё какую-нибудь поучительную историю из нашего участия :)
Ссылки для детального изучения:
* ICFPC 2012 Task
* Наша версия QTree на github.com
* Immutable data structures in C#