Бот Starcraft 2 на основе перехвата и анализа рендеринга

    Matthew Fisher из Стэнфордского Университета написал интересную статью о реализации бота на основе перехвата потока API библиотеки D3D9 (Microsoft Direct 3D, являющуюся частью библиотеки DirectX).

    Как пишет сам автор, бот играет в Starcraft 2 (SC2) перехватывая, понимая и реагируя на поток сообщений D3D9, посылая нажатия клавиш и движения мыши обратно игре. Он не похож на других ботов, сделанных на основе редактора SC2 и использующих скриптовый язык, или проектов наподобии BWAPI (работает только с оригинальным StarCraft), который внедряется в адресное пространство игры. Боты, основанные на этих методах зачастую имеют возможность обойти ограничения, с которыми сталкивется человек при игре; например, они могут одновременно отдавать разные приказы разным юнитам, они могут видеть происходящее вне экрана в любое время, им не составляет труда добраться до наземного юнита, закрытого летающим.




    В статье довольно много технических подробностей и выложены исходники кода, которые реализуют бота. Основная задача статьи – показать простую программу, которая работает как перехватчик и интерпретатор команд D3D9. Преимущество такого подхода к реализации бота по сравнению с другими методами (внедрение в адресное пространство, написание бота на скриптовом языке SC2) очевидны – метод универсален и его можно применять к другим программам, создание бота по этому методу должно быть легче и доступнее. Недостатки метода тоже довольно очевидны: на разбор сцены уходит довольно много времени и сил и достичь APM (количество действий в минуту) сравнимых с другими методами скорее всего не получится.

    Бот разделен на три компонента:

    1. Mirror Driver – хранилище базовых объектов, которые отрисовываются на карте. Объекты представляют собой текстуры, шейдеры, пиксели и другую базовую графическую информацию.
    2. Scene Understanding – данные, полученные Mirror Driver поступают на вход этому компоненту, который преобразовывает их в сущности, которые присутствуют в игре. То есть переводит базовую информацию на более высокий уровень, с которой уже можно строить стратегию управления игрой.
    3. Decision Making – компонент, отвечающий за принятие решения, или по-простому – мозги бота.

    Так как поток вызовов рендеринга сцены последователен, результат разбора сцены представляет собой таблицу (много трафика), которую необходимо преобразовать в информацию, на основе которой можно принимать решения и управлять игрой. После принятия решения на основе опять же графической информации посылается то или иное нажатие мыши или клавиши клавиатуры.

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



    Алгоритм принятия решения очень похож на действия человека. Дается та или определенная команда, бот ее пытается выполнить. Например: построить здание, добавить юнита в группу, атаковать врага и т.д.

    Самой интересной частью конечно же является наблюдение за игрой бота и его действий. Автор статьи записал видео игры под управление бота:


    По результатам анализа игры SC2 показал, что в “спокойное” время APM бота находится в пределах 500 действий, в режиме битвы от 1000 до 2000. Не все эти действия полезны и микроуправление сложно реализовывать; команды бота могут быть бесполезны или даже вредны, по сравнению с поведением юнита по умолчанию.

    Учитывая что автор ставил целью статьи именно показать, какие инструменты можно использовать для написания “базы” бота, а не реализацию самого бота, это довольно хороший результат. Ведь для улучшения показателей бота, можно менять компонент принятия решений, особых технических ограничений для построения бота такая реализация не накладывает.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 57
    • +34
      Видео смотреть больно глазам… По реплаю его точно пропалят)
      • –3
        А вообще, конечно блок принятия решений слабый. Где микроконтроль юнитов в атаке, где пилоны на передовой, где разведка, где запирающие форсфилды?? Не понятно, куда тратится такое безумное колличество APM. Просто на перещёлкивание между юнитами?!
        • +6
          китайцы примерно так и играют :)
          • +25
            Корейцы
          • +2
            Вы хотели сказать «южные корейцы»)) Китайцы в мировом рейтинге достаточно низко.
            Но вообще-то они куда спокойнее играют. У них в среднем всего 150 APM))
          • 0
            На reply прокрутку не видно
            • 0
              Там записываются только команды отдаваемые объектам, то есть по сути отдаваемый на сервер трафик?
              • 0
                И команды, полученные от других игроков. В SC1 по крайней мере было так.
              • +1
                Во втором старике можно в реплае выбрать игрока и камера будет двигаться так же как двигалась у него. Там только не все клики мышкой видно.
            • +3
              Видео занятное, но на второй минуте уже начинает кружиться голова. :)
              • +28
                У меня пошли разноцветные круги в глазах, потом я пустил слюну и заснул, а проснулся вообще в больнице, где оказалось, что я вообще сурок.
                • +2
                  это ещё что, у меня от этой фигни брат умер!
              • +5
                Учитывая что автор ставил целью статьи именно показать, какие инструменты можно использовать для написания “базы” бота, а не реализацию самого бота, это довольно хороший результат

                Hello word bot :)
                • +13
                  dovg: Hello world, грамотей!
                  • +8
                    А так же Hello Excel и Hello PowerPoint ;)
                  • –10
                    Анализ информации, поступающий от Direct3D, это конечно хорошо, но абсолютно не работает если производитель будет с этим хоть как-то боротся. Приведу пример — покерные боты, распознающие изображение путем его сравнения с эталонными фрагментами тривиально ломаются, если клиент начинает незаметно с точки зрения человека менять графику — например, случайным образом менять оттенки цветов плюс минус одна градация, сдвигать элементы на один пиксель в случайном направлении итд. Тут та же история — если кто-то начнет активно эксплоитить этот метод то близам достаточно будет добавить код, случайным образом немного меняющий трехмерное представление объектов и карты текстур — незаметное глазу человека но достаточное, чтобы боту стало очень проблемматично различать юниты и элементы интерфейса.
                    • +1
                      Оттенки машина может различать даже лучше человека. Не обязательно же зашивать оттенок по точному вхождению. Тоже самое касается и положения на экране — вполне можно устроить поиск.
                      • 0
                        а это — падение производительности.
                        • +1
                          Я не спорю. Любая логика и усложнения — ведут к падению производительности. Но это только усложнение работы, а не пресечение возможности работать вообще. Согласны?
                        • +5
                          Там не надо отслеживать ни координаты, ни цвета.
                          Перехват идет вызовов отрисовки, а не анализ конечной картинки со всеми объектами, вот тут хорошо показан разбор сцены: graphics.stanford.edu/~mdfisher/CaptureA/Capture.html.

                          Учитывая что наверняка можно провести реверс-инженеринг ресурсов игры и придать каждой текстуре уникальную подпись на основе какого-нибудь параметра наверняка можно обойти подобную защиту. Боту же все равно как это будет выглядеть на экране.
                          • –2
                            Можно. Но fuzzy matching напрягают уже намного сильнее — это тривиально намного дороже по процессорному времени. Там уже начинаются проблемы с Realtime работой — два кадра в секунду для бота Starcraft будет не фонтан :)
                            • 0
                              Только вот дело в том, что Вам понадобится ещё найти, что конкретно автор изменил. По опыту могу сказать, что даже не очень значительные изменения со стороны авторов, и в бот приходится вносить достаточно большие изменения.
                              • 0
                                А там нельзя будет перехватить изменение этой текстуры? Ведь наверняка команды к изменению текстур пойдут через тот же API, и задача сведется просто к тому, чтобы не потерять связь между изначальной и конечной текстурой, которую пытаются видоизменить.
                                • 0
                                  Скорее всего, можно. Но я имел в виду, что мы ведь не знаем точно, что поменялось, правда? :)
                              • 0
                                Или вообще берем корреляцию… Только где ресурсов на это взять для реального масштаба времени?
                                • 0
                                  Я не оспариваю падение производительности. Выше писал.
                                  Можно запускать механизмы поиска только тогда, когда произошли изменения (если их можно отследить, конечно), можно кэшировать результаты поиска и использовать их в дальнейшем. Навернуть, в общем, можно довольно много. :) Я же говорю о том, что все эти уловки не делают работу невозможной вообще, а только усложняют ее.
                                  • 0
                                    Так и я вам не в укор это написал. И как ниже меня комментируют со стороны движка усложнения тоже упираются в производительность.
                                  • 0
                                    Вряд ли движок игры сможет позволить себе менять текстуру каждый раз при выводе на видеокарту. Максимум что они могут себе позволить, это при первом изъятии текстуры в память добавить к ней немного шумов. То есть если написать хороший уловитель этого шума, то он будет работать не все время, а всего лишь при появлении неизвестной текстуры.
                                • +1
                                  фигня все это (сорри), предусмотреть калибровочный режим где бот не играет а «смотрит» и откладывает в памяти характерные черты на будущее несложно

                                  • 0
                                    да ну глупости все это, от детура тяжко им спасаться. Помню как-то интересно мне было свой вх длдя кс сорса сделать, начал с мелочей, а получился достаточно мощный чит с возможностью набегу убить тех кто позади и не один античит не спалил (хотя играл недолго, заработало и интерес пропал). Пруф: www.youtube.com/watch?v=al7Xrjz3JXM
                                  • –7
                                    Можно было и просто в 4-гейт пуш сыграть.
                                    Что за странное бо через барака и потом цитадель. Выхода в дарков не было.
                                    Странно :D
                                    • 0
                                      Бедняга.
                                      Существенной лажей этого алгоритма, является игнорирование миникарты, что существенно увеличило бы производительность в купе с прогнозированием исполнения приказов собственными юнитами, тогда рендерить бы пришлось только зоны активности.
                                      В остальном сама идея хороша как развитие рекогнайз методик.
                                      • 0
                                        С чего вы взяли что он ее игнорирует?
                                        • 0
                                          Если бы не игнорил меньше дергался бы я думаю, еще по уму надо не только миникарту анализировать, но и у себя хранить данные о юнитах, тогда можно вообше прыгать только когда новый юнит на миникарте появляется или чтоб приказ отдать.
                                      • +3
                                        Интересно было бы натравить его на бронзовую лигу и посмотреть выйдет ли он в серебро.
                                        • +5
                                          Странно, почему ещё никто не написал комментарий «YOU MUST CONSTRUCT ADDITIONAL PYLONS» :)
                                          • +5
                                            Ну вот, теперь Nvidia с Microsoft договорятся, и будут шифровать все DX вызовы.

                                            И Intel c остальными будут не в накладе: и процессору работы прибавится, и вообще повод обновить сокет и всю платформу :)
                                            • +1
                                              Вы мне напоминаете одного заказчика, который просил картинки на его сайте от граберов зашитить, причем он очень настаивал, чтоб и принтскрин тоже не работал, не только прямой даунлоад.
                                              • 0
                                                Есть такие решения, OmniTrust например. Хотят плагин в браузер. В целом работают в определнных случаях. Например доступ в онлайнаукционы.
                                            • +1
                                              Уже жду когда можно будет компонент Decision Making самому написать.
                                              Даешь Google AI challenge на SCII в следующем году!
                                              • 0
                                                Так а ждёте чего? Есть какие то препятствия?
                                                • 0
                                                  Я думаю самым выгодным будет играть в 4 гейт с парой ветвлений — не пропустить фотон раш и не ломиться на форсфилды.
                                                  • 0
                                                    Только с 6 пулом и другими чизами будут проблемы. :)
                                                    • 0
                                                      хм, таким образом можно взять парк машин и запустить целую тестовую бронзовую лигу, в которой боты будут всех рашить. заодно можно в нее пустить пару реальных игроков с целью поиздеваться. можно даже чат эмулировать «lol, 6 pool, u mad?» или «say hello to mum»
                                                • 0
                                                  По-моему бесполезное видео — ничего не понятно, все скачет и рябит. Лучше бы выложили реплай…
                                                  • +1
                                                    Написал письмо автору. Может поделится.
                                                  • 0
                                                    было бы хорошо не полностью автоматизировать (бот управляет стратегией), а сделать некоторые вещи болле «макро» например (элементы тактики).

                                                    Пока приток денег > 300 и денег > 1000 строить рабочих, жилища и армию.

                                                    Так можно сократить количество мелких суетных движений.
                                                    • 0
                                                      Вот дали бы доступ к юнитам (и строениям) на уровне Colobot/Ceebot — резко бы повысилась компьютерная грамотность человечества ;-)
                                                      • +1
                                                        Сталкеры (эти юниты стреляющие в конце победившие врага) с блинком (телепортом на короткую дистанцию) являются самым грозным оружием в руках ИИ…
                                                        • 0
                                                          Любое оружие в руках ИИ будет грозным, просто потому что он сможет действовать быстро и эффективно. Предел APM при котором стратегия игры уже не будет улучшаться находиться выше выше 500 это точно.

                                                          Человек вряд ли сможет соперничать с ботом.
                                                          • +1
                                                            На самом деле любые юниты с ренжем становятся грозными против юнитов ближнего боя. Больше всего страдают зерги похоже. Это запись бота, который с помощью маринесов без потерь справляется с лингами и банелингами:
                                                            www.youtube.com/watch?feature=player_detailpage&v=mrbYd4OFrWE#t=68s

                                                            • +1
                                                              Клевое видео. Но заметил что не совсем оптимально алгоритм работает. Например когда маринера не атакуют, он все равно пытается отбежать, хотя может там общая линия фронта учитывается.

                                                              Но вот это конечно жесть: For one Marine the Bot needs around 300 APM.
                                                              • 0
                                                                Немного удивляет стратегия, когда он мутой на маринов полетел. Ощущение что зерговский бот послабее. А так прикольное видео)
                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                              • 0
                                                                :) По теме комментов много, поэтому займусь оффтопиком. Может кто знает откуда взялась фигурка, которая на первой фотографии в посте? :)
                                                                • 0
                                                                  А на сколько легко такой метод обнаруживается системами защиты?

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое