blackbox 2016

Что в этом репозитории?

Моё решение BlackBox Challenge 2016.
В итоге я занял 24 место.

Решение

Я довольно долго пытался построить решение с помошью машинного обучения и честного reinforcement learning, но все мои решения оказывались намного хуже базового regression bot-а. Поэтому я решил улучшить коэффициенты, чтобы хотя бы превзойти baseline.
Но вручную настраивать коэффициенты мне не очень хотелось, поэтому я применил метод, похожий на упрощенный метод отжига (я бы назвал его случайным спуском).

Последовательность действий

1) Оптимизируем бота

Изначальный regression bot у меня работал 14 секунд. Немного поменяв код можно получить версию, работающую за 6.5 секунд, но это всё ещё слишком медленно.
Дальше я занялся оптимизацией на Cython-е. Простое переписывание кода на Cython дало прирост скорости до 1.64 секунд.
В конце концов у меня получилось ускорить бота до 0.38 секунд на игру.

В процессе оптимизации очень пригодилась команда

cython -a my_bot/super_fast_bot.pyx

При этом генерируется файл с аннотацией, показывающей, где происходят обращения к питону. Например, наибольший прирост скорости дали переписывание скалярного произведение с numpy на обычный цикл и передача массива через указатель, а не через memoryview.

2) Случайно меняем коэффициенты и пытаемся максимизировать количество очков за игру.

Начинаем с как-то посчитанных коэффициентов, после этого много раз случайно модифицируем их и, если удалось улучшить результат, то запоминаем новые коэффициенты.

Коэффициенты regression bot-а, 10000 игр на train уровне, смещения из N(0, 0.01) - получаем 2851.03 на train, 2246.28 на test и 2291 на валидации.
Коэффициенты с шага 1, 10000 игр на train уровне, смещения из N(0, 0.001) - получаем 2964.60 на train, 2259.35 на test и 2323 на валидации.
Коэффициенты с шага 2, 10000 игр на train уровне, смещения из N(0, 0.0001) - получаем 2972.12 на train, 2257.18 на test и 2324 на валидации.
Коэффициенты с шага 3, 10000 игр на train уровне, смещения из U(0, 0.00001) - получаем 2980.40 на train, 2254.82 на test и 2328 на валидации.
После шага 4 получаем окончательные коэффициенты для моего решения.

Интересно, что можно точно так же максимизировать результат на тестовом уровне, но при этом резко ухудшаются результаты на валидации.
Например, за счет чередования обучающего и тестового уровней при обучении у меня получалось найти параметры, при которых значения и на обучающем, и на тестовом уровнях лучше, чем в моем окончательном решении, но на валидации результат получался намного хуже.

Что стоило улучшить:

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

Неудачные решения

1) Упрощенная версия Q-learning и SGD вместо нейронных сетей.

Из-за довольно сильного ограничения в 2 минуты я решил, что нейронные сети будут работать слишком долго (и о наличии GPU на сервере ничего не было сказано), поэтому я решил использовать вместо них что-нибудь попроще, например SGD-регрессоры.
Здесь есть код, но у меня не не получилось набрать больше -9000.

2) Попытка сымитировать поведение checkpoint bot-а.

Немного доработав алгоритм, у меня получилось добиться от checkpoint bot-а больше 97000 на обучающем уровне. Я пытался строить разные классификаторы на основе оценок, которыми руководствуется checkpoint bot (количество очков через 100 ходов в будущем), предсказывающие:

Непосредственно оценку за действие
То, что оценка за действие равна максимально возможной
Одно из 16 состояний, отвечающих тому, какие действия выгоднее всего делать. То есть в большинстве случае без разницы, что делать, а также часто можно выбрать между двумя состояниями с равными оценками. Очень редко есть только одно правильное действие.

С помощью этого метода у меня получилось набрать только -5000, что тоже значительно хуже baseline-а.

amorgun/blackbox-2016