ICFP Contest 2011. Hi, team.
Напишу отчет пока все не забыл. Надо задокументировать положительные и отрицательные моменты пока все не забыл.
Мероприятие:
http://www.icfpcontest.org/
Конкурс программистов приуроченый к ежегодной конференции по функциональному программированию.
Сборы:
В этом году я наконец-то увидел в новостях анонс даты за месяц-полтора и забил ее себе в календарь до, а не после самого мероприятия. Знаю про него уже несколько лет, ни когда не вспоминал вовремя чтобы поучаствовать. Т.к. конкурс идет три для, то я взял выходной на пятницу. Кроме меня в пятницу играл еще один человек, а третий подключился с пятницы вечера. Для лондонцев довольно удобно, москвичам хуже.
Люди:
Для участия требовалась команда которую я стал искать среди своих нынешних и бывших коллег. Думаю одному можно было бы участвовать, но результат был бы не лучше того, что получилось. План был собрать 5 человек работающих удаленно ибо в Лондоне набрать столько знакомых энтузиастов у меня бы не вышло.
Постепенно набралось 4 человека из которых двое колебались в душе, это чувствовалось не смотря на их согласие участвовать. В будущем нужно их сразу отсекать, чтобы можно было искать еще кого-нибудь. Играли в комманде Маер и Сергей.
Технологии:
Для хранения кода использовали svn как самый всем знакомый. Купил месяц на sourcerepo.com чтобы создать приватный репозиторий для команды. Работает нормально если бы не сюрприз от провайдера в последний день. Можно было открыть свой с NAS'а но рисковать не хотелось.
Писать решили на Java т.к. из 5 человек 3 джависта и 2 сиплюсплюсника. Из реально игравших два джависта и сишник. Лучше бы всем писать на одном языке, это бы помогло ускорить процесс.
Для обсуждения использовали skype конференцию, чат и звонки по необходимости. Это, а так же выбраный тариф репозитория, накладывало ограничение на размер команды. Вообще чат в скайпе не самый хороший. Слишком много пустого места и быстро листать смотреть историю не удобно. Так же отмечу скайп конференцию. Втроем еще туда-сюда, но нужно соблюдать какой-то протокол чтобы друг-друга не перебивать ибо из-за лага перебиваешь постоянно. В пятером это будет вообще труба.
Для документирования и хранения идей использовали Google Documents. При нашем темпе работы, параллельное редактирования работало удовлетворительно. Диаграммы почти не рисовали, а то было бы уже не так здорово.
Все тулзы были настроены заранее и была тестовая сессия посмотреть как оно работает. Оно работало.
Задание:
Написать бота, который играет в Lambda: The Gathering. Описывать условие подробно лень, слишком долго писать, пост не для этого. В общих чертах: у каждого игрока набор слотов со здоровьем и значением и набор карт со значениями. Значения - константы или функции. У каждого игрока полный набор карт в руке, карты не расходуются. Играют двое, задача убить все слоты противника. Ходят по очереди. В свой ход можно либо выполнить функцию из слота на любую карту или функцию карты на слот. Игра заканчивается когда все слоты одного из игроков мертвы либо когда исчерпан лимит ходов 100 000. Собственно действия производятся за счет побочных эффектов функций. Доступные функции: S, K комбинаторы, тождественное отображение, арифметики немного, перемещение и атаки-лечения, а так же зомби.
Как мы играли:
Пятница. В первый вечер (четверг) прочитав задание, почесали репу и пошли спать. На утро вскочил как на работу и пообщавшись с коллегой начал писать имплементацию игры. Предполагали, что бот будет оценивать ситуацию и принимать решения согласно происходящему на столе. Понимания как использовать карты не было. К середине дня первая имплементация уже более-менее начала работать. Т.к. моя скорость написания и коммита кода была самой высокой, то я монополизировал модель и Маер стал думать над картами. К концу дня у нас была модель с багами (как потом выяснилось). Подключился Сергей и сразу стал двигать идею полного перебора. Мы подписались под это дело и это стало нашей ошибкой.
Суббота. Суббота была потеряна потому, что я писал undo/redo в модель для алгоритма, Сергей писал собственно перебор, а Маер думал над ограничениями. В итоге мы, конечно это запустили, но стало ясно, что достаточной глубины перебора нам не получить. Алгоритм нашел на уточке пару рекурсивных ударов, но они были явно недостаточны для успешной борьбы. Сергей завернул проект в ант, который делал gzip для деплоя на тестовый сервер. Еще какое-то время было потрачено на то, чтобы можно было на нашей программе запускать несколько стратегий или сцеплять ее в различных вариантах с демо сервером игры и захватывать результат для сравнения.
Воскресенье. Воскресенье мы встретили ни с чем. Перебор не работал, надо было переходить к следующей стадии. Было понятно, что нужно собирать формулы и применять их и отслеживать живость своих слотов. Я даже успел сделать заготовку для этого, которая бы собирала метаоперации из карт и подлечивала слота и восстанавливала бы мертвые. В итоге я с помощью Маера и его формул довольно быстро написал очень простой бот который через атаку выбивал начальные слоты противника и замирал. Даже с таким ботом мы побивали кого-то, но по победам болтались где-то на уровне 40%. Маер с Серегой игрались в игру и придумывали комбинации, но и ко второй половине воскресенья особого прогресса не было. Как убить за 1000-600-400-122 хода мы не понимали. В середине дня, когда я сделал попытку закомитить очередную порцию изменений выяснилось что мне недоступен репозиторий. После некоторых изысканий выяснилось, что проблема у провайдера. Другие члены комманды все видели, я не видел только репозиторий, но видел админку от него. Трэйсрут не добивал. Пришлось задействовать резервный канал и настроить wireless tether на Андроиде. Неожиданно, но эта система заработала и я смог комитить-апдэйтить через 3G. В итоге стало понятно, что мы не успеем доделать умного бота и пришлось применить план Б. Я добавил в бота лечение рабочих ячеек что улучшило наши показатели. Потом приделал добивание бота если мы выживали. В итоге мы стали побеждать за 50К ходов если противник не сопротивлялся или не лечился. Добавить что-то более оптимальное не получалось потому, что я начал тупить из-за усталости после 5 часов сна с субботы на воскресенье. Маер писал мне формулы но я не мог их транслировать в последовательность карт т.к. я не набрал еще критической массы знаний в голове. Как создать в слоте комбинатор подставляющий аргумент итоговой функции в несколько аргументов вложенной я не понял... В последний момент была добавлена фича, чтобы в прод-режиме программа не останавливалась даже если считала что кто-то умер. Но! Я умудрился перепутать true и false и она в тест режиме не останавливалась. Это мы узнали когда она упала на неофициальном сервере из-за оставшегося бага после окончания конкурса. И этот баг и ошибку модели я нашел посмотрев на код на свежую голову.
Потом был отсыл результата и генерация контрольной суммы, которую я непонятно откуда взял и потом до опубликования результатов сомневался примут ли нашего бота. Но все обошлось.
Итог:
83 место из 199 участников
Выводы:
Интересно.
Командная организация хромала. То, что я почти все время писал код, не дало времени как следует подумать. Надо было больше распределять задачи, для этого нужно было всем писать на одном языке и желательно с примерно равной квалификацией.
Ошибка с решением попробовать перебор. Сергей имел опыт написания подобного для MTG подобной игры, но надо было не взирая на это попробовать оценить глубину поиска. Это стоило нам дня работы, т.е. 33% времени.
Ошибки в коде посаженные под конец как бы намекают, что надо иметь вторую пару глаз смотрящих за кодом.
Надо было писать DSL для упрощения написания алгоритма бота и это можно было делать параллельно с моделью.
К следующему году нужно подтянуть какой-то язык не такой тяжелый как джава, а более гибкий и приемлемый для маленьких проектов.
Смотреть что-то для голосового общения, скайп как раз майкрософт похоронит к тому времени. :)
Иметь резервный канал/репозиторий/средство общения.
Мероприятие:
http://www.icfpcontest.org/
Конкурс программистов приуроченый к ежегодной конференции по функциональному программированию.
Сборы:
В этом году я наконец-то увидел в новостях анонс даты за месяц-полтора и забил ее себе в календарь до, а не после самого мероприятия. Знаю про него уже несколько лет, ни когда не вспоминал вовремя чтобы поучаствовать. Т.к. конкурс идет три для, то я взял выходной на пятницу. Кроме меня в пятницу играл еще один человек, а третий подключился с пятницы вечера. Для лондонцев довольно удобно, москвичам хуже.
Люди:
Для участия требовалась команда которую я стал искать среди своих нынешних и бывших коллег. Думаю одному можно было бы участвовать, но результат был бы не лучше того, что получилось. План был собрать 5 человек работающих удаленно ибо в Лондоне набрать столько знакомых энтузиастов у меня бы не вышло.
Постепенно набралось 4 человека из которых двое колебались в душе, это чувствовалось не смотря на их согласие участвовать. В будущем нужно их сразу отсекать, чтобы можно было искать еще кого-нибудь. Играли в комманде Маер и Сергей.
Технологии:
Для хранения кода использовали svn как самый всем знакомый. Купил месяц на sourcerepo.com чтобы создать приватный репозиторий для команды. Работает нормально если бы не сюрприз от провайдера в последний день. Можно было открыть свой с NAS'а но рисковать не хотелось.
Писать решили на Java т.к. из 5 человек 3 джависта и 2 сиплюсплюсника. Из реально игравших два джависта и сишник. Лучше бы всем писать на одном языке, это бы помогло ускорить процесс.
Для обсуждения использовали skype конференцию, чат и звонки по необходимости. Это, а так же выбраный тариф репозитория, накладывало ограничение на размер команды. Вообще чат в скайпе не самый хороший. Слишком много пустого места и быстро листать смотреть историю не удобно. Так же отмечу скайп конференцию. Втроем еще туда-сюда, но нужно соблюдать какой-то протокол чтобы друг-друга не перебивать ибо из-за лага перебиваешь постоянно. В пятером это будет вообще труба.
Для документирования и хранения идей использовали Google Documents. При нашем темпе работы, параллельное редактирования работало удовлетворительно. Диаграммы почти не рисовали, а то было бы уже не так здорово.
Все тулзы были настроены заранее и была тестовая сессия посмотреть как оно работает. Оно работало.
Задание:
Написать бота, который играет в Lambda: The Gathering. Описывать условие подробно лень, слишком долго писать, пост не для этого. В общих чертах: у каждого игрока набор слотов со здоровьем и значением и набор карт со значениями. Значения - константы или функции. У каждого игрока полный набор карт в руке, карты не расходуются. Играют двое, задача убить все слоты противника. Ходят по очереди. В свой ход можно либо выполнить функцию из слота на любую карту или функцию карты на слот. Игра заканчивается когда все слоты одного из игроков мертвы либо когда исчерпан лимит ходов 100 000. Собственно действия производятся за счет побочных эффектов функций. Доступные функции: S, K комбинаторы, тождественное отображение, арифметики немного, перемещение и атаки-лечения, а так же зомби.
Как мы играли:
Пятница. В первый вечер (четверг) прочитав задание, почесали репу и пошли спать. На утро вскочил как на работу и пообщавшись с коллегой начал писать имплементацию игры. Предполагали, что бот будет оценивать ситуацию и принимать решения согласно происходящему на столе. Понимания как использовать карты не было. К середине дня первая имплементация уже более-менее начала работать. Т.к. моя скорость написания и коммита кода была самой высокой, то я монополизировал модель и Маер стал думать над картами. К концу дня у нас была модель с багами (как потом выяснилось). Подключился Сергей и сразу стал двигать идею полного перебора. Мы подписались под это дело и это стало нашей ошибкой.
Суббота. Суббота была потеряна потому, что я писал undo/redo в модель для алгоритма, Сергей писал собственно перебор, а Маер думал над ограничениями. В итоге мы, конечно это запустили, но стало ясно, что достаточной глубины перебора нам не получить. Алгоритм нашел на уточке пару рекурсивных ударов, но они были явно недостаточны для успешной борьбы. Сергей завернул проект в ант, который делал gzip для деплоя на тестовый сервер. Еще какое-то время было потрачено на то, чтобы можно было на нашей программе запускать несколько стратегий или сцеплять ее в различных вариантах с демо сервером игры и захватывать результат для сравнения.
Воскресенье. Воскресенье мы встретили ни с чем. Перебор не работал, надо было переходить к следующей стадии. Было понятно, что нужно собирать формулы и применять их и отслеживать живость своих слотов. Я даже успел сделать заготовку для этого, которая бы собирала метаоперации из карт и подлечивала слота и восстанавливала бы мертвые. В итоге я с помощью Маера и его формул довольно быстро написал очень простой бот который через атаку выбивал начальные слоты противника и замирал. Даже с таким ботом мы побивали кого-то, но по победам болтались где-то на уровне 40%. Маер с Серегой игрались в игру и придумывали комбинации, но и ко второй половине воскресенья особого прогресса не было. Как убить за 1000-600-400-122 хода мы не понимали. В середине дня, когда я сделал попытку закомитить очередную порцию изменений выяснилось что мне недоступен репозиторий. После некоторых изысканий выяснилось, что проблема у провайдера. Другие члены комманды все видели, я не видел только репозиторий, но видел админку от него. Трэйсрут не добивал. Пришлось задействовать резервный канал и настроить wireless tether на Андроиде. Неожиданно, но эта система заработала и я смог комитить-апдэйтить через 3G. В итоге стало понятно, что мы не успеем доделать умного бота и пришлось применить план Б. Я добавил в бота лечение рабочих ячеек что улучшило наши показатели. Потом приделал добивание бота если мы выживали. В итоге мы стали побеждать за 50К ходов если противник не сопротивлялся или не лечился. Добавить что-то более оптимальное не получалось потому, что я начал тупить из-за усталости после 5 часов сна с субботы на воскресенье. Маер писал мне формулы но я не мог их транслировать в последовательность карт т.к. я не набрал еще критической массы знаний в голове. Как создать в слоте комбинатор подставляющий аргумент итоговой функции в несколько аргументов вложенной я не понял... В последний момент была добавлена фича, чтобы в прод-режиме программа не останавливалась даже если считала что кто-то умер. Но! Я умудрился перепутать true и false и она в тест режиме не останавливалась. Это мы узнали когда она упала на неофициальном сервере из-за оставшегося бага после окончания конкурса. И этот баг и ошибку модели я нашел посмотрев на код на свежую голову.
Потом был отсыл результата и генерация контрольной суммы, которую я непонятно откуда взял и потом до опубликования результатов сомневался примут ли нашего бота. Но все обошлось.
Итог:
83 место из 199 участников
Выводы:
Интересно.
Командная организация хромала. То, что я почти все время писал код, не дало времени как следует подумать. Надо было больше распределять задачи, для этого нужно было всем писать на одном языке и желательно с примерно равной квалификацией.
Ошибка с решением попробовать перебор. Сергей имел опыт написания подобного для MTG подобной игры, но надо было не взирая на это попробовать оценить глубину поиска. Это стоило нам дня работы, т.е. 33% времени.
Ошибки в коде посаженные под конец как бы намекают, что надо иметь вторую пару глаз смотрящих за кодом.
Надо было писать DSL для упрощения написания алгоритма бота и это можно было делать параллельно с моделью.
К следующему году нужно подтянуть какой-то язык не такой тяжелый как джава, а более гибкий и приемлемый для маленьких проектов.
Смотреть что-то для голосового общения, скайп как раз майкрософт похоронит к тому времени. :)
Иметь резервный канал/репозиторий/средство общения.