Технологии в Контуре

Немного триллера, как и положено в заметках об ICFPC. Организаторы опубликовали результаты первого (https://goo.gl/MmnzxY) и второго раунда полного, 72-часового соревнования. В первом раунде участвовало 120 команд, которые играли четвёрками на небольших картах. Мы посмотрели на результаты и расстроились: наш бот набрал всего 70 очков. При этом лучшая команда набрала 122 очка, а медиана — 81,5 очков. Это значит, что наша команда вылетела из соревнования.

Это был «удивительно плохой результат» на фоне 1 и 2 места после 24-часового соревнования. Поэтому мы пошли смотреть записи игр и разбираться, где накосячили.

Сначала выяснили, что наш бот плохо играет в ситуации, когда ему активно противостоят на картах с низкой связностью. Например, в одной игре (https://goo.gl/XF8uBh) красная команда блокировала каждый наш ход — в итоге сама заняла последнее место, а нас утащила на третье, не позволив заработать зачётных очков. Мы обсуждали, что такое поведение противников возможно, и осознанно не учили бота противостоять ей. Такая стратегия может работать только на небольших картах, где низкая связность и мало противников. На средних и больших картах, где много «обходных путей» в графе и больше 4 команд, повредить нашему боту этой стратегией почти невозможно. Много очков мы на этом не потеряли, поэтому продолжили поиски.

Выяснили, что наш бот теряет много очков на конкретной карте — «треугольнике». Это экстремальный пример маленькой карты: всего три «шахты» и очень низкая связность. Если не оставить за собой подходы к шахтам в самом начале, следующими ходами их займут другие команды. Есть игры, где это хорошо видно (https://goo.gl/Nw7pHW). Мы обсуждали отдельную стратегию для таких карт: сделать полный перебор позиций и использовать критерий минимакса. Осознанно не стали этого делать, чтобы не усложнять бота. Были готовы потерять немного очков, чтобы «дождаться» средних и больших карт, где минимакс уже бесполезен.

Эти находки объясняли, почему мы потеряли около 10 очков. Куда делись ещё 50? И тут мы увидели СТРАШНОЕ. В куче игр (например, https://goo.gl/NxW8fD) наш бот делал несколько ходов и начинал неистово пасовать. Поэтому занимал последнее место и получал ноль очков. Страшно было то, что наш бот не умел и не мог пасовать. Мы не программировали такого поведения.

Это означало одно — у нас баг. Довольно быстро выяснили, что бот пасует только на картах, где можно делать особые ходы — options. Их разрешили в середине соревнования, поэтому бот из 24-часового зачёта ничего о них не знал. Мы добавили поддержку options в последнюю ночь перед окончанием ICFPC и всё утро дебажили. Наш инструмент для сравнения стратегий показывал, что стратегии с использованием options получаются эффективнее. Мы даже посчитали, какую долю от разрешённых options-ходов нужно делать (примерно половину), чтобы стратегия получала наибольший прирост эффективности (см. последнюю колонку):

430 viewsIgor Lukanin, edited 05:02