Фэндом

Виртуальная лаборатория

Формализация среды для задачи - Двухуровневое целеполагание

перенаправлено с «Формализация среды для задачи "Двухуровневое целеполагание"»

204 622статьи на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

© Сергей Яковлев, 2006 - 2009

Использование этой информации в коммерческих целях запрещенно. Но Вы можете копировать и перерабатывать данную статью в научных и образовательных целях, с последующим предоставлением результата на тех же правах. Для подробной информации см. Авторское право.



Постановка проблемы Править

Двухуровневое целеполагание агента как задача искусственного интеллекта

Навигация Править

История вопроса была такова. Требовалось найти такую задачу для ИИ, в которой агент проявлял бы некоторые элементы интеллектуальности, и тем самым бы чтобы такая задача отсеивала бы менее удачные алгоритмы. Актуальность проблемы подверждали и другие публикации, напрмер, статья Андрея Плахова "О проблеме создания искусственного интеллекта", где среди прочего утверждалось:

«Программистам предлагалось (Microsoft Terrarium) создавать искусственную жизнь, не больше и не меньше. Это, наверное, самое известное из подобных соревнований, а вообще их проводится очень много — энтузиасты-организаторы с завидной регулярностью предлагают создавать программы, играющие то в войну роботов, то в колонизацию Юпитера. Бывают даже соревнования по выживанию среди компьютерных вирусов. Что же мешает хотя бы этим проектам служить созданию настоящего ИИ, который в будущем сможет и воевать, и Юпитер колонизировать? Одно простое слово — непродуманность. Даже могучие умы Microsoft не смогли придумать правила, в которых сложное поведение выгодно. Что уж говорить об остальных. Что ни турнир — а все побеждает одна и та же тактика: "чем проще – тем лучше"! Никакая другая тактика даже близко не могла сравниться с этой по своей эффективности. Это, разумеется, проблема правил игры. Но именно с ней и сталкиваются все подобные турниры. Чтобы поощрять сложное поведение, нужен сложный мир, а на компьютере такой смоделировать очень непросто.»

После чего мной было предложено поразмышлять на эту тему "Мы, конечно, не могучие умы Microsoft :) , но какую – нибудь приличную постановку задачи сделать сможем".

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


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


Поэтому на третьем шаге - встал вопрос о формализации задачи, в том смысле, чтобы ее однозначно понимать и увидеть ее цель.

Есть некоторые нароботки по формализации этой задачи:

При этом может оказаться, что условия задачи недостаточны для поставленной цели. Цель же поставленна с одной стороны достаточно четкая: это выработать такие условия среды, которые однозначно бы способствовали написанию именно интеллектуальных методов, а методы перебора, жесткой логики и т.п. не смогли бы пройти такой своеобразный турнирный тест. Поэтому если изначально условия задачи только это предполагали, но не являлись этим, их следовало бы модифицировать как только это станет ясно. Но с другой стороны, цель не столь четкая, т.к. предполагает однозначное понимание термина "интеллектуальный метод" ... но мы поступим так - интеллектуальность мы определять не будем, т.к. никто не знает что это такое на самом деле ... единственно мы знаем некоторые принципы интеллектуальности - и возьмем лишь самый базовый - алгоритм не должен выполнять перебор всех ситуаций, и быть детерменированным. И в таком случае, пригодной средой мы будем считать ту, в которой такие жестко детерминированные методы не могут добится результата или дают не те характеристики которые нужны ...

См. также Править

Протейшая интерпретация двухуровневого целеполагания Править

Для задачи используем мотив стратегической игры Цивилизация.

MapRegion.jpg

Характеристики типов территорий


Модельная среда представляет собой карту местности, разделенную на 276 квадратов (участков) различного типа – луг, равнина, океан, река и т.д. (всего 16 видов). Каждый тип территории отличается количеством ресурсов, которые можно получить, обрабатывая эту территорию. Различают три вида ресурсов – пища, металл, деньги. В таблице показаны все классы и их характеристики.

Игра начинается с одного поселенца, который помещается в случайную позицию на карте. Задача поселенца выбрать место для будущего города, необходимого для того, чтобы обрабатывать местности на карте. Видимость карты для поселенца составляет 25 квадратов (радиус 2 квадрата вокруг него).


Сделав свой выбор, поселенец строит город, а сам пропадает – превращается в одного жителя города. Город занимает площадь 9 квадратов (радиус 1 квадрат вокруг него), потенциальных для выбора места обработки. Центр города считается всегда обрабатываемым. Окраины (8 квадратов) могут обрабатываться жителями, на одного жителя – один квадрат. Выбор делается статично в момент появления жителя. Таким образом, сразу после постройки выбирается место для обработки. Далее при накоплении на складах города определенного количества еды – появляется житель города (и стоит задача выбора места обработки), а при накоплении определенного количества металла - появляется новый поселенец (и стоит задача выбора места для нового города).

