Історія участі (і майже перемоги) в щорічному змаганні Russian AI Cup 2016

Привіт, Хабр! Мене звуть Дичковський Олексій, і я хочу вам розповісти про те, як я витратив півтора місяці свого життя на написання бота для спрощеної версії DotA.

Щорічно компанія Mail.ru проводить онлайн-чемпіонат з програмування ігрових стратегій (Russian AI Cup 2016). Я брав участь в цьому змаганні у 2012 році (СodeTanks) і, зовсім небагато, 2013 (СodeTroopers). В цьому році, неабияк наївшись веб розробкою, я вирішив спробувати взяти участь ще раз. Я спочатку не сподівався (але, звичайно ж, дуже хотів зайняти якесь призове місце і в цілому для мене це був швидше тест, наскільки я ще можу реалізувати щось цікаве. Про те, що з цього вийшло можна прочитати під катом.



Досить випадково помітивши анонс майбутнього змагання на сайті russianaicup.ru я почав готуватися. Маючи досвід участі раніше, я порахував, що шаблон для свого кастомного візуалізатора мені дуже згодиться і заощадить трохи часу під час самого змагання. Вся підготовка в цілому полягала у написанні свого візуалізатора, який умів виводити лише кілька базових фігур.

7 листопада, в день старту RAIC 2016, перше, що я зробив — відкрив правила і став читати, що ж організатори приготували нам в цьому році. DotA? Та ну, не може бути… Так точно DotA! Після прочитання правил залишилося стійке відчуття, що коду писати треба буде багато… Дуже багато. І усвідомлення цього на самому початку не сильно додавало натхнення. Також в цьому році старт конкурсу збігся з днем народження моєї дружини, тому довелося відкласти початок розробки на день, адже в найближчі півтора місяця мене буде складно виколупати з-за ПК. Можливо, це також допомогло мені трохи більш точно осмислити, яким буде мій бот в цьому змаганні. З самого початку у мене був якийсь план, і я його дотримувався.

Перший тиждень, або «у що я вплутуються...?»
Перші три вечори пішло на створення проекту, прикручування ліній, вздовж яких будемо ходити в атаку, поганенький вибір однієї з трьох ліній (на старті гри — як у quick start guy — базової стратегії, що надається організаторами, після смерті — де побільше ворогів і своїх поменше), а також прикручування візуалізатора, кістяк якого був написаний за тиждень до RAIC. Далі треба було вчитися якось ходити… Займатися великою кількістю геометрії було моторошно лінь, а пролазити в «щілини» між миньонами, магами і деревами таки хотілося… оскільки інших варіантів на розум не прийшло, то вирішив зробити локальну «сітку», по якій можна ходити, та заодно у неї закласти підрахунок небезпеки і корисності перебування в тій чи іншій точці.

image
Схема ігрової карти. Лінії, по яких варто атакувати ворожу базу (top/bottom/middle lane), відокремлені один від одного лісом.

П'ятниця і вихідні пройшли за роздумом, варто все ж не вплутуватися в цю справу… Але все ж до вечора неділі щось з рухом було реалізовано. Перший варіант сітки був з кроком 2 розміром 401 * 301 точку (відстань 600 вперед уздовж лінії бою, 300 і 200 назад). В кожній точці цієї сітки вівся підрахунок score — «корисності знаходження» за вирахуванням «небезпеки знаходження» в ній. В кінцевому варіанті осередок сітки складалася з безлічі полів і враховувала небезпека від міньйонів, небезпека від магів, небезпека від будівель, корисність знаходження в зоні, з якої я можу атакувати ворогів (були розділені на дві різні змінні для ближнього і далекого бою, в кожній з них враховувався тільки найкраще значення), корисність знаходження в зоні навколо покалічених ворогів (для отримання досвіду за їх вбивство) і дві додаткові змінні otherDanger і otherBonus для реалізації милиць випадків на кшталт збору бонусів, створення небезпечної зони в місці появи ворожих крип, запобігання непотрібного догляду в ліс, забивання в кут карти і т. д. Кожен хід перестворювати таку матрицю дуже не хотілося, тому при оновленні її координат (вона рухалася разом з магом) всі ці значення обнулялися.


Початковий варіант матриці. Відстань до переднього краю матриці — 600 «пікселів». Праворуч і ліворуч — 300, тому — 200. Відстань між точками — 2. Матриця вийшла занадто великий. Кількість точок в самій матриці — 401 * 301. Вона завжди спрямована уздовж лінії битви, незалежно від орієнтації мага.

Запуски на локал раннери показали, що мій підхід працює занадто повільно… За умовами змагання на кожен тик стратегії виділялося 10 мсек, а за моїм вимірам на локальній машині виходило відчутно більше. Відфільтрував світ до необхідного мінімуму: живі юніти і вежі на відстані 600 до моєї локальної сітки, дерева — так, щоб обрахування враховував їх як перешкоди, але додавав як можна менше «зайвих» дерев. Додатково збільшив крок сітки до 3, і отримав продуктивність більш схожою на ту, що треба. Оптимізації все ще були потрібні, але на перший час вирішив, що і так зійде достатньо. Все ж пройшла вже практично тиждень, а викинути щось своє на поля битв хотілося. Точка, до якої рухався, вибиралася як просто найкраща серед точок на матриці за значенням score. Пошук шляху я влаштував пріоритетною чергою, де вагою ребра було не відстань (хоча як другий чинник воно таки враховувалося), а небезпека отримати ляпаса від ворожої команди, при цьому не враховуючи корисність перебування в ній. При такому підході може бути знайдений такий шлях, який хоч і буде коротким, якщо б бот вмів ходити тільки по точках матриці, але буде слабкою, що здорово заважає швидкому переміщенню. Цю проблему я вирішив бінарним пошуком уздовж всього шляху, де перевіряв можливість пройти з своєї точки в шукану навпростець (перед запуском бинпоиска перевірялася досяжність кінцевої точки шляху). Т. о. якщо перешкод на шляху не було — бот просто йшов прямо до точки призначення.

Добре, можемо ходити, трохи боятися ворожих магів і міньйонів вміємо… А як же бій? Хм… Створив лист цілей, відфільтрував їх так, щоб дерева не заважали стріляти (попутно забуваючи, що відфільтровані дерева так, щоб порахувати їх як перешкоду на сітці небезпеки, чого явно недостатньо, якщо мета стоїть відразу за деревом), поставив цілям пріоритети, залежать від того, якою % хп цілі залишився. Пріоритет магів і веж на перший час поставив у 5 і 6 разів вище, ніж у міньйонів. Потім вчу бота повертати для пострілу — якщо ми можемо з поточної позиції стріляти і кількість тиків до перезарядки вже десь на межі того, за скільки ми можемо «докрутити» на мета — повертаємося до мети, інакше поворот у бік руху.

Тестування з local runner.
Попрацювавши з локал раннери, з сумом зрозумів — все таки варіант шляху не дуже годиться… Під час виходу з «небезпечних» зон відразу намагаємося втекти в оптимальну точку, але ж від удару міньйона можна просто втекти задом (швидкість пересування міньйонів дорівнює швидкості руху мага задом і боком), якщо втекти від нього. Вчимося тікати від ворожих міньйонів — тепер намагаємось бігти по прямій не до кінцевої точки, а до такої проміжної точки на шляху, небезпека якої відчутно менше небезпеки в поточній точці мого мага. Змінив пошук точки, до якої переміщаємося — тепер вона вибирається не відразу, а в міру пошуку шляхів по всій матриці, враховуючи крім score цільової точки небезпека, якої ми піддамося на шляху до неї. На цьому етапі це була банально сума всіх небезпек * 0.02 (всі коефіцієнти з самого початку і до кінця вибиралися на око, змінювалися рідко).

Після реалізації нового вибору шляху та більш детального тестування в локал раннери сумуємо і думаємо залишити витівку (RAIC) я помітив, що в часові рамки код знову не влазить. Включивши профайлер java коду, побачив, що все-таки хоч пошук шляху і їсть чимало, але основне навантаження — це обчислення score для кожної точки матриці. Адже для кожної точки матриці йде перевірка за всім юнітам з розрахунком від них відстані до цієї точки, навіть якщо ця відстань значно більше, ніж те, на якому цей юніт може вплинути на мою матрицю… Хм. Виніс підрахунок небезпек в окремі оновлення координат сітки цикли, створив структуру для застосування впливу юніта на score точок сітки. Перед тим, як рахувати відстань від юніта до кожної точки черговий рядка матриці, став перевіряти відстань від юніта до відрізка, кінцями якого є кінці цього рядка. Тепер якщо юніт гарантовано не може вплинути на score точок в даному рядку матриці небезпек — просто пропускаю цілком всю рядок. І ось ця оптимізація вже дозволяла локально цілком стерпно вкладатися в ліміти. Все це здавалося дуже кривим, але якось працювало…

І все ще, мабуть, не бот готовий до перших боїв. У ближньому бою маг колупати сірником бити палицею не вміє, дерева — нездоланна перешкода, з лінії постійно ворожі маги і міньйони виганяють в ліс… Додаю перевірку на те, що поруч є хтось або щось, що можна стукнути, і якщо немає потреби зараз повертати для пострілу — давай-ка стукнем це щось палицею. Виправляю проблему того, що по деревах взагалі стріляти не хочемо (хоча пріоритет пострілу встановив в 0, але якщо немає інших цілей). Додаю штраф за відходження далеко від центру лінії… Значно зменшив матрицю, в якій вважаю окуляри (до відстані 351 вперед і по 150 назад і з боків. Здавалося розмір не сильно впливає на поведінку) і перша версія пішла в бій!

Жалюгідне видовище, несамовитий видовище… Маг столбенеет при підході ворожого мага (т. к. по всій матриці пошуку стає занадто небезпечно), його затискають міньйони, він застряє, намагаючись втекти за край карти, тікає в кут карти, звідки втекти виходить тільки на свою базу через 1.2 до твк (час на відродження)… Виправляю всі ці недоліки, додаючи додаткові штрафи за перебування в точках біля краю карти, додаємо край карти як перешкода, прибираю остолбенение, якщо скрізь дуже небезпечно (сума небезпек більше хп мого мага). Все це трохи допомагає, і тепер, хоча все одно ефект не дуже, але якось жити можна. А тим часом топи вже щосили бігають за бонусами.

Як навчити бота ходити за бонусами робити все що завгодно, але тільки не те, що треба.
Що ж, треба і мені вчитися бігати за бонусами… За них дають досить чимало очок. Тільки ось незрозуміло, як. Для початку вирішив навчитися користуватися швидкістю по максимуму… Заодно заділ на майбутнє — вчимося враховувати всі аури і пасивні навички, статус HASTENED (прискорення) — і тепер, якщо мене раптом міньйони затовчуть на бонус, я буду швидше бігати! Потім, спостерігаючи за боями з іншими суперниками, зрозумів, що я постійно потрапляю під ворожі вежі… А один постріл це більше третини хп мага. Додав їх положення в світі і запам'ятав час до наступного пострілу. Заодно зробив так, щоб під час перезарядки веж мій маг підходив ближче. Все ще погано втікаємо від міньйонів, т. к. біжимо строго по своїй сітці, а її напрям рідко збігається з напрямком, в якому слід було б тікати від міньйона. У підсумку виходить, що мій бот тікає від міньйона «злегка навскоси», а останній, прямуючи строго на мене, постійно скорочує відрив. Рішення — додав локально розгляд кількох напрямків одного кроку приблизно в ту сторону, в яку мій бот вважає, що варто рухатися (напрямок до найближчих точок на шляху + кут, який можна розглянути додатково)… Ось тут і структури для розрахунку очок в точці знадобляться. Вибираємо точку з цієї множини в першу чергу з більшою корисністю перебування в ній для себе, а в другу — ближче до потрібного напрямку руху… Тепер можна нормально обходити красивою колу небезпечні зони, а не бігати за принципом «крок вперед — крок у бік», та й тікати від міньйонів тепер можна більш ефективно рівно по прямій. Ще додамо в матрицю небезпека від зони появи ворожих міньйонів за деяку кількість часу до їх появи, щоб можна було вчасно відійти звідти і не опинитися в їх оточенні…

(Кликабельно, всередині gif-ка)


Скріншот з візуалізатора. Зелений круг трохи з краю від центру розмальованого прямокутника (навколо якого немає «білої» зони, в яку не можна ступити) — маг, яким керує стратегія. Червоні — вороги, зелені — свої. Синя нерівна лінія від центру мого мага — шлях, куди ми зараз йдемо. Чорні смужки з центру мага — який кут розглядається при спробі підібрати найкращий крок. Рожева — напрям, в якому на даний момент найімовірніше краще йти. Червона — обраний напрям для наступного кроку.

Neo mod.
Прокинувшись вранці в суботу, був сповнений рішучості щось придумати з бонусами, але виявив, що мій бот дістався приблизно до топ 100, і там несподівано почали стріляти не в центр, а краєчок мого мага, майже в кожному рейтинговому бою жорстоко і впевнено б'ючи його, поки той не міг нічого відповісти. Однак робити так само не хотілося, т. к. топи хоч ще і не вміють ухилятися, але точно скоро будуть, а хочеться туди, наверх… План прийшов в голову простий і водночас складний — а не буду я робити так само, я спробую просто ухилятися, благо за ті 12 тиків, які летить снаряд, можна цілком собі непогано відійти… Швидкості мага недостатньо, якщо стріляють в центр, але від такої проблеми може допомогти.

Для початку треба запам'ятовувати твк появи всіх снарядів, щоб згодом можна було підрахувати, куди максимум може долетіти кожен з них. У фіналі в цілому можна буде ігнорувати всі постріли від союзників, але в перших двох раундах ігнорувати постріли не дуже-то союзних магів не варто. Оскільки конкуренція за очками також працює і всередині однієї команди, «союзні» маги теж часто люблять добивати своїх (полум'яний привіт mortido). Потім перевіряємо, чи перетинається снаряд зі мною, якщо я буду стояти на місці (відстань до відрізка польоту снаряда менше, ніж сума радіусів мого мага і снаряда, до якого додатково додається відстань, на яке я можу зробити крок, щоб випадково не зробити крок під снаряд). Якщо хоча б один снаряд може в мене потрапити — намагаємося ухилитися. Першим ділом — порахую, скільки чого бот «зловить», якщо буде просто стояти на місці (варіант, коли просто боїться зробити крок під снаряд). Цей базовий шкоди беру за початковий і намагаюся відійти в будь-яку сторону зі швидкістю, як якби я йшов боком чи задом. Також при цьому враховується сумарна кількість очок в точках, через які ми пройдемо під час уворота (якщо стоїмо на місці — складаємо одну і ту ж точку кількість тиків, яке знадобиться). Якщо на цьому етапі не вийшло ухилитися від снаряда — намагаюся бігти на всі боки на максимально можливій швидкості (повертаючи в обрану сторону). При спробах відійти або відбігти від снаряда також перевіряю, що я не натикаюся на перешкоду, допускаючи, що всі міньйони рухаються прямолінійно весь час, а маги, будівлі і дерева стоять на місці. Якщо на поточному тику я уперся в перешкоду, на наступному тику я все одно спробую повторити крок. Раптом хто-небудь так відійде… Вийшло ухилитися від снаряда? Блокуємо пошук шляху, переміщаємося в напрямку, де утрати отримав би поменше і перебувати побезопасней. А якщо при цьому ще поворот в певну сторону допоміг втекти — блокуємо управління поворотом бота на цьому тику і крутимо його в ту сторону, в яку біжимо (повертає мій в останню чергу, після розрахунку пострілу).

Одночасно з написанням алгоритму уворота прийшло усвідомлення, що стріляти в центр не найкращий варіант… Краще стріляти в точку трохи спереду від центру мага, тоді тікати треба довше і однаково довго і вперед, і назад. Вирішив залишити це знання на майбутнє.

І все ж — бонуси.
Так крок за кроком, написавши купу поліпшень (у т. ч. чергове покращення способу визначення, коли ж варто рубати ці ненависні мною на пару з ботом дерева), я все ж сів писати саме похід за бонусами. До того часу в топі за них почалася справжня бійка і нечасто можна було будь-бонус спокійно і безкарно забрати. Став запам'ятовувати, де востаннє бачили ворожих магів, щоб не йти в бік бонусу у випадку, якщо з великою ймовірністю вони зможуть його забрати раніше за мене. На тиках, кратних 2500, ймовірність знаходження бонусів на своїх місцях встановлювалася в 1. Якщо який-небудь ворожий маг поза зоною видимості міг за час, поки він не видно, добігти до бонусу, то ймовірність знаходження бонусу в точці поступово зменшувалася. І чим ближче маг був до бонусу в останній раз перед тим, як його бачили — тим сильніше падала ймовірність того, що бонус все ще знаходиться на своєму місці. Також став запам'ятовувати розташування ворожих міньйонів, щоб можна було повертатися в точку на лінії їх руху на відстань свого пострілу. У коді додалася четверта «лінія» — вона просто ставила напрямок, в якому мені хочеться йти. Також, при активуванні цієї лінії, у матриці небезпек точкам, ближче до цільової, нараховував додатковий бонус. Тепер бот рухався в ту сторону і не занадто сильно застрявав для добивання ворожих міньйонів, магів або веж.

(Кликабельно, всередині gif-ка)


Пкреключение на четверту «псевдо» лінію. Вона ставила напрямок матриці строго в точку, до якої треба йти. В даному випадку маг трохи заздалегідь відправився до найближчого бонусу через ліс.

Одночасно з написанням походів за бонусами додав можливість зміни лінії атаки крім як на момент смерті (початкова реалізація не передбачала такої можливості в інших ситуаціях). Оскільки тепер у мене є збережені дані за місцезнаходженням всіх колишніх в зоні видимості юнітів, то бот став краще розуміти, на який з ліній наша оборона слабкіше нападників (на це перестав впливати тимчасовий вихід ворожих магів і міньйонів з поля зору). В цілому з цього моменту і до кінця раунду 2 вибір лінії виглядав як «йдемо туди, де побільше ворогів, а своїх магів поменше».

Як останній штрих, але все-таки трохи окремо стоїть, я все ж в третій раз переписав алгоритм пошуку кращої позиції та шляхи до неї. В останній і фінальній його ітерації кращою точкою вважалася та, де сума середнього score на шляху до неї і score в самій точці була максимальною. Для цього спочатку знову ж пріоритетною чергою шукав шлях по матриці, значення score в якій для цього пошуку було зменшено на максимальне його значення (щоб уникнути позитивних «петель»). Після такої зміни в ходьбі бота виявився серйозний недолік — він став дуже любити бігати навколо ворожих міньйонів і будівель, часто заходячи їм за спину, ніж сам собі відрізав шлях до відступу від ворожих магів. Розділив поля небезпеки від міньйонів на 2 частини: тепер крім зони атаки додатково виділялася зона, в якій він буде атакувати мене (мінімум із view range і відстані до найближчого союзного мені юніта). Цим мені вдалося позбутися від цієї проблеми, і обирається моїм ботом шлях тепер став виглядати відчутно більш логічним, ніж раніше.

