?

Log in

Previous Entry | Next Entry

Hextris

В эти выходные прошло соревнование ICFPC - волшебная пора, когда все функциональные программисты мира (все 800!) могут оторваться от своей дневной работы на джаве, С++ или РНР и на три дня представить, что их любимый язык все-таки где-то применим.

В этом году надо было сделать свой решатель тетриса, но хексагонального, с занятной неевклидовой геометрией (движение фигуры по прямой не сохраняет взаимное расположение частей в их координатах относительно друг друга, движения и повороты работают по-разному в зависимости от места происходящего).


К этому сверху был прилеплен поиск и использование волшебных заклинаний ("ктулху фхтагн бешельме чернмернда") - каждый ход кодируется одним из нескольких возможных символов, если из этих символов в решении складывается какое-нибудь заклинание, за это дают дополнительные очки, и, видимо, много. Я как обычно участвовал без ансамбля, поэтому на заклинания совсем забил, занимался только тетрисом. За первый день сделал логику игры (загрузка данных, движения фигур, сжигание рядов, подсчет очков) с визуализацией и ручным управлением, можно было играть самому, а также прогнать пример от организаторов и убедиться, что все работает. Все получалось довольно гладко, разве что на поворот фигур потратил неожиданно много времени: гуглить готовые подходы не стал, хотя понимал, что наверняка известны какие-нибудь красивые подходы с трехмерными координатами. Стал придумывать сам, но формулу для преобразования координат при повороте не придумал, вместо этого сделал табличку (отображение разных координат при повороте), заполнявшуюся индуктивно: точка, вокруг которой идет поворот, не меняется, ее ближайшие 6 соседей меняются местами циклично, а дальше если для какой-то клетки знаешь, как при повороте двигается ее ближайший сосед, то ее движение состоит из такого же ровно сдвига (вместе с тем соседом) плюс поворот вокруг этого ближайшего соседа, такой поворот уже известно как делается.

На второй день стал придумывать стратегию для игры, и в течение второго и третьего дней ее постепенно реализовал (как-то не очень быстро каменный цветок выходил). Работало все следующим образом. Когда очередная фигура появляется на поле, понятно, что остановиться ей надо будет или где-то непосредственно рядом с уже имеющимися заполненными клетками, или рядом со стеной (краем уровня). Очки дают за сжигание полностью заполненных горизонтальных рядов, поэтому нас интересует соседство горизонтальное прежде всего. Поэтому в самом начале игры для каждой фигуры, для всех ее поворотов, были составлены списки точек, которыми она может касаться горизонтально. Когда фигура появляется на поле, надо пройтись по всем пустым горизонтальным соседям уже имеющихся на поле объектов и примерить к ним текущую фигуру по тем спискам потенциальных точек соприкосновения, т.е. перебирать все-все возможные ее положения не нужно, лишь те, где ожидаются касания. Для каждой такой потенциальной позиции приземления оценивается ее привлекательность: приведет ли ее занятие к полному заполнению каких-нибудь горизонтальных рядов (и их количество), если нет, то для каждого горизонтального ряда занимаемой позиции оценивается наибольшее количество получающихся заполненных подряд клеток (больше - лучше), плюс поправка на высоту: сжигать ряды лучше те, что выше, а вставать на пока еще незаполненные лучше пониже. Чуть позже был добавлен еще один фактор: сравнивалось количество "пузырей" (недостижимых сверху пустых клеток, т.к. фигуры могут двигаться лишь вбок и вниз, но не вверх) до и после занятия позиции, образование новых "пузырей" пенализируется, снижает оценку привлекательности позиции. Оценив все эти потенциальные позиции для приземления фигуры и отсортировав их по привлекательности, первая версия брала первую достижимую из них (для которой найдется путь от исходного положения фигуры). Это дало смешной результат: т.к. часто вращение фигуры на некоторые углы отображает ее в себя, позиции с такими углами поворота получают одинаковую оценку, и после сортировки по оценке первой часто попадалась позиция повернутая, в результате фигура перед ее занятием делала ненужные вращения, что по условиям задачи чревато обнулением очков. Поэтому вместо первой достижимой позиции из отсортированного списка брался набор позиций с одинаковыми оценками и из них выбирался вариант с кратчайшим путем, это отсекало ненужные вращения. Поиск пути был простым А* в трехмерном пространстве (x,y,угол), в процессе поиска строится множество достижимых позиций, в котором для каждой клетки сказано, как туда попали. Если для какой-то интересующей нас позиции путь не нашелся, то значит поиск пути перебрал все достижимые клетки карты, и при поиске путей для других позиций уже ничего еще раз строить не нужно: если позиция достижима, она уже в нашем множестве достижимых, и путь к ней уже известен, а если ее там нет, то путь не существует. В итоге все работало мгновенно, как-то еще оптимизировать или усложнять поиск не понадобилось. Памяти процесс ел меньше 3 МБ на маленьких задачах и около 20 МБ на больших.