Количество необходимой еды для появления нового жителя зависит от размера города (числа жителей этого города). При одном жителе нужно 20 ед. Еды, при двух – 30 ед. и т.д. Количество металла необходимое для создания поселенца 40 ед. Задача состоит в выборе стратегии при которой за 80 ходов можно добыть наибольшее количество денег. Важной частью условий является предоставление информации о самих правилах игры – играющему автомату. Например, непосредственно ему не известно сколько тех или иных ресурсов можно добыть на определенном типе территории.

Map.jpg

Карта

Map step50.jpg

50 ход при моделировании. Красный квадратик - "Центр города", желтый квадратик - "поселенец", зеленых крестик - "житель"


Игра осложняется тем, что информация о правилах агент получает косвенно, через систему т.н. учителей (об этом см. следующий раздел).

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

Другие интерпретации Править

Можно начать с того, чтобы поменять легенду, хотя это математически ничего не меняет, но как минимум поясняет как легко можно перейти к любой интерпретации:

Биологическая интерпретация Править


Модельная среда представляет собой экологическую нишу, разделенную на 276 квадратов (участков) различного типа – луг, равнина, океан, река и т.д. (всего 16 видов). Каждый тип территории отличается количеством ресурсов, которые можно получить, обрабатывая эту территорию. Различают три вида ресурсов – пища, материал для постройки места размножения (гнездо), биоматериалы (новые фрагменты ДНК, РНК).

Игра начинается с одной особи, которая помещается в случайную позицию на карте. Задача особи выбрать место для гнезда, необходимого для того, чтобы размножаться. Видимость карты для особи составляет 25 квадратов (радиус 2 квадрата вокруг него).

Сделав свой выбор, особь строит гнездо. Гнездо занимает площадь 9 квадратов (радиус 1 квадрат вокруг него), потенциальных для выбора места добычи ресурсов. Центр гнезда считается всегда обрабатываемым. Места прилегающие к гнезду (8 квадратов) могут обрабатываться особями, которые находятся в гнезде, на одну особь – один квадрат. Выбор делается статично в момент появления новой особи. Таким образом, сразу после постройки выбирается место для обработки.

В зависимости от добытой еды – появляется новые особи (и стоит задача выбора места обработки), а при накоплении определенного количества материала - особь может перемещаться дальше приделов гнезда и построить новое гнездо (и стоит задача выбора места для нового гнезда).

Количество необходимой еды для появления нового особи зависит от числа уже живущих особей в гнезде - чем более тесное жильё, тем большее количество пищи необходимо для прокормки. При одной особи нужно 20 ед. еды, при двух – 30 ед. и т.д. Количество материала необходимое для создания нового гнезда 40 ед.

Задача состоит в выборе стратегии при которой за 80 ходов можно добыть наибольшее количество биоматериалов, имяя которые можно в дальшейшем эволюционировать.

Важной частью условий является предоставление информации о самих правилах игры – играющему автомату. Например, непосредственно ему не известно сколько тех или иных ресурсов можно добыть на определенном типе территории.

Военная интерпретация Править

Ресурсы:

int FoodCount; // Снабжение припасами

int MetalCount; // Обеспечение оборудованием для развертывания

int MoneyCount; // Стратегическое значение

Типы территорий (int argFoodCount, int argMetalCount, int argMoneyCount) // Процент распространенности

new PlaceType( 82, "Степь", 1, 1, 0); // 13.0 %

new PlaceType( 146, "Равнина", 2, 1, 0); // 15.9 %

new PlaceType( 130, "Луг", 2, 0, 0); // 19.9 %

new PlaceType( 97, "Лес", 1, 2, 0); // 4.3 %

new PlaceType( 114, "Пастбище", 1, 3, 0); // 0.7 %

new PlaceType( 210, "Пашня", 3, 1, 0); // 0.7 %

new PlaceType( 109, "Парк", 2, 3, 0); // 0.4 %

new PlaceType( 200, "Озеро", 3, 0, 0); // 0.4 %

new PlaceType( 147, "Река", 2, 1, 1); // 8.7 %

new PlaceType( 65, "Холм", 1, 0, 2); // 6.5 %

new PlaceType( 50, "Поселение", 1, 1, 2); // 2.5 %

new PlaceType( 172, "Порт", 2, 2, 3); // 1.8 %

new PlaceType( 77, "Аэропорт", 1, 0, 3); // 0.7 %

new PlaceType( 72, "Океан", 1, 0, 1); // 19.9 %

new PlaceType( 66, "Тундра", 1, 0, 0); // 4.3 %

new PlaceType( 17, "Горы", 0, 1, 0); // 0.4 %

Экономическая интерпретация Править

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

Биоинформатика Править

Наконец самой серьезной интерпретацией является решение парадокса Левенталя ...

Как белок ухитряется найти свою нативную структуру среди астрономического числа возможных за те немногие секунды, что отпущены на его сворачивание? Сложность проблемы заключается в том, что поднятый вопрос нельзя решить чисто экспериментально. Действительно: предположим, у белковой цепи есть другая “ненативная”, но еще более стабильная укладка. Как ее найти если сам белок ее не находит? Ждать результата в течении примерно 10^{80} лет? С другой стороны, действительно ли существует противоречие между “структурой стабильности” и “структурой быстро сворачивающейся”? Может быть, стабильная структура автоматически является фокусом “быстрых” путей сворачивания, и поэтому автоматически обладает свойством сворачиваться быстро?

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

