Еще один игровой бот для «Космических рейнджеров HD» (издатель 1С) наводит на интересные мысли о путях развития искусственного интеллекта (ИИ).
Немного лирики
Можно перефразировать эпиграф в загадку:
По кругу летает,
Никому не мешает,
С нее взлетают,
А их убивают…
(Роджерия)
Немного теории
Машины делают, чтобы облегчить труд человека. И, более того, чтобы выполнять работы, которые человек сам выполнить не в силах. Например, человек не может поднять груз весом в полтонны, а с помощью системы блоков – может. Вычислительные машины – компьютеры и программное обеспечение к ним — служат тем же целям, что и другие машины. Например, задача рассортировать несколько десятков тысяч слов по алфавиту для человека будет утомительной, делать он ее будет долго, а вероятность ошибок для среднего исполнителя со средним уровнем ответственности будет значительной. Современный компьютер выполнит эту задачу без ошибок за очень короткое для человека (доли секунды) время. Всё это общеизвестно и сказано здесь только для того, чтобы дать определение ИИ. Не претендуя на оригинальность в этом определении, отмечу, что определений ИИ очень много, поэтому, прежде чем говорить об ИИ, приходится конкретизировать этот термин.
Итак, предложим следующее определение: к ИИ относятся задачи, которые компьютер решает заметно хуже человека.
Понятно, что если составить список таких задач для сегодняшнего дня и список для задач пятидесятилетний давности, то эти списки будут различаться. Однако различия будут не столь сильными, как различия общих вычислительных возможностей для компьютеров сегодняшнего дня и ЭВМ, которые были полвека назад. То есть производительность и объемы памяти возрастают на многие порядки, а почти все труднорешаемые задачи так и остаются труднорешаемыми. Здесь намеренно допущена двусмысленность. С точки зрения теории вычислительной сложности, труднорешаемые задачи – это задачи с экспоненциальной теоретической оценкой количества операций от размерности задачи в наихудшем случае. При том что основной вопрос этой теории «P =? NP» продолжает оставаться открытым. В ИИ есть задачи, «просто» решаемые тупым перебором, если бы такой перебор был возможен по времени, например, шахматы. Однако многие другие задач ИИ явно не требуют экспоненциального количества операций и в то же время выглядят труднорешаемыми не в силу вычислительной сложности, а в силу трудности построения надежных и эффективных алгоритмов для их решения. Очевидно, что такое второе значение термина «труднорешаемая» качественно отличается от первого: в теории вычислительной сложности этот термин означает строго доказуемую экспоненциальную оценку, тогда как во втором значении строгое математическое доказательство трудности построения надежных и эффективных алгоритмов представляется крайне затруднительным. При этом мы не рассматриваем алгоритмически неразрешимых задач и полагаем, что если человек справляется с какой-то задачей, то существует алгоритм ее решения.
На нынешнем этапе развития ИИ умения человека выглядят идеалом, к которому нужно стремиться, однако и человек нередко ошибается. Уровень этих ошибок различный — от элементарных ошибок, вызванных недостатком необходимых знаний конкретного человека, его невнимательностью, усталостью, до более сложных – таких, как иллюзии и когнитивные искажения. Отсюда следует немаловажный вопрос: возможно ли задачи ИИ решать лучше, чем это делает человек, т.е. возможен ли «супер-интеллект», или же ряд задач ИИ в принципе не возможно всегда решать правильно, т.е. всегда будет отличная от нуля вероятность ошибочного решения? Несколько примеров было в моей предыдущей публикации, в частности:
широко известный пример затруднительного [для человека] распознавания — это капчи, на которые натыкаешься в Интернете на каждом шагу. Бывают такие каракули, что приходится несколько раз нажать на кнопку смены капчи, прежде чем удается «доказать, что
не верблюдне робот.
Другим важным моментом, о котором говорилось в упомянутой публикации, является автономность:
абсолютная автономность – вредный миф. По крайней мере, на ближайшие десятилетия. На собственном и на чужом опыте автор [Дэвид Минделл «Восстание машин отменяется! Мифы о роботизации»] подробно показывает, что в наши дни наиболее успешными являются системы, где достаточно полно реализуется взаимодействие человека с автоматом, а не отчуждение человека от процесса принятия решений. В правильности этой идеи лично я убедился на своем скромном примере игровых ботов для игры КР2HD: бот для планетарных битв по нашей с соавтором идее должен быть полностью автономным, и сейчас этот проект забуксовал.
Итак, предложено много определений ИИ. В соответствии с этими определениями существуют различные классификации задач ИИ. Не претендуя на оригинальность (как и в случае с определением), возьмем следующую классификацию. Это классификация по целям.
Цель рационального ИИ – выбрать уровень автономности, на котором:
1) программа будет полезной;
2) программа не будет ошибаться слишком часто, по сравнению с человеком;
3) программа не будет чрезмерно сложной для написания, отладки и сопровождения.
Другой класс в нашей классификации это «революционный» ИИ. Его цель сделать программу максимально автономной. Такая программа обычно представляет научный и спортивный интерес, при том, что ее практическая ценность может быть близка к нулевой.
С точки зрения приведенной классификации предлагаемое ниже решение поставленной задачи является рациональным. Ничего особо революционного здесь не предлагается, однако выражу надежду, что и такой умеренный подход, исходящий из реальных возможностей и ориентированный на практическое использование, представляет определенный интерес для науки.
Отмечу, что в определении никак не оговаривается метод решения. Из предложенного определения следует простая практическая идеология: если обнаружена задача, которую компьютер решает хуже человека – значит, это задача ИИ. И решать ее можно как угодно – лишь бы решалась: можно использовать нейронные сети и обучение, а можно и не использовать. Остается надеяться, что предлагаемый рациональный подход, в результате применения которого будет происходить неизбежное накопление опыта решения подобных задач, продвинет ИИ. В общем-то так и происходит: слишком амбициозные проекты терпят крах, а более скромные неспешно, но все же продвигают ИИ к новым рубежам.
Стоит также сказать и о методах исследования ИИ. Безусловно, даже простой робот, собранный из стандартных деталей конструктора роботов, очень зрелищен, способствует популяризации идей ИИ и хорошо привлекает не искушенных в ИИ спонсоров. К сожалению, воспроизведение эксперимента с таким роботом натолкнется на очевидные трудности, а научный метод требует воспроизводимости. Поэтому в научном плане игровой бот для достаточно распространенной, не специально сочиненной для данного лабораторного исследования игры, представляется интереснее.
И, наконец, переходя от теории к практике, отметим, что, наверное, не удастся найти фундаментального труда по ИИ, где бы не упоминались философские вопросы, тесно связанные с ИИ. Нисколько не преуменьшая их значение, отметим, что предложенные выше определения позволяют не углубляться во многие из этих вопросов в рамках данной работы.
Задача
Основной целью игры КР2HD является набрать как можно больше очков. Очки игра рассчитывает по формуле:
Очки = Опыт*Сложность/100/max(7, Время игры/365)^1.3,
где Опыт — начисляется в том числе и за уничтожение врагов, в частности, за уничтожение пиратов;
Сложность – от 50% до 200% в числе прочих стартовых условий устанавливается игроком перед началом новой партии;
Время игры — это дни в игре: каждый ход – это один день.
Игра начинается с игровой даты 1 января 3300 г. и может развиваться по нескольким сюжетным линиям. Однако опытным игрокам известно, что наибольшее число очков приносит многолетняя битва с пиратами (точнее, их избиение) в звездной системе Тортугац. Это кульминация игры: предшествующая часть партии – по сути, подготовка к данной битве, а последующая часть очень короткая и заключается в том, чтобы как можно быстрее в несколько игровых дней закончить игру на соответствующей выбранной концовке базе, так как в дальнейшем очки будут только понижаться. Резкий рост числа уничтоженных игроком пиратов, сопровождаемый резким ростом очков, хорошо виден на графиках топа таблицы рекордов игры: Robo Brain –первое место, SHERIFF – второе:
Как видим, битва длится несколько игровых лет, но может растянуться до 20 лет и более. При игре на рекорд с перебором нескольких вариантов для достижения максимального числа очков (об этом игровом приеме будет рассказано ниже) игрок может потратить на битву в Тортугаце несколько реальных месяцев и больше!
Система Тортугац становится доступной игроку после выполнения ряда заданий, на описании которых мы останавливаться не будем. Система состоит из двух необитаемых планет и одной пиратской базы под названием Роджерия, которая, как и планеты, вращается по круговой орбите вокруг звезды. Диаметры орбит разные, так что столкновение невозможно. После выполнения нескольких действий, прилетев на Роджерию и взлетев с нее, игрок получает возможность уничтожать каждый ход примерно 13 пиратов, которые ежедневно будут взлетать с «муравейника» Роджерии. В игре есть разное оружие, но для данной битвы наиболее подходит так называемое оружие массового поражения (ОМП): Вертикс и ИМХО-9000.
Цифра в левом нижнем углу около стилизованного кубика показывает вес данного предмета. Так, приведенный на рисунки вертикс весит 190 единиц, а ИМХО-9000 весит 113. Горанд – это так называемый микромодуль, который при установке в орудие уменьшает его износ при каждом выстреле и при ответных выстрелах врагов. Установленный микромодуль вынуть из орудия невозможно. Износ показан «градусником» вверху. Важной особенностью ОМП является поражение не только вражеского корабля, на который нацелено орудие, но и всех неприятельских кораблей в радиусе действия орудия, однако, если цель настолько непрочная, что будет уничтожена с первого выстрела, то поражение других врагов не произойдет. Поэтому игрок применяет следующий тактической прием: запускает в космос несколько кораблей-роботов, называемых транклюкаторами (или просто транки), и стреляет по ним, тогда значительная часть энергии выстрела достается пиратам.
Каждый такой транк-мишень игрок заранее оборудует генератором защитного поля (ГЗП) и ремонтным дроидом, чинящим корпус транка. Благодаря этому транк выдерживает многократные выстрелы из одного или нескольких ОМП игрока. Все используемое на кораблях оборудование постепенно изнашивается, однако изнашивается с разной скоростью. ГЗП практически не изнашивается на протяжении многих игровых лет, а вот ремонтный дроид изнашивается сравнительно быстро. Для починки дроида и другого оборудования, кроме ОМП, служит артефакт нанитоиды (или просто наники, см. рис.), при установке которого в специальный слот корабля всего за несколько ходов происходит починка изношенного оборудования (кроме названного, это двигатель, топливный бак, радар и сканер). На каждом корабле имеется трюм, где может храниться не используемое на данный момент оборудование, вооружение и транки. В трюме все эти вещи почти не изнашиваются. Поэтому во избежание преждевременного износа наников, их по окончании починки нужно сразу убрать из слота в трюм.
Как уже было сказано, ОМП наники не чинят, поэтому после полного износа ОМП приходится выбрасывать в космос, там его можно подбирать и отвозить на Роджерию с помощью транка, оснащенного захватом. Для успеха Роджерийской кампании необходимо очень хорошее оснащение корабля игрока – в этом случае даже несколько десятков пиратов никакой угрозы для него представлять не будут, как муравьи жуку.
Во время битвы корабль игрока на Роджерию садится не должен – как только сядет, битва прекратится и пираты перестанут каждый день массово взлетать под пушки игрока. Поэтому игрок захватывает с собой как можно больше ОМП. Это количество ограничено вместимостью корабля игрока – максимально допустимым суммарным весом всех вещей на корабле. Однако и тут существует тактический прием, позволяющий взять ОМП больше, чем вмещает корабль. Для этого нужно поместить ОМП в орудийные слоты транков. Каждый транк, как и корабль игрока, имеет пять орудийных слотов (корабли с меньшим количеством слотов для битвы в Тортугаце будут малоэффективны и их обычно не используют). Загружать ОМП, как и другие вещи, в трюм транка бессмысленно, так как при загрузке транка в трюм корабля игрока транк автоматически выгрузит все содержимое своего трюма в трюм корабля. Однако орудия, установленные в орудийные слоты транка, и установленное в другие слоты транка оборудование (обычно это двигатель, топливный бак, ремонтный дроид, ГЗП и иногда захват — подробнее про оборудование можно прочитать здесь) транк не выгружает. Вес такого оборудование не учитывается для загрузки корабля игрока. Например, вес транка на рисунке всегда будет 49 единиц, даже если в его слоты будет установлено ОМП суммарным весом 500 единиц. Поэтому, кроме транков-мишеней, игрок захватывает с собой в Тортугац как можно больше транков-чемоданов с установленными в них запасными комплектами ОМП и воюет с пиратами до тех пор, пока все ОМП не придут в негодность.
На следующем снимке экрана игры приведен участок экрана с Роджерией справа, кораблем игрока и транками-мишенями. Пиктограммы ОМП у транков показывают, какие ОМП игрока на них нацелены. На снимке также присутствуют многочисленные бочки с горючим, которые вываливаются из пиратских кораблей при уничтожении. Кроме бочек еще имеются минералы, образующиеся при столкновении метеоритов с кораблями и базой. Зеленая точечная линия, идущая от корабля игрока к транку, показывает курс корабля, которым он последует в следующий ход. В данном случае корабль будет следовать за транком.
Для задания курса игроку нужно навести курсор мыши на точку экрана и нажать левую кнопку мыши («кликнуть в точку»). Если эта точка будет расположена вблизи транка, корабль последует за транком не в ту точку экрана, на которую было указано, а куда полетит транк. Если точка будет в окрестности Роджерии, то корабль сядет на Роджерию и битва досрочно завершится. Чтобы посадки не произошло, нужно дважды «кликнуть в точку». Все эти особенности прокладки курса должен учитывать игровой бот.
Как видим, с точки зрения перемещений игровое пространство представляется двумерным, однако стоит рассмотреть третью координатную ось, перпендикулярную плоскости экрана и направленную в сторону игрока, так как объекты игрового мира (корабли, база, бочки, метеориты и т.д.) размещаются на разных слоях по этой оси и могут заслонять друг друга.
К нулевому, самому далекому от игрока слою, следует отнести фон. В настройках игры мы отключили изображение фона, поэтому фон стал равномерно черным. На следующем слое располагаются планеты и Роджерия. На следующем — бочки и метеориты. Так, на рисунке видно, что некоторые бочки заслоняют часть Роджерии. Далее на следующем слое располагаются транки и пиратские корабли, затем пиктограммы ОМП, затем корабль игрока, огонь выстрелов и, наконец, самый близкий к игроку слой информационный: сообщения и диалоги игры закрывают все другие слои.
С помощью функциональных клавиш клавиатуры можно сохранить и загрузить игру. Так, при сохранении на экране появляется диалог с именем системы – в нашем случае будет «Система Тортугац». Если такое сохранение было уже сделано, к имени сохранения добавляется очередной номер. Сохраненная игра будет записана в файл под тем же именем и с расширением “.sav” во внутреннем зашифрованном формате игры. Для срабатывания диалога достаточно нажать клавишу Enter на клавиатуре.
Очень важная для бота особенность – это дамп игры на текущий момент: набрав на клавиатуре “MAKEDUMP” при нажатых клавишах Ctr и Shift, увидим диалог, как и при обычном сохранении игры. Однако, нажав клавишу Enter, получим не только файл с расширением “.sav”, но и текстовой файл с расширением “.txt” под тем же именем. Файл имеет древовидную структуру, записанную с помощью вложенных скобок, где содержится много нужной информации о корабле игрока и об активированных им транках. К сожалению, некоторая необходимая информация там отсутствует. В частности, износ корпуса транка не соответствует действительности игры. Указаны экранные координаты каждой бочки, но нет координат Роджерии и активных транков. Эту информацию боту придется получать с помощью компьютерного зрения. Об этом расскажем ниже, а сейчас, чтобы покончить с дампом, отметим простой прием с именованием файлов: проверяем, нет ли в папке сохранений игры файлов с именами «Система Тортугацdmp.sav» и/или «Система Тортугацdmp.txt», и если такой есть, то удаляем его. К имени нужного нам дампа бот, имитируя нажатие клавиш на клавиатуре, добавит в диалоге игры «dmp». Таким образом, бот знает, какой файл ему нужно читать, после того как игра его запишет, для этого бот дожидается доступа к файлу. Отметим, что текст объемом примерно 9 Мб пишется на диск с человеческой точки зрения очень быстро, но не мгновенно с точки зрения программы, поэтому во избежание сбоев в работе бота все подобные конфликты нужно предусмотреть.
Стоит также отметить, что в игре предусмотрены: настройка, при которой каждый ход сохраняется в файле «TurnSave.sav», и горячая клавиша для быстрого сохранения, при нажатии которой без всяких диалогов записывается файл игры «QuickSave.sav», и, соответственно, клавиша загрузки быстрого сохранения, для каковой загрузки требуется утвердительный ответ на диалог «да/нет». Ряд других полезных для бота возможностей отметим ниже при его описании. А тут, чтобы закончить разговор о файловой системе игры, заметим, что действия с ней игры занимают ощутимое для бота время на ожидание. После загрузки файл может освободиться, но игре потребуется дополнительное время на обработку информации, чтобы стать активной. При основных файловых операциях экран игры сменяется заставкой с индикатором прогресса («градусником»). Могут происходить и исключительные ситуации типа ошибки записи файла. Вероятны и другие сбои, происходящие от багов игры. Все это добавляет объективные сложности и неопределенности в работу бота. Очевидно, что если бы игра использовала какие-либо средства межпрограммного взаимодействия, например, COM, то эти трудностей не было бы. Таким образом, игра не имеет никаких приспособлений для бото-строения, и бот со стороны игры по сути должен проходить обратный тест Тьюринга, т.е. быть для игры неотличимым от игрока-человека.
С первого взгляда описанная игра может показаться не очень интересной, однако, если судить по упоминавшейся таблице рекордов, содержащей более 200 рекордов, – придется признать, что игра пользуется определенным успехом. Из описания видно, что игра не простая и требует от игрока терпения, аккуратности и внимания. Очевидно, что такая задача гораздо интереснее для создания бота, чем искусственная лабораторная игра, в которую никто не играет и которая создана исключительно для исследований по ИИ. При этом стоит отметить, что в цели данной статьи не входит обсуждение игры — такое обсуждение было сделано ранее. Здесь отмечаются только частные особенности, влияющие на поведение бота в одной из фаз игры. Поэтому приведенное краткое описание никоим образом не может претендовать на инструкцию по игре.
Проблемы и решения
Выше мы уже отметили ряд проблем. По их сути уже можно заключить, что бот должен использовать приемы программ реального времени, несмотря на то, что сама игра является пошаговой стратегией (про планетарные и аркадные битвы здесь не говорим) и что ОС Windows не является системой реального времени. Кроме того, некоторую необходимую информацию бот может получить только через компьютерное зрение, распознавая информацию из снимков экрана игры. (Альтернативный хакерский путь доступа к оперативной памяти игры или к файлам сохранения, например, с помощью ArtMoney и подобных инструментов, рассматривать не будем, поскольку это не только не спортивно, но и неинтересно – достаточно записать себе любое количество очков и говорить больше будет не о чем).
Выше уже отмечалось, что Роджерия вращается вокруг звезды по круговой орбите, поэтому корабль игрока должен следовать за ней, чтобы взлетающие пираты находились в зоне поражения ОМП корабля. Существует не очень известный тактический прием, называемый «посадкой на колесо». У базы есть детали, напоминающие колеса, – зачем они такому гигантскому космическому устройству, остается только гадать. Если «кликнуть мышью» на «колесо» и сделать ход, то посадки на Рождерию не происходит, корабль прилипает к «колесу» и каждый следующий ход будет следовать за базой.
В отличие от предыдущего рисунка, здесь в настройках игры космический фон не убран.
Описанный прием посадки на колесо заметно экономит время игры, однако некоторые взлетающие с Роджерии пираты успевают выйти из зоны поражения ОМП игрока. Больше опыта и очков удается получить, если каждый ход корабль будет оказываться над геометрическим центром Роджерии («над» — с учетом сделанного выше замечания по слоям третьего измерения игрового мира).
Прочность корпусов и оснащение взлетающих с Роджерии пиратов день ото дня меняются случайным образом. Чемпионами игры было установлено, что изменения взлетающих пиратов происходят, если «поговорить» с транком, т.е. нажав клавишу «Т» (разговор), навести курсор мыши на транка и нажать левую кнопку мыши. Откроется модальный диалог, в котором можно выбрать задание для этого транка («следуй за мной», «возвращайся назад», «приступить к сбору вещей» и т.д.) Можно не выбирать никакой команды и нажать клавишу Esc – диалог закроется, но состав взлетевших пиратов будет другой. Еще один такой пустой разговор снова изменит состав взлетевших пиратов. Таким образом, для максимального набора очков стоит попробовать провести один, два, три и т.д. разговоров с транком, каждый раз возвращаясь на предыдущий ход, и выбрать случай, в котором удалось получить максимальный опыт, определяемый из дампа игры.
Как уже отмечалось, в дампе нет координат базы и транков, а их нужно знать, чтобы оказаться над центром Роджерии и вызвать транка. Для нахождения этих координат в боте применяются функции библиотеки компьютерного зрения OpenCV.
Бот, имитируя нажатие горячих клавиши игры, центрирует изображение, в результате корабль игрока оказывается в центре экрана, т.к. мы предполагаем, что за предыдущие ходы корабль не сильно отдалился от Роджерии. Однако во избежание ошибок бот пока будет работать с полноэкранным изображением. Далее бот делает быстрое сохранение и убирает метки ОМП с экрана. Роджерия, никак не поворачиваясь, летает вокруг звезды, спрайт достаточно большой, поэтому он хорошо распознается по приведенному ниже шаблону. Бочки и минералы крутятся на месте вокруг своих (похоже, произвольных) осей. Этот мусор соизмерим с размерами транков и мешает их распознаванию. Поэтому средствами игры бот делает два снимка экрана с интервалом в 4 секунды, загружает их и находит в первом по шаблону Роджерию, а потом попиксельно складывает.
(Размер: 100 х 93)
Вращающийся мусор размазывается. Далее все пиксели в модели RGB, отличающиеся по каждой цветовой компоненте от эталонного изображения Роджерии (без всякого мусора) не более чем на 20 единиц (подобранно экспериментально значение), зачерняются. Таким образом, Роджерия удаляется из результирующего изображения, но остаются объекты более близких слоев, которые могли ее частично закрывать. Далее бот вырезает квадрат 700 х 700 пикселей с центром в центре экрана, дополнительно размывает это изображение с помощью функции OpenCV cvSmooth с параметрами CV_GAUSSIAN, 9, 9 (подобранны экспериментально) и переходит к распознаванию транков.
В отличие от Роджерии транк может поворачиваться на угол кратный 45 градусам, а применяемая функция OpenCV распознавания по шаблону cvMatchTemplate не инвариантна к повороту. Поэтому последовательно ищем транки по восьми возможным шаблонам:
К сожалению, на этом этапе мусор можно спутать с транком, поэтому дополнительно для каждого найденного объекта определяется мера сходства. Сходным пикселем считается пиксель, который по каждой цветовой компоненте в модели RGB не отличается от соответствующего пикселя шаблона более чем на 45 единиц и имеет яркость более 18 единиц, таким образом, исключается серый мусор, на который может наложиться распознаваемый транк. Мера сходства вычисляется как отношение числа сходных пикселей к числу всех пикселей шаблона, умноженная на 100% и округленная до целого числа.
На следующем рисунке представлено распознанное описанным образом изображение: область распознавания заключена в большой красный квадрат, объекты, распознанные как транки с критерием сходства больше 10%, заключены в красные прямоугольники (маленькими квадратиками обозначены центры), объекты, найденные функцией cvMatchTemplate, но не прошедшие по критерию меры сходства, – в синие прямоугольники. Числа — мера сходства.
К сожалению, испытания показывают, что и при таком многокаскадном распознавании с последующим уточнением периодически случаются ошибки. Поэтому список найденных объектов, которые предположительно являются транками, окончательно проверяется средствами игры: каждый предполагаемый транк вызывается на разговор. Если это действительно транк, то в верхнем правом углу экрана игры появляется следующий модальный диалог:
Этот диалог уверенно распознается по шаблону:
описанным образом с вычислением меры сходства при пороговом значении 80%. Если объект не транк (и не пират, см. ниже), диалога не появляется, а появляется надпись по центру вверху экрана «Разговор невозможен». Надпись быстро исчезает, и принимать какие-либо действия по ее распознаванию представляется излишним.
При большом количестве мусора случаются ситуации, в которых ни один из указанных объектов не откликается как транк. В этом случае все найденные объекты закрашиваются черным, и производится новая попытка поиска транков. Эксперимент показывает, что в ряде случаев это помогает. А когда не помогает, можно еще раз сделать два снимка экрана и повторить всю процедуру распознавания. Если и это не помогло, то боту приходится признать свое бессилие и обратиться за помощью к игроку. Испытания показывают, что такие ситуации происходят довольно редко, гораздо чаще бот останавливается из-за необходимости ремонтных работ на корабле и транках в игре.
Бочки с горючим мешают не только распознаванию транков, но и несут непосредственную угрозу желаемому ходу игровой партии. Когда бочек скапливается очень много, одна из них взрывается от выстрела, вызывая взрывы рядом расположенных бочек — происходит цепная реакция с лавинообразным нарастанием. В результате число бочек резко уменьшается, но взрывы могут уничтожить транк и при недостаточной защите нанести урон кораблю игрока. Точно предсказать ход, на котором это произойдет, невозможно, поэтому в случае потери транка игроку приходится возвращаться по сохранению игры на несколько дней до взрыва и переигрывать. Кроме того, при игре бота иногда происходит захват бочки кораблем игрока. Поэтому при остановках бота игроку стоит осмотреть трюм на предмет выбрасывания бочек в космос.
Иногда в ходе игры появляется пират, который угрожает игроку. В этом случае открывается модальный диалог, аналогичный диалогу с транком, но с другим текстом. Несмотря на то, что текст отличается, шаблон распознавания диалога с транком подходит и для этого случая, т.к. заданное значение меры сходства не слишком большое. Бот на каждом ходу проверяет снимок экрана игры на такой диалог и в случае обнаружения имитирует нажатие клавиши Esc для закрытия диалога. В противном случае дальнейшее функционирование бота окажется невозможным. Также иногда некоторые пиратские корабли при распознавании ботом оказываются похожими на транк. В этом случае при переборе вариантов бот может вызывать на разговор пирата, как и транк.
В некоторых случаях получается, что имитация нажатие клавиши Esc была лишней, что приводит к появлению основного меню игры (тоже модальный диалог) в центре экрана. Проверку на такие ситуации бот производит после каждой имитации нажатия на клавишу Esc, распознавая на снимке экрана следующий шаблон:
Для закрытия основного меню бот должен повторить имитацию нажатия на клавишу Esc.
Сделав пробный ход, бот определяет координаты центра прямоугольника, описывающего Роджерию, и, возвратившись на ход назад, пытается проложить курс в эту точку. Однако вблизи от этой точки может оказаться транк или пират, и тогда корабль игрока полетит за транком (или пиратом), а не в указанную точку, поэтому бот пробует и другой вариант – сделать ход, при котором корабль остается на том же месте. После чего бот сравнивает эти варианты и выбирает тот, в котором расстояние от центра корабля до центра Роджерии меньше.
Задавшись целью написать рационального бота, ограничим его самостоятельность следующим образом: бот будет делать ходы, следя за износом оборудования и за сохранностью находящихся под наблюдением транков. Будет самостоятельно пробовать варианты с 0, 1, 2 и т.д. разговоров с транками и выбирать вариант с максимальным опытом. Будет следить за износом ОМП. Однако замену ОМП и починку оборудования предоставим игроку – бот будет останавливаться, когда требуется вмешательство игрока для смены ОМП или установки наников в слот или снятия наников из слота в трюм. Также бот будет останавливаться в случае гибели находящегося под наблюдением транка, для того чтобы игрок выбрал день возврата и принял меры для дополнительной защиты транка (например, установил бы на транк дополнительные защитные артефакты или же перестал на несколько дней использовать этот транк в качестве мишени). Чисто технически эти операции также можно было бы автоматизировать, однако тут возможно много ситуаций с неоднозначными решениями и, на мой взгляд, не стоит лишать игрока удовольствия принять эти решения самостоятельно – иначе игра полностью утратит интерес для игрока и зачем тогда бот. Пусть самую утомительную и рутинную часть игры будет выполнять бот, а игроку останется наиболее интересная и не столь обременительная часть.
Задача отслеживания оборудования для починки вроде бы простая для программирования бота, но вот незадача: в дампе игры оборудование и артефакты, установленные в слоты корабля и находящиеся в его трюме, не различимы. Поэтому бот будет предупреждать игрока об износе находящегося под наблюдением оборудования, когда износ достигнет некоторого предельного значения, запоминать это оборудование и информировать игрока, если износ запомненного оборудования снизится до значения, с которого наники перестанут чинить оборудование. В первом случае игрок должен поставить наники из трюма в слот своего корабля или транка, во втором – проделать обратную операцию.
GUI
Основная вкладка окна бота показана на следующем рисунке.
Бот может играть в двух режимах: в полнофункциональном и в ускоренном с сокращенной функциональностью. Выбор режима определяется количеством разговоров с транком — поле «Разговоры». Если это количество больше нуля, то бот делает первый пробный ход, потом возвращается в предыдущий день, вызывает один из активных транков для разговора, закрывает диалог и делает ход, потом снова возвращается в предыдущий день и снова говорит с транком. И так столько раз, сколько разговоров указано в поле «Разговоры». Из всех сделанных попыток выбирается та, что принесла максимальный опыт.
Для игры в ускоренном режиме игроку нужно, как было описано выше, «прилепить» корабль к Роджерии посадкой на колесо. В этом режиме боту не нужно распознавать базу и транков, делая скрины на каждом ходу, поэтому скорость прохождения заметно возрастает, а количество ошибок сильно снижается. Для еще более быстрого прохождения при низком уровне износа всего, что находится под наблюдением, бот может делать дамп игры не каждый день: можно задать частоту дампов в поле «Частота анализа». Когда износ станет близким к критическому, бот перейдет на ежедневный анализ дампа.
Как уже отмечалось, для правильного функционирования бота в игре должны быть сделаны соответствующие настройки. Поэтому при первом запуске бот предлагает в диалоге внести необходимые изменения в файл конфигурации игры. В случае согласия игрока бот копирует файл конфигурации игры CFG.TXT в файл CFG.BAK и вносит необходимые изменения в файл CFG.TXT. Чтобы вернуться к прежней конфигурации, игроку нужно запустить бота и нажать на кнопку «Вернуть CFG файл». Бот удалит файл CFG.TXT и переименует файл CFG.BAK в CFG.TXT. При следующем запуске бота он, не обнаружив файла CFG.BAK, предложит внести необходимые изменения в файл конфигурации игры.
Обучение, самообучение и самопознание
Большие надежды в ИИ возлагают на обучение и в особенности на самообучение. В связи с этим стоит вспомнить общеизвестные факты: как обстоит дело в случае с совершенствованием естественного интеллекта – прежде всего, с обучением детей. Оно со времен пещерных людей является всеобщим, даже героя Киплинга Маугли учат читать книгу джунглей. Многие мастера и хорошие специалисты в разных областях учатся всю жизнь, но все же для большого количества взрослых обучение не считается обязательным настолько, насколько оно считается обязательным для ребенка. В этом плане, не преуменьшая роль самообучения, все же приходится признать, что традиционно у всех народов основной упор делается на обучение, причем на жесткое модальное обучение типа «делай так». Так в основном учат и воспитывают родители, воспитатели и школьные учителя: «мой руки перед едой», «не грызи ногти», «не держи ложку в кулаке», «паяльник надо держать как карандаш», «не откладывай на завтра то, что можешь сделать сегодня», «на токарном станке нельзя работать в галстуке – может намотать и удушить», «ты не должен поступать с другими так, как не хотел бы, чтобы они поступали с тобой» и т.д. При этом обоснование необязательно. Действительно, можно попытаться разъяснить ребенку, почему нужно мыть руки перед едой, но значительно труднее объяснить, почему нельзя держать ложку в кулаке – ведь ему так удобнее ее держать. Каждый школьник поймет, что движущиеся части станка могут намотать галстук, но найдутся спорщики, которые будут говорить, что галстук может быть коротким, что длинный можно заколоть булавкой и т.д. Стандартная линия поведения учителей и инструкторов – уходить от таких споров: «таковы требования техники безопасности и они не обсуждаются».
Самообучению в детском воспитании обычно отводится второстепенная роль. Конечно, бывают талантливые дети, и известно много случаев, когда заинтересовавшийся школьник самостоятельно по книгам осваивает что-то не входящее в школьную программу. Однако такие случаи обычно рассматриваются как исключения, пусть и довольно многочисленные, из общего правила. При этом обычно отмечается, что знания, полученные школьником в результате подобного самообучения, обычно поверхностны и не систематичны, а иногда и ошибочны, если не сумел разобраться или не так понял. Очевидно, что для взрослого достаточно образованного человека самообучение обычно проходит гораздо плодотворнее.
Учитывая сказанное, идея полностью самообучающейся программы ИИ представляется сомнительной. В настоящее время мы достаточно хорошо знаем только одну систему принципов начального обучения – обучение детей. Поэтому нам ничего не остается, как применять эти принципы к ИИ. И, в частности, отмеченный принцип модального обучения учителем при необязательности самообучения. По сути, модальное обучение «делай так» не отличается от программирования правил поведения в предметной области. В случае описанного здесь бота приведенные выше правила по решению возникающих в ходе игры проблем зашиваются в виде программного кода. В ходе испытаний этого кода уточняются параметры, например, пороги для меры сходства.
Продолжая список проблем, расскажем о проблеме анимации выстрелов: после нажатия на пробел игра делает ход, с Роджерии взлетает очередная партия пиратских кораблей, орудия корабля игрока производят выстрел и далее все в дыму, как на ниже приведенном снимке экрана, сделанном через 3.5 сек. после нажатия ботом клавиши пробела (команда игры «сделать ход»).
Такой снимок не пригоден для распознавания – нужно подождать, когда дым рассеется, а объекты перестанут двигаться. Для минимизации этой паузы служит вкладка бота «Роджерия»:
После нажатия на кнопку «Создать серию» (надпись на кнопке меняется на «Отменить») появляется сообщение, предлагающее игроку перейти в экран игры и нажать F10. Бот сделает серию фотографий экрана («скринов») с задержкой, соответствующей указанным игроком параметрам. Далее игрок просматривает эту серию и выбирает приемлемую паузу. (На рисунке в поле Результат за именем файла через разделитель «=» записано значение паузы в мсек.)
В связи с этим возникает интересный теоретический вопрос: можно ли назвать описанный процесс обучением? А если нет, то чем модальный приказ воспитателя ребенку «мой руки перед едой» по сути отличается от приказа игрока боту «после хода сделать паузу в 4 сек. и только после нее сделать снимки экрана»?
Выбор паузы можно было бы полностью автоматизировать, например, следующим сценарием самообучения: в начале бот устанавливает явно завышенную паузу, а потом ее уменьшает до тех пор, пока результаты распознавания резко не ухудшатся. Возможно, такое решение кому-то покажется более красивым, однако, на мой взгляд, это было бы бесполезным украшательством. Паузу устанавливал только один раз, но можно предположить, что при смене среды, например, видеокарты, возникнет необходимость в изменении этого параметра.
Выше мы сказали, что в требования, предъявляемые к рациональному боту, входит полезность. Вряд ли бот будет практически полезным, если будет проходить игру слишком медленно, поэтому все паузы по возможности минимизировались.
Стоит также сказать несколько слов о самопознании (самоанализе). Его непреодолимая трудность является одним из ярчайших примеров ограниченности естественного интеллекта. Известный основоположник философии интуитивизма А. Бергсон отмечал, что хотя человек может поднять руку, он не может объяснить, как он это делает. Позже, работая над системами автоматического доказательства теорем, исследователи столкнулись с парадоксальным фактом: ни один математик не может объяснить, как он доказывает теоремы настолько полно, насколько нужно для реализации этих систем. Не помогает и то обстоятельство, что математике люди учатся в сознательном возрасте и могут шаг за шагом рассказать, как они изучали математику. Еще сложнее представляется ситуация с распознаванием речи и зрительных образов – никто не может рассказать, как он этому научился. Таким образом, ограничение естественного интеллекта проявляется в трудностях обучения ИИ распознаванию речи, зрительных образов, доказательству теорем и т.д.
Обработка редких и исключительных ситуаций
Выше отмечались ситуации, происходящие относительно редко, например, не найден транк, переход в главное меню и т.д. Такие ситуации стоит отличать от исключительных ситуаций. Исключение – достаточно строгое понятие, согласно Википедии, определяемое как
ошибки времени выполнения и другие возможные проблемы […], которые могут возникнуть при выполнении программы и приводят к невозможности (бессмысленности) дальнейшей отработки программой её базового алгоритма.
Механизм обработки исключений заложен в вычислительной среде. Стоит также отметить, что частота возникновения исключений не оговаривается, и в принципе исключения могут быть совсем не редкими.
Механизм обработки исключений заложен в вычислительной среде. Стоит также отметить, что частота возникновения исключений не оговаривается, и в принципе исключения могут быть совсем не редкими.
Редкие ситуации – не столь строгое, скорее эвристическое понятие, целиком зависящее от предметной области и моделирующей среды (в нашем случае – от игры). Как можно видеть из приведенных выше примеров, не все редкие ситуации приводят к невозможности или бессмысленности дальнейшей отработки программой её базового алгоритма. Например, захват кораблем бочки не требует каких-либо немедленных ответных действий бота. В предлагаемом решении освобождение от случайно захваченных бочек возложено на игрока и, как правило, может им производиться в удобное время, т.е. при очередной остановке бота для ремонта, замены ОМП и т.д. Если игрок отметит все бочки для захвата, то на следующем ходе его корабль может оказаться перегруженным, однако в реальной игре бота подобная ситуация представляется маловероятной.
В общем случае приходится признать, что даже самый тщательный анализ нетривиальной задачи не гарантирует выявления редких ситуаций, и при обучении с некоторыми из таких ситуаций можно не столкнуться. Эти соображения добавляют сомнения в отношении полной автономности, упомянутой выше. При рациональном подходе редкие ситуации обрабатываются человеком. Недавно большой резонанс вызвало сообщение о роботе-полицейском, утопившемся в фонтане супермаркета. Предполагаю, что причиной этого «суицида» стала не учтенная редкая ситуация.
Реализация, эмпирический подход
В 1976 г. Ньэлл (A. Newell) и Саймон (H.A. Simon) на вручении им премии Тьюринга прочитали лекцию на тему «Информатика – экспериментальная наука». Вслед за ними Дж. Ф. Люгер заявил:
каждая программа ИИ должна рассматриваться как эксперимент: он вопрос перед природой, и ответ на него – это результат выполнения программы. Отклик природы на заложенные конструкторские и программные принципы формирует наше понимание формализма, закономерностей и самой сути
(Дж. Ф. Люгер, Искусственный интеллект: стратегии и методы решения сложных проблем. 4-ое издание. М: Вильямс, 2003, С. 780).
Выше неоднократно отмечался не только экспериментальный подход к определению параметров, но и к выбору методов — например, эксперимент показал необходимость использования меры сходства. Собственно программирование и ловля основных багов заняли у меня очень небольшое время (примерно 10% от всего затраченного времени), во многом еще и потому, что в основу этого бота легла переделанная программа ранее сделанного мной бота для генерации корпусов кораблей в КР2HD. Основное время ушло на прохождение реальной партии и корректировки бота во время этого прохождения. Хотя, как и во всякой длительной задаче, не требующей постоянного участия оператора, если считать реальные затраты времени, то они небольшие – пока бот играет в игру на одном компьютере, можно рядом заниматься другими делами на другом компьютере. При остановке бот подаст звуковой сигнал. Для большего удобства игрока при использовании бота предусмотрена возможность указать в настройке бота программу, которую он запустит на выполнение при остановке. Например, это может быть программа телефонного звонка игроку, на случай, если игрок находится в другой комнате. Кроме того, есть опция выключения компьютера: при остановке бот сохранит игру и выключит компьютер.
Игра и мои предыдущие боты написаны на Delphi-7, в целях повторного использования кода эта же среда была выбрана и для данного бота. Кроме уже упомянутой OpenCV использованы библиотеки Delphi-OpenCV (Laentir Valetov, Mikhail Grigorev), TntWare Delphi Unicode Controls (Troy Wolbrink) и программа установки Inno Setup (Jordan Russell). Бот тестировался под ОС Windows XP SP3, Windows 8.1 и Windows 10. Версии игры КР2HD 2.1.2155 и 2.1.2170. Испытания в реальной партии заняли около 12 игровых лет, что превосходит длительность Роджерийской битвы в вышеупомянутых рекордах, но, конечно же, в таблице рекордов можно найти партии, где эта битва длилась дольше. По впечатлениям от этих испытаний бот удался. Удалось достигнуть поставленную цель рационального ИИ (см. выше) — «выбрать уровень автономности, на котором»:
1) «Программа будет полезной» — пользу ощутил, вместо тупого избиения пиратов на протяжении нескольких месяцев занимался гораздо более интересными делами, в то же время ощущал постоянное присутствие в игре, периодически принимая интересные игровые решения, которые не доверил боту.
2) «Программа не будет ошибаться слишком часто, по сравнению с человеком» — действительно, частоту ошибок удалось снизить до приемлемого, на мой взгляд, уровня: раз в час, а иногда дольше. При этом допускаю, что при более длительной и более тщательной отладке длительность безошибочной работы программы может быть увеличена.
3) «Программа не будет чрезмерно сложной для написания, отладки и сопровождения» — с особыми сложностями не столкнулся. Во всяком случае, не сравнить с упомянутым выше ботом планетарных битв (ПБ-бот). Хоть он показал некоторые успехи, но никто, в том числе и я, его продвинуть пока не смог.
Заключение
Программирование игр традиционно считается одним из важнейших направлений развития ИИ. В этом направлении можно выделить под-направление программирования ботов для игр: засунуть бота-жука в муравейник игры с целью посмотреть, что будет. Чтобы ответить на вопрос «зачем это нужно», стоит рассматривать современные естественные науки и гуманитарные области (например, художественное кино и литературу) с точки зрения модельного подхода. Научная теория, кинофильм, игра – суть модели, позволяющие исследовать некоторые общие принципы. В частности, например, из предложенной здесь модели-бота следуют принципы рационального выбора степени автономности, которые, на мой взгляд, могут оказаться полезными для, например, предотвращения самоубийств в фонтанах таких неигрушечных по назначению изделий, как упомянутый выше робот-полицейский.
Может показаться, что более сложная модель, например, более сложная игра или более сложная задача данной игры принесли бы больше интересных результатов. Однако принцип «чем сложней – тем лучше» далеко не всегда оказывается оправдан в подобных исследованиях – переусложненные модели, основанные на большом количестве правил с большим количеством параметров, зачастую приводят к ситуации, когда за деревьями не видно леса. Так, упомянутый ПБ-бот, ориентированный на более сложную задачу, не позволил сделать столь интересных наблюдений.
В заключение считаю своим приятным долгом поблагодарить Святослава за обсуждение тактики игры, идеи бота и за предварительное тестирование стартовых версий бота, а также Robo Brain‘а за обсуждение тактики игры.
Автор: third112