(Кликабельно, всередині gif-ка)


Скріншот з візуалізатора. У даному випадку алгоритм уворота заблокував контроль повороту мага і сам повертає в бік бігу (статус RUN_FROM_PROJECTILE). Також видно, що бот запам'ятав останнє положення одного з ворожих магів. На додаток малюється орієнтовний максимальна відстань, на яке даний маг міг втекти.

З цього моменту і до самого раунду 1 більше особливих поліпшень не робилося. Виправлялися баги і серйозні недоліки в коефіцієнтах. Поступово рейтинг мого бота зростав, поки не влаштувався в десятці. На цьому етапі можна було відзначити, що % перемог у мого бота досить малий у порівнянні з іншими учасниками з топа пісочниці. Мабуть обережне ставлення до бонусів не давало набирати максимальну кількість очок, але виживаність у мага була на більш-менш прийнятному рівні, за рахунок чого свої окуляри він стабільно набирав.

Після першого раунду.
За підсумками першого раунду я зайняв 8 сходинку у рейтингу, що для мене виявилося приємною несподіванкою. Правила 2 раунду відрізнялися від правил раунду 1 наявністю можливості вивчення і застосування навичок. В останній день перед запуском в пісочниці ігор за правилами 2 раунду була прикручена можливість стрільби крижаними стрілами. У перший же вечір на тлі того, що мало які стратегії вміли користуватися навичками і ухилятися, виглядало дуже вражаюче. Однак… Через 1 день стало очевидно, що проти ботів, обрали файрбол в якості першої ульты, битися виходить погано. Спроби виправити це коефіцієнтами і додаванням обліку радіусу вибуху від файрбола в алгоритм уворота ні до чого не привели. Не можеш перемогти ворога — очоль його. Наступним етапом стало написання стрільби файрболом. В загальному то нічого краще перебору пострілу навколо стоять на місці міньйонів (так, щоб зачепити останніх краєм файрбола і краєм вибуху), будівель і всіх ворожих магів (при цьому вважаючи, що останні завжди оптимально намагаються від вибуху втекти) швидко не придумалося і як тимчасовий варіант був зроблений саме такий перебір. Враховувалися тільки ті варіанти пострілу, які я можу зробити з поточним радіусом каста. Але… Немає нічого більш постійного, ніж тимчасове. До самого фіналу алгоритм перебору залишився таким же, за винятком уточнення, чи ворожий маг втекти від мого файрбола чи ні.
Після цілком вдалого тестування використання файрбола на полях битв, я отримав перше місце в пісочниці і вирішив зайнятися поліпшенням того, що вже було написано. Написав клас WizardsInfo, у якому зберігалася інформація про пасивних навыыках, ультах, діючих на мага aurach. Перемкнув код, де використовувалася подібна інформація, на використання нового класу. І, як виявилося через цілий тиждень, серйозно зламав свої оберти. При відсутності статусу прискорення бот при симуляції спроб ухилитися намагався зробити це на швидкості на 30% менше, ніж у нього було насправді. Помітив я це зовсім не відразу тому, що в загальному-то вони працювали, але стали робити свою справу набагато гірше.

За підсумками перегляду боїв на сайті, де мене часто вбивали агресивні стратегії, якби вони удвох на мене одного, для поліпшення відступ був доданий розворот матриці пошуку шляху на 180 градусів (тобто вона в такому випадку вважалася на більшу відстань назад, ніж вперед), якщо мій бот вважав, що знаходиться в небезпеці (наприклад, вийшов на двох ворожих магів і поруч зі мною немає союзників). Виправив атаку незруйновних будівель (за правилами не можна було завдати шкоди другій вежі на лінії, не знищивши першу, однак друга вежа з сусідньої лінії була досить близько, щоб бот відволікався на неї). Було дуже багато спроб поліпшити ситуацію з допомогою зміни впливу ворогів на score в матриці. З явно позитивних змін — при розрахунку області небезпеки від ворожих магів став враховуватися кут їх повороту, крім кулдаунов умінь ворожих магів стало враховуватися також наявність мани і час її відновлення. Повністю переписана система націлювання з тією метою, щоб маг більш обережно вибирав, яким заклинанням він скористається в наступний раз (наприклад, навіщо взагалі витрачати ману навіть на базові магічні ракети, якщо у нас є файрбол, а мани не залишилося? Можна ж бити палицею або просто стояти в сторонці). Додано облік можливості уворота ворожого мага від мого пострілу. У розрахунку пострілу з допомогою базового заклинання і крижаний стріли для ворожих магів тепер став намагатися вистрілити в дві точки — центр мети і в точку, при стрільбі в яку збоку тікати однаково довго і вперед, і назад (ця точка знаходиться дещо спереду від центру мага). Тут я використовував знання, отримане при написанні алгоритму уворота. А рейтинг все танув і танув, від чого ставало все сумніше і сумніше.

І все-таки, через тиждень після поломки алгоритму ухилення я, розглядаючи черговий бій через свій візуалізатор, виявив, що мій бот, запустивши логіку ухилення і спокійно і акуратно йдучи від снаряда, випущеного «в чистому полі», несподівано став вважати, що ухилитися від снаряда він не може, і продовжив бій, як ні в чому не бувало піймавши порцію шкоди. Це змусило мене перевірити конкретно цю ситуацію. Баг, який став винуватцем тижневої смутку і печалі, був локалізований і жорстоко покараний.

Підготовка до раунду 2.
Після виправлення проблеми в алгоритмі уворота рейтинг знову почав зростати, і я перестав боятися не пройти у фінал. Однак за час, необхідний для підготовки до раунду 2, хотілося б навчитися користуватися всіма ультами, щоб потім можна було їх використовувати у фіналі. Але спочатку… Мій маг все ще дуже пасивно стоїть на лінії і не особливо завантажуватиме до атаки ворожих магів, які тримаються на відстані. І це хотілося б виправити. Минулого тижня була переписана система націлювання, і тепер в неї можна було більш-менш легко вставити даний милицю дане поліпшення. Я навчив бота підбігати безпосередньо до бажаної мети, якщо виконаний постріл у неї більш чи менш перекривав ризик на шляху до точки пострілу. Бот став грати відчутно агресивніше, набагато частіше змушуючи ворогів відступати від лінії битви, щоб підлікуватися, і набагато рідше відпускаючи підлікуватися ледь живих ворогів.

А далі… За час, що залишився до включення в пісочниці правил фіналу навчив мага використовувати заклинання прискорення і щита, відрегулював використання всіх бойових заклинань начебто фростболта, виправив чергову проблему з застряванням в деревах (яка виявилася майже прямо перед раундом 2) і… Для випадку, якщо кількість ворогів на лінії бота більше, ніж кількість союзників, враховуючи самого бота, включив вивчення гілки навичок, яка відповідає за швидкість бігу. І тут був помічений баг, виправлення якого було відправлено в 0:00:01, тобто із запізненням всього на одну секунду. А саме — незадовго до 2 раунду я таки вирішив навчити свого бота накладати заклинання прискорення на союзників, але зламав накладення цього заклинання на себе. І якщо на лінії був бій 2 на 3, то все було добре (т. к. за правилами при накладенні заклинання прискорення на союзника маг, який його накладає, також отримує копію заклинання на себе), то в бою 1 на 2 дана проблема була таки дуже критична. Проблема дала про себе знати буквально в перші ж бої у першій частині другого раунду, т. к. вибір лінії у мого бота досі працював за алгоритмом, реалізованому для раунду 1, тобто він вибирав ту лінію, де найменше своїх. Але це не завадило йому зайняти місце у верхніх рядках за підсумком першої частини другого раунду.

До другої частини раунду була додана логіка пошуку цілей для файрбола за зоною каста мага (одночасно з доопрацюванням логіки набігання для пострілу при його використанні), виправлені чергові помічені проблеми з застряванням в деревах (так, дерева все ще перемагали мого бота). Логіка застосування заклинань стала набагато краще враховувати те, коли ж необхідне кількості мани відновиться для чергового заклинання. Вже після запуску другої частини раунду 2 була трохи підправлена стрільба по миньонам (тепер стріляв у передній край, тобто туди, куди він дивиться. При стрільбі у центр міньйон міг відбігти від снаряда, якщо втік у бік від нас).

Підготовка до фіналу.
У фіналі правила відрізнялися тим, що тепер усіма магами за одну із сторін управляє стратегія однієї людини, що відкривало нові простори для командної гри. Перше, що я спробував зробити — скопіювати код для раунду 2 і покласти їх поруч, щоб запускати їх у випадку, якщо гра йде за правилами раунду 2, т. к. ускладнювати логіку, роблячи залежність від поточних правил гри не хотілося зовсім. Але… Система вирішила, що мої рішення приймати вона більше не хоче, і кілька годин було витрачено на пошуки причини, чому ж система видає помилку про те, що я її надсилаю «некоректний архів»… якби не загальний чат, то пошук причини міг би затягнутися і на набагато більший час. А виявилося — система просто не хоче приймати вихідні коди, які в розпакованому варіанті займають більше мегабайта на диску. Як я примудрився написати більше, ніж на мегабайт??? Загалом, з допомогою лому і якоїсь матері исходники, не знаходяться в активній розробці, були стиснуті минифификаторами, викинуті візуалізатори для перших двох раундів і необхідний мегабайт був досягнутий. Згодом у системі розширили можливість посилки исходников до 2МБ і даний пункт знайшов відображення в правилах, але в ту ніч, щоб надіслати пробний варіант стратегії на фінал (всі свої маги відправлялися на центральну лінію), довелося витратити досить багато часу. В результаті відправив неперевірену версію і пішов спати. У цій версії всі мої маги повинні були вчити різні гілки навичок і атакувати через одну центральну лінію (т. зв. «пуш з мзс»). А зранку виявив, що така тактика цілком непогано проявляє себе навіть з урахуванням того, що в 2 ночі я залив версію з багом і мої маги взагалі не хотіли вчити якісь навички.

Виправивши проблему з навичками і прибравши групове ходіння за бонусами (тепер за бонусом ходив тільки найближчий з моїх магів), приступив до написання групового взаємодії. Часу було виділено порівняно з іншими раундами відчутно менше (всього тиждень), а писати треба було по суті щось зовсім нове. Взаємодія між союзниками в раундах 1 і 2 було сильно ускладнено через сильної різниці стратегій, тому мною воно писалося окремо саме для фіналу.

Першою проблемою, з якою зіткнувся «пуш з мзс», була перевантаженість лінії союзними магами, які заважали один одному ухилятися від снарядів суперників і часто блокували шляхи відходу на безпечну відстань від ворогів. Рішення було досить простим і очевидним — додав штраф за перебування занадто близько з союзними магами, який ігнорувався, коли поточний маг сам знаходився в небезпеці. Тепер мої маги не заважали один одному ухилятися, а якщо хто-небудь з моїх хотів відступити в більш безпечне місце, він як би «розштовхував» інших. Разом з цією правкою додалася ще одна — зробив додаткове позитивне поле на відстані 600 від кожної союзної мага, завдяки чому в поведінці ботів залишалося достатньо свободи, але розбігатися занадто далеко один від одного вони вже не хотіли.

(Кликабельно, всередині gif-ка)


Небезпека навколо союзних магів при грі 2*5. Т. до. вона відключалася, якщо знаходимося в «небезпечній» зоні — іноді допомагала відступити, «розштовхуючи» своїх магів. В кінці гифки можна помітити зону «тяжіння». До своїх магів.

Наступна цілком розв'язувана проблема, з якою зіткнувся «пуш з мзс», була адаптивна стратегія від Івана Тямгина tyamgin, яка поверталася на захист в 4 людини, побачивши п'ятьох в атаці на центрі. Але спочатку робила це так, що всі ці 4 мага вступали в бій кожен зі свого боку, як би оточуючи моїх. Потрапивши в таке оточення, мої боти губилися і не могли збагнути, кого ж краще бити першим. І за час замішання один його маг, який залишався на бічній лінії, часто встигав дійти до моєї бази і знищити її.

Для вирішення такої проблеми я почав виділяти подобу «кластера» моїх магів для атаки — збиралася група для активних дій, яка складалася з усіх більш-менш цілих одиниць, що знаходяться близько один до одного (в радіусі близько 350 пікселів від середнього арифметичного їх координат). Якщо таких перебувало більше двох — у середньому радіусі дії (~900 пікселів) шукав магів, які не знаходяться під своєю вежею і поряд з ними немає магів для допомоги (максимум один, але для цілей без такої підтримки пріоритет був більше). Мета, у якій пасивними навичками була обрана швидкість або мала статус прискорення, ігнорувалися, т. к. ганятися за ними виходило собі дорожче. Якщо відповідні цілі знаходилися — мої маги всієї натовпом бігли в бік бідолахи, досить ефективно набираючи собі досвід і відправляючи заблукали магів на той світ позбавляючи відкололися від загальної групи магів тілесної оболонки. Для цього використовувалася четверта «псевдо лінія», яка спочатку була зроблена для збору бонусів і зміни лінії. В ній раніше був передбачений досить сильний бонус за те, щоб маг «йшов в потрібному напрямку», яке задавалося просто координатою, куди ми хочемо потрапити. Агресивна атака поодиноких ворогів згодом досить сильно допомагала в боях проти стратегій, які наполегливо намагалися ходити через ліс і всіляко оточувати мої основні сили.

Наступна проблема — втрата бази ворога досить високий, і, розбивши повністю центральну лінію, мої частенько довго не наважувалися на штурм. Так вони могли дочекатися, поки по інших лініях вороги не дійдуть до моєї бази і не знищать її раніше, ніж мої все ж зважаться на бій. В цілому нерішучість прибирати не хотілося, адже база ворога справді небезпечне місце, але додалося одна умова — якщо ми маємо перевагу в чисельності або на будь-який з бічних ліній була знищена моя друга вежа, то небезпека від бази починала ігноруватися і всім магам дружно було наказано заходити на ворожу базу з більш зручною боку з допомогою все тієї ж четвертої «псевдо лінії», яка додатково стимулювала дану атаку (при грі за академію це сторона, трохи правіше ворожої бази, т. к. найближча до бази вежа не так сильно заважає).