Передача информации с помощью систем учителей Править

Правила для осуществления системы учителей могут быть весьма разнообразными, здесь мы опишем лишь пример.

Отсутствие непосредственной информации о типе территории Править

Информация о типе территории автомату напрямую не предоставляется. Взамен этого он может обратиться к учителю, предоставив ему визуальное изображение интересующего его квадрата (цвет 1000 точек в 256 цветовой гамме). Учитель же, на самом деле эту информацию игнорирует, но зная от кого идет запрос (например, от конкретного поселенца или города) определяет его координаты, сверяется с таблицей расположения территорий на карте, и возвращает ответ в следующей форме: визуальному изображению такому-то соответствует такой-то тип территории. При этом разные изображения могут соответствовать одному и тому же типу территорий.

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

Отсутствие непосредственной информации о наличии ресурсов на определенном типе территории Править

Взамен информации о наличии ресурсов в том числе или ином месте предоставляется экспертная оценка пригодности выбранного места для определенной цели (например, для постройки города, выборе территории для обработки и т.п.). Для предоставления экспертной оценки по постройке города, поселенец предоставляет информацию о том, какие на площади предполагаемого города (9 квадратов) существуют типы территорий (по ему мнению), в ответ учитель дает свою экспертную оценку. Например, это может быть число от 0 до 255, говорящие о том, что 0 – совсем не пригодное место, а 255 – наилучшее место для строительства города. При выборе обрабатываемой территории ситуация сходна, с той лишь разницей, что не учитывается уже занятые территории.

Учитель делает свою оценку на базе какого-нибудь известного классического алгоритма “Принятия решений”, например, применяя взвешенную оценку альтернатив. Дополнительно к этому методу учитель учитывает уже занятые территории – если предполагается строить город на городе, то экспертная оценка будет 0, если предполагается город строить на территории окраин уже построенного города (где потенциально уже может обрабатываться территория), то экспертная оценка будет 50. Автомат должен сам решать на сколько стоит доверять такой оценке или стоит ее игнорировать.


Жесткие алгоритмы проверки Править

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

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

Построить жесткий алгоритм, вычисляющий алгоритм при известных "если знать что она длится 80 ходов, если знать при каком условии появляется новый житель в городе и поселенец, если знать какие типы территорий существуют и сколько на каждой из них ресурсов, и главное по какому параметру оценивается успех."


для вырожденного случая когда есть всего два типа територий - Океан (1/0/2) и Степь (1/1/0) - стратегия следующая: имеет смысл устанавливать цель города - получение поселенца (степь+степь), только тогда когда до середины игры он сможет предоставить 2-х и более поселенцев. По прошествию 25% игры следует использовать смешенную стратегию (степь+океан), а после 50% пройденной игры наращивать только объем золота (тип города океан+океан). Вырожденность заключается в том, что здесь города не растут, т.к. прирост пищи только 2 ед., что равно ее расходу на одного жителя (напомню, что центр города обрабатывается без жителя). В итоге - получаем 484 ед. золота ... и ни какая другая стратегия не позволяет улучшить показатель. Вторая по значимости стратегия построить единственный город на территории (океан+океан) - доход 320 ед. золота. При наличии только двух видов территорий найти необходимое распределение видов территорий, можно практически за 1-2 хода ... но даже если при специальном распределении потребуется искать берег океана, то оставаясь в выйгрыше на это можно потратить до 13 первых ходов. (да, и действительно, не легко - пол дня с карандашем просидел ) Для более сложных распределенний дело техники ...

Что же касается, берега океана - Вы возможно не поняли, стратегию я описал вам на человеческом языке, понятно, что алгоритм будет оперировать совершенно другим ... и если Вы вчитаетесь в формулировку, то найдете там все свои ответы. Стратегия была просчитана в ручную, и были рассчитаны все возможные варианты для того вырожденного случая, когда имеются только два типа территорий - степь и океан. Если океана вообще нет - то денег набрать вообще нельзя, т.к. только там есть соответствующий ресурс, для агента нет таких понятий как океан или степь, для него есть только распределение ресурсов - 2 пища, 0 металла, 2 денег - это МЫ назваем океан, 2 пища, 2 металла, 0 денег - степь ... У алгоритма нет кусков стратегии, у него есть детерминированный алгоритм расчета, как получить большее количество денег, при текущем распределеннии территорий, даже не смотря на то, что это распределение не все доступно для наблюдений, из-за этого есть некий риск, но риск совершенно детерминированный, например, если известно, что при открытой территории, ее можно использовать определенным образом, как в вырожденном примере, нужно искать берег океана, но если нет суши, то можно безпройгрышно потратить до 13 шагов, а если нет океана - то вообще можно затратить все ходы. Если же поиск не удался, то используем то, что есть. В итоге риск на поиск практически не влияет на конечный результат. Если бы за 13 ходов ничего не нашли, то поиск утрачивает свою надобность, т.к. все равно не обогнать другую стратегию.

Ссылки Править

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на Фэндоме

Случайная вики