В последний день к описанной схеме был еще добавлен look-ahead: последовательность фигур известна заранее, поэтому вместо принятия решений лишь по текущей фигуре был сделан рекурсивный перебор на пару шагов вперед. Вместо того, чтобы брать наиболее привлекательную достижимую позицию, составлятся список из 5 лучших достижимых (с разными оценками, чтобы отсечь те, что отличаются лишь поворотами), для каждой из них моделируем что получится при ее выборе, рекурсивно ищем решение для следующей фигуры, так на несколько фигур вглубь (в будущее), в этом дереве вариантов для листьев выбирается максимум, он возвращается наверх и складывается с оценкой узла-родителя, из его таких сложенных вариантов выбирается максимум и передается наверх.. В итоге для текущей фигуры выбирается такое положение, которое дает максимальную сумму оценок для этой и нескольких следующих фигур. Например, если текущей фигурой можно сжечь один ряд и следующей можно будет сжечь еще один, но если сейчас один не сжигать, то следующая сможет сжечь оба, то будет выбран именно последний вариант, ибо за сжигание двух рядов сразу дают больше очков, чем за два сжигания по одному ряду. С таким look-ahead'ом все стало ощутимо медленнее, но все равно большинство задач обсчитывалось меньше чем за минуту, и чтобы обновить все решения мне понадобилось менее получаса. Писал на D, исходники на битбакете, 1200 строк включая гуй.

Вот, получилось довольно интересно, на мой взгляд. Поскольку заклинаниями не занимался, очков набрал не очень много, в общем зачете из 300+ зарегистрированных команд на 103 месте (в этот раз назвался Dr. Zoidberg).

Tags:

Comments

( 15 comments — Leave a comment )
gineer
Aug. 11th, 2015 05:34 pm (UTC)
очевидно потроллил
swizard
Aug. 11th, 2015 06:00 pm (UTC)
> волшебная пора, когда все функциональные программисты мира (все 800!) могут оторваться от своей дневной работы на джаве, С++ или РНР и на три дня представить, что их любимый язык все-таки где-то применим.

И как обычно, их ждёт разочарование :)
В квалификации победили вот эти ребята с вот этим: "The solvers are written in Java and C#".
thedeemon
Aug. 11th, 2015 06:12 pm (UTC)
274 commits!
Там целая армия работала чтоле?

>"The solvers are written in Java and C#".

С обвязкой на РНР и эвалюатором на С++, прицельный плевок. :)

Edited at 2015-08-11 06:14 pm (UTC)
swizard
Aug. 11th, 2015 06:27 pm (UTC)
> Там целая армия работала чтоле?

если я ничего не путаю, их там чуть ли не десять человек в команде


> С обвязкой на РНР и эвалюатором на С++, прицельный плевок. :)

будет особенно смешно, если они же финал ICFPC выиграют =)
pbl
Aug. 12th, 2015 09:50 am (UTC)
> И как обычно, их ждёт разочарование :)

Ну не всегда же. Хаскель, Окамл и Эфшарп брали первое восемь из семнадцати раз. Не говоря уж о jabber.ru с его Окамлом. Сколько раз он лайтнинг брал, кто-нибудь знает точно?
yantayga
Aug. 11th, 2015 07:29 pm (UTC)
А я так и не смог придумать для А* нормальной целевой функции...
thedeemon
Aug. 11th, 2015 08:11 pm (UTC)
Это, должно быть, от излишнего мудрствования и сомнений. Я делал хрестоматийно: количество уже пройденных шагов до данной ячейки + примитивная оценка оставшегося расстояния до цели max(dx,dy), где dx и dy - модули разницы соответствующих координат двух точек.
swizard
Aug. 11th, 2015 08:38 pm (UTC)
а у нас клетки были в кубических координатах, поэтому я просто квадрат дистанции использовал, даже без количества шагов
perdakot
Aug. 12th, 2015 04:09 am (UTC)
Если мероприятие функциональное, почему тогда на D?
thedeemon
Aug. 12th, 2015 05:45 am (UTC)
Там на любых языках можно (см. соседнюю ветку про команду на первом месте). Раньше я на окамле участвовал, но теперь предпочитаю D.
Azamat Kalimoulline
Aug. 12th, 2015 04:11 pm (UTC)
А ты учитывал, что в пузырь можно прийти с помощью поворота с вынесенным пивотом?
thedeemon
Aug. 12th, 2015 05:47 pm (UTC)
Нет, не учитывал. Это, конечно, прокол. Да и без этого оценочную функцию можно было еще улучшать и улучшать.
binf
Sep. 5th, 2015 01:55 pm (UTC)
фигассе, никогда бы не подумал D умеет в винформс

а чего не WPF? там жеж меньше писанины
thedeemon
Sep. 5th, 2015 03:13 pm (UTC)
Это DFL, она очень похожа на WinForms, но это самостоятельная либа, обертка над WinAPI, никакого дотнета не требует.

Не WPF ибо связки его с D мне неизвестно, да и незачем. Писанины и тут немного - весь бойлерплейт по созданию и инициализации контролов сгенерен редактором форм.
binf
Sep. 5th, 2015 03:50 pm (UTC)
Спасибо за разъяснения, впечатлён весьма. Редактор форм - это вообще вау. Надо будет про D книжку почитать.
( 15 comments — Leave a comment )