Искусственный интеллект. В дополнение к основной цели работы выделяем следующие задачи
 Скачать 1.7 Mb.
|
|
2.2 Подготовка к написанию ИИ Прежде чем приступить к написанию бота, необходимо решить некоторые дополнительные задачи: подготовить дополнительные средства для помощи в разработки; определиться со средой, в которой функционирует бот для конкретной игры; выбрать методологию написания ИИ и методы принятия решения о выборе. 2.2.1 Подготовка окружения для разработки В ходе первых попыток написания собственного бота, я столкнулся с рядом сложностей, в связи, с чем составил список того, что необходимо сделать для успешного завершения проекта, прежде чем приступать к непосредственному писанию ИИ. Журналирование Система, при которой игровой движок общается, с ботами в виде отдельных процессов через стандартный ввод-вывод означает отсутствие возможности пошаговой отладки даже во время тестирования на локальном компьютере. Поэтому автор с самого начала создал систему журналирования (или логов), которая достаточно полно раскрывала процессы, происходящие во время игры. Свой движок Чтение логов утомительный процесс и занимает слишком много времени. Для решения этой проблемы и для более глубокого понимания процессов, происходящих, в движке игры автор решил переписать движок на языке Python. Это позволило подключать ИИ напрямую к движку в качестве библиотеки, тем самым давая возможность для отладки. Модификации в визуализаторе Так же для удобства разработки автор модифицировал визуализатор сыгранных игр, написаны на Java и поставляемый в стандартном наборе (рис. 7).  Рис. 7 - Фрагмент модифицированного визуализатора В частности: Была добавлена возможность менять скорость воспроизведения при помощи дополнительного аргумента во время вызова приложения. Изначально она была слишком медленной. Были добавлены линии, показывающие траекторию полёта флотилий. Часто было не понятно, какая цифра куда движется. Была добавлена возможность передавать визуализатору дополнительную отладочную информацию касательно планет с последующим её выводом на экран (на рисунке белый цифры под планетами). Например, при выборе цели для каждой планеты считается коэффициент, найти и сопоставить с конкретной планетой, из логов было достаточно сложно. Написание тестов В подобной задаче безусловным подспорьем являются модульные тесты, которые также присутствуют в написанном ИИ Система игры на всех картах Для эффективной проверки производительности разрабатываемого ИИ был написан несложный сценарий для запуска бота на всех картах из начального набора. В конце работы он выдаёт статистическую информацию по тому, сколько игр было выиграно, проиграно и за сколько ходов. 2.2.2 Процесс разработки Процесс разработки бота можно разделить на несколько этапов: Написание первого бота и тестирование его на всех картах против всех простых ботов, что идут в начальном наборе. Улучшение бота до тех пор, пока он не будет побеждать в 100% случае. «Замораживание» бота в его текущем состоянии и установка его на место противника и переход к пункту 2. Т.е. теперь задача играть против своего же бота, и улучшая следующее поколение прийти к полной победе над ним. Периодически пользоваться TCP Server’ом (http://www.benzedrine.cx/planetwars/). Это неофициальный централизованный сервер, на котором можно в реальном времени сразиться с другими клиентами сервера. Главное отличие от официально сервера заключается в следующем: (а) В скорости. Подключившись игра начинается практически сразу, в отличии от официального сервера, где каждый бот играет в среднем раз в пол часа. (b) Не нужно заливать свой программный код на сервер. Код бота запускается на компьютере его владельца, тем самым давая возможность записывать логи для последующего анализа. (c) Игроки на TCP Server’е зачастую очень сильные, поэтому для бота это всё равно, что стресс тестирование. Если появляется ощущение, что бот уже достаточно работоспособный, его можно упаковывать и засылать на официальный сервер и переходить к пункту 3. 2.2.3 Выбор типа ИИ и метода его написания Поэтому уместным в данной задаче применение агентно-ореинтированного подхода. Характеристики игры очень похожи на свойства среды, в которых функционирует агент, играющий в шахматы за одним важным исключением. Средний коэффициент ветвления в шахматах примерно равен 35. Т.е. в среднем на каждом полу ходу игрок может выбирать среди 35 возможных решений, что даёт приблизительно 35100 различных комбинаций состояний игры. При этом программа DeepBlue могла просмотреть только на 14 ходов вперёд. Для написания агента с использованием конкретных правил и законов, а иначе говоря, используя стратегию и тактику, необходимо использовать знания о том «как работает мир». Такой агент называется агентом основанным на модели. С учётом того, что мы не собираемся использовать алгоритмов поиска, для просмотра всех вариантов развития событий. То для такого агента достаточно разработать систему рефлексов, т.е. механизмы, реагирующие исключительно на текущее акты восприятия. Хотя некоторые аспекты алгоритма всё же можно рассматривать как предсказание, когда система защиты строится на предположении относительно некоторых планет. 2.2.4 Характер среды Критерии успеха, наряду с описанием среды, а также датчиков и исполнительных механизмов агента, предоставляют полную спецификацию задачи, с которой сталкивается агент. Критерием успеха или показателем производительности в случае игры ВП является счёт на конец соревнования в итоговой рейтенговой таблице, а так же результат каждой сыгранной партии. Во время локального тестирования на всех картах такими показателями являются также количество ходов, за которое бот победил и проиграл. Существуют характеристики, по которым можно классифицировать среды, в которых оперируют ИИ. В данном случае имеет место форма взаимодействия ИИ, представляющая собой детерминированную, поочередную, охватывающие двух игроков игру с нулевой суммой и с полной информацией. Эти и другие свойства среды, и их значения, применительно к данной игре приведены в таблице 2. Таблица 2 -Характеристики среды игры ВП
Продолжение таблицы 2
Стратегия и тактика В этом разделе описаны стратегии и тактики, которые я применил и реализовал в своём агенте. Так же тут делается попытка связать их со знаниями о военном ремесле, описанными в трактате «Искусство Войны» (5-6 вв. до н. э.). Это правило действительно и тут, потому что игра продолжается максимум 200 ходов. Что бы достичь победы, медлить нельзя. В этой игре быстрота развёртывания сил и захвата планет очень важна. В момент главного сражения разница в одну планету может решить исход партии. Как уже говорилось ранее в начале игры у обоих игроков условия совершенно одинаковые. У каждого есть по планете с сотней кораблей, а все остальные планеты находятся на равных расстояниях от начальных планет игроков, т.к. карта симметричная. Из этого можно ещё раз подчеркнуть мысль, что исход каждого поединка зависит исключительно от алгоритмов игроков. Общую стратегию, можно охарактеризовать как «играть, что бы не проиграть», т.к. главное в этой игре - правильная оборона, что будет раскрыто ниже. Вся стратегия автора делиться на 6 этапов или элементов. Алгоритм проходит через все эти этапы принимает решение о выборе. Каждый из них описан далее более подробно. 2.3.1 Первый ход и расширение Самым первым этапом игры является фаза «развёртывания», в которой особенно важно самый первый выбор. Причина тому в симметричности первоначального состояния игры для обоих игроков. Поэтому очень важно с первых секунд игры попытаться получить преимущество, выбрав планеты для первой атаки наиболее эффективно. В отличие от шахмат в этой игре нет игрока, идущего первым, оба игрока делают свой первый полу-ход, не зная о решении противника. Неправильное решение на первом шаге может закончиться быстрой победой противника. Пример на рисунке 8.  Рис. 8- Ошибка первого игрока (светло-серый) на первом шаге В показанной ситуации начальные планеты игроков находятся, очень близко друг от друга и один из участников не обращая на это внимание, рассылает большую часть своих кораблей на захват нейтральных. В то же время его противник не спешит распускать все корабли. В результате ошибки второй игрок следующим ходом захватит изначальную планету первого игрока и получит тем самым победное преимущество, т.к. начальные планеты имеют высокий коэффициент роста (обычно 5). На самом деле при хорошей самообороне и правильно выбранной функции выбора цели для атаки никакой особой логики в первый ход вкладывать не обязательно (будет видно далее). Хотя мы всё же разработали рефлекс который срабатывает на первом и последующих ходах, если ситуация такая как описана выше. Он оставляет все корабли на первом ходу, а на втором посылает все корабли на главную планету противника. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||