Введение
Начиная с первого Starcraft AI Competition, проведённого в 2010 году, тема искусственного интеллекта в стратегиях реального времени (RTS) становится всё более популярной. Участники таких соревнований представляют своих ИИ-ботов Starcraft, которые сражаются в стандартной версии Starcraft: Broodwar. Эти соревнования по играм RTS, вдохновлённые предыдущими соревнованиями, такими как Open RTS (ORTS), стали примерами демонстрации текущего состояния искусственного интеллекта в стратегических играх реального времени. ИИ-боты Starcraft управляются с помощью интерфейса Brood War Application Programming Interface (BWAPI), разработанного в 2009 году в качестве способа взаимодействия и управления Starcraft: Broodwar с помощью языка C++. С ростом функционала и популярности BWAPI начали появляться первые ИИ-боты (агенты) для Starcraft и появилась возможность организации настоящего соревнования ИИ по Starcraft. Мы подробно расскажем о каждом крупном соревновании ИИ по Starcraft, а также о развитии UAlbertaBot, нашего бота, участвующего в этих соревнованиях. Следует учесть, что я был организатором соревнований AIIDE с 2011 года и, естественно, имею больше информации об этих соревнованиях. Каждое соревнование будет рассматриваться в хронологическом порядке проведения, с указанием полных результатов и ссылок на скачивание исходных кодов ботов и файлов ответов соревнований AIIDE и CIG.
При желании можно прочитать отчёт о AIIDE Starcraft AI Competition 2015 года здесь.
«Почему не StarCraft 2?»
Этот вопрос мне постоянно задают, когда я говорю, что мы устраиваем соревнования ИИ по Starcraft: BroodWar. В этих соревнованиях в качестве интерфейса программирования BroodWar используется только BWAPI. BWAPI был создан реверс-инжинирингом BroodWar и применяет считывание и запись в пространство памяти программы BroodWar для считывания данных и отправки команд в игру. Поскольку любая программа, занимающаяся подобными действиями, будет считаться хаком или чит-движком, Blizzard сообщила, что не разрешает нам делать что-то подобное для StarCraft 2. На самом деле, большинство версий лицензионных соглашений конечного пользователя (EULA) StarCraft 2 явно запрещает любое изменение программы. Мы рады, что компания Blizzard позволила нам проводить турниры с использованием BWAPI, она даже помогла нам, предоставив призы для турнира AIIDE, однако из-за изменения её политики мы не можем повторить то же самое для StarCraft 2.
Существуют и другие игровые движки RTS, которые можно использовать в соревнованиях. Один из таких движков — ORTS — бесплатный программный движок RTS, на котором проводились соревнования, пока в 2010 году не был выпущен BWAPI и проведены первые соревнования AIIDE Starcraft AI Competition. Ещё один движок — microRTS, это движок RTS на Java, который играет в упрощённую RTS на основе сеток. Он был разработан специально для тестирования техник ИИ.
Техники ИИ для RTS
Крайне рекомендую изучить замечательные обзоры современного состояния техник ИИ для StarCraft и описания архитектур ботов в следующих статьях:
- StarCraft Bots and Competitions [2016]
D. Churchill, M. Preuss, F. Richoux, G. Synnaeve, A. Uriarte, S. Ontanon, and M. Certicky
Springer Encyclopedia of Computer Graphics and Games - RTS AI Problems and Techniques [2015]
S. Ontanon, G. Synnaeve, A. Uriarte, F. Richoux, D. Churchill, and M. Preuss
Springer Encyclopedia of Computer Graphics and Games - A Survey of Real-Time Strategy Game AI Research and Competition in StarCraft [2013]
S. Ontanon, G. Synnaeve, A. Uriarte, F. Richoux, D. Churchill, and M. Preuss
Accepted to TCIAIG (August 2013)
Благодарности
Исследования и соревнования ИИ по RTS требуют огромного объёма труда множества людей, поэтому я хочу поблагодарить тех, кто помогал в организации нынешних и прошлых соревнований, разрабатывал ботов и в целом помогал развитию ИИ для RTS. Во-первых, я благодарю исследовательскую группу ИИ RTS Альбертского университета (UofA), членом которой я являюсь. Университет участвует в изучении ИИ для RTS с момента выхода мотивирующей статьи Майкла Буро (Michael Buro) в 2003 году. UofA проводил ORTS AI Competition в 2006-2009 годах, и начиная с 2011 года ежегодно проводит AIIDE Starcraft AI Competition. Хочу лично поблагодарить бывших и действующих членов исследовательской группы ИИ RTS за всю их многолетнюю помощь в рекламе, организации и проведении этих соревнований, а также за то, что они продолжают проводить исследования мирового уровня в этой области. На фотографии ниже, слева направо: Николас Баррига (Nicolas Barriga), Дэвид Чёрчилл (David Churchill), Мариус Станеску (Marius Stanescu) и Майкл Буро (Michael Buro). На снимок не попали бывшие члены группы Тим Фуртак (Tim Furtak), Стерлинг Оерстен (Sterling Oersten), Грэм Эриксон (Graham Erickson), Дуг Шнайдер (Doug Schneider), Джейсон Лоренц (Jason Lorenz) и Абдалла Саффидин (Abdallah Saffidine).
Я хочу также поблагодарить тех, кто организовал и провёл текущие и прошлые соревнования Starcraft AI Competition. Спасибо Бену Веберу (Ben Weber) за организацию первых соревнований AIIDE Starcraft AI Competition, которые зажгли международный интерес к области исследований ИИ для RTS. Михал Сертицки (Michal Certicky) ежегодно вкладывает большие усилия для проведения и поддержки Student Starcraft AI Tournament, а также постоянной турнирной лестницы и видеостриминга ботов. Также он сильно помог в популяризации области ИИ для RTS. Организаторами соревнований CIG Starcraft AI Competition стали Йохан Хагельбак (Johan Hagelback), Майк Преус (Mike Preuss), Бен Вебер (Ben Weber), Тобиас Мальман (Tobias Mahlmann), Гёнджун Ким (Kyung-Joong Kim), Хочхоль Чо (Ho-Chul Cho), Инсеок О (In-Seok Oh) и Манче Ким (Man-Je Kim). Благодарю также Красимира Крастева (Krasimir Krastev) (krasi0) за хранение оригинальной Starcraft AI Bot Ladder. Также большое спасибо Санти Онтанону за развитие системы ИИ microRTS. И особую благодарность я приношу Адаму Хайнерману (Adam Heinermann) за то, что он продолжает разрабатывать BWAPI. Без него все эти исследования были бы невозможны.
Соревнования Starcraft AI Competition
AIIDE 2010
[Прим. пер.: таблицы в оригинале статьи собираются джаваскриптом, поэтому переносить их в перевод было бы слишком трудоёмко. Если нужны рабочие ссылки в таблице, они доступны в оригинале.]
Соревнования AIIDE Starcraft AI Competition впервые были проведены в 2010 году Беном Вебером в Expressive Intelligence Studio Калифорнийского университета в Санта-Круз, как часть конференции по искусственному интеллекту и интерактивным цифровым развлечениям AIIDE (Artificial Intelligence and Interactive Digital Entertainment). 26 участников соревновались в четырёх различных игровых режимах, которые варьировались от простых боёв до игры в полный Starcraft. Поскольку это был первый год проведения соревнований и инфраструктура ещё была не развита, каждая игра турнира запускалась вручную на двух ноутбуках. Записывать результаты приходилось тоже самостоятельно. Кроме того, для ботов не сохранялась информация, которая позволила бы им узнавать больше о противниках между матчами. В соревнованиях 2010 года было четыре турнирных категории. Первый турнир представлял собой битву с микроменеджментом юнитов на плоской поверхности, состоявшей из четырёх отдельных игр с разными сочетаниями юнитов. Из шести соревнующихся победителем стал FreSCBot, а Sherbrooke занял второе место. Второй турнир тоже представлял собой микроменеджмент юнитов, но у же на сложном рельефе. В этой категории было два претендента, и в ней снова выиграл FreSCBot, обогнав Sherbrooke. Третий турнир представлял собой технически ограниченную игру в StarCraft на одной известной карте с отключенным «туманом войны». Игроки могли выбрать только расу протоссов и использование новых юнитов было запрещено. В этом турнире с выбыванием после двух поражений (double elimination) участвовало восемь ботов. В финале MimicBot занял первое место, победив Botnik. Поскольку это был вариант StarCraft с полной информацией, MimicBot выбрал стратегию «повторять порядок строительства противника, получая при возможности преимущество в экономике», и она сработала достаточно хорошо.
Четвёртый турнир считался основным соревнованием, в котором боты играли в полноформатную игру StarCraft: Brood War со включенным «туманом войны». Турнир вёлся в формате double elimination со случайными парами. Выбирались результаты лучших пяти игр. Противники могли играть за любую из трёх рас, в геймплее были запрещены только действия считающиеся «читерством» в сообществе StarCraft. Поскольку компьютерные программы, написанные на BWAPI, не имеют ограничений на количество отправляемых движку Starcraft команд, была возможны некоторые действия, не предусмотренные разработчиками, например, скольжение зданий и хождение наземных юнитов сквозь стены. Такие действия считались читерством и были запрещены в турнире. Набор карт из пяти хорошо изученных профессиональных карт объявлялся противникам заранее. Из них для каждой игры выбиралась случайным образом одна. Четвёртый турнир выиграл Overmind — бот зергов, созданный крупной командой из Калифорнийского университета (Беркли). Overmind победил в финале терранского бота Krasi0 Красимира Крастева.
Overmind активно использовал мощного и ловкого летающего юнита зергов муталиска (Mutalisk), которым он очень успешно управлял с применением потенциальных полей. В целом стратегия Overmind заключалась в первоначальной обороне из зерглингов (Zergling) и тонущих колоний (Sunken Colony) (неподвижных защитных башен) для защиты изначального развития и сбора ресурсов для создания первых муталисков. После создания муталисков они отправлялись на вражескую базу, патрулировали и атаковали её периметр. Если бот не выигрывал прямую первую атаку, он медленно патрулировал и уничтожал любых незащищённых юнитов, постепенно истощая врага до предела, после чего уничтожал его последней атакой. Занявший второе место бот krasi0 использовал глубоко защитную стратегию терранов. Он строил бункеры (Bunker), осадные танки (Siege Tank) и ракетные башни (Missile Turret) для защиты. После постройки определённого количества юнитов он отправлял армию механических юнитов на базу врага. Этот бот работал достаточно хорошо и в соревнованиях проиграл только Overmind. В 2011 году сайт Ars Technica написал превосходную статью об Overmind. Также проводился матч человека против машины, в котором участвовал профессиональный игрок и лучшие ИИ. Его можно посмотреть здесь:
Первая версия UAlbertaBot была выпущена летом 2010 года и отправлена на соревнования AIIDE 2010 в сентябре. Группа из шести студентов под моим с Майклом Буро из Альбертского университета руководством создала первоначальную версию UAlbertaBot с использованием BWAPI и стандартной библиотеки Brood War Standard Add-on Library (BWSAL), которая предоставляла такие функции, как простая планировка очереди строительства, размещение зданий и управление рабочими. Версия 2010 года бота UAlbertaBot играла за расу зергов и использовала одну основную стратегию, в которой активно применялся летающий юнит зерков муталиск. Хотя функции боя и микроменеджмента у бота были реализованы хорошо, серьёзные логические ошибки в начале игры и планировании порядка строительства привели к плохим результатам в соревнованиях 2010 года. Он был побеждён в третьем раунде сетки терранским ботом krasi0. Эта первая реализация UAlbertaBot страдала от технических проблем, поэтому после соревнований мы приняли решение полностью переписать бота к следующим соревнованиям.
CIG 2010
После успеха соревнований AIIDE 2010 была предпринята попытка проведения соревнований по ИИ для Starcraft в размках конференции Computational Intelligence in Games (CIG). В соревнованиях CIG 2010, организованных Йоханом Хагельбаком, Майком Преусом и Беном Вебером, использовался единственный режим игры, похожий на третий турнир с техническими ограничениями с соревнований AIIDE 2010, но вместо расы терранов боты играли за расу протоссов. К сожалению, первый год соревнований CIG пострадал от серьёзных технических проблем, что привело к решению использовать специально созданные карты Starcraft вместо традиционных, которые приводили к критическим ошибкам ПО Brood War Terrain Analysis (BWTA) многих ботов. Из-за этих частых «зависаний» было решено, что в соревнованиях невозможно определить победителя. UAlbertaBot не участвовал в этих соревнованиях, потому что находился в процессе полного переписывания.
AIIDE 2011
В 2011 году соревнования AIIDE проводились в Альбертском университете и так продолжается и по сей день. Они ежегодно организуются и проводятся мной и Майклом Буро. Из-за малого количества участников в первом, втором и третьем турнирах соревнований 2010 года, мы решили, что в 2011 соревнования AIIDE будут состоять только из полнофункциональной игры в Starcraft (с теми же правилами, что и в четвёртом турнире 2010 года), а от более мелких турниров по микроменеджменту мы отказались. Изменены были и правила турнира: все участники должны предоставить исходный код своих ботов и разрешить его публикацию после завершения соревнований. Для этого было несколько причин. Во-первых, снижался барьер входа для будущих соревнований: программирование ИИ-бота для Starcraft занимает очень много времени, поэтому будущие участники могут скачать и изменить исходный код старых ботов, чтобы сэкономить время. Ещё одна причина — упрощение защиты от читов: на турнире теперь играются тысячи игр, поэтому мы не можем наблюдать за каждой и отслеживать использование читерских тактик, но их гораздо проще обнаружить исследованием исходного кода (слишком сильная обфускация кода запрещена). И последняя причина: помощь в развитии современных ИИ для Starcraft. Разработчики ботов могут заимствовать стратегии и техники ботов прошлого, изучая их исходный код. В идеале все боты в новых соревнованиях должны быть как минимум такими же сильными, как в прошлом году. В соревнованиях 2011 года участвовало 13 ботов.
Турниры 2010 года запускались Беном Вебером на двух ноутбуках. Приходилось вручную запускать Starcraft и создавать игры. Физическая нагрузка была довольно высока — в единственном турнире double elimination со случайными парами проводилось примерно 60 игр. Это привело к негативным отзывам: турнир в таком стиле сильно зависел от того, насколько повезёт с парой. Поэтому в соревнованиях 2011 года мы решили избавиться от любой случайности в турнирах и использовали формат кругового цикла. В таком формате нужно сыграть в гораздо большее количество игр, поэтому летом 2011 года Джейсон Лоренц (летний студент-бакалавр Майкла Буро) и я написали ПО, автоматически составлявшее график и запускавшее турниры кругового цикла в Starcraft на произвольном количестве компьютеров, соединённых в локальную сеть. В этом ПО использовалась клиент-серверная архитектура с одним сервером, создающим график игр и хранящим результаты, и несколькими клиентами, на которых была запущена игра Starcraft и ПО для мониторинга процесса игры и записи результатов после её завершения. Файлы ботов, повторы игр и окончательные результаты были доступны всем клиентам в общей папке Windows в локальной сети. Первоначальная версия ПО позволяла проводить 2340 игры за то же время, за которое мы провели 60 игр в соревнованиях 2010 года. Боты сыграли по тридцать раз с каждым из противников. В соревнованиях использовалось 10 карт, выбранных из профессиональных турниров и сбалансированных для всех рас. Их можно было скачать с веб-сайта соревнований заранее. Соревнования AIIDE были созданы по модели «человеческих» соревнований, в которых набор карт и противники известны заранее, чтобы можно было подготовиться и смоделировать действия оппонентов.
В конце пятидневных соревнований первое место занял Skynet, второе — UAlbertaBot, а третье — Aiur. Skynet — это бот протоссов, написанный разработчиком ПО Эндрю Смитом (Andrew Smith) из Великобритании, он использовал множество надёжных стратегий протоссов: раш зилотов (Zealot), армия драгунов (Dragoon)/зилотов в середине игры и армия из зилотов, драгунов и разорителей (Reaver) в конце игры. Его надёжная работа с экономикой и хорошая защита на ранних этапах позволили продержаться против намного более агрессивных ботов протоссов — UAlbertaBot и Aiur. UAlbertaBot тогда играл за расу протоссов, и подробно описан в следующем параграфе. Aiur был написан Флорианом Ришо (Florian Richoux), студентом магистратуры Нантского университета. Он тоже играл за протоссов и использовал несколько разных стратегий, таких как раш зилотами и армия из зилотов и драгунов. Между лучшими тремя финалистами возникла интересная ситуация «камень-ножницы-бумага»: Skynet выиграл UAlbertaBot в 26 играх из 30, UAlbertaBot победил Aiur в 29 играх из 30, а Aiur одержал победу над Skynet в 19 играх из 30.
Бот Overmind, выигравший соревнования AIIDE 2010, не участвовал в 2011 году, потому что обнаружилась его большая уязвимость к агрессии на ранних этапах игры и он легко побеждался рашами всех трёх рас. Команда разработчиков Overmind также сообщила, что не хочет раскрывать исходный код бота, поэтому не может участвовать в соревнованиях 2011 года. Вместо них команда студентов-бакалавров из Беркли участвовала с терранским ботом Undermind, занявшим седьмое место.
UAlbertaBot был полностью переписан в 2011 году мной и Стерлингом Оерстеном (студентом Майкла Буро) и вместо зергов начала играть за расу протоссов. Самой важной причиной перехода к протоссам заключалась в том, что мы обнаружили, что реализация стратегий протоссов гораздо проще с технической точки зрения, и эти стратегии гораздо более стабильны при тестировании. Стратегии расы зергов сильно зависят от умного расположения зданий и эту проблему в то время мы исследовали не очень хорошо. Поскольку зерги довольно слабы в защите на ранних этапах игры, их здания нужно располагать таким образом, чтобы они формировали «лабиринт» до базы, замедляющий продвижение врага к рабочим юнитам. У расы протоссов нет такой проблемы и её защита на ранних этапах достаточно хороша благодаря мощным юнитам — зилотам и драгунам. Ещё одна причина перехода к протоссам — добавление системы поиска порядка строительства, которую разрабатывали с учётом более простой инфраструктуры зданий протоссов, поэтому она не работала для зергов и терранов. Эта система планирования порядка строительства зданий имела цель построить определённое количество типов юнитов. Она могла автоматически планировать оптимальные по времени порядки строительства в реальном времени, и обеспечивала гораздо лучшие результаты, чем приоритетная система порядка строительства системы BWSAL, использованной в версии UAlbertaBot 2010 года. Добавленная в UAlbertaBot новая система планирования очереди строительства была первой версией комплексного подхода на основе поиска, сейчас используемого во всех ботах на соревнованиях ИИ для Starcraft. Эта новая версия UAlbertaBot реализовала очень агрессивную стратегию раннего раша зилотами, который ошеломлял противников и позволял выиграть многие игры всего за несколько минут. Если первоначальная стратегия раша зилотами не убивала врага, она переходила в создание дистанционных юнитов — драгунов для использования в стратегии на средних и поздних этапах игры. UAlbertaBot довольно хорошо работал и достиг второго места в соревнованиях. Соотношение побед и поражений у него было сравнимо только с результатами Skynet и Undermind. Боту Skynet удалось остановить ранние раши UAlbertaBot с помощью впечатляющего использования драгуна в начале игры, позволившего убить несколько зилотов одним драгуном. Стратегия Undermind заключалась в строительстве нескольких бункеров терранов в качестве начальной защиты, препятствующей агрессивному рашу UAlbertaBot.
CIG 2011
Соревнования CIG 2011 были организованы Тобиасом Мальманом из Копенгагенского университета информационных технологий и Майком Преусом из Дортмундского технического университета. Учтя уроки предыдущего года, на этот раз соревнования CIG проводили на стандартном «человеческом» наборе из пяти карт, однако в отличие от AIIDE, карты не были известны участникам заранее. В соревнованиях использовались те же правила, что и в турнире AIIDE 2011: полнофункциональная игра в Starcraft со включенным «туманом войны» и запретом читерства. Два важнейших отличия в правилах заключались в том, что для CIG необязательно было раскрывать исходный код ботов, а набор карт был неизвестен заранее. Поскольку и AIIDE, и CIG проходили в августе (из-за графика конференций) и в них часто участвовали одинаковые боты, организаторы CIG решили немного изменить правила турнира, скрыв набор карт, что привело бы к более интересным результатам. В соревнованиях участвовало десять ботов, и поскольку у организаторов CIG не было ПО для автоматизации, игры запускались вручную всего на нескольких компьютерах. Из-за этого вместо одного кругового турнира, как в AIIDE, соревнования были разделены на две группы из пяти ботов с десятью круговыми играми на каждую пару. После этого группового этапа лучшие два бота из каждой группы выходили в финальную группу и для каждой пары снова игрались по десять игр. Несмотря на то, что UAlbertaBot победил Skynet в первой группе, Skynet занял первое место в финале, второе место с незначительным отрывом занял UAlbertaBot, третье — Xelnaga, а четвёртое — BroodwarBotQ.
Поскольку между двумя соревнованиями был промежуток всего в пару недель, для CIG ни в Skynet, ни в UAlbertaBot не вносилось крупных изменений. Единственными изменениями в UAlbertaBot было удаление фрагментов введённой вручную информации о картах и расположении зданий на картах, участвовавших в AIIDE. Они были заменены алгоритмическими решениями.
SSCAIT 2011 (подробные результаты)
Первый студенческий турнир по ИИ для Starcraft (Student Starcraft AI Tournament, SSCAIT) проводился зимой 2011 года и был организован Михалом Сертицки из Университета Коменского в Братиславе. Этот турнир был задуман как часть курса «Введение в ИИ», преподаваемого Михалом в университете. В качестве части курса каждый студент должен был написать бота для соревнований. Поскольку на курсе было много студентов, в соревнованиях приняло участие 50 человек. Все они были студентами. Специализированное ПО, написанное Михалом, использовалось для автоматического составления графика и запуска игр турнира. Формат турнира разделил 50 участников на десять групп по пять человек для групповых этапов. 16 финалистов переходили на этап сетки double elimination. Победителем финала стал Роман Даниэлис (Roman Danielis), студент Университета Коменского. О ботах и стратегиях на этих соревнованиях известно не так много, потому что они не получили широкой известности за пределами университета, поэтому бот UAlbertaBot в них не участвовал.
AIIDE 2012
Соревнования AIIDE 2012 снова проводились в Альбертском университете. В них было внесено серьёзное изменение: постоянное хранилище файлов позволяло ботам обучаться в процессе всего времени соревнований. ПО управления турниром было улучшено, каждый бот получил доступ к папке чтения и папке записи, содержащимся в общей папке, доступной для всех клиентских машин. В течение каждого раунда боты могли считывать из папки чтения и записывать в папку записи, и в конце каждого кругового цикла (когда между всеми ботами было проведено по одной игре на одной карте) содержимое папки записи копировалось в папку чтения, предоставляя доступ ко всей информации, записанной в предыдущих раундах. Такой метод копирования гарантировал, что никакой из ботов не получит преимущества в информации в течение раунда благодаря графику. В соревнованиях 2012 года участвовало десять ботов, и к концу пятого дня было сыграно 8279 игр, по 184 для каждой пары ботов. Окончательные результаты были почти аналогичны результатам 2011 года. Skynet занял первое место, Aiur — второе, а UAlbertaBot — третье. Работа Aiur была усовершенствована введением новой стратегии под названием textit{cheese}: стратегии раннего раша с фотонной пушкой (Photon Cannon), к которой другие боты оказались не готовы.
Матчи человека против машины 2012 года можно посмотреть здесь:
Для этих соревнований в UAlbertaBot было внесено одно серьёзное обновление — добавление SparCraft combat simulation package. В версии 2011 года UAlbertaBot просто ждал создания порогового количества зилотов, а затем постоянно отправлял их на вражескую базу и даже не отступал. В версии 2012 года был обновлён модуль симуляции боя, позволивший выполнять оценку результатов боя. Он применялся в битвах, чтобы предсказать, кто ней выиграет. Если прогнозировалась наша победа, то бот продолжал атаковать, если победа врага — бот отступал к своей базе. Эта новая тактика доказала свою силу на практике, однако защита Aiur на раннем этапе игры значительно улучшилась по сравнению с прошлым годом, когда UAlbertaBot занял второе место. В UAlbertaBot для соревнований 2012 года также реализовали три чёткие стратегии: раш зилотами из версии 2011 года, раш драгунами и раш тёмными тамплиерами (Dark Templar). Бот также использовал ввод-вывод в постоянный файл для хранения данных матчей против конкретных противников, и выбирал стратегию против соответствующего бота с помощью формулы UCB-1. Эта стратегия обучения работала довольно хорошо: 60% побед в начале турнира превратились к концу турнира в 68,6%. Одна из главных причин победы Aiur над UAlbertaBot в турнире заключалась в том, что стратегии рашей драгунами и тёмными тамплиерами были плохо реализованы. Поэтому алгоритм обучения выбору стратегий в конце концов пришёл к постоянному использованию стратегии раша зилотами, и исследование других стратегий на примере прошлых побед оказалось бесполезным. Если бы стратегия раша зилотами выбиралась в каждой игре, то UAlbertaBot занял бы второе место.
CIG 2012
В соревнованиях CIG 2012 года использовалось ПО управления турниром с AIIDE, поэтому в рамках турнира можно было провести гораздо больше игр. В соревнованиях было десять участников, причём многие боты участвовали и в AIIDE. Использовался набор из шести заранее неизвестных карт, которых не было в предыдущем турнире. Всего было сыграно 4050 игр, каждый бот сыграл со всеми остальными по 90 раз. Как и в AIIDE, ботам для обучения были доступны чтение и запись в постоянный файл, однако из-за различий в структуре сетевых папок соревнований AIIDE и CIG они работали не совсем так, как задумывалось. Также стоит заметить, что по сравнению с AIIDE здесь был в три раза больше сбоев ботов, поэтому стало очевидно наличие технических проблем с ПО управления турниром AIIDE. Skynet снова победил, UAlbertaBot занял второе место, Aiur — третье, а Adjutant — четвёртое. В этих соревнованиях UAlbertaBot не использовал файл данных и обучение, потому что эта техника проявила себя не лучшим образом на соревнованиях AIIDE 2012. Была реализована стратегия раша зилотами, позволившая боту взобраться на второе место.
SSCAIT 2012 (подробные результаты)
Несколько месяцев спустя, в декабре, был проведён второй турнир SSCAI, который гораздо шире рекламировался участникам за пределами Университета Коменского. В соревнованиях снова участвовало много ботов с курса Михала Сертицки по ИИ, а общее количество участников составило 52 бота. Формат турнира представлял собой простой круговой цикл, где каждый бот играл по одной игре с остальными, или по 51 игре на каждого бота. После завершения кругового цикла финальные бои были разделены на две категории: студенческий дивизион и смешанный дивизион. Для участия в студенческом дивизионе бот должен был быть написан единственным студентом. Очки распределялись следующим образом: 3 очка за победу, 1 очко за ничью. В финале студенческого дивизиона первое место занял Матей Истеник (Matej Istenik) (бот Dementor) из Жилинского университета (Словакия), второе — Марцин Бартницки (Marcin Bartnicki) из Гданьского технологического университета, а третье — UAlbertaBot. Смешанный дивизион был доступен для всех участников. Восемь лучших ботов соревновались в сетке с выбыванием после первого поражения. В финале IceBot победил Марцина Бартницки и занял первое место. В этих соревнованиях использовалась версия UAlbertaBot с CIG 2012, потому что в SSCAIT тоже применялся набор неизвестных карт.
CIG 2013
В 2013 году соревнования CIG проводились на несколько недель раньше, чем AIIDE. ПО управления турниром, которое должно было быть готово к соревнованиям AIIDE, переписывалось, поэтому в CIG использовали версию ПО 2012 года. Это значило, что система файла обучения не работала по тем же причинам, что и в предыдущем году. Из-за дополнительных технических трудностей с настройкой турнира была сыграна всего 1000 игр, всего четверть от количества прошлого года. Тройка лучших была такой же, что и в предыдущем году: Skynet — первое место, UAlbertaBot — второе, и Aiur — третье. Xelnaga переместился с прошлого шестого места на четвёртое. UAlbertaBot подвергался серьёзным изменениям (см. в разделе ниже), которые были ещё не завершены ко времени соревнований CIG 2013, поэтому участвовала версия бота с AIIDE 2012. Обновление было полностью завершено к соревнованиям AIIDE несколькими неделями позже.
AIIDE 2013 (подробный отчёт о соревнованиях)
Для соревнований AIIDE 2013 ПО управления турниром было почти полностью переписано, чтобы быть более устойчивым в разных схемах сетей. Предыдущие версии ПО полагались на существование общих папок Windows для хранения файлов, теперь вместо них стали использовать обмен данными через сокеты Java. Все файлы ботов, повторы игр, результаты и папки чтения/записи запаковывались и отправлялись через сокеты Java. Это означало, что турнир теперь можно проводить в сети с любой конфигурацией, поддерживающей TCP (для сокетов Java) и UDP (для сетевой игры Starcraft). Руководство/демонстрацию этого ПО управления турниром можно посмотреть здесь:
В соревнованиях 2013 года участвовало всего 8 ботов, и это до сих пор остаётся минимальным количеством из всех турниров, хотя и качество ботов было довольно высоким. Всего было сыграно 5597 игр, что позволило провести 200 битв с каждым из ботов, по двадцать на каждой из десяти карт, оставшихся неизменными с прошлого года. Обычные фавориты снова хорошо себя проявили, однако UAlbertaBot занял первое место и сверг с трона Skynet, переместившегося на второе. На третьем месте — Aiur, на четвёртом — Ximp, новый бот, написанный Томасом Вайда (Tomas Vajda), студентом с курса по ИИ Михала Сертицки в Университете Коменского. Ximp играл за расу протоссов и его стратегия заключалась в очень раннем расширении экономики под защитой фотонных пушек. Он играл в глубокой защите и строил армию авианосцев (Carrier), очень сильных летающих юнитов поздних этапов игры. После создания определённого количества авианосцев они пролетали по всей карте, уничтожая всё на своём пути. К сожалению, ошибка в коде Ximp приводила к 100% сбоев игр на карте Fortress, дававших противникам лёгкую победу. Если бы не этот сбой, он бы запросто занял третье место. Примечательно также впечатляющее обучение стратегии бота Aiur: первоначальный уровень побед в 50% постепенно повысился к концу соревнований до 58,51%, что подняло его с четвёртого на третье место.
Для этих соревнований в UAlbertaBot внесли изменения, но более важной была обновлённая версия SparCraft. В UAlbertaBot раньше использовалась более простая версия SparCraft, но она давала намного менее точные результаты, чем новый модуль SparCraft. Он правильно симулировал все повреждения и типы брони, что не учитывалось в предыдущей версии. Это обеспечивало гораздо более точную симуляцию, значительно улучшившую поведение бота в начале игры. Бота избавили от стратегий драгунов и тёмных тамплиеров и оставили только раш зилотами, который по-прежнему был сильнейшей стратегией. Единственным исключением были бои со Skynet, где бот, выполнявший раш тёмными тамплиерами в прошлом соревновании продемонстрировал, что он довольно слаб к этой стратегии. В версии UAlbertaBot 2012 года был найден баг, заставлявший всех рабочих юнитов бота преследовать любых юнитов, что привело к победе Skynet и Aiur из-за недостатка ресурсов, когда такое происходило. Были исправлены эта серьёзная ошибка и несколько мелких, благодаря процент побед достиг своего максимума. UAlbertaBot обогнал Skynet почти на 10% побед.
SSCAIT 2013 (подробные результаты)
В соревнованиях SSCAIT снова участвовало много ботов с курса по ИИ 2013 года и более 50 участников. В турнире 2013 года было проведено почти в два раза больше игр, чем в 2012 году: игралось по два раунда кругового цикла между всеми ботами на выбранных случайным образом картах. Результаты снова были разделены на две категории, студенческую и смешанную, с теми же правилами, что и в прошлом году. В студенческом дивизионе первое место занял Ximp, второе — бот WOPR, написанный Сореном Клеттом (Soren Klett) из Университета Билефельда, а UAlbertaBot снова занял третье место. Технические проблемы и ошибки на ранних этапах игры Ximp с соревнований AIIDE были исправлены и он очень хорошо проявил себя на этапе кругового цикла. В смешанном дивизионе лучшие восемь ботов из этапа кругового цикла играли в сетке с выбыванием после первого поражения (single elimination). В четвертьфинале UAlbertaBot был побеждён ботом IceBot. Финал проводился между IceBot и krasi0. Бот krasi0 победил и IceBot занял второе место. Версия UAlberaBot для AIIDE использовалась в этих соревнованиях без всяких изменений.
CIG 2014
Соревнования CIG 2014 организовали Гёнджун Ким, Хочхоль Чо и Инсеок О из Седжонского университета. В них участвовало 13 ботов. В 2014 году для CIG использовались 20 карт, неизвестных противникам. До сего времени это был самый большой набор карт, использовавшихся в соревнованиях ИИ по Starcraft. В турнире применялась обновлённая версия ПО управления турниром AIIDE, то есть чтение и запись в файл впервые полностью заработали на соревнованиях CIG. Всего было сыграно 4680 игр, каждый бот сыграл по три раза со всеми остальными на каждой из двадцати карт. В часть сильных ботов прошлого были внесены крупные изменения, и это сказалось на результатах.
В соревнованиях выиграл IceBot, второе место занял Ximp, третье — LetaBot, и четвёртое — Aiur. IceBot участвовал в соревнованиях с 2012 года, но никогда не занимал места выше шестого. Его стратегии были полностью переработаны и над его созданием трудилось больше людей. В результате получилась гораздо более стабильная и надёжная система. Благодаря очень прочной защите на ранних этапах игры он мог обороняться от многих ботов с ранним агрессивным поведением. Ximp продолжил использовать свою стратегию с авианосцами, внеся небольшие изменения и исправив ошибки. LetaBot был новым ботом терран, написанным Мартином Ройаккерсом (Martin Rooijackers) из Маастрихтского университета. Исходный код основан на версии UAlbertaBot 2012 года и адаптирован под игру за терранов. UAlbertaBot занял в соревнованиях пятое место, потому что не обновлялся для соревнований этого года. Из-за победы UAlbertaBot в AIIDE 2013 часть ботов реализовали стратегии, специально нацеленные на победу над ним, а сочетание со специально разработанной защитой от ранней агрессии у IceBot, Ximp и LetaBot отобросило его на пятое место.
AIIDE 2014
Малое количество участников в 2013 году вынудило шире освещать событие, чтобы привлечь больший интерес к соревнованиям 2014 года. Кроме того, если команда, участвовавшая в соревнованиях 2013 года, не присылала нового бота в 2014 году, то версия 2013 года автоматически повторно участвовала в турнире, чтобы оценить, насколько улучшаются новые версии. Всего на соревнования было отправлено 18 ботов, и этот рекорд до сих пор не побит. Версии UAlbertaBot, Aiur и Skynet 2013 года участвовали повторно, потому что у их авторов не нашлось времени внести изменения. Поскольку между соревнованиями CIG и AIIDE прошло всего пара недель, многие боты были одинаковыми, и это сказалось на результатах: четвёрка лучших осталась такой же, как в CIG. IceBot стал первым, Ximp — вторым, LetaBot — третьим, и Aiur — четвёртым. UAlbertaBot оказался на седьмом месте и был полностью аналогичен версии, отправленной на CIG 2014.
Матчи человека против машины 2014 года можно посмотреть здесь:
- IceBot vs. Bakuryu — игра 1, игра 2
- Ximp vs. Bakuryu — игра 1, игра 2
- LetaBot vs. Bakuryu — игра 1, игра 2
- Aiur vs. Bakuryu — игра 1, игра 2
SSCAIT 2014 (подробные результаты)
В 2014 году структура SSCAIT была обновлена и стала использовать ПО управления турниром, что позволило пользоваться той же структурой файлов чтения и записи для обучения, а также играть больше игр за меньшее время. Поскольку все три вида соревнований использовали теперь это ПО с открытым исходным кодом, которое участники могли использовать и тестировать, отправка ботов и проведение турниров упростилось. Участники могли быть спокойны, их боты работали на всех трёх соревнованиях. Формат и правила турнира были такими же, как в 2013 году: каждый из 42 участников играл со всеми другими ботами по два раза, то есть была сыграна 861 игра. Результаты снова были разделены на студенческий и смешанный дивизион. В студенческом дивизионе первое место занял LetaBot, второе — WOPR, а UAlbertaBot — третье. В смешанном дивизионе игрался турнир восьми лучших ботов с выбыванием после первого проигрыша. В финале LetaBot победил бота Ximp и выиграл соревнования, а UAlbertaBot оказался сильнее IceBot в матче за «бронзу» и занял третье место.
Версия UAlbertaBot была той же, что и в AIIDE 2013, но с небольшими улучшениями поведения в области позиционирования юнитов и размещения зданий. После довольно плохих результатов CIG и AIIDE было удивительно, что эта старая версия UAlbertaBot заняла третье место в обоих дивизионах.
CIG 2015
В 2015 году на CIG, снова организованных участниками из Седжонского университета, были внесены значительные изменения в правила. Самое важное изменение: раскрытие исходного кода участвующих ботов не обязательно. Это удивило многих, потому что соревнования проходили в рамках научной конференции. Второе изменение: один автор может участвовать с несколькими ботами. Это противоречивое решение, ведь существовала возможность битвы двух ботов одного автора, где один автоматически может проиграть другому. Также один бот мог передавать другому информацию о предыдущих матчах. К счастью, таких проблем не обнаружилось. Соревнования 2015 года проводились в два раза меньше времени из-за возникших в последний момент технических сложностей, поэтому было сыграно всего 2730 игр между 14 участниками.
Результаты этих соревнований были довольно удивительными, потому что все три лучших места заняли новые участники, и все они играли за зергов. Победитель ZZZBot написан разработчиком ПО Крисом Коксом (Chris Coxe). В нём была реализована единственная стратегия: раш четырьмя зерглингами, самая быстрая атака, которую можно совершить в Starcraft. Несмотря на относительно простую стратегию и реализацию, немногие из ботов были готовы к такой быстрой атаке и молниеносно проигрывали. На втором месте оказался tscmoo-Z, бот зергов, написанный Вегардом Мелла (Vegard Mella), независимым программистом из Норвегии. Бот Tscmoo в основном использовал стратегии среднего и позднего этапов игры, реализовывал почти дюжину разных порядков строительства и стратегий и со временем учился подбирать нужную к каждому противнику. Третье место занял Overkill, ещё один зерговский бот, его автором был китайский инженер по обработке данных Сыцзя Сюй (Sijia Xu). Overkill имел в своём арсенале несколько стратегий, но в основном полагался на муталисков и походил на Overmind с соревнований AIIDE 2010. Во время CIG UAlbertaBot проходил процесс серьёзных изменений и новая версия не была готова к участию, поэтому снова участвовала версия с AIIDE 2013, занявшая десятое место.
AIIDE 2015 (подробный отчёт о соревнованиях)
Начиная с 2011 года соревнования AIIDE в Альбертском университете проводились в студенческой компьютерной лаборатории, состоявшей из двадцати машин с Windows XP. Поскольку лабораторию активно использовали студенты, игры можно было запускать только в промежутке между концом учебного года и началом следующего (обычно в конце августа). В 2015 году соревнования проводились на виртуальных машинах, поэтому благодаря большой помощи Николаса Баррига (ещё одного студента, изучавшего ИИ для RTS у Майкла Буро) можно было провести гораздо больше игр. Всего у нас было четыре сервера под Linux, на каждом из которых стояло по три виртуальные машины с Windows XP, то есть всего 12 виртуальных машин для турнира. График проведения AIIDE тоже изменился (соревнования перенесли на ноябрь), и это значило, что их можно проводить полные две недели, то есть в два раза дольше, чем в прошлом году. Ещё одно преимущество виртуальных машин заключается в том, что за соревнованиями можно следить и управлять ими через ПО удалённого рабочего стола. С помощью KRDC по туннелю ssh можно было управлять одновременно всеми 12 машинами, а турнир можно было останавливать или перезапускать прямо из дома.
На соревнованиях AIIDE было зарегистрировано 25 ботов, три из которых не участвовали по техническим причинам. 22 участника представляли 12 стран, что сделало эти соревнования крупнейшими и охватывающими наиболее количество стран. В 2015 году также получилось наиболее равномерное распределение рас. В прошлые года зерги были представлены слабо, но в этом году участвовало пять новых ботов-зергов, многие из которых участвовали ранее в соревнованиях CIG. Распределение рас AIIDE показано ниже.
Также был первый случай участия бота (UAlbertaBot) со случайным выбором расы. Выбрав Random, бот получал случайным образом одну из трёх рас Starcraft после запуска игры. Это означало, что бота гораздо сложнее запрограммировать, ведь необходимы стратегии для всех трёх рас, однако это давало и преимущество, потому что противник не знал расу UAlbertaBot, пока не обнаруживал его в игре. Также были внесены изменения в ПО управления турниром, исправившие ошибку в хранении постоянного файла, иногда приводившую к перезаписи файла. Благодаря переходу в 2015 году на виртуальные машины соревнования могли иметь любую длительность, поэтому в этот раз они продолжались 14 дней. Всего было сыграно 20 788 игр, по девять игр с каждым из 22 ботов на каждой из десяти карт. Это в два раза превосходило предыдущий рекорд сыгранных игр. Вот сравнительная таблица количества игр каждого крупного соревнования ИИ по Starcraft:
Финалисты были очень близки друг к другу: статистически разница процентов побед между первым и вторым, третьим и четвёртым местами была меньше 1%. Три новых зерговских ботов проявили себя чрезвычайно хорошо — tscmoo занял первое место с 88,52% побед, ZZZKBot — второе с 87,83% побед, а Overkill — третье с 80,69% побед. UAlbertaBot оказался на четвёртом месте с 80,2% в режиме случайного выбора расы. Это было большое достижение, потому что игру за несколько рас сложнее реализовать. Ещё одно достижение UAlbertaBot — он одержал более 50% против каждого бота в соревнованиях, однако не достиг максимального общего процента побед. Причина заключалась в том, что UAlbertaBot имел 2/3 побед против слабых ботов, потому что одна из трёх рас не побеждала этих ботов. Можно изучить подробные результаты соревнований с достижениями каждого бота. Общие стратегии tscmoo, ZZZKBot и Overkill не изменились со времени CIG 2015, однако в каждом боте были исправлены небольшие ошибки. Мы также провели матч «человек против машины», в котором участвовал опытный игрок в Starcraft и лучшие боты соревнований. Игру можно посмотреть здесь.
Почти все модули UAlbertaBot были переписаны за несколько месяцев до AIIDE 2015. Бот научился играть не только за протоссов, но и за другие расы. Это потребовало гораздо более надёжного и общего подхода к микроменеджменту и планированию порядка строительства, которые ранее подгонялись под протоссов. Система поиска порядка строительства была обновлена и теперь могла выполнять поиск порядка строительства для любой из трёх рас. Исправлены ошибки, приводившие ранее к сбоям UAlbertaBot во время соревнований. Новой версии этого ПО дали название BOSS (build order search system, система поиска порядка строительства) и она была опубликована на github как часть проекта UAlbertaBot. Ещё одним большим изменением UAlbertaBot стало создание конфигурационных файлов опций бота. Файлы записывались в JSON и бот парсил их в начале каждой игры. Конфигурационные файлы содержат множество опций принятия стратегических и тактических решений, например, выбор стратегий для каждой из рас, опции микроменеджмента юнитов и опции отладки. Также они содержат порядки строительства UAlbertaBot для начала игры, которые можно быстро и удобно редактировать. Благодаря этому файлу конфигурации все опции и порядки строительства можно редактировать без повторной компиляции бота, что ускоряет разработку и упрощает модифицирование и использование другими программистами.
За несколько дней перед соревнованиями проводились тестовые игры, сыгранные против многих ботов, участвовавших в AIIDE 2014 и CIG 2015. Был выполнен ручной анализ этих матчей и созданы порядки строительства и стратегии против некоторых из ботов, таких как Skynet, LetaBot, Ximp и Aiur. Например, против Ximp бот использовал стратегию сильной противовоздушной обороны, потому что известно, что Ximp всегда строит авианосцы. Если бот играл против Aiur за терранов, то он создавал большое количество грифов (Vulture), потому что они препятствовали рашам зилотов Aiur. Это было рискованно, потому что любой из противников мог изменить стратегию перед соревнованиями AIIDE, но многие из них этого не сделали, и такая модель в долгосрочной перспективе себя оправдала. Если бот играл против неизвестного противника, он по умолчанию использовал одну из трёх стратегий раша, в зависимости от назначенной ему расы: раш зерглингами у зергов, зилотами у протоссов и морпехами (Marine) у терранов. Благодаря этому соревнования стали очень удачными для UAlbertaBot и процент побед над каждым из ботов был высоким.
SSCAIT 2015 (подробные результаты)
От переводчика: подробных результатов AIIDE 2016 мне найти не удалось, но вот этот отчёт даёт общее представление.
Следующие соревнования AIIDE пройдут в сентябре 2017 года, регистрация заканчивается 1 августа.
Автор: PatientZero
