О среде:
I. Формализация моно, мульти агентности ...
Несмотря на то, что в среде "Civilization" находится только один игрок (в дальнейшем агент), следует отметить две особенности приводящие к тому, что данную среду нужно рассматривать как среду с мульти-агентными взаимодействиями:
1. Агент с помощью юнитов - поселенцев за один ход параллельно в разных местах воздействует на среду;
2. Воздействие каждого юнита-поселенца сводятся (кроме движения необходимого для этого) к созданию активного центра (юнита-город) в среде. Такой город в течении времени способен воздействовать на среду и возможности агента в целом, а так же поощрения от среды, независимо от последующих действий агента. Такие воздействия могут быть трех типов: (1) уменьшаю число территории для будующей застройки, обесценивая соответствующую территорию (2) накопляют ресурсы, т.е. изменяют поощрение (3) увеличивают число поселенцев, что позволяет агенту увеличивать параллельность своих действий .
Таким образом, так как функционирование города происходит по правилам среды, и не управляются агентом, то такой город воздействует на среду, так как если бы в среде существовал бы другой активный агент и действия их были бы взаимосвязанными (в результате чего среда модифицировалась бы не зависимо от действий агента). Но отличием является то, что такой агент (система городов) не является противодействующим нашему агенту (системе поселенцев), а наоборот способствует достяжению результата.
II. Формализация поощрений:
Для агента существует следующая информация, которая может быть расцененна как поощрение:
1. Прирост (изменение) показателей Ri в городе Nj,
где i=1 (кол-во пищи), 2 (кол-во металла), 3 (кол-во денег),
4 (кол-во укомплектованных городом рабочих),
5 (кол-во укомплектованных городом поселенцев);
j - порядковый номер города.
2. Прирост (изменение) суммарных показателей Sum(Ri).
III. Зависимости переходов из состояния в состояние (модель переходов)
Здесь
- i-ое действие j-ого юнита-поселенец;
- i-ое действие j-ого юнита-рабочий (в городе находятся 9 рабочих);
IV. Модель действий - А, B
1. Для юнита-поселенец, возможны 9 действий: Аi={"(1,1)","(0,1)","(1,0)","(-1,1)","(1,-1)","(0,-1)","(-1,0)","(-1,-1)","0,0"}, где передвижения обозначены приращением координат переселенца, при этом если юнит остается на месте, то это означает что он - строит город.
2. Для юнита-рабочий, возможны 2 действия Bi={0,1}: работать, отдыхать.
3. Действие агента - суммарное действие всех переселенцев А1*А2*...*Аn.
4. Действие города Сi={ 0, 1 }: 0 - накапливать ресурсы, 1 - обменять ресурсы на юнит-поселенец.
Управление 9-ю действиями юнита-поселенец осуществляет агент.
Управление 2-мя действиями юнита-рабочий и 2-мя действиями города осуществляет среда по определенным правилам.
V. Определение состояний - S
Состояние зависит от:
1. Размера карты на плоскости (в рассматриваемом случае 15*10+14*9 = 276 квадратов)
2. От количества городов. Эквивалентом этому будет замена одного города 9 рабочими, которые находятся на площади города, и находятся в одном из двух состояний работают/отдыхают
3. От количество одновременно перемещающихся юнитов-поселенец.
Общее число состояний равно:
1. Если имеется только один юнит поселенец и нету городов, то число состояний равно размеру карты, т.е. 276 состояний, обозначим это число N;
2. Если на карте нету юнитов поселенец и могут быть созданы различные города, то число состояний равно
, т.к. на каждом квадрате карты может быть рабочий который работает или отдыхает, и соответственно число состояний будет равно комбинации всех возможных случаев. Величина
достаточно большая чтобы выразить число возможных ситуаций цифрой, поэтому более уместно использовать размер требуемый для хранения этого числа, т.е. 276 бит (35 байт), и в дальшейшем выражать число состояний в битах.
3. Если на карте неограниченное число юнитов поселенец и нету городов, то
, где M - максимальное число юнитов в одной клетке, ограничим такое максимальное число юнитов, которые могут находится в одной клетке 8-ю, тогда необходимо 276 байт.
4. Если имеется различное число юнитов поселенец и могут быть созданы различные города, то число состояний равно сумме (или комбинации ???, но вроде указанного объема достаточно, чтобы состояния описывались в указанном объеме независимо друг от друга, т.е. отдельно наличие городов и отдельно наличие поселенцов) пунктов 2 и 3, т.е. 276+35 = 311 байт
(в последнем пункте не уверен, поэтому перепроверте, кто соображает ... )
Из-за такого огромно числа состояний (около
) задача относится к NP - полной, что означает, что решение не может быть полученно путем перебора всех последовательностей переходов, которые приводили бы к наилучшему результату. Но для описания множества состояний достаточно 311 байт.
VI. Модель наблюдения (необходимо для задач PoMDP) - О
1. Для юнита-поселенец для наблюдения доступны 25 состояний (квадратов на карте) в 8 из которых он может переместиться.
2. Для агента видна та часть карты, которая была открыта юнитами-поселенцами за время игры
3. Модель наблюдений лучше описать графом из 276 вершин, соответствующим каждому квадрату карты, и 8 переходами от каждой вершины - показывающими взаимное расположение квадратов на карте. При этом общая модель наблюдений будет следующей
)
, т.е. 1 - соответствующий квадрат на карте открыт (доступен для наблюдения), 0 - информация о квадрате не известна.
----
Об агенте:
A.I. Контроллер пространственных ходов - врожденный безусловный минимальный интеллект агента
Контроллер пространственных ходов обеспечивает минимальный рациональный уровень ходов юнитов-поселенцев. Для того, чтобы интеллектуальная часть агента не была загруженна малозначищими вопросами. Для этого эта интеллектуальная часть должна оценить возможность каждого из 10 действий (а не выбрать одно из них) и предоставить эту оценку (число от 0 до 255) контроллеру пространтвенных ходов (КПХ).
1. КПХ осуществляет то действие, которое оценивается максимальной оценкой.
2. Если юнит достиг границы карты, и действие с максимальной оценкой нельзя осуществить будет выбранно действие с меньшей оценкой пока действие будет возможно осуществить.
3. Если юнит совершает перемещение обратное по направлению к предыдущему действию, то такое действие отклоняется и осуществляется действие с меньшей оценкой.
4. Если юнит хочет совершить действие по созданию города и оценка этого действия не превышает 100, то такое действие отклоняется и осуществляется действие с меньшей оценкой.
5. Если все оставшиеся возможные действия оценены одинаково, то осуществляется движение в случайном направлении.
A.II. Учитель - врожденный условный минимальный интеллект агента
Если действия КПХ агент не может изменить, то обучение учителя (которое происходит в off line фазе) он может со временем изменить. Обучение учителя направленно на то, чтобы агент мог хоть как то рационально вести себя в среде. Такое рациональное поведение может оказаться выгодным при равномерном распределеннии ресурсов по территории карты, а так же при примерно одинаковой важности каждого из ресурсов. Это происходит от того, что учитель обучает агента оценивать каждое из 9 действий (кроме отдыха) в соответствии с методом взвешенной оценки альтернатив.
А именно, из 9 альтернатив по каждому ресурсу находится максимальное и минимальное значение ресурсов суммированное по все площади города. Значения всех ресурсов приводятся к одному маштабу
*255)
, где maxmin - разница между максимумом и минимумом среди 9 альтернатив данного ресурса. Полученные значения и есть оценки.
А. III. Упрощение задачи, для акцентирования на нерешенной проблеме
Изначальная задача была упрощенна с целью сосредоточить внимание на основной проблеме. В изначальном варианте, предполагалась, что юниты обладают только визуальными сенсорами, на которые подается визуальное изображение 25 квадратов карты, т.е. модель наблюдения для юнитов-поселенец. И учитель дополнительно обучает распозновать эти территории. При этом одна и таже территория могла иметь разное изображение. В текущей версии, это положение упрощенно так, что уже на вход подается тип территории, а учитель обучает только тому сколько на ней ресурсов и как оценить совокупность из 25 территорий. При этом этим упрощением не стоит злоупотреблять в реализации агента. Предполагается, что агент будет способен построить модель реализуемых им действий и стратегий в целом, имея возможно прогнозировать в неизвестных ситуациях. Но упрощение позволяет сосредоточится не на прогнозировании вида территорий (на основе изображения), а именно на всем ходе принятия решений по оценке действия.