Иииихааа
Ура, по итогам ICFPC 2012 мы на 12 месте, что несомненно большой успех! (http://www-fp.cs.st-andrews.ac.uk/~icfppc/scoretable-final.txt)
И еще немаловажно, что на этот раз мы наконец-то обыграли команду hack the loop :)
Состав команды Ural Nerds в этом году: Илья Петров, Николай Орехов, Антон Савин. Илюха весь год обещал к нам приехать, но в итоге так и не приехал, и как обычно играл по скайпу, гад такой.
Полноценный отчет с почасовой хронологией уже написать невозможно, но по такому случаю, опишу хотя бы кратко, как у нас все работает. Наверняка для этой штуки есть название, но я его сходу сказать не смогу. В некотором роде это похоже на генетический алгоритм, можно еще наверное сказать что это похоже на particle filters.
В общем, у нас живет популяция "копателей", как мы их называли - т.е инстансов робота, в количестве N штук. Каждый ход каждый из них генерит потомков, делая все возможные ходы, таким образом популяция увеличивается в несколько раз. Есть функция оценки ситуации для робота, куда входят набранные очки, уровень воды, количество доступных лямбд, доступность лифта, может быть еще что-то. И мы выбираем из большой популяции N копателей пропорционально значению функции оценки, плюс берем элитарную особь (с максимальным значением функции).
Самая главная фишка заключается в функции оценки - как выбрать такую функцию, которая будет лучше всего работать? Ответ прост: машинное обучение. Опять же мы сделали быстро и просто: взяли карты из примеров и гоняли алгоритм имитации отжига, который подбирал такие коэффициенты в формуле, которые максимизируют очки, набранные на этих картах.
Для подстраховки в итоговую версию мы включили 3 разных набора коэффициентов - сначала гоняем первый, потом если нас еще не прервали второй и т.д
Еще фишка, которая вспоминается - в последние часы игры прикрутили "спрямление" пути - проходимся по уже построенному пути и проверяем, нет ли там бессмысленных хождений взад-вперед (ведь путь был построен как результат случайных блужданий)
Конечно (в том числе это следует и из итогового протокола), решение далеко не идеально. В частности, зверски неоптимально был сделан апдейт карты, из-за которого пришлось при размере карты больше 100х100 ограничивать карту этим размером (и я подозреваю, что именно это явилось главной причиной провала на последней карте).
Ну и мораль всего этого: Coursera и Udacity - это очень хорошо!
И еще немаловажно, что на этот раз мы наконец-то обыграли команду hack the loop :)
Состав команды Ural Nerds в этом году: Илья Петров, Николай Орехов, Антон Савин. Илюха весь год обещал к нам приехать, но в итоге так и не приехал, и как обычно играл по скайпу, гад такой.
Полноценный отчет с почасовой хронологией уже написать невозможно, но по такому случаю, опишу хотя бы кратко, как у нас все работает. Наверняка для этой штуки есть название, но я его сходу сказать не смогу. В некотором роде это похоже на генетический алгоритм, можно еще наверное сказать что это похоже на particle filters.
В общем, у нас живет популяция "копателей", как мы их называли - т.е инстансов робота, в количестве N штук. Каждый ход каждый из них генерит потомков, делая все возможные ходы, таким образом популяция увеличивается в несколько раз. Есть функция оценки ситуации для робота, куда входят набранные очки, уровень воды, количество доступных лямбд, доступность лифта, может быть еще что-то. И мы выбираем из большой популяции N копателей пропорционально значению функции оценки, плюс берем элитарную особь (с максимальным значением функции).
Самая главная фишка заключается в функции оценки - как выбрать такую функцию, которая будет лучше всего работать? Ответ прост: машинное обучение. Опять же мы сделали быстро и просто: взяли карты из примеров и гоняли алгоритм имитации отжига, который подбирал такие коэффициенты в формуле, которые максимизируют очки, набранные на этих картах.
Для подстраховки в итоговую версию мы включили 3 разных набора коэффициентов - сначала гоняем первый, потом если нас еще не прервали второй и т.д
Еще фишка, которая вспоминается - в последние часы игры прикрутили "спрямление" пути - проходимся по уже построенному пути и проверяем, нет ли там бессмысленных хождений взад-вперед (ведь путь был построен как результат случайных блужданий)
Конечно (в том числе это следует и из итогового протокола), решение далеко не идеально. В частности, зверски неоптимально был сделан апдейт карты, из-за которого пришлось при размере карты больше 100х100 ограничивать карту этим размером (и я подозреваю, что именно это явилось главной причиной провала на последней карте).
Ну и мораль всего этого: Coursera и Udacity - это очень хорошо!