Теория ИФтоматов

Многие замечают сходство изображения ИЛ в виде графа и Автомата с конечным набором состояний.

Практически 1 к 1. ИЛ и в правду является системой с конечным набором состояний, а значит всякое ИЛ-произведение — автомат.
Однако мало кто знает какую пользу можно из этого вынести.

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

Графтомат
Первое из представлений — это граф.

Кругами обозначаются состояния автомата(однако нельзя их сразу считать «комнатами» как в ИФ), возможные выходы из состояния обозначаютсся стрелками, причем каждой стрелке соотвествует условие перехода. Выводимый текст в комнатах также зависит от условий.

Так вот, внутри одной комнаты может быть несколько состояний и, соответственно, переходов между ними. Поэтому «комната как состояние» подойдет лишь в очень редких случаях.

С переходами, в случае ИФ, тоже особенность — в автомате переход осуществляется сразу при выполнении условий, а в ИФ — переходы могут не существовать при определенных условиях(не выводиться).

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

Но главный вопрос — для всех ли представлений автомата(напомню, теория активно развивалась начиная с 1971г.(Conway, J.H. (1971). Regular algebra and finite machines), особенно в СССР, и накопилось много довольно интересной информации) существуют редакторы соответствующего представления для ИЛ, все ли особенности автоматов учтены при проектировании ИЛ-редакторов?


Редактором графового представления ИЛ является twine.
Особенность в том, то на карте обозначается сама возможность переходов и выводимый текст комнаты(с условными макросами).
Чего не видно(по сравнению с обычным автоматом)? Условий существования перехода над линиями(обычные стрелки могут обозначать безусловный переход по выбору пользователя).

Кодтомат
Автомат можно реализовать в виде кода на языке программирования.
Причем, наличие label+goto жизненно важно. Но можно реализовать и виртуальную машину(там где label+goto отсутствуют).

room1:
  puts(" Вы находитесь в комнате №1 ");
  if(visitedRoom2==true) puts("Вы вернулись из комнаты 2");
  puts(" 1:  Перейти в другую комнату ");
  if(read()==1) {goto room2;}
room2:
  puts("  Теперь вы находитесь в комнате №2 ");
  puts("  В этой комнате пусто ");
  puts(" 1:  Вернуться в комнату №1 ");
  if(read()==1) {goto room1; visitedRoom2=true;}

Таким образом, при проверке условий и считывании ввода, осуществляется переход между комнатами(вместе с установкой условий).
Такой способ легко реализуем.
И его использовали раньше для написания ИФ на языке Бейсик в 80-х годах.
0010: print " Вы находитесь в комнате №1 "
0020: print " 1:  Перейти в другую комнату "
0030: input "введите ответ», A
0040: if A=1 then go to 0050
0050: print " Теперь вы находитесь в комнате №2 "
0060: print "В этой комнате пусто"
0070: print " 1:  Вернуться в комнату №1"
0080: input "введите ответ", A
0090: if A=1 then go to 0010

Код на Бейсике характеризуется наличием метки для каждой строки(0050), что избавляет от необходимости её обозначать. Переход осуществляется по меткам.

Для такого представления автомата(а значит и представления ИЛ) уже существует редактор — QGen, и, сам по себе, язык платформы QSP:
#room1
'Вы находитесь в комнате №1'
ACT 'Перейти в другую комнату':
        GOTO 'room2'
END
-
#room2
'Теперь вы находитесь в комнате №2'
'В этой комнате пусто'
ACT 'Вернуться в комнату №1': GOTO 'room1'
-


Представления ИЛ в виде графа и ИЛ в виде кода всем известны.
Но изучаем дальше — ведь еще не все возможные представления ИЛ разобраны!

Таблицтомат

Вот табличного редактора ИФ еще не было!
Это и понятно, т.к. табличное представление ИЛ требует возможностей текстового процессора!

Возможно существование табличного редактора ИЛ на основе LibreOffice(со всеми плюшками в виде проверки орфографии и выделения текста).

Автомат-о-автомат
Табличное представление и представления в виде графа являются чем? Декларативными представлениями автомата!
https://ru.wikipedia.org/wiki/Декларативное_программирование