Після цих поліпшень поразок у боях 2*5 практично не залишилося, і я зосередився на намаганнях написати альтернативні тактики на випадок, якщо все-таки варіант атаки по центру дійсно почнуть масово перемагати. Однак у моєї стратегії не дуже добре виходило протистояти моїй же початкової тактики на фінал і після не дуже численних експериментів на цю тему цю ідею я все-таки відкинув.

Фінал
Прийшла п'ятниця — останній день перед першою частиною фіналу. На роботі був узятий відгул, все йшло просто чудово, і ніщо не віщувало біди. У четвер вночі моя стратегія все ще відчутно більш стабільно вигравала, ніж стратегії найближчих переслідувачів, і в п'ятницю я вже думав було розслабитися, але не тут то було. Антон Чумаченко (Antmsu), мабуть не дуже любив все це час спати по ночах, за час мого сну виправив деякі недоліки у своїй стратегії і тепер його стратегія майже постійно стала мене перемагати. Розслабитися морально вже не виходило, і я почав шукати підходи до того, як зламати конкретно цю стратегію в чесному бою. Ближче до вечора успіхів у цьому з допомогою невеликих змін досягти так і не вийшло, а ламати стратегію, протестовану практично на всіх фіналістах, страшенно не хотілося. До того ж після обіду мене також практично постійно став перемагати NighTurs, і ситуація стала виглядати зовсім вже гнітюче порівняно з тим, що було ще в четвер ввечері… В цілому, настрій в той день набагато простіше передати через зображення, ніж словами.


Коміти і гілки в локальному Git репозиторії в останній день перед стартом фіналу. Єдиний комміт в 4.30 PM, який пішов далі, не містив рівним рахунком ніяких поліпшень для стратегії.


Уважно спостерігаючи за поведінкою суперників в останні пару годин перед першою частиною фіналу, я зібрався з духом і спробував щось змінити в мікро управлінні бота, спираючись на свої спостереження. Зміни були незначні і додали агресивність моєї стратегії, однак запускати неперевірені зміни у фінал проти всіх учасників я не став. В результаті скористався можливістю перевірити нік суперника і тільки для Antmsu і NighTurs включав останні апдейти, все одно все виглядало так, що з ними в бою втрачати вже нічого.

Всім (включаючи мене) дуже сподобалася несподівана стратегія від Кирила Болонкина (core2duo), яка мені у першій частині фіналу завдала 6 поразок з 6, але програла всі 6 боїв NighTurs, тим самим, як здавалося на ранок, завдавши мені практично контрольний удар в плані можливості повернутися на позицію хоча б в топ 2. Подивившись перші пару боїв, я вирішив, що чекати дива сенсу немає, і результати краще буде подивитися вранці. Я припускав, що мене чекає приблизно третє місце, але морально готувався до гіршого варіанту.


Результати кращих учасників першої частини фіналу russian ai cup 2016. P — кількість перемог, G — кількість ігор. Мій нік в Ukrainian Ai Cup — Commandos. Кликабельно.

The last stand.
Вивчивши проміжні результати фіналу після першої частини, все, включаючи мене, сходилися на думці, що учасники з топ 2 будуть з'ясовувати стосунки «між собою», а я з великою часткою ймовірності збережу третю позицію. В якійсь мірі це мене тішило, т. к. за результатами було видно, що хоча б третє місце втратити вже відносно складно, але… Ipad? А навіщо мені взагалі Ipad? Я хочу MacBook! Хоча б Air... загалом, провівши у відносно депресивному стані всю п'ятницю я вирішив, що останню добу перед другою частиною фіналу втрачати на очікування того, що ж буде далі, не можна. І я абсолютно точно хочу піднятися вище. Тим не менше, кілька годин були проведені в роздумах, як же отримати бажаний результат. Всього 12 і 13 ігор було програно поточної двійкою лідерів фіналу, і я від них відставав на цілих 12 і 11 ігор відповідно. Навіть якщо я почну перемагати їх зі 100% шансом, що виглядало малоймовірно, цього все одно не вистачить, щоб наздогнати їх і тим більше обігнати. І мною було прийнято рішення переглянути програші з усіма гравцями і виправити це. Мені потрібен був практично 100%-ий результат. Та ну, це неможливо, може краще на корпоратив сходи.

Першою, звичайно ж, звертала на себе увагу стратегія core2duo. Управління магами на мікро рівні у нього було досить слабке і можна було практично зі 100% гарантією перемоги піти на нього в атаку в лоб. Це, на мій погляд, ідеальна тактика в даному випадку, але все ще хотілося чогось більш універсального на випадок появи клонів даної стратегії. Рішення було просте — якщо на лініях, відмінною від центральної, знаходиться дуже багато ворожих магів, я сильно підвищував бонус за перебування моїх магів в точках, з яких вони зможуть наносити шкоди. З цим підходом моя стратегії практично постійно перемагала при грі з core2duo, але очікуючи нових каверз від останнього для підстраховки додав перевірку: if («core2duo».equals(playerName)) — йдемо в пряму атаку на найближчого ворожого мага, де б той не перебував. Крім близько 100% ймовірності перемоги при поточних стратегіях це ще й принесло додаткову впевненість, що нічого поганого він мені зробити не зможе.

