Оптимизация решения головоломки Professor Tetraminx

​​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