Также, декларативным представлением является код для Instead:
room2 = room {
	nam = 'Зал';
	dsc = 'Вы в огромном зале.';
	way = { 'main' };
};
 
main = room {
	nam = 'Главная комната';
	dsc = 'Вы в большой комнате.';
	obj = { 'tabl' };
	way = { 'room2' };
};

tabl = obj {
	nam = 'стол';
	dsc = [[В комнате стоит {стол}.]];
	act = 'Гм... Просто стол...';
	obj = { 'apple' };
};
--https://instead.syscall.ru/wiki/ru/gamedev/documentation

Он показывает ЧТО имеется, и КАК реагирует.

Однако, декларативное и императивное представления взаимоконвертируемы!!!
Это значит, что тот же код на Instead или Twine можно сгенерировать процедурно, причем весьма специфическим образом.

Переведем код выше в процедурную парадигму:
room("Зал")
dsc("Вы в огромном зале.")
way("Главная комната")
end()

room("Главная комната")
dsc("Вы в большой комнате.")
obj("стол")
way("Зал")
end()

object("стол")
act("click",'Гм... Просто стол...')
obj("яблоко")
end()

Что изменилось?
Пропали промежуточные переменные(main,room2).
Вместо этого можно оперировать сразу именами(«Зал»,«Главная комната»)!
А значит нету дублирования имен(как для комнат, так и для объектов).
Код стал чище — он без скобок и точек с запятой.

Процедурная генерация декларативного представления!

Каков главный вывод?
Реализованы не все представления автомата для задания ИЛ(некоторые здесь не рассмотрены).
Существует еще потенциал роста.

Похожие публикации

Тут ничего нет

20 комментариев

Oreolek
Это и понятно, т.к. табличное представление ИЛ требует возможностей текстового процессора!

Возможно существование табличного редактора ИЛ на основе LibreOffice(со всеми плюшками в виде проверки орфографии и выделения текста).
Возможно, но нежелательно. К такой таблице нужен ворох автоматических проверок — как минимум что room2 и room1 действительно существуют, а переменные visited_mall существуют и где-то используются (у вас в табличке, кстати, нет разделения между проверкой переменной и изменением).


object("стол")
act("click",'Гм... Просто стол...')
obj("яблоко")
end()

Почему яблоко — это obj, а не object? Почему у него нет свойств, описания? А между прочим, в исходном примере на INSTEAD это — такой же объект, как и стол. По-моему, упрощение некорректно.

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

Рекомендую познакоииться с движком Ink. Он был как раз опубликован для борьбы против табличек как инструмента для писательского творчества.

P.S. А вообще, детерминированные конечные автоматы — это самые основы разработки искусственного интеллекта, в эту сторону тоже очень и очень интересно копать.
pixman
Возможно, но нежелательно. К такой таблице нужен ворох автоматических проверок — как минимум что room2 и room1 действительно существуют, а переменные visited_mall существуют и где-то используются
Проверки(комнат и переменных) нужны в любом случае и при любом движке(это элементарная вещь). Пренебрежение отловом ошибок — на совести разработчика API.
(у вас в табличке, кстати, нет разделения между проверкой переменной и изменением)
Вообще-то она есть — во второй колонке проверяются переменные, а в четвертой выполняется код(в т.ч. и установка переменных "(set x)").

object("стол")
act("click",'Гм... Просто стол...')
obj("яблоко")
end()

Почему яблоко — это obj, а не object? Почему у него нет свойств, описания? А между прочим, в исходном примере на INSTEAD это — такой же объект, как и стол. По-моему, упрощение некорректно.
obj() — это процедура включения объекта в данную комнату/объект. Стол содержит яблоко как объект. Однако в примере яблоко не объявлено(не объявлено оно и в instead-примере) — было решено этим пренебречь — главное суть перехода к другой форме записи(а они всегда эквивалентны, т.к. это всего-навсего другая форма записи). Так что я ничего не упрощал — только иначе записал(причем у такой формы записи менее нагруженный(запятыми и скобками, лишними именами) синтаксис).

