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

Question

Я не уверен, что именно я пытаюсь спросить. Я хочу быть в состоянии сделать некоторый код, который может легко принять начальное и конечное состояние и некоторые правила, и определить пути / варианты, чтобы туда добраться.

Так, например, подумайте о такой игре, как Starcraft. Чтобы построить фабрику, мне нужно построить казарму и командный центр. Поэтому, если у меня ничего нет и я хочу фабрику, я могу сказать -> Командный центр-> Казармы-> Фабрика. Каждая вещь требует времени и ресурсов, и это должно быть отмечено и рассмотрено на пути. Если я хочу свою фабрику на 5 минут, то есть меньше вариантов, чем если я хочу на 10.

Кроме того, движок должен быть способен рассчитывать доступные ресурсы и эффективно их использовать. Эти три здания могут стоить всего 600 полезных ископаемых, но двигатель должен планировать командный центр, когда у него будет 200 (или без затрат).

Это в конечном итоге будет иметь требования, аналогичные 10 морским пехотинцам при 5 минутах, модернизации пехотного оружия в 6:30, 30 морпехам по 10 минутам, Factory @ 11 и т. Д.

Итак, как мне сделать что-то подобное? Моей первой мыслью было использовать некоторый процедурный язык и принимать все решения с нуля. Я мог бы смоделировать систему и ветвление и сделать разные выборы. В конечном счете, некоторые решения быстро делают невозможным достижение целей позже (если я построю 20 складов снабжения, я, вероятно, не собираюсь делать этот завод вовремя).

Тогда я подумал, что функциональные языки не предназначены для этого? Я пытался написать пролог, но у меня были проблемы с такими вещами, как расчеты времени и расстояния. И я не уверен, что лучший способ вернуть "план".

Я думал, что смогу написать:

depends_on(factory, barracks)
depends_on(barracks, command_center)
builds_from(marine, barracks)
build_time(command_center, 60)
build_time(barracks, 45)
build_time(factory, 30)
minerals(command_center, 400)
...
build(X) :- 
  depends_on(X, Y),
  build_time(X, T),
  minerals(X, M),
...

Вот где я запутался. Я не уверен, как построить эту функцию и запрос, чтобы получить что-нибудь даже близко к тому, что я хочу. Я должен был бы как-то учесть скорость, с которой полезные ископаемые собираются в течение времени, потраченного на строительство и другие возможные пути с дополнительным золотом. Если я хочу только 1 морской пехотинец за 10 минут, я бы хотел, чтобы двигатель генерировал много планов, потому что есть множество способов закончить 1 морской пехотинец за 10 минут (возможно, отключить его после стольких, не уверен, как это сделать в прологе)).

Я ищу совет о том, как продолжить этот путь или советы о других вариантах. Я не смог найти ничего более полезного, чем башни Ханоя и примеры предков для ИИ, так что даже некоторые хорошие статьи, объясняющие, как использовать пролог, чтобы ДЕЛАТЬ РЕАЛЬНЫЕ ВЕЩИ, были бы удивительными. И если я каким-то образом смогу настроить эти правила полезным способом, как получить пролог "планы" (способы решения запроса), кроме записи в стандартный вывод, как это делают все вышеперечисленные примеры из Ханоя? Или это предпочтительный способ?

Мой другой вопрос: мой основной код написан на ruby ​​(и, возможно, на других языках), и варианты взаимодействия с прологом - это вызов моей пролог-программы из ruby, доступ к виртуальной файловой системе из пролога или какая-то структура базы данных (маловероятно)). Я использую SWI-Prolog atm, лучше ли мне делать это процедурно в Ruby, или построение этого на функциональном языке, таком как пролог или haskall, стоило бы дополнительных усилий по интеграции?

Извините, если это неясно, я ценю любую попытку помочь, и я перефразирую вещи, которые неясны.

Answer 1

Ваш вопрос типичен и очень распространен для пользователей процедурных языков, которые сначала пробуют Пролог. Это очень легко решить: вам нужно думать с точки зрения отношений между последовательными состояниями вашего мира. Состояние вашего мира состоит, например, из прошедшего времени, доступных минералов, вещей, которые вы уже построили и т. Д. Такое состояние может быть легко представлено термином Пролог и может выглядеть, например, как time_minerals_buildings(10, 10000, [barracks,factory])). Учитывая такое состояние, вы должны описать, как выглядят возможные государства-преемники государства. Например:

state_successor(State0, State) :-
     State0 = time_minerals_buildings(Time0, Minerals0, Buildings0),
     Time is Time0 + 1,
     can_build_new_building(Buildings0, Building),
     building_minerals(Building, MB),
     Minerals is Minerals0 - MB,
     Minerals >= 0,
     State = time_minerals_buildings(Time, Minerals, Building).

Я использую явное соглашение об именах (State0 -> State) пояснить, что речь идет о последовательных государствах. Конечно, вы можете также вставить объединения в заголовок статьи. Код примера является чисто гипотетическим и может выглядеть несколько иначе в вашем конечном приложении. В этом случае я описываю, что истекшее время нового состояния - это время старого состояния + 1, что новое количество минералов уменьшается на количество, необходимое для создания Buildingи что у меня есть предикат can_build_new_building(Bs, B), что верно, когда новое здание B может быть построен при условии, что здания, указанные в Bs уже построены. Я предполагаю, что это недетерминированный предикат в целом и даст все возможные ответы (= новые здания, которые могут быть построены) при возврате, и я оставлю это в качестве упражнения для вас, чтобы определить такой предикат.

Учитывая такой предикат state_successor/2, который связывает состояние мира с его прямыми возможными преемниками, вы можете легко определить путь состояний, которые приведут к желаемому конечному состоянию. В простейшей форме он будет похож на следующую DCG, которая описывает список последовательных состояний:

states(State0) -->
     (   { final_state(State0) } -> []
     ;   [State0],
         { state_successor(State0, State1) },
         states(State1)
     ).

Затем вы можете использовать, например, итеративное углубление для поиска решений:

?- initial_state(S0), length(Path, _), phrase(states(S0), Path).

Кроме того, вы можете отслеживать состояния, которые вы уже рассматривали, и избегать их повторного изучения и т. Д.

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

Answer 2

Предостережение: мой Пролог ржавый и неглубокий, так что это может быть от основания

Возможно, подход "разностного двигателя" будет уместным:

• поставил цель, как "построить фабрику",
• Отношения обратной цепочки проверит наличие харак-бараков и скажет сначала построить бараки,
• который проверит наличие has-command-center и скажет вам построить build-command-center,
• и так далее,
• накопление плана (и затрат) по пути

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