​​CayleyPy: Professor Tetraminx puzzle

Месяц назад я рассказывал как участвовал в ресерч соревнованиях Cayley. С тех пор я поучаствовал в ещё одном соревновании - Professor Tetraminx.

Напоминаю, что суть задачи - из рандомного состояния головоломки (после N поворотов) дойти в исходное за минимальное количество шагов.

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

Я начал тогда, когда лучшее доступное решение было 28863 и улучшил его до 28467, получив новый лучший результат и обойдя мирового эксперта Tomas!

Блогпост с деталями напишу позже, но пока расскажу, что нового было сделано по сравнению с моим прошлым подходом:
- Как известно, решить такую головоломку брутфорсом нельзя. Но вполне можно с помощью BFS подсчитать все состояния после 6-9 шагов. Так что теперь мой подход не пытается дойти до финального состояния, а просто до состояния, которое находится на расстоянии 6-7 до финального. Это довольно важно, ибо иногда поиск останавливается лишь в нескольких шагах от успеха - и этот подход спасает такие кейсы
- Sparse Q - новая голова для нейронки (по предложению Vlad Kuznetsov), которая даёт скор сразу для всех возможных переходов из текущего состояния - это сильно ускоряет обчение и инференс
- многократное расширение датасета с разными подходами по сбору данных
- PieceTransformer в качестве модели и его бленд с обычным ResMLP
- V-consistency - хитрый подход для улучшения beam search. Простыми словами: если одна голова модели говорит, что мы в 10 шагах от цели, а другая голова говорит, что после одного шага мы будем в 15 шагах - это неправильно; а если головы выдают 10 и 9 - значит мы движемся в правильном направлении

Теперь продолжу участвовать в других соревнованиях этой серии и всем рекомендую :)

#kaggle #datascience