Другим пунктом йшов єдиний мій програш стратегії учасника GreenTea. У цій грі мої маги дуже вперто не хотіли йти на фінальний штурм при рівній кількості, але набагато, набагато більше пошарпаному суперника. При розгляді цієї гри більш пильно за допомогою дебага додатково знайшовся ще один баг — при пошуку «кластера» моїх магів для створення атакуючої групи у разі, якщо хоча б один маг був занадто далеко, група не могла бути знайдена через проблеми в оновленні середнього арифметичного позицій магів «кластера» при виключенні найдальшого з них. Виправивши даний баг і дописавши логіку для форсування атаки на ворожу базу в разі, якщо той, що обороняється суперник має набагато меншу кількість хіт поінтів, я перейшов до розгляду наступних проблем.

Далі йшли програші учасникам TonyK і tyamgin. Тестування з останніми на той момент версіями TonyK не виявило скільки-небудь великого числа поразок, і я подумав, що в його стратегіях щось було зламано. На всякий випадок ту ж злегка більш агресивну тактику, яка грала в першій частині фіналу тільки з Antmsu і NighTurs, перевірив і на ньому. Т. к. видимих проблем не виникло — залишив все як є. Те ж саме дрібне зміна було застосовано і в боях з tyamgin. Візуально воно давало невеликий позитивний ефект, і за результатами перевірок також було залишено як є.

Решта 4 учасника, з якими я мав поразки у першій частині фіналу, виділялися із загальної купи тим, що всі вони так само, як і я, всіма п'ятьма магами йшли по центральній лінії. Це була левова частина моїх поразок (звичайно, якщо забути про стратегію core2duo), і вирішити все це підбором коефіцієнтів і дрібними правками в мікро контролі магів, як я це намагався зробити напередодні в п'ятницю проти Antmsu, мені уявлялося дуже малоймовірним. Надихнувшись досвідом, отриманим від core2duo, я вирішив спробувати зробити для них щось особливе. Було досить нескладно помітити, що 3 з 4 цих стратегій на момент першої частини фіналу (а перед другою частиною фіналу все 4, що мені непогано допомогло) без зупинки йшли в атаку на першу ж вежу ворога аж до ближнього бою. План був простий — а що, якщо спробувати розбити цілу групу атакуючих на дві частини? До того ж коли вони підбігають до моєї вишці, то стають уразливі для заходження з флангу… За планом не у всіх з них буде можливість відступити в одному напрямку, і максимально швидке настання в спробі притиснути частина магів суперника до лісу може, в теорії, принести бажаний результат.


План атаки з флангу. Червоними стрілками позначені мої плановані пересування, синіми — очікувану поведінку суперника. Кликабельно.

Для перевірки цієї теорії спочатку я модифікував свою версію так, щоб вона ігнорувала небезпека від першої вишки і йшла на неї в атаку. Потім моя змінена стратегія запускалася з допомогою local-runner проти моєї версії, яка вже вміла робити захід з флангу для даного випадку. Результати вийшли вельми переконливими — нехай і з втратами у вигляді вежі, а іноді ще й 1 мага, але безглузда атака з флангу найчастіше призводила до отримання відчутної переваги на початку гри, і цього виявлялося достатньо, щоб залишилася частина битви практично стабільно проходила вже в користь свіжого оновлення. Надихнувшись локальним успіхом, я вирішив перевірити, як ця ідея буде працювати в бойових умовах на mortido і ud1, т. к. за моїми припущеннями, вони не стануть витрачати час на серйозні спроби написати щось, що ламало би мій підхід. Перевірка в бойових умовах також була успішно пройдена, і я замінив цю стратегію попереднім варіантом, щоб не світити збільшити ймовірність сюрпризу для учасників топ 2. Подальше шліфування дрібниць проходило з допомогою local-runner, і вже приблизно до 4 години ночі реалізація нового варіанту атаки була завершена.

Для перевірки на топ 2 учасниках я залив оновлену версію 11.39, тобто за 21 хвилину до початку другої частини фіналу. Тестування на топ 2 було пройдено успішно (1 поразка з 4 ігор, але, як виявилося, шанс на мою перемогу був навіть вище), і в такому вигляді стратегія залишилася до кінця.

Після запуску ігор я вже був у стані вичавленого лимона і пішов подрімати. Після невеликого відпочинку мене чекало дві новини, одна приємна і одна не дуже. Приємна — моя стратегія дійсно йшла практично без поразок (всього одну поразку за дві хвилі, а це 118 ігор). Неприємна — тестування проходило помітно повільніше, ніж у перший день, і було досить сумнівно, що хвиль буде стільки ж, скільки і в попередній… А за підсумками перших хвиль здавалося, що обігнати хоча б одного з двох перших учасників практично неможливо. Але тим не менше навіть за 5 хвиль з великою часткою везіння моєї стратегії все ж таки вдалося зайняти другу сходинку в підсумковому результаті.



Результати кращих учасників другій частині фіналу russian ai cup 2016. Кликабельно.



Остаточні результати кращих учасників фіналу russian ai cup 2016. Кликабельно.

Незважаючи на випадання з життя на півтора місяці, однозначно не шкодую, що не закинув ідею в самому початку. Завдання вийшла дуже об'ємною і по мірі реалізації постійно доводилося вибирати, які особливості правил і в яких випадках враховувати, а які варто проігнорувати. Врахувати в кінцевій реалізації усі нюанси було практично неможливо, що, мабуть, було додатковим цікавим і складним моментом у конкурсі, хоча фінальний алгоритм і залишив відчуття незавершеності. Хотілося б висловити організаторам RAIC подяку за проведення такого масштабного та й захоплюючого конкурсу, і вже практично за традицією, особливу подяку хотілося б висловити Роману Удовиченко (Romka) за створення загального чату, де багато учасники знаходили для себе корисну інформацію, досить інформативні таблиці з проміжними результатами (можна бачити на скріншотах вище), які допомогли мені у підготовці до останньої частини фіналу, і за початкову вичитку даного поста.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.