Строго говоря, любая однопользовательская игра — это конечный автомат, потому что все исходы детерминированы. Но вы пытаетесь описать одной моделью и простые механики интерактивной литературы, которые соединяют куски текста (например, параграфы книг-игр), и игры с моделью мира, откуда возникает путаница.
Я о том и говорю, что внутри одной комнаты может быть несколько состояний и поэтому взаимосвязь состояний(как граф) может не соответствовать однозначно модели мира(как граф)(количество состояний необязательно соответствует числу комнат). Никакой путаницы здесь нет — придется только объявлять состояния(прогресс в истории) как комнаты(что в Instead, что в QSP) и делать «комнатные» переходы. Момент интересный, тем не менее.
fireton
— Уважаемый, подскажите пожалуйста, где мы находимся?
— Вы на воздушном шаре!
pixman
Лагранжа, Лапласа и Лейбница — почему существует три(а на деле еще больше) нотации для записи дифференциалов?
Потому что, «there is no silver bullet».
Эта древняя проблема перекочевала в программирование из математики. Некоторые даже используют больше одной нотации при решении диффуров — меняя одну на другую прямо в процессе.
Подумайте.
А в справочниках можно встретить двойную таблицу — для нотации Лагранжа в одной колонке и нотации Лейбница в другой. В учебниках по теории даже пояснения дают иногда в обоих нотациях.
Нет самого лучшего способа представления подходящего сразу для всех IF'ов.
А выбор формата представления под соответствующую механику/модель мира на больших задачах может быть существенным.
lukyuk
Pixman, серьёзно, теоретиков и так полно, а «теоретиков» ещё больше. Считаешь свою идею стоящей — пиши игру или движок. Кубик Рубика, крестики-нолики или ещё чего придумается. А вот потом уже статью «Зацените классную идею! Она работает!».
Peter
> А значит нету дублирования имен(как для комнат, так и для объектов).
В инстеде это не дублирование, а разное назначение. Одно дело, как выглядит объект для игрока, и другое — для программиста. Писать все время «Замечательный меч кладенец».sila = 100, вместо sword.sila может быть кому-то и удобно, но не мне точно. :)

В принципе, в инстеде оба идентификатора можно использовать. Правда, не во всех ситуациях они взаимозаменяемы. Да и nam — вообще говоря — изменяемый атрибут. Можно сделать так, что nam будет не нужно писать. Можно создавать объекты без knife =, а описывать их прямо на месте (внутри комнаты)… И тд.

Так что про дублирование — сказано не совсем корректно. Есть некоторая избыточность в назначении объекту nam, если он никогда не будет взят, например. Но, повторюсь, это можно менять если немного изменить конструктор.
pixman
> А значит нету дублирования имен(как для комнат, так и для объектов).
В инстеде это не дублирование, а разное назначение. Одно дело, как выглядит объект для игрока, и другое — для программиста. Писать все время «Замечательный меч кладенец».sila = 100, вместо sword.sila может быть кому-то и удобно, но не мне точно. :)
Если уж и сравнивать, то эквиваленты:
vset("меч.сила", 100) и sword.sila=100

Вот здесь уже стоит почесать репу, т.к. программист не будет писать названия диферамбами(лень заставит писать короче) + из кода убирается транслит и только-автору-ведомые сокращения на английском.
Я серьезно!
_smzap=false; -- Смотрел ли записку
_rzsv2=false; -- Разговаривал ли с Вовой 2
_rzvsl=false; -- Разговаривал ли с Леной
_smblo=false; -- Смотрел блокнот
_rzsv3=false; -- Разговаривал ли с Вовой 3

-- Инстедоз-1. Дежавю.

Если вы взглянете на любую игру то увидите что авторам названия приходится выдумывать(причем английским или транслитом):
criocabin2 = obj {
	nam = 'Криокамера';

Причем далеко не все объекты и комнаты содержат параметры, чтоб это дублирование приносило пользу.
Peter
Вы просто смотрите фрагменты кода и делаете выводы на основании каких то своих предположений.

Я же всего лишь сказал, что nam имеет другой смысл, это просто из дизайна движка следует. nam — это обычно видимая игроком информация. Например может быть много criocabinXXX, которые выглядят одинаково. Или nam вообще может быть функцией и показывать время. Или этот текст может быть на разных языках. Дублирование есть в том случае, если мы используем и disp и nam — и не собираемся работать с объектом по nam. Но это другая ситуация. Путем изменения конструктора, можно сделать nam необязательным атрибутом.

Насчет невозможности делать русские имена переменных, это может быть действительно недостатком для кого-нибудь. Но к «дублированию» это уже не относится. :)
pixman
Речь не о nam, а о существовании переменной типа room, которую приходится объявлять дополнительно.
lukyuk
Инстед прекрасен и всё в нём устроено разумно.
lukyuk
Есть direct-режим, там можно кодить без room.
Peter
А вообще, тут вопрос критериев оценки и задач движка.
CYOA можно и на markdown сделать и на каком-то примитивном простом диалекте языка, или нарисовать в редакторе визуальном… Но когда мы моделируем мир, нужен более подходящий язык. Для задач CYOA инстед избыточен. Хотя на нем самом можно написать генератор иои парсер того же markdown, в принципе.
Peter
А насчет автоматов, я не совсем понял. Берем игру на inform (или на INSTEAD) и пытаемся рисовать ее графами. Ничего хорошего из этого не выйдет (если только это не совсем примитивная игра). Из-за стремительного роста состояний. Максимум, удастся карту нарисовать. Понятно, что в теории и на брейнфаке можно все написать, но зачем?.. Графы для CYOA, а это далеко не вся ИЛ
lukyuk
Gudleifr , перелогиньтесь. :)
Gudleifr
lukyuk, не-е, давайте без меня. Коллега fireton правильно отметил основную мысль. Зачем поминать конечные автоматы, если не пользоваться ими?
Oreolek
lukyuk , первое официальное модераторское предупреждение за оффтоп. Мы обсуждаем статью, а не автора (или, тем более, других авторов). И к персональным блогам это тоже относится.
Antokolos
По поводу табличного представления: в весьма упрощенном виде оно есть на небезызвестном сайте Storymaze. У них нет переменных и (пока) только три возможных варианта выбора, но тем не менее. Удобно для редактора, основанного на веб-формах.

Лично я считаю самым полезным и наглядным всё же графовое представление, т.к. только оно позволяет взглянуть на игру с высоты птичьего полёта. Хотя это только лично мой стиль, народ ухитряется писать книги-игры в doc-файлах и даже на бумаге.

Взаимодействие объектов и составные объекты, кстати, тоже можно графически записать. Составной объект: квадратик внутри квадратика. Действие объектом A на объект B — стрелкой.
Antokolos
Вот простой примерчик
major-kolz
У меня была идея записывать сложные предметы (obj) в виде автоматов. В голове тогда держал двустволку из «Провала»: там было два состояния на патронташ (есть патроны/пустой), по два на два ствола (заряжен/пуст), по два на два курка (взведен/нет) и два для переключателя огня (верхний ствол/нижний) — итого 32 состояния, в которых может находится предмет. Конечно, некоторые из них совпадают — есть, к примеру, класс состояний «готов к выстрелу»: есть патроны-заряжен-взведен-верхний & есть патроны-заряжен-взведен-нижний & нет патронов-заряжен-взведен-верхний & нет патронов-заряжен-взведен-нижний. Можно еще выделить классы «в шаге от выстрела» (нужно либо переключится ствол, либо взвести курок), в «двух шагах» от выстрела (зарядить и взвести, либо переключить и взвести), «в трех шагах» и «бесполезно» (патроны кончились и разряжено; патронташ можно было наполнять, кстати).

Для такого сложного предмета, все равно (пусть в голове), но приходиться строить диаграмму состояний с переходами. Это выливается в «глубокий» оператор выбора (если повезет, он даже без ошибок покроет наши классы состояний), который потом копируется в обработчики inv (или dsc), use и used. Идея была в том, чтобы записать один раз все состояния, а уже в них объявить соответствующие обработчики. Вот так приблизительно оно должно было выглядить. Собственно, идею я забросил потому, что пример получился ничуть не «легче», чем записанный обычным образом.
major-kolz
Кстати, pixman , а как бы в процедурном стиле выглядел бы такой код?