3 Место от Santa 2025

Сетап соревнования кратко описан тут: https://t.me/pseudolabeling/327

Задача чуть меньше, чем NP-полная (∃R), а для таких пока не найдено одного оптимального алгоритма, так что все лучшие решения будут иметь несколько этапов. В этом случае этапы следующие:
1. Берем хорошее решение меньшего размера и 'наращиваем' на него прямоугольники
2. Собираем из этих запчастей кубик
3. Отжигаем получившеся решение с помощью SA. Вообще каждый Санта решается с помощью SA, так что запомните эти две буквы на следующий год
4. Модификацией sparrow важимаем последние соки

Для начала про sparrow- это такой алгоритм двумерной упаковки, основанный на эвристиках и написанный на Rust 🦀. О нем все узнали из того, что его автор занял 6 место, ставил синичку на аватарку и вообще везде указал, что он такой вот молодец и придумал новый алгортим. Я его понимаю, это его творение и его успех. По умолчанию он решает задачу 'утрамбовки' в прямоугольник известной высоты, передвигая объекты и оптимизируя длину прямоугольника.

В райтапе первый пункт описан плохо, но я додумаю для вас:
Берем пазл меньшего размера с высокой эффективностью. Эффективность определяем так: делим площадь квадрата на число деревьев и получаем условную 'плотность'. Чем плотнее- тем эффективнее. Логика простая- если такой коэф низкий, то и 'воздуха' в решении мало.
Дальше с помощью ванильного sparrow решаем две подзадачи в виде двух прямоугольников, достраиващих решение до квадрата большей площади. Можно конечно разбить и на два идентичных прямоугольника + маленький квадрат, но кажется особого смысла в таком лишнем ограничении нет и оно только испортит.

Пункт второй: SA
Строго и формально лучше всего читать на сайте ммп
Обычно алгоритм на основе SA это смесь с ILS: отжиг из SA и kick из ILS

Отжиг на пальцах:
1.Фиксируем температуру T.
2. Берем случайное дерево, его немного поворачиваем и шевелим. Если из-за этого деревья пересекаются- начинаем с начала.
3. Если скор (размер описанного вокруг елок квадрата) после такого шевеления улучшился- это наше новое базовое решение.
4. Если не улучшился- то делаем это решение базовым только с вероятностью обратно пропорциональной изменению площади (-delta(space) / T)

ILS-Kick еще проще:
Чтобы не застояться в локально минимуме, иногда применяем шаг kick- каждое дерево случайно смещаем в одну из сторон и если не случился overlap, то оставляем как новое базовое решение.

Пункт третий:
Для sparrow придумали тоже пару модификаций, чтобы побить автора:
1. Переписали его под прямую оптимизацию стороны квадрата
2. Написали свою версию warm-start, чтобы не начинать каждый раз с начала. Хотя вормстарт не надо было писать самим, а надо было подтянуть мастер.
3. Дописали доп ограничения для солвера: решение должно быть либо зеркально симметричным, либо 4-симметричным (по вертикали и горизонтали). Так получается больше ограничений и можно отметать слабые решения раньше.
4. Так же добавили специальный параметр регуляризации, заставляющий выстраивать решения вдоль какой-нибудь заранее заданной оси:

P(thetta) = w * B(c) * delta(thetta, thetta*) ^ 2.

Тут w, thetta*- это гиперпараметры силы регуляризации и угла оси, вдоль которой надо выстраиваться

B(c) = 1 + (b - 1)(1 - r) ^ p.

B(c) нужен, чтобы от центра решения к краям регуляризация слабела: r- расстояние до центра паззла, а b и p- тоже гиперпараметры.

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

Соревнование в этот раз на мой взгляд чуть менее веселое, чем было в прошлом году с Геммой, но кагл стаф мне и не должен угождать.

Как взять золото в March Mania? 🏀

В прошлом году анализировал то, как выигрывается March Mania и самая надежная стратегия- это модифицировать Raddar notebook. Я долго ждал, пока Raddar его выложит, но сколько можно? Я сам сделал вам Raddar Notebook.

Raddar- это такой кагл грандмастер, который был 10 лет назад топ 4 каглла, но сейчас подзабил на соревы и в основном лудит в March Mania. Прямо как мы с вами! Форки его ноутбука стабильно появлятеся в топ 10 уже 5 лет, но не он. Ему не везет настолько, что приходится жаловаться на форуме, что его жена стибильно выше него в ладдере March Mania.

База отработана почти с самого начала сорев по NCAA:
1. Берем фичи повторяющиеся из года в год
2. Берем XGBoost
3. Завышаем вероятности в 'неравных схватках'
4. Руками фиксим вероятности для самых первых матчей, чтобы хакнуть Brier Score.

Этот подход как автомат Калашникова, попадал в топ 10 каждый год. Весь секрет в том, чтобы изменить базовый ноутбук и тем самым стать чуть-чуть лучше или хуже, чем все остальные. Ну и молиться, конечно!

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

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

Так что форкайте ноутбук, запускайте и делайте самбит, репостите другим людям. Чем больше будет команд- тем больше будет золотых медалек

🏀🏀🏀
https://www.kaggle.com/code/asimandia/this-year-s-raddar-notebook?scriptVersionId=300874279

Мой 🏀 баскетбольный 🏀 ноутбук кстати пока не вернули в паблик. Если в пн вечером не вернут- во вторник перевыложу сюда код для всех подписчиков