Език за описание на светове

 

Ще сведем задачата за създаването на ИИ към задачата за намирането на подходящия език за описание на света. Този език няма да е език за програмиране, защото езиците за програмиране описват само изчислими функции, докато този език ще опише малко по-широк клас от функции. Друга особеност на този език ще е, че при него описанието ще може да бъде разбито на отделни модули. Това ще ни позволи да търсим описанието на света автоматично, като го откриваме модул по модул. Подходът ни за създаването на този нов език ще бъде да започнем от един конкретен свят и да напишем описанието на тази конкретен свят. Идеята ни е, че езикът, който може да опише този конкретен свят, ще е подходящ за описанието на произволен свят.

Keywords: Artificial Intelligence, Language for description of worlds, Event-Driven Model, Definition of Property, Definition of Algorithm.

1. Въведение

Тази статия представя един нов подход в изследването на ИИ. Това е Event-Driven (ED) подходът. Идеята, която стои зад ED подхода е, че моделът не трябва да поема цялата входно-изходна информация, а трябва да отрази само важните събития.

 

Всяко действие е събитие. Всяко наблюдение също е събитие. Ако моделът отразява всички действия и всички наблюдения, то той ще се претовари с прекалено много информация. Ако моделът се ограничи само до няколко „важни“ събития, тогава това претоварване ще бъде избегнато. По този начин стигаме до идеята за Event-Driven моделите.

 

Недостатък (или може би предимство) на ED модела е, че той не описва един конкретен свят, а описва клас от светове (това са световете изпълняващи определена зависимост). В тази статия ние ще използваме ED моделите, за да описваме светове. Резултата на това описание няма да е един конкретен свят, а ще бъде клас от светове (сечението на класовете получени от съответните ED модели).

 

С какво тази статия е различна. Обикновено, когато се разглежда мулти-агентна система се предполага, че светът е даден, а това което се търси е стратегия. Тоест, светът е част от известните неща в условието на задачата, а стратегията е неизвестното. В тази статия ще предполагаме, че светът не е даден, а той е това, което се търси.

 

Обикновено, когато се предполага, че светът е даден, тогава предполагаме, че ни е дадена една релация, която описва света напълно. Тук ще се опитваме да опишем света и ще го описваме частично чрез ED модели.

 

Структура на езика. Описанието на света няма да прилича на хомогенна система състояща се от един единствен пласт. По-скоро описанието на света ще има структура състояща се от много различни пластове. На фигура 1 представяме тази структура като пирамида, където първият пласт е основата на пирамидата.

 

Figure 1

Първият пласт това ще са събитията. С тях ще опишем Event-Driven моделите. С тези модели ще описваме зависимости. Важно е състоянията на ED моделите да не са еднакви. За да се различават състоянията трябва в поне едно от тях нещо специално да се случва. Това специалното нещо ще го наречем „следа“.

 

Първата ни идея за следа е това да е нещо постоянно. Например, да имаме едно състояние, където винаги е студено. Следващата ни идея е подвижната следа, тоест специалното поведение може да се появи и да изчезне или да се премести. Например, студа да се премести в съседната стая.

 

Следващите пластове в пирамидата това ще са различни видове зависимости (всички зависимости ще представяме с ED модели). Първо ще сложим постоянните зависимости. Това са зависимостите, които се наблюдават през цялото време. В повечето статии се предполага, че всички зависимости са постоянни, но тук ще предположим, че освен тях имаме зависимости, които се наблюдават от време на време. Непостоянните зависимости ще наречем „явления“. Тоест, както „следата“ може да е постоянна или подвижна, така и зависимостите могат да бъдат постоянни или „явления“.

 

Алгоритмите също са непостоянни зависимости (наблюдават се докато алгоритъма се изпълнява). Ще представим алгоритъма като последователност от събития. Обикновено алгоритмът се разглежда като последователност от действия, защото се предполага, че главният герой е този, който го изпълнява. В тази статия алгоритмите ще са някакви зависимости и ако някой от агентите действа така, че да запази зависимостта ще считаме, че агентът изпълнява алгоритъма.

 

Когато едно явление е свързано с наблюдението на обект, това явление ще го наречем „свойство“. По този начин стигаме до абстракция от по-високо ниво. Това е абстракцията за „обект“. Обектите не ги наблюдаваме директно, а ги засичаме благодарение на техните свойства.

 

Следващата абстракция, до която ще стигнем, това са агентите. Тях също не можем да ги наблюдаваме директно, но можем да ги засечем благодарение на техните действия. За да опишем света, трябва да опишем агентите, които живеят в него и да кажем какво знаем за тях. Най-важното е дали са ни приятели и дали с действията си ще се опитват да ни помогнат или да ни попречат.

 

Казаното дотук описва само изчислими светове. Неизчислим свят ще се получи, ако добавим правило зависещо от това дали съществува някакъв алгоритъм (по-точно съществува ли изпълнение на този алгоритъм).

 

Приноси.

            1. Формална дефиниция на понятието събитие. Имало е и други опити за формализацията на това понятие, но досегашните опити не са били успешни.

            2. Свят, в който състоянието знае всичко.

            3. Event-Driven модел. Това понятие вече сме го въвели в [4], но в тази статия показваме как с помощта на ED моделите може да се създаде език за описание на светове.

            4. Показваме, че Markov decision process (MDP) е частен случай на ED модел и че ED моделът е естественото обобщение на MDP.

            5. Показваме, че светът може да зависи от неизчислимо събитие. Тоест, описанието на света може да бъде описание на неизчислима функция.

            6. Свеждаме задачата за създаването на ИИ към задачата за описанието на света и създаването на език за описание на света.

            7. Дефиниция на понятието алгоритъм. Представяме алгоритъма като последователност от събития в произволен свят. Представяме машината на Тюринг като ED модел, който се намира в един специален свят, в който имаме безкрайна лента. По този начин показваме, че новата дефиниция обобщава понятието „Машина на Тюринг“ и разширява понятието алгоритъм.

            8. Дефиниция на понятието обект, като абстракция, която не може да се наблюдава директно, а чрез свойствата на обекта.

            9. Дефиниция на понятието агент, като абстракция, която не може да се наблюдава директно, а чрез действията на агента.

            10. Език за описание на светове.

 

Структура на статията. Започваме с главата „Формални дефиниции“ където дефинираме строго понятията събитие, свят и Event-Driven модел. В следващата глава се отговаря на някои интересни въпроси. Следват глави описват структурата на езика за описание на светове. Това става чрез описанието на три свята, които сме избрали като пример.

2. Формални дефиниции

За да бъде изложението строго ще започнем с теоретико-множествени дефиниции на понятията събитие, свят и Event-Driven модел.

 

Тази глава може да бъде пропусната, защото по-нататък в статията не се използва теоретико-множествената дефиниция на „свят“. Вместо това се търси приблизително описание на света. Точно описание на света не може да бъде намерено, защото има много различни светове, които са неразличими за наблюдателя, защото имат едно и също дърво на възможните действия и наблюдения. Такива светове ще наричаме еквивалентни. Светът не може да бъде определен дори и с точност до еквивалентност, защото „историята“ , с която разполагаме, не ни описва цялото дърво, а само един от неговите пътища. Ние дори не разполагаме и с цялата история, а само с нейното начало до текущия момент.

 

Няма да използваме и теоретико-множествената дефиниция на Event-Driven моделите. За тях се използва тяхната функционална дефиниция. Теоретико-множествената дефиниция на Event-Driven моделите би се получила от теоретико-множествената дефиниция на света, но ние не знаем тази дефиниция. Ние действаме на обратно, от ED моделите получаваме описание на света, а не от вече известният свят да получим ED моделите.

 

Що се отнася до събитията, и там не ни е нужна точната теоретико-множествената дефиниция, защото текстът на статията може да бъде разбран на базата на интуитивната представа за понятието събитие.

2. 1. Събитие

Събитието ще го представим чрез неговите прояви. Проявата на събитие ще дефинираме като булева функция на времето. Тоест, събитието се проявява във времето като в едни моменти се случва, а в други моменти не се случва. Самото събитие ще дефинираме като описание на всевъзможните прояви на събитието.

 

Едно събитие може да има много различни прояви. Проявите на събитието могат да зависят от „миналото“, от „бъдещето“, от случайността и от други външни фактори.

 

При описанието на събитие ще използваме само миналото, бъдещето и случайността. Няма да използваме други външни фактори, но ще допускаме интервали на несигурност. Тоест, ще допускаме неточни описания на събития като с тази неточност ще покрием възможните външни фактори. Пример за неточно описание на събитие е, когато във всеки момент събитието се случва с вероятност в интервала [0, 1] (тоест, във всеки един момент не знаем събитието дали ще се случи и дори не знаем каква е вероятността да се случи).

2. 2. Проява на събитие

Ще предполагаме безкрайно дискретно време. Тоест времето ще е изоморфно на ℕ. Нека S е крайна азбука (нищо не пречи и да е безкрайна). Нека имаме безкрайна дума от букви от S:

a₀, a₁, a₂, a₃, …

 

Тази безкрайна дума ще я наричаме история или живот. За всеки момент t историята ще я разделим на две части. Първата част (a₀, …, a_t-1) ще бъде дума с дължина t и тази част ще наречем минало. Втората част (a_t, a_t+1, a_t+2, …) ще бъде безкрайна дума започваща от момента t и тази част ще наречем бъдеще. Проява на събитие при конкретната история ще наричаме безкрайна дума (безкрайна редица) от нули и единици. Ще предполагаме, че проявата на събитието зависи от историята.

2. 3. Описание на събитие

Събитията ще ги описваме чрез характеристични функции. Характеристична функция на събитие C ще бъде такава, която взима като аргумент миналото и бъдещето и връща като стойност вероятностен интервал.

 

C : S^* ⨯ S^∞ ® [0, 1] ⨯[0, 1]

 

Забележка: От дължината на първата дума (на миналото) можем да получим кой е моментът t. Друг еквивалентен вариант за дефиниция би бил, ако аргументите на характеристичната функция бяха цялата история и момента t. Ние предпочетохме първия вариант на дефиницията, защото предполагаме, че събитието обикновено зависи само от края на миналото и от началото на бъдещето без да зависи от конкретния момент t.

 

Детерминистична характеристична функция ще наричаме такава, която връща само стойностите 0 и 1 (0 е интервалът [0, 0], а 1 е интервалът [1, 1]). Хубавото на детерминистичната характеристична функция е, че тя не зависи от случайността. Ако живеем един живот два пъти, то събитието ще се прояви по един и същи начин (във всеки момент t ще има една и същата стойност). В този случай описанието на събитието ще е съвсем точно.

 

Характеристична функция с фиксирана вероятност ще наричаме такава, която връща само интервали с дължина 0 (интервали от вида [p, p], които отговарят на фиксирана вероятност p). Тази характеристична функция зависи от случайността, но тя също дава съвсем точно описание, защото ако живеем един живот многократно, то във всеки момент t делът на случаите когато събитието се е случило ще клони към съответната вероятност p (това е според закона за големите числа).

 

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

 

Дефиниция: Ще казваме, че една характеристична функция притежава свойството „не брои от началото“, ако е изпълнено:

 

"w′ÎS^* ( C(w′w₁, w₂) Í C(w₁, w₂) )

 

„Не брои от началото“ означава, че ако добавим още минало и по този начин изместим началото назад, това няма да промени съществено събитието, а може само да го уточни (тоест, вероятностният интервал може да се свие).

 

Някои характеристични функции ще броят от началото, а други няма. Например, когато броим кой ден от седмицата е, тогава трябва да броим от началото (от сътворението на света). Когато гледаме само дали миналото завършва на някаква дума, тогава няма да броим от началото.

 

Дефинирахме събитието като характеристична функция върху континуум много безкрайни обекти. Бихме предпочели да го представим по по-прост начин. Ще въведем апроксимацията на събитие, която няма да зависи от цялата история, а ще зависи само от част от нея. Това ще е функция върху изброимо много крайни думи.

 

Дефиниция: Апроксимация C ′ на събитието C ще наричаме функция, която на част от миналото (някакъв край) и част от бъдещето (някакво начало) връща вероятностен интервал. Този интервал трябва да включва всички интервали, които биха се получили, ако се продължи историята. Освен това, това трябва да е най-малкият интервал с това свойство.

 

C ′: S^* ⨯ S^* ® [0, 1] ⨯[0, 1]

 

"w′ÎS^* "w″ÎS^∞ C(w′w₁, w₂ w″) Í C′ (w₁, w₂)

 

"C″  ("w′ÎS^* "w″ÎS^∞ C(w′w₁, w₂ w″) Í C″ (w₁, w₂) ) Þ

C′ (w₁, w₂) Í C″ (w₁, w₂)

 

 

 

Ако предположим, че събитието C „не брои от началото“, тогава има биекция между характеристичните функции и техните апроксимации. Тоест, апроксимацията на характеристичната функция напълно описва събитието. (Ако събитието „брои от началото“, тогава това пак е вярно, но в този случай ще трябва да вземем в апроксимацията цялото минало.)

 

Апроксимацията ни казва какво знаем за събитието на базата на част от историята. Границата на апроксимацията е характеристичната функция на събитието. Множеството от интересните точки на апроксимацията ще наречем база на апроксимацията.

 

Дефиниция: База на апроксимацията C ′ ще наречем множеството от двойки думи, такива ще всяко намаляване на разглежданата част от историята води до увеличаване на интервала.

 

{ <a, b> | (a=w′w₁ & b=w₂ w″ & (w′¹e ∨ w″¹e)) Þ C′ (a, b)¹C′ (w₁, w₂)}

 

За да опишем едно събитие е достатъчно да вземем базата на апроксимацията и стойностите, които дава апроксимацията върху това множество.

2. 4. Събития зависещи от събития

Трябва да отбележим, че дадената от нас формална дефиниция на събитие не покрива всички случай, които ни интересуват. Не се покрива случая на събитие зависещо от друго или от същото събитие.

 

Нека вземем като пример събитието „преход от топло към студено“. Нека на базата на миналото и на бъдещето да може със сигурност да се определи, че има такъв преход, но да не може точно да се определи в кой момент това се е случило. Нека имаме три последователни стъпки и във всяка от тях имаме вероятност 1/3 събитието да се е случило. Ако приемем, че събитието се е случило, на първата стъпка, то тогава то няма да се случи в следващите две стъпки. Ако приемем, че то не се е случило на първата стъпка, тогава ще се случи в някоя от следващите две и вероятността за всяка стъпка нараства от 1/3 на 1/2. Тоест, в този пример събитието не зависи само от случайността, от миналото и от бъдещето. То ще зависи още и от тава какви събития са се случили до момента.

2. 5. Свят

Първо ще кажем какво вижда агентът. Той вижда един поток от информация или една редица от вход и изход (наблюдения и действия). Тази редица ще бъде историята. Тя изглежда така:

 

v₀, a₁, v₁, a₂, v₂, a₃, v₃, …

 

Този поток от информация е проявлението на света, но зад това проявление се крие същността, която агентът трябва да разбере.

 

Какво представлява тази същност? Това е една функция, която генерира този поток от информация. По-точно функция, която взима като аргумент действията (изходите) и връща като стойност наблюденията (входовете).

 

v_i = f(a_i)

 

Тук описахме нещата твърде опростено, като предположихме, че функцията f няма памет и не зависи от това, което се е случило до момента. Предположихме, че функцията f зависи единствено и само от последното действие на агента. Това опростяване е прекалено и с него се губи същността на задачата. Въпреки това ние споменаваме за това възможно опростяване, защото то се използва в почти всички статии за ИИ. В литературата, когато е налице това опростяване се казва, че имаме Full Observability, а когато го нямаме се казва, че разглеждаме случая на Partial Observability.

 

Забележка: Повечето автори, когато говорят за Full Observability предполагат, че функцията f има два аргумента (действието на агента и последното наблюдение). Тоест, те предполагат, че f има някаква памет и помни последното наблюдение. Всъщност, това не е никаква памет, защото последното наблюдение се вижда в момента и не е нужно да се помни. Случая, когато се помни последното наблюдение, на практика не се различава от случая, когато няма никаква памет. И в двата случая няма нищо скрито и не се налага да използваме „въображение“, за да си „представим“ невидимата част от състоянието на света.

 

Забележка: Някои автори използват различна терминология. Например в [17] се използва термина „игра“ вместо „свят“. Също така в [17] се използва термина “Game Description Language” вместо “Language for Description of Worlds” и “Imperfect Information”вместо “Partial Observability”. Можем да разглеждаме света като игра, както и играта като отделен самостоятелен свят. Както се пее в песен на група Mystery “The World is a Game”.

 

В тази статия ние ще предполагаме, че функцията f има памет. Тоест, ще предполагаме, че разглеждаме случая на Partial Observability. Сега функцията f ще изглажда така:

 

< s_i+1, v_i > = f(s_i, a_i)

 

Тук s_i е състоянието на света. Състоянието на света е паметта на света.  Но функцията f е самият свят, което означава че s_i е паметта на функцията f. Тоест, s_i е това, което светът е запомнил в момента i.

 

Функцията f ще взима като аргумент текущото състояние на света и действието на агента и ще върне две неща (наредена двойка). Първото, което ще върне, е новото състояние на света (новата стойност на паметта), а второто е новото наблюдение.

 

Можем ли да кажем, че функцията f описва света и че тя е неговата същност? Не съвсем, трябва да добавим още и s₀. Тоест, трябва да добавим и началното състояние на света (или началната стойност на паметта). Сега вече можем да кажем, че тройката <S, s₀, f > е светът или поне, че това го описва точно. Тук S е множеството на възможните състояния на света.

 

Забележка: Ще предполагаме, че действието и наблюдението на агента са букви от крайна азбука, а състоянието на паметта е реално число. Тоест, ще предполагаме, че информацията която се приема и предава за една стъпка е ограничено количество, а паметта на света е континуум. Размерът на континуум ни е нужен, за да може в паметта на света да се запише една безкрайна редица от нули и единици (броят на тези редици е континуум).

 

По-голям размер от континуум не ни е нужен, защото всяка функция f, чиято памет е повече от континуум, може да се представи като функция с континуум памет. Нека вземем релацията на еквивалентност „неразличими състояния“ (тоест, две състояния са еквивалентни, ако няма значение от кое от двете сме тръгнали). Фактор множеството на тази релация има размер не по-голям от континуума. Можем да представим f като функция над това фактор множество вместо като функция над S. По този начин ще представим f като функция с континуум памет.

 

Всички множества с размер континуум са изоморфни помежду си. Затова можем да изберем всяко едно от тези множества. Можем да изберем най-известното от тези множества. Това е множеството на реалните числа ℝ и затова можем да предполагаме, че S=ℝ.

 

За да стане картината по-цветна и по-интересна ще допуснем, че не всички действия на агента са разрешени. Тест, ще допуснем, че в един момент са разрешени едни действия, а в друг момент са разрешени други. За целта ще предположим, че функцията f не е тотална и за някои двойки от състояние на света и действие не е дефинирана. От частичната функция f ще получим тоталната f₁ по следния начин:

 

 

Тук undef е една специална константа, която ще бъде наблюдението на агента, когато той се опита да играе некоректен ход.

 

Ще предполагаме, че историята е получена чрез функцията f₁, тоест историята съдържа некоректни действия както и наблюдението “undef”. По този начин произволни действия ще пораждат история. Ако го нямаше това предположение, тогава само коректните действия биха породили история.

 

Каква е разликата между това да предполагаме, че функцията f е тотална и да предполагаме, че не е, но сме конструирали от нея тоталната функция f₁? В първия случай f ще е произволна тотална функция, докато във втория случай f₁ ще е тотална функция, която има едно специално свойство и то е че ако играем един ход два пъти последователно и ако първия път ходът е некоректен (връща undef), тогава и втория път ще е некоректен. Ние бихме могли да разчитаме на това свойство на f₁, но може и да не разчитаме много. Например, може да проверим дали е заключена вратата и ако е заключена да не проверяваме пак, а може да проверим два пъти последователно въпреки че при първата проверка вратата е била заключена.

2. 6. Недетерминиран свят

Дефинирахме света като една детерминистична функция, но това противоречи на нашата представа, че светът е недетерминиран и че в него има случайност. Как да въведем случайността? Ще заменим конкретните състояния на света с множества от състояния. Когато знаем точно кое е състоянието на света, тогава функцията f ще е детерминирана и ще каже точно кое ще е следващото състояние на света и точно кое ще е следващото наблюдение. Може да не знаем точно кое е състоянието на света, а да го знаем приблизително. Тогава ние вместо едно конкретно състояние ще имаме множество от състояния.

 

Ще трябва да въведем и вероятност. Трябва да кажем каква е вероятността на различните подмножества на S. За целта ще добавим някакво вероятностно пространство над S, което ще означим с W.

W = < S, F, P>

 

Тук F ще е множеството от измеримите подмножества на S (тези които имат вероятност), а P ще е функция, която за всяко измеримо множество връща неговата вероятност.

 

Искаме всички подмножества на S да имат вероятност, а не само измеримите. Нека MÌ S, което не е измеримо. За M ще кажем, че неговата вероятност е в интервала [a, b]. Тук a ще бъде точната горна граница на вероятностите на всички измерими множества, които са подмножества на M, а b ще бъде точната долна граница на вероятностите на всички измерими множества, които са надмножества на M. (В литературата a се нарича inner measure, b се нарича outer measure.) По този начин за всяко множество от състояния дефинирахме вероятност или вероятностен интервал.

 

За да определим функцията f₄, която е недетерминираният вариант на функцията f са ни нужни още два варианта на f:

 

f₂(M, a, v)= { s | $s′ÎM, < s, v > = f₁(s′, a) }

 

Това е образа на M при предположение, че сме изпълнили действието a и сме видели наблюдението v.

 

f₃(M, a, v_i) = <M′, p_i> = <f₂(M, a, v_i), a.P(M_i)>

 

Функцията f₃ връща множество и вероятност. Множеството е образът на M, а p_i е вероятността следващото наблюдение да е v_i.

 

Имаме n+1 възможни резултата (n възможни наблюдения и една възможност a да е некоректен ход). Действието a разбива множеството S на n+1 непресичащи се подмножества A_i.

 

A_i = { s | $s′< s′, v_i > = f₁(s, a) }

 

От тези множества получаваме M_i=MÇA_i. Всяко едно от множествата M_i си има вероятност или вероятностен интервал и това е вероятността на резултата v_i. Тук v_i пробягва всички възможни наблюдения. Последният възможен резултат е undef. В този случай състоянието на света остава същото, тоест множеството M се ограничава до M_n+1. Тоест, следващото множество от състояния ще е M_n+1= f₂(M_n+1, a, undef)= f₂(M, a, undef).

 

Вероятността на всеки резултат е вероятността на съответното множество M_i, но тези вероятности трябва да се нормират, тоест тяхната сума трябва да е единица. Затова нормираме или преминаваме към релативна вероятност спрямо вероятността на M като умножаваме по някаква константа a. Ако вероятността на M е p, тогава релативната вероятност се получава като разделим всички вероятности на p. Ако вероятността на M е интервалът [a, b], тогава трябва да разделим всички вероятности на b.

 

От функцията f₃ лесно ще получим недетерминираната функция:

 

 f₄(M, a)

 

Тази функция връща n+1 възможни резултата от вида < f₂(M, a, v_i), v_i> и всеки от тези резултати го връща с вероятността p_i, която ни дава f₃.

 

Детерминирания свят го представихме като тройката <S, s₀, f >, а недетерминираният свят ще бъде четворката:

< S, M₀, f₄, W>

 

Тук M₀ е някакво множество от състояния на света (началното множество), а W е някакво вероятностно пространство. За W имаме много различни възможности и различните възможности ще ни дадат различни недетерминирани светове. Ще предполагаме, че S съдържа само достижимите състояния, тоест тези до които може да се достигне тръгвайки от някое от състоянията на M₀ чрез някакви действия и чрез функцията f.

 

Забележка 1: Има още един начин, по който може да се дефинира случайността в недетерминирания свят. Ние я дефинирахме чрез вероятностно пространство. Другият начин е да се вземе дървото на всички възможни истории започващи от M₀. В това дърво на четна дълбочина се разклоняваме по наблюдение, а на нечетна по действие. На всяко разклонение по наблюдение слагаме вероятности на всички ребра. Тоест, ще опишем вероятностното пространство чрез изброимо много числа (така няма да определим пространството еднозначно, но единственото, което ни интересува, са тези вероятности). Обратно, от това дърво можем да получим вероятностно пространство, което дава тези вероятности. Тоест, двете дефиниции са еквивалентни.

2. 7. Свят, в който състоянието знае всичко

Искаме да дефинираме събитията като множества от състояния. За да се случи това, състоянието трябва да може да ни каже дали събитието се случва в това състояние. За целта състоянието трябва да знае всичко. Тоест, състоянието трябва да помни цялото минало и да знае дори и бъдещето.

 

Ще направим нов модел на света, в който ще има много повече състояния (множеството S′). Отново ще вземем дървото на всички възможни истории започващи от M₀. От това дърво ще направим гора, като в корена вместо M₀ ще сложим s (тук s ще пробяга M₀). Така получените дървета ще се разклоняват само на нечетна дълбочина (по действие), а по наблюдение няма да се разклоняват. Ще вземем всички пътища в тази гора (от корен до безкрайност) и това ще са всички възможни истории започващи от M₀. (Някои от тези истории може да се повтарят, тоест една и съща история, но с различно начално състояние.) В тази гора в общия случай имаме континуум много дървета и във всяко дърво има континуум много пътища.

 

Състоянията на новия модел трябва да знаят три неща. Кое е състоянието s, от което сме тръгнали, кой е текущият момент и каква е цялата история (която се е случила до момента t и която ще се случва от t нататък).

 

S′ = { <s, t, h> | sÎM₀, tÎℕ,  h is possible history }

 

Новото начално множество ще бъде S₀′.

 

S₀′ = { <s, 0, h> | sÎM₀,  h is possible history }

 

Ще дефинираме функцията shift по следния начин:

 

shift( <s, t, h>)= <s, t+1, h>

 

С помощта на функцията shift ще дефинираме множествата S_i′.

 

S_i+1′ = shift( S_i′ )

 

Сега вече можем да представим събитията като подмножества на S′. Детерминираните събития ще бъдат подмножества, събитията с фиксирана вероятност ще бъдат размити множества (fuzzy sets), а останалите ще бъдат Interval-valued Fuzzy Sets. За да опростим изложението, оттук нататък ще предполагаме, че всички събития са детерминирани.

 

За всеки момент от времето t събитието A ще разделя S_t′ на две (състояния при които A се случва в момента t и такива при които не се случва).

 

За да довършим дефиницията на новия модел, трябва да кажем коя ще е новата функция f.

 

 

Тук h(obs, t) е наблюдението в момента t при историята h, а h(act, t) е съответното действие. Да припомним, че историята е получена чрез функцията f₁ и може да съдържа некоректни действия и наблюдението “undef”.

 

Функцията f ′ е доста проста частична функция.Тя е дефинирана точно когато съответното действие в историята е a и връща следващото състояние и наблюдението, което е в историята за момента t.

 

Новото вероятностно пространство W₀ ще бъде дефинирано само за S₀′, а не за цялото S′. С помощта на функцията shift ще пренесем това вероятностно пространство върху всички множества S_i′.

W₀ = < S₀′, F₀, P₀ >

 

Новата вероятност P₀ ще ни дава вероятността едно множество (събитие) да се случи в момента 0. Ще получим новите вероятности P_t, които ще ни дават вероятността едно събитие да се случи в момента t. В сила са следните две равенства:

 

"M′ ÍS′ P_t(M′) = P_t+1( shift(M′) )

 

"M′ ÍS′ P_t(M′) = P_t( M′Ç S_t′ )

 

Как да определим вероятността P₀, чрез вероятността P? Всяко множество M′ разделя M₀ на три части:

 

"M′ ÍS′ M_in = {sÎM₀ | "h <s, 0, h > Î M′ }

 

"M′ ÍS′ M_out = {sÎM₀ | "h <s, 0, h > Ï M′ }

 

"M′ ÍS′ M_mid = (M₀\M_in) \ M_out

 

Естествено е да предположим, че:

 

 

M_in това са състоянията, от които ако тръгнем събитието M′ ще се случи в момента 0 независимо какви са действията на агента. Аналогично M_out са състоянията, от които ако тръгнем събитието няма да се случи независимо от действията на агента. Остават в M_mid състоянията, за който има значение какви са действията на агента. Естествено е да предполагаме, че не знаем действията на агента и тогава P₀(M′ ) ще бъде следният вероятностен интервал:

 

P₀(M′ ) = [P(M_in)/P(M₀), 1–P(M_out)/P(M₀)]

 

В забележка 1 представихме света като безкрайно дърво, в което на всяко наблюдение съответстваше някаква вероятност. Нека сега и на действията да съпоставим вероятности. Ако на всяко действие съпоставим като вероятност интервала [0, 1], тогава за P₀ ще получим горната вероятност. Това е естествената вероятност, която се получава, когато не знаем какви ще са действията на агента. В [4] отбелязахме, че когато агентът търси модел, той изучава не само поведението на света, но и собственото си поведение. Агентът ще определи вероятностите P₀ на базата на събраната статистика. Естествено е събраната статистика да отрази и неговото собствено поведение. Тоест, вероятностното пространство W₀, което е получено чрез статистиката, може да бъде различно и да дава повече информация. Това означава, че ако разгледаме дървото от забележка 1, вероятностите на действията могат да бъдат и по-конкретни от интервала [0, 1].

 

Сега ще заменим функцията f ′ с друга функция, която ще е по-полезна и по-удобна. Функцията f ′ връща две неща – състояние и наблюдение. В случая наблюдението не ни е нужно, защото то се определя от състоянието. Вторият аргумент на f ′ е действие, а ние бихме искали той да бъде произволно събитие. Затова ще въведем една нова функция g, която за произволно множество от състояния M и произволно събитие A ще ни върне следващото множеството от състояния при предположение, че се е случило събитието A.

 

g(M, A) = shift( MÇA )

 

2. 8. Какво ще наричаме „въпрос“?

Всяка релация на еквивалентност над множеството S′ ще наричаме въпрос. Тоест, въпрос ще наричаме всяко разбиване на множеството S′ на класове на еквивалентност. Въпросът, който асоциираме с релацията на еквивалентност е: „В кой клас на еквивалентност попада състоянието?“

 

Релациите на еквивалентност над S′, освен въпрос, ще ги наричаме още и многозначни събития. Обикновеното събитие е двузначно, то или се случва или не се случва. Ако едно събитие е n-значно, то ще го представим като n двузначни събития, които не се пресичат (не могат да се случат едновременно).

 

Отговор на въпрос ще наричаме belief и това ще е функция, която за всеки клас на еквивалентност връща вероятностен интервал.

 

Първият въпрос (релация на еквивалентност), който ще разгледаме е: „Кое е текущото наблюдение?“ Този въпрос разбива множеството S′ на n+1 класа на еквивалентност V_i.

 

 V_i = {<s, t, h> | h(obs, t-1)=v_i }

 

По-долу ще разгледаме три модела на света. Тези модели ще са определени от три неща:

1. Събитията, които проследяваме (които моделът наблюдава).

2. Релация на еквивалентност (чиито класове на еквивалентност ще са състоянията на модела).

3. „Следата“ (това което прави състоянията различни и разпознаваеми).

 

Следва първият от тези три модела:

2. 9. Fully observable Markov decision process

При този модел на света събитията, които ще проследяваме ще бъдат действията на агента.

 

A_a = {<s, t, h> | h(act, t)=a }

 

Въпросът (релацията на еквивалентност), който ще разгледаме ще бъде „Кое е текущото наблюдение?“. Тоест, състоянията на модела ще бъдат класовете V_i. Този модел има хубава и ясна „следа“, защото всяко състояние се разпознава еднозначно по текущото наблюдение. За да завършим модела са ни нужни вероятностите за преход от състоянието i към състоянието j, когато се извършва действието a. (Тук константата a_i е добавена, за да нормират вероятностите.)

 

p_iaj = a_i.P_t+1( g( V_i , A_a) Ç V_j) = P_t+1( g( V_i , A_a) Ç V_j) / P_t( V_i ÇA_a)   (1)

 

Константите p_iaj зависят от t. Би било хубаво, ако p_iaj не зависи от t, но ако все пак зависи, тогава p_iaj няма да е число, а ще бъде интервал (между минимума и максимума по t). Когато изчисляваме този минимум и максимум, няма да взимаме тези t, за които P_t( V_i ÇA_a)=0, защото в тези моменти е невъзможно да се е случило събитието V_i (т.е. съответното наблюдение да е i) и да се е извършва действието a. (В конкретния случай е възможно всяко действие, но това го казваме, защото по-долу ще разгледаме Partially observable MDP, където ще може някои от действията да са невъзможни в някой от класовете.)

 

Така получихме модел с n+1 състояния и матрица p_iaj на вероятностите на преходите. Този модел е известен в литературата като Fully observable MDP. Изниква въпросът дали този модел изпълнява свойството на Марков, тоест дали моделът е съвършен (най-добрият възможен модел, който да не може повече да се подобри).

 

От една страна е добре моделът да изпълнява свойството на Марков, защото това означава, че сме намерили най-доброто възможно решение. От друга страна това не е добре, защото означава, че сме достигнали една граница, която не можем да преминем оттук нататък и не можем повече да подобряваме модела.

 

За всеки модел ние ще предполагаме, че той може и да изпълнява свойството на Марков, но че е по-вероятно да не го изпълнява. Тоест, ще предполагаме, че това може и да е най-добрият възможен модел, но по-вероятно е да има и по-добри модели.

 

Ако p_iaj зависи от t, тогава моделът не изпълнява свойството на Марков. Ако моделът изпълнява това свойство, тогава това ще е нещо което ние ще можем да предположим, но никога няма да можем да докажем.

2. 10. Partially observable Markov decision process

Това ще е следващият модел, който ще направим. Събитията отново ще са възможните действия, но въпросът ще бъде произволен. Тоест, ще имаме произволно разбиване на S′ на подмножества. Нека класовете на еквивалентност при това разбиване са събитията C_i. Вероятностите p_iaj отново ще се изчисляват със същата формула (1), която имахме за Fully observable MDP. Разликата е само, че сега класовете са други:

 

p_iaj = a_i.P_t+1(g( C_i , A_a) Ç C_j) = P_t+1(g( C_i , A_a) Ç C_j) / P_t( C_i ÇA_a)     (2)

 

Друга разлика е, че сега следата няма да е толкова ясна. За всяко състояние C_i имаме n+1 възможни наблюдения и всяко от тези наблюдения се случва с някаква вероятност q_ij. (Константата b_i е за нормиране на вероятностите.)

 

q_ij = b_i.P_t(C_i Ç V_j) = P_t(C_i Ç V_j) / P_t( C_i )

 

Тук, ако се ограничим със стандартната дефиниция за Partially observable MDP, тогава единствената възможна следа на модела ще са вероятностите q_ij. Ние обаче ще предположим, че може да има и други следи, т.е. други събития, които да са характерни за едно състояние C_i. Например може в това състояние определено действие да не може да се случи. Друга възможност за следа е определена конюнкция от събития да е невъзможна, макар събитията от конюнкцията поотделно да са възможни. По-интересна следа би се получила, ако състоянието не се променяше на всяка стъпка, а ако моделът стоеше известно време в едно и също състояние. Такива следи ще имаме при ED моделите.

 

Отново ще е добре, ако вероятностите p_iaj и q_ij не зависят от t, но ако зависят от t, тези вероятности ще бъдат вероятностни интервали.

 

Отново изниква въпросът дали Partially observable MDP е съвършен (дали изпълнява свойството на Марков). Имаме много различни PO MDP (за всяка релация на еквивалентност имаме такъв модел). Въпросът е има ли измежду всичките тези модели един, който да е съвършен. Отговорът е: Да има, но този модел може да е с континуум много състояния. На нас такъв модел не ни върши работа. Бихме искали модел с крайно или поне изброимо много състояния, а такъв модел може и да няма.

2. 11. Event-Driven Model

Това ще е третият модел, който ще направим и той ще е обобщение на предишните два. Сега множеството от събитията, които моделът ще проследява ще е произволно (все пак ще предполагаме, че това е малко множество, защото ако проследяваме прекалено много събития, моделът ще стане прекалено сложен). Въпросът (релацията на еквивалентност) ще е почти произволен с едно единствено ограничение. Ще искаме събитието „никое от проследените събития“ да не променя състоянията на модела. Тоест, искаме когато не се случва никое от проследените събития моделът да не променя състоянието си.

 

Забележка. Това изискване изглежда твърде ограничително, но то се изпълнява винаги когато събитието „никое от проследените събития“ е празното множество (т.е., когато то е събитието „никога“). Такъв е случаят при MDP, когато проследените събития са действията. При всеки избор на  множество от проследени събития можем да намерим въпрос (релация на еквивалентност), такъв че това изискване да е изпълнено. Как ще намерим такъв въпрос? Идеята е, че ако помним само проследените събития и нищо друго, тогава, ако никое от проследените събития не се случи, състоянието на модела няма да се промени.

 

Горната забележка показва, че споменатото изискване не е прекалено ограничително и че съществуват много ED модели.

 

Трябва да определим и какви ще са вероятностите за преход между състоянията на модела при възникване на някое от проследените събития. Тези вероятности се дават от долната формула, която е подобна на (1) и (2), но тук A е произволно събитие от множеството на проследените. Аналогично с MDP моделите вероятността на p_iAj може да не е число, а да е интервал. Също така p_iAj може да зависи от t, но бихме предпочели да не зависи.

 

p_iAj = a_i.P_t+1(g( C_i , A) Ç C_j) = P_t+1(g( C_i , A) Ç C_j) / P_t( C_i ÇA)

 

По-долу в статията са описани конкретни ED модели, но в тях не са зададени стойностите на p_iAj. Когато тази стойност не е дадена, приемете че тя е неизвестна (т.е. това е интервалът [0, 1]).

 

Трябва да кажем какво се случва, когато се случат едновременно две от проследените събития. При MDP това беше невъзможно, защото две действия не могат да се случат едновременно, но при ED моделите това е съвсем възможно. Имаме две възможни дефиниции. Можем недетерминирано да изберем едно от случващите се събития или да постъпим така сякаш двете събития са се случили последователно. Във вторият случай трябва да изберем кое събитие се е случило първо и кое второ. По този начин решаваме въпроса за случващите се едновременно събития.

 

Остана да опишем и следата на модела. Какво е това, което се случва в състоянията на модела и което отличава тези състояния. Както при PO MDP и тук няма да се ограничим само с вероятностите на наблюденията, а ще използваме всички възможни събития, като ще търсим някое, което се случва по различен начин в различните състояния. Интересното при ED моделите е, че тук състоянието не се променя на всяка стъпка. Може да имаме период от няколко стъпки, в който никое от проследените събития не се случва и моделът не променя състоянието си. Тоест, сега когато говорим за следа няма да говорим за един момент, в който нещо специално се случва, а ще говорим за цял период. Например, в един период от време може да се наблюдава определено явление (зависимост, която се наблюдава временно наричаме „явление“).

2. 12. Related work

В основата на нашия език за описание на светове ще стоят Event-Driven (ED) моделите. Тези модели приличат на крайни автомати, но в ED моделите стрелките отговарят на събития. Markov decision process е частен случай на ED модел, но при него събитията са действията на агента. ED моделите са подробно описани в [4].

 

Какво е събитие и кой въвежда понятието събитие в ИИ? Първият, който въвежда това понятие е Xi-Ren Cao. Той въвежда събитията в статията си [1] през 2005 г.

 

По-късно, през 2008, Xi-Ren Cao заедно с Junyu Zhang в статията си [2] дават дефиниция на понятието събитие. Тази дефиниция не е добра, защото зависи от модела и защото дефиницията предполага, че се помни последното състояние, в което е бил моделът, а това е нещо, което няма причина да бъде запомнено. Ето как изглежда тяхната дефиниция на събитие:

 

E Í S ⨯ S, при конкретен модел

E = {<s_i-1, s_i> | ако E се случва в момента i }

 

Защо тази дефиниция зависи от модела? Защото авторите на [2] предполагат, че светът има само един единствен модел, а това не е така. В [5] е показано, че светът има много модели. Дори в [5] е показано, че светът има минимален и максимален модел. Тук минимален и максимален е по отношение на това какво знае моделът за миналото и за бъдещето.

 

Каква трябва да бъде дефиницията?

 

E Í S, при произволен модел

E = {s_i | ако E се случва в момента i }

 

При различни модели състоянието може да „помни“ повече или по-малко от миналото. При дефиницията на Xi-Ren Cao състоянието помни последното състояние, в което е бил моделът. Както казахме, това е нещо, което няма причина да бъде запомнено. Ако решим да помним нещо, по-добре е да запомним последното действие на агента. Така ще е очевидно, че действията на агента са събития.

 

Дефиницията в [2] не е съвършена и може и трябва да се подобри, но това по никакъв начин не намалява заслугата на Xi-Ren Cao, защото той е първият, който забелязва, че не е достатъчно да наблюдаваме само действията и че трябва да обобщим до по-широк клас от събития.

 

Всъщност, действията ни казват всичко, но те ни дават прекалено много информация. Когато моделът следи всички действия, той е залят и претоварен с прекалено много информация. Обобщавайки действията до произволни събития ние ограничаваме входящата информация и можем да се ограничим до „важните“ неща.

 

Забележка: Терминът събитие се използва в много статии, но обикновено в друг смисъл. Например в [12] терминът събитие се използва в смисъл на наблюдение. Наблюдението е частен случай на събитие, но при нас събитието е по-общо понятие.

3. Интересни въпроси

3. 1. Описаната функция

Описанието на функцията f ще е го представим, чрез един клас от функции F. Описаната функция f″ ще бъде един представител на класа F (най-простата функция от F).

 

Забележка 2: Тук говорим за различни функции, а е по-правилно да говорим за различни светове. Можем да предположим, че винаги S=ℝ и че M₀ винаги е интервалът [0, 1]. За вероятностното пространство W можем да предположим, че вероятността в интервала [0, 1] е дължината (Лебеговата мярка) и че извън интервала [0, 1] вероятността е нула. Ако направим тези предположения, тогава светът ще се определя единствено от функцията f и тогава ще бъде коректно вместо за различни светове да говорим за различни функции.

 

Дефиниция: Описание на света ще наричаме множество от ED модели.

 

Забележка: Тук малко опростяваме нещата. По-долу ще видим, че в описанието на света освен ED моделите има и други неща, като обекти, агенти и други неща, но нека за момента предположим, че описанието се състои само от ED модели.

 

Всеки ED модел ни дава определена зависимост и множество от светове изпълняващи тази зависимост. Функциите на световете от това множество образуват един клас от функции.

 

Дефиниция: Класът F на описанието ще наричаме сечението на всички класове от функции съответстващи на ED моделите от описанието.

 

Ако F=Æ ще наричаме описанието противоречиво.

 

Ако описанието не е противоречиво, можем да конструираме една функция f″, такава че f″Î F. Освен това ще предполагаме, че f″ е възможно най-простата функция. Тоест, че не притежава никое свойство, което не е описано от някой от ED моделите на описанието.

 

Дефиниция: Функцията f″ ще наричаме описаната функция.

 

В тази статия няма да се занимаваме с това как може да се конструира функцията f″ от описанието на света. Ще предполагаме просто, че тази функция може да се конструира и че ние знаем как това може да стане.

 

В забележка 2 предположихме, че за функцията f е вярно S=ℝ и т.н. Тези неща няма да ги предполагаме за функцията f″. Ще предполагаме, че f″ е дефинирана в някакво изброимо множество S″ от крайни думи, които са описанията на състоянието на света написано на езика за описание на светове. Какво ще съдържа това описание? То ще казва в кое състояние е всеки от ED моделите, които участват в описанието на света. Ако това състояние не се знае точно, то ще е описано приблизително с някакъв belief. Описанието на състоянието на света ще съдържа още информация за „подвижните следи“, за обектите, за агентите и т.н.

 

Можем ли да кодираме функцията f″ и да я представим като функция над ℝ? Да можем, но няма да го правим. Това ще е едно изкуствено кодиране, което не ни е нужно.

 

Трябва да отбележим, че ако си мислим функцията f″ над ℝ тя е недетерминирана функция съответстваща на описаната по-горе функция f₄. Ако си мислим f″ над S″, то тя е детерминирана, но описанията в S″ описват множества от състояния на света и вероятностите на тези множества. Тоест, f″ над S″ е една детерминирана функция, която описва една недетерминирана функция (f″ над ℝ). Когато казваме, че f″ е детерминирана ще имаме предвид, че f″ над ℝ е детерминирана, защото f″ над S″  винаги е детерминирана.

 

Има две причини, поради които няма да търсим функцията f, а ще търсим функцията f″, която е нейно приближение.

 

1. Функцията f може да не е описуема. Тоест, може тази функция да си няма описание, което ние да намерим.

2. Функцията f може да е описуема, но да е твърде сложна и да не можем да намерим нейното описание. Затова ще търсим нейно приближение f″, което да е по-просто, макар и не съвсем точно.

3. 2. Коректност на описанието

Казахме, че описанието на света няма да описва една конкретна функция, а ще опише клас от функции. Дали описанието ще е коректно, т.е. дали функцията на света f ще е елемент на класа от функции F? Описанието зависи от много предположения. Ако всичките предположения са верни, тогава fÎF. Ако някое от предположенията е грешно, тогава fÏF.

3. 3. Съвършено описание

Дали описанието е съвършено? Тоест, можем ли да подобрим модела, като запомним още нещо, така че новият модел да дава по-добра прогноза за бъдещето. Ако моделът помни всичко важно и нищо полезно не е останало незапомнено, тогава моделът изпълнява свойството на Марков.

 

Ако f″ = f, тогава описанието е съвършено. Тук трябва да заменим равенството с еквивалентност, защото е достатъчно двете функции да са еквивалентни. Две функции ще са еквивалентни, ако пораждат едно и също дърво. (Става дума за дървото от забележка 1.) Еквивалентните функции са неразличими за наблюдателя. Тоест, ако f″≃ f, тогава описанието е съвършено.

3. 4. Изчислимост на света

Първият въпрос, който ще си зададем, когато описваме света, е дали функцията f е изчислима? Отговорът е, че тази функция вероятно е неизчислима. Вторият въпрос е дали функциите от класа F (които описват света) са изчислими? В този клас има континуум много функции и очевидно във F има неизчислими и дори и неописуеми функции. Можем да конструираме f″, която е конкретен представител на класа F. Тоест, във F има описуема функция, но дали тази функция е изчислима? Възможно ли е всички функции от F да са неизчислими? Отговорът е: Да, ако тези функции зависят от неизчислимо събитие, то те всичките са неизчислими.

 

Можем да си представим света и агента като две черни кутии, които си обменят информация. Функцията, която описва агента трябва да е изчислима, защото, ако не е изчислима, няма как да напишем програма, която да я изчислява. Тоест, няма да можем да създадем ИИ. От друга страна функцията f″ може спокойно да е неизчислима. Ние света няма да го създаваме, защото той вече е създаден и на нас ни остава задачата само да го опишем. Въпросът е можем ли да опишем неизчислима функция? Да, можем да опишем такава функция, но разбира се няма да можем да изчислим описаното.

 

Ние самите, когато си представяме света, си го представяме неизчислим. Вземете като пример правилото: „Ако съществува доказателство, тогава твърдението е вярно“. Това правило е неизчислимо, защото въпросът дали съществува доказателство е полуразрешим.

 

Какво щяхме да правим, ако трябваше да създадем света (тоест, да го емулираме с компютърна програма)? Тогава щяхме да се интересуваме не само от тава дали функцията f″ е изчислима, а дали е изчислима за разумно време. Например, в играта шах всяка позиция или е печеливша, или не е печеливша. Дали позицията е печеливша е изчислимо, но ако искаме да изчислим печеливша ли е началната позиция, тогава няма да ни стигне нашият живот, за да го изчислим (дори и животът на нашата галактика няма да е достатъчен). Това е при предположение, че използваме най-бързия компютър, с който разполагаме. Този феномен се нарича „комбинаторна експлозия“ и означава, че някои функции са на теория изчислими, но на практика не са.

 

Тоест, ние няма да се интересуваме изчислима ли е функцията f″ и доколко лесно изчислима е тя. Това означава, че езикът за описание на светове ще може да описва дори и неизчислими светове. Въпросът е, ще може ли да се описват неописуеми светове? Може ли светът да е неописуем? Да може да е неописуем, но, ако е такъв, тогава ние няма как да го опишем. Какъвто и език за описание да изберем, описанията ще са изброимо много, докато световете са много повече. Затова очевидно ще има неописуеми светове, но ние ще се ограничим с описуемите и ще предполагаме, че за всеки неописуем свят има описуем, който е достатъчно подобен на него.

3. 5. Как свеждаме задачата?

Казахме, че свеждаме задачата за създаването на ИИ до задачата за намирането на език за описание на светове. Ако имаме търсения от нас език за описание, как от този език ще направим програмата ИИ?

 

В [6] казахме, че ИИ трябва да отговори на два въпроса: „Какво става?“ и „Какво да правя?“. В тази статия няма да се занимаваме с втория въпрос, но ако сме разбрали света, то бихме могли мислено да направи няколко хода напред и с алгоритъм подобен на Min-Max да изберем най-доброто действие, което се очаква да доведе до най-доброто възможно бъдещо развитие.

 

По-голяма трудност представлява отговорът на първия въпрос. Този въпрос е свързан с разбирането на света. Тоест, намирането на функцията f, която е същността на света. Намирането на функцията f е намирането на нейното описание f″ написано на някакъв език за описание на светове. Както казахме, освен функцията f″ трябва да намерим и моментното състояние на света. За да намерим тази текуща стойност, ние отново се нуждаем от езика за описание на светове, защото този език ще ни даде и формàта на паметта (формàта на S″). Тоест, за да намерим текущата стойност на паметта ние трябва да знаем, в кой формат е записана тази стойност.

 

Ако знаем езика за описание на световете, ние ще знаем какво търсим и лесно ще направим програма, която да търси такова описание. Разбира се, няма да е лесно да направим това търсене ефективно.

 

Нужно е описанието да бъде откриваемо. За целта, то трябва да бъде разделено на отделни модули (отделни ED модели). Тези модули трябва да представляват зависимости, които могат да бъдат открити една по една. Например, ако вие се опитате да отгатнете паролата на моя имейл, това ще ви бъде трудно, защото възможните комбинации са твърде много. Ако можете да отгатвате паролата буква по буква, тогава задачата ви би била много по-проста. За първата буква има малко възможности и вие можете лесно да я отгатнете стига аз да съм достатъчно добър, за да ви казвам дали сте познали. Тоест, нужно е описанието да се разбие на отделни прости модули и всеки от тях да има по нещо специфично, което да го направи откриваем.

3. 6. Колко ще са агентите?

Във всеки свят има поне един агент и това е главният герой. Това е агентът, който получава входа от света и който със своя изход влияе на света. Във вашия свят вие сте главният герой. Вие имате модел на света и този модел описва още много други агенти. Това са хора, животни, божества, дори предмети, защото предполагаме понякога, че предметите също извършват действия. Например, колата ви се разваля. Вие може да предположите, че това е действие извършено от колата. Когато колата се движи вие не предполагате, че тя прави това по собствена воля, но кучетата така възприемат света. Кучето лае по колата, а не по шофьора. Тоест, кучето приема колата като отделен агент и не разбира, че всъщност шофьора е този, който я управлява.

 

Можете да предположите, че във вашият свят има само един агент и това сте вие. Може да предполагате, че всички останали хора не съществуват реално, а са само плод на вашето въображение. Всеки свят може да бъде представен като едно-агентен или като мулти-агентен, но мулти-агентният модел е много по-естествен и разбираем. Затова повечето от нас си мислят, че не са сами на света и че в техния свят има и други хора (агенти).

 

Конкретният свят, който ще разгледаме ще бъде играта шах и ще разгледаме два варианта на този свят. В първия вариант агентът ще е един и ще играе сам срещу себе си. При втория вариант агентите ще са двама. Главният герой ще играе с белите фигури, но ще има втори агент (противник), който ще мести черните фигури. Вторият вариант е по-интересен и по-сложен, но е и по-труден за описване.

3. 7. Защо конкретен свят?

Когато искаме да създадем нов език за програмиране, ние не го създаваме от веднъж, а първо избираме една конкретна задача и пишем програма, която да решава тази задача. После взимаме друга задача и пишем друга програма и така постепенно усъвършенстваме езика като го пригаждаме към задачите, които искаме да решим.

 

Аналогично ще постъпим, когато искаме да създадем език за описание на светове. Ще вземем един конкретен свят и ще се опитаме да го опишем на някакъв език. Този език първоначално няма да е универсален и да може да опише произволен свят, но ако успее да опише първия свят, това ще е успех. Прилагайки този език към различни светове постепенно ще го усъвършенстваме докато не се получи универсалният език, който ни трябва.

 

Първият свят, с който ще започнем, това ще е играта „шах“. По-точно това ще е свят, в който агентът играе шах. Дали агентът ще е сам в този свят или вътре в света ще има още един агент, който да е противникът му и който ще мести черните фигури?

 

Ще започнем с по-простия вариант, когато агентът (главният герой) е сам и мести и белите и черните фигури. Когато агентът играе с бяла фигура той ще смени цвета на фигурите си и следващият му ход ще бъде с черните. Така играят хора поставени в изолация, като затворници и други. Много по-интересно е да се играе с противник, но тогава светът е много по-сложен. Във втория случай светът ще стане неизчислим, защото ще имаме агент, който мести черна фигура, а това е агент, който изпълнява алгоритъм.

 

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

 

Сега ще ми кажете, че това е напълно изчислимо и че ако ви дам определен ход и позиция, вие веднага ще ми кажете дали ще сте шах след този ход. Да, това е изчислимо в случая с играта шах, защото там всичко е крайно (крайна дъска 8 x 8), но в общия случай това дали съществува алгоритъм е неизчислимо. (Дали съществува конкретно изпълнение на даден алгоритъм е неизчислимо.)

4. Шах с един играч

4. 1. Кой конкретен свят?

Ще предположим, че агентът играе шах и мести фигури по шахматното табло. Този свят е емулиран в компютърната програма [7], която е написана на езика [8].

 

Figure 2

 

В лявата част на фигура 2 се вижда потока входно-изходна информация. Това не е целият поток, а само последните 50 стъпки. На първия ред са наблюденията на агента, а на третия ред са действията му. Възможните наблюдения са четири {0, x, y, z}. Възможните действия също са четири {0, a, b, c}. За по-добра четливост нулата и символът „c“ са заменени с точка и с минус. На втория ред се вижда кои действия са позволени в конкретния момент (2 означава, че действието a е некоректно, 4 означава, че b е некоректно, 6 означава, че и a и b са некоректни).

 

Това, което е в лявата част на фигура 2, е това, което вижда агентът. Това, което е в дясната част на фигурата, агентът не го вижда, но трябва да си го представи, за да разбере света. В дясно се вижда позицията на таблото, вижда се коя фигура агентът е вдигнал (коня), вижда се и от къде я е вдигнал (жълтото квадратче), вижда се и кое е наблюдаваното в момента квадратче (ограденото с червена линия).

4. 2. Partial Observability

Ограничили сме агента да не вижда цялото табло, а да вижда само едно от квадратчетата (това, което е наблюдаваното в момента). Агентът може да мести поглед и да променя квадратчето, което вижда, като по този начин може да огледа цялото табло. Въпреки това, важно е, че предполагаме, че агентът не вижда цялото табло и че имаме Partial Observability. По този начин от агента се изисква да може да си представи тази част от света, която той не вижда в момента. Агентът ще вижда само едно от квадратчетата, а цялото шахматно табло ще бъде в неговото въображение.

 

За да има въображение, агентът трябва да има идея за текущото състояние на света (за s_i). Какво значи да има идея? Най-добре да знае точно какво е текущото състояние на света. Ако не знае точно, добре е да знае приблизително (например – няколко възможности или отговорът „не знам“). Когато агентът мести фигура и виртуалният му противник му отговаря, тогава агентът още не знае какво е местил противникът му. Той може да огледа таблото и да разбере точно какво е играл противникът. Тоест, да уточни текущото състояние на света и да избистри идеята, която има за текущото състояние.

4. 3. Използваме кодиране

Агентът ще може да извършва 8 действия. Той ще може да мести поглед (квадратчето, което наблюдава) в четирите посоки. Ще може да вдигне фигурата, която вижда и да пусне вдигната фигура в квадратчето, което вижда в момента. Седмото и осмото действие е да не прави нищо.

 

Ще ограничим действията на агента до четири букви {0, a, b, c}. Символите 0 и „c“ ще използваме да действията „не върша нищо“. Как с оставащите два символа ще опишем 6 действия? Това ще стане чрез кодиране. Ще разделим стъпките на три. На всяка първа стъпка ще казваме как движим квадратчето по хоризонтала (т.е. как движим прозореца ни на наблюдение). На всяка втора стъпка ще казваме как движим квадратчето по вертикала, а на всяка трета стъпка ще казваме дали вдигаме фигура или пускаме вдигнатата фигура.

 

В [3] споменахме, че трябва да избягваме излишното кодиране, защото светът е достатъчно сложен и няма нужда допълнително да го усложняваме. Тук обаче не става дума за излишно кодиране, защото с това кодиране светът не се усложнява, а става по-прост, защото заменяме осем действия с четири.

4. 4. Две празни действия

Защо въвеждаме две действия, които означават „не върша нищо“? Всъщност, когато агентът стои и не върши нищо, той наблюдава света. Въпросът е дали той ще е пасивен наблюдател или ще наблюдава активно?

 

Когато вие стоите и наблюдавате света, вие не сте пасивен наблюдател. Най-малкото е, че вие движите поглед.

 

Всички зависимости, които може да види пасивният наблюдател са периодични. В известен смисъл периодичните зависимости са малко и не са особено интересни. Много по-интересни са зависимостите, които може да види активния наблюдател.

 

Очакваме агентът да може да забележи определени зависимости (свойства). Например, вида и цвета на фигурите са такива свойства. Когато агентът седи в едно квадратче и не върши нищо, ще му е трудно да хване зависимостта (свойството), още повече, че може да му се наложи да хваща две или три зависимости едновременно. Ако агентът е активен и може да редува две действия, тогава зависимостите, които наблюдава ще са много по-ясни и по-бързо откриваеми.

 

За да различим двете действия „не върша нищо“, второто сме го нарекли „оглеждам“.

4. 5. Едно, две, три

Първата зависимост, която ще съществува в този конкретен свят (света на играта шах) идва от това, че разделихме стъпките на три. Тази зависимост ще наречем „Едно, две три“. Моделът на тази зависимост е изобразен на фигура 3.

 

 

Figure 3

 

Какво представлява тази зависимост? Тя брои: едно, две, три.

 

Тази зависимост се представя с един Event-Driven модел. В конкретния случай това е модел с три състояния. В този модел имаме само едно събитие и това е събитието „винаги“ (тоест, „истина“ или „на всяка стъпка“).

4. 6. Следа

Дали в състоянията на гореописания модел се случва нещо специално, което да можем да забележим и което да ни помогне да открием този модел? Тоест, има ли „следа“ (това е терминология въведена в [4]).

 

Да, в третото състояние задължително едно от действията a или b е некоректно (или и двете). Това е така, защото в третото състояние ние казваме дали вдигаме фигурата, която виждаме или пускаме вдигната вече фигура. Няма как тези две действия да са възможни едновременно.

 

Можем и без тази следа да опишем света, но без нея зависимостта „Едно, две три“ би била много по-трудно откриваема. Затова е добре, че имаме някаква следа в този модел.

 

Следата е това специалното, което дава смисъла на модела. Например, в хладилника има студена бира и това прави хладилника един по-специален шкаф. Ако във всички шкафове имаше студена бира, тогава хладилника нямаше да е по-специален и щеше да е все едно кой шкаф ще отворим.

 

Следата ни дава възможност да предскажем какво ще се случи. Ако отворим хладилника, очакваме вътре да има студена бира. Освен това, следата ни помага да познаем в кое състояние сме и да ограничим недетерминираността. Например, отваряме бял шкаф, но не знаем дали това е хладилника или друг бял шкаф. Ако вътре има студена бира, тогава ще разберем, че сме отворили хладилника и по този начин ще ограничим недетерминираността.

 

Ще разглеждаме два вида следа – постоянна и подвижна. Постоянна следа ще са специалните неща (явления), които всеки път се случват, а подвижна следа ще са нещата, които се случват временно.

 

Например, да си представим една къща като един Event-Driven модел. Състоянията на този модел ще са стаите. Нещо постоянно за стаите ще е броят на вратите. Временни явления, които се явяват и изчезват са „светла“ и „топла“. Тоест, постоянната следа може да ни каже коя стая е преходна, а подвижната следа ще ни каже, коя стая в момента е топла.

 

Стаите могат да са свързани с различни обекти. Тези обекти си имат свойства (явленията, които се наблюдават, когато наблюдаваме съответния обект). Обектите могат да са постоянни или подвижни и съответно техните свойства ще са постоянни или временни явления. Пример за постоянни обекти са мебелите (особено по-тежките). Пример за подвижни обекти са хората и животните. Тоест, постоянната следа ще описва това което е постоянно, а подвижната следа ще описва това, което е временно.

 

Постоянната следа ще предполагаме, че е вградени в дефиницията на функцията f″, а подвижната следа ще предполагаме, че се описва от състоянието на света. Все пак, когато подобряваме функцията f″ и променяме представата си за света, ще предполагаме, че част от постоянната следа може да стане подвижна. Например, „Колко врати има стаята?“ е нещо постоянно, докато някой ентусиаст не пробие още една врата.

4. 7. Horizontal и Vertical

Следващият Event-Driven модел, който ще ни е нужен за описанието на света е моделът „Horizontal“ (фигура 4).

 

Figure 4

 

Този модел ще ни даде отговор на въпроса, в коя колона на шахматната дъска се намира квадратчето, което наблюдаваме.

 

Тук имаме две събития и това са събитията „наляво“ и „надясно“. Тоест, агентът мести поглед наляво или надясно. Тоест, той извършва действията a и b, когато моделът 1 е в състоянието 1. Имаме и две следи. В състоянието 1 не може да се играе наляво. Тоест, когато сме в състояние 1 събитието „наляво“ не може да се случи. Аналогично, е със състоянието 8 и следата, че там не може да се играе надясно. Тези две следи ще направят моделът откриваем. Например вие, ако сте в тъмна стая широка 7 стъпки, ще установите, че след седем стъпки наляво по-наляво не може. Ще го установите, защото ще се блъснете в стената. Тоест, сблъсъка със стената е следата в случая. Такъв сблъсък ще има само на първата и на последната позиция.

 

Тази следа, освен че ще ни помогне да открием модела, тя ще е полезна още за да ни обясни света. Как иначе бихте си обяснили защо в най-лявата колона не можете да играете „наляво“?

 

Съвсем аналогичен на модела „Horizontal“ е моделът „Vertical“ (фигура 5).

 

Figure 5

 

Този модел ще ни каже в кой ред се намира квадратчето, което наблюдаваме. Аналогично имаме две събития („напред“ и „назад“), както и две следи („не може напред“ и „не може назад“)

 

Логично е да направим декартовото произведение на горните два модела и да получим модел с 64 състояния, който ще отговаря на шахматното табло.

 

Лошото е, че в това декартово произведение няма постоянна следа. Тоест, нищо специално не се случва в някое от квадратчетата. Случват се разни работи, но те не са постоянни, а временни. Например, в едно квадратче може да виждаме бяла пешка и това да е сравнително постоянно, но не е напълно постоянно, защото пешката може да се премести.

 

Стигаме до извода, че следата може и да не е постоянна.

4. 8. Подвижна следа

Както казахме, „подвижна следа“ ще са специалните неща, които се случват в едно състояние, но не се случват постоянно, а само временно.

 

Как да изобразим подвижната следа? Постоянната следа изобразявахме, като отбелязвахме върху състоянието дали някакво събитие винаги се случва в това състояние (винаги отбелязваме с червено, а със синьо отбелязваме, когато никога не се случва).

 

Подвижната следа ще изобразим като масив, който има толкова клетки, колкото състояния има съответния модел. Във всяка клетка ще запишем подвижните следи, които в момента са в съответното състояние. Тоест, масивът на подвижната следа ще мени стойностите си.

 

Ето как ще изглежда масива на подвижната следа на декартовото произведение на втория и третия модел:

 

Figure 6

 

Тази подвижна следа е много сложна, защото това е подвижната следа на модел с 64 състояния. Нека да вземем подвижната следа на модел с две състояния (фигура 7). Това е моделът 4, който помни дали сме вдигнали фигура. Неговата подвижна следа ще помни коя е вдигнатата фигура. Разбира се, този модел освен подвижна следа си има и постоянна, която казва, че в състоянието 2 не може „нагоре“, докато в състоянието 1 не може „надолу“.

 

Подвижната следа на този модел представлява масив с две клетки, които съответстват на двете състояния на ED модела. Клетката, която съответства на текущото състояние е отбелязана, като е оградена с червена линия. Не е толкова важно какво има в клетката съответстваща на текущото състояние, а това което е в другите клетки, защото те ни казват какво ще се случи, когато някоя от другите клетки стане текуща. В случая, ако пуснем вдигната фигура ще отидем в състоянието 1 и там ще видим вдигната фигура. (Ще видим това, което сме пуснали. В случая ще видим „бял кон“.)

 

Figure 7

Казахме, че езикът за описание на светове ще ни каже как изглежда паметта на функцията f. Къде се записва вътрешното състояние на света? Записва се на две места. Първо, това е текущото състояние на всеки от моделите и второ, това е подвижната следа. Например на фигура 6 виждате как чрез подвижната следа се представя позицията на шахматната дъска.

 

Ако езика за описание на светове беше стандартен език за програмиране, неговата памет щеше да е стойността на променливите и на масивите. Тук можем да направим аналогията, че текущото състояние на един ED модел е стойността на една променлива, а стойността на една подвижна следа е стойността на един масив.

 

Стойността на текущото състояние на един ED модел обикновено е едно число, ако моделът е детерминиран, но може да е няколко числа, ако ED моделът има няколко текущи състояния (стойността може да е belief , ако различните състояния си имат различна вероятност). Стойността на всяка от клетките на подвижната следа ще се състои от няколко числа, защото в едно състояние може да има много подвижни следи. Разбира се, постоянните следи също може да са повече от една.

5. Алгоритми

След като описахме основните правила на играта шах и позицията на таблото, следващата стъпка е да кажем как се движат фигурите. За целта ни е нужно понятието алгоритъм.

 

За повечето хора алгоритмът това е машина на Тюринг. Това е така, защото те разглеждат само функциите от ℕ в ℕ и за тях алгоритъм е нещо което изчислява такава функция. За нас алгоритмът ще описва последователност от действия в произволен свят. Например за нас алгоритми ще са готварските рецепти, танцовите стъпки, умението да се хване топка и т.н. Казахме последователност от действия. Нека се коригираме и да стане последователност от събития. Действието е събитие, но не всяко събитие е действие или поне не е наше действие, а може да е действие на някой друг агент. В описанието на алгоритъма освен наши действия ще има и други събития. Например, чакаме докато водата кипне. Кипването на водата е събитие, което не е наше действие.

 

При нашата дефиниция алгоритмът може да се осъществи въобще без нашето участие. Да вземем като пример Лунната соната. Това е алгоритъм, който ще изпълним, ако изсвирим Лунната соната, но ако я изсвири някой друг, тогава това пак ще е алгоритъм, но изпълнен от някой друг. Ако разпознаем Лунната соната, ние ще сме разпознали този алгоритъм, нищо че не го изпълняваме.

 

Няма да е много важно кой изпълнява алгоритъма. Нормално е един алгоритъм първо да ни го покаже някой друг, после да го изпълним и ние.

 

Ще разгледаме три варианта на алгоритъм:

1. Релсов път.

2. Планинска пътека.

3. Отивам си вкъщи.

 

При първия вариант ще предполагаме, че имаме ограничения, които не ни позволяват да се отклоним от изпълнението на алгоритъма. Например, когато се качим на рейса, ние пътуваме по маршрута и не можем да се отклоним, защото друг кара рейса. Когато слушаме Лунната соната, отново нищо не можем да променим, защото не свирим ние.

 

При втория вариант ние можем да се отклоним, но има последствия, ако се отклоним. Планинската пътека минава покрай пропаст. Ако се отклоним, ще паднем в пропастта.

При третия вариант можем да се отклоним от пътя. След отклонението можем отново да се върнем в пътя, а може и да минем по друг път. Алгоритъма за прибиране у дома ни казва, че ако го изпълним, ще сме си вкъщи, но по никакъв начин не сме задължени да го изпълним или да го изпълним точно по този начин.

 

Обикновено, когато говорим за алгоритъм предполагаме детерминираност. Представяме си компютърна програма, при която за всеки следващ момент се знае точно кое ще е действието, което ще бъде извършено. Вече дори и компютърните програми не са еднонишкови. При многонишковите програми не е съвсем ясно кое ще е следващото действие, което ще бъде извършено. Още по-ясен е примерът с готварските рецепти. Когато правим палачинки, не е казано дали първо да сложим яйцата и после млякото или обратното. И в двата случая ще изпълним един и същ алгоритъм.

 

Представете си алгоритъма като движение в пещера. Можете да вървите напред, но можете да се върнете и назад. Галерията има разклонения и вие имате избор на къде да завиете. Само, ако излезете от пещерата, ще сте прекратил изпълнението на алгоритъма „движа се в пещерата“. Тоест, ще си представяме алгоритъма като ориентиран граф с много разклонения, а не като път без разклонения.

5. 1. Алгоритъма на фигурите

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

 

Можеше да изберем и варианта „планинска пътека“. Тоест, да може да се отклоните от алгоритъма, но това да е с последствия. Например, вдигате фигурата и започвате да изпълнявате алгоритъма, но ако го нарушите, ще изпуснете вдигната фигура и тя ще се върне на мястото си.

 

Можеше да изберем и варианта „отивам си вкъщи“. При този вариант се движите както пожелаете, но можете да поставите фигурата само на тези места, където алгоритмът би могъл да я поставил, ако беше изпълнен. Тоест, имате пълна свобода на движението, а алгоритмът само ви дефинира кои ходове са коректните.

 

Ще изберем първият вариант главно защото сме пуснали агента да играе случайно и ако не го вкараме в релси, за него ще е много трудно да изиграе коректен ход. Освен това трябва да си помислим за това как агентът ще разбере света. Как ще ги открие тези алгоритми? Ако го вкараме в релси, той ще научи алгоритъма по неволя, но ако го оставим свободно да се движи за него ще е много трудно да отгатне какви са тези правила на движение (какви са тези алгоритми). Например, ако покажете на един ученик алгоритъма за намиране на корен квадратен, то на него ще му е сравнително лесно да го научи. Много по-трудно би му било, ако му обясните какво е корен квадратен го оставите сам да намери алгоритъма за изчисляването му. Можете да покажете на ученика какво е корен квадратен с дефиниция или с примери, но по-лесно ще ви разбере, ако му покажете директно алгоритъма.

 

Какво ще представляват алгоритмите? Това ще са Event-Driven модели. Ще има някакво събитие, което ще е вход и което ще стартира алгоритъма и още някакво събитие, което ще е изход и след което алгоритъма ще престане да се изпълнява. По-нататък ще направим изходите да са два (успешен и неуспешен изход).

 

Всяка фигура ще си има алгоритъм:

5. 2. Алгоритмите на царя и на коня

Най-простият алгоритъм ще бъде алгоритъма на царя (фигура 8). Входящото събитие ще бъде вдигам фигурата цар. Входящата точка ще бъде състоянието 1 (при всичките алгоритми това ще бъде входящата точка). Събитията ще са 4 (наляво, надясно, напред и назад).

 

 

Figure 8

Следата ще се състои от четири събития (не може наляво, не може надясно и т.н.) Тези четири събития (следи) ще ограничат движението до девет квадратчета. Тези 4 събития (следи) ще са релсите, в които ще влезем и които няма да ни позволят да напуснем деветте квадратчета докато изпълняваме алгоритъма. На фигура 8 четирите следи са отбелязани с червени хоризонтални линии. Например, горните три състояния имат първата следа, което значи, че от тези три състояния не може напред.

 

Ще можем да пуснем вдигната фигура (царят) във всеки момент, когато пожелаем. Разбра се, може да има други правила или алгоритми, които да ни ограничават. Например, не можем да вземем собствена фигура, тоест има и други ограничения, но те не идват от този алгоритъм. Ако пуснем фигурата в състоянието 1, тогава ходът ни няма да е истински, а ще е фалшив. Ако пуснем фигурата в някое от другите състояния, тогава ще сме изиграли един истински ход.

 

Малко по-сложен е алгоритмът на коня (фигура 9). Основната разлика с алгоритъма на царя е, че тук има още една следа. Тази следа ни ограничава и в някои от състоянията няма да можем да спускаме вдигната фигура. (Тази следа е отбелязана на фигура 9, а другите 4 следи не са отбелязани.) Спазвайки този алгоритъм ние имаме само две възможности. Първата е да изиграем коректен ход с коня, а втората е да изиграем фалшив ход като върнем коня там откъдето сме го взели.

 

Figure 9

5. 3. Алгоритмите на топа и на офицера

Макар че има малко състояния алгоритмът на топа е по-сложен (фигура 10). Причината за това е, че този алгоритъм е недетерминиран. Например в състоянието 3 когато играем „напред“, тогава има две стрелки които отговарят на това събитие. Съответно има две състояния, които могат да са следващите. Тази недетерминираност веднага се разрешава, защото в състоянието 1 задължително трябва да се вижда, че от това квадратче е вдигната фигура, докато в състоянието 3 задължително това не трябва да се вижда. Тоест, имаме следа която веднага разрешава тази недетерминираност.

 

Figure 10

Алгоритмът на офицера е още по сложен (фигура 11). Основната причина за това е, че не можем да се придвижим директно по диагонала, а за целта трябва да направим две стъпки (първата по хоризонтала и втората по вертикала). Когато в състоянието 1 се случи събитието „наляво“, тогава ние не знаем дали сме тръгнали по диагонала „наляво и напред“ или по диагонала „наляво и назад“. Тогава се получава недетерминираност, която не може да бъде разрешена незабавно. Все пак, тази недетерминираност ще се разреши когато дойде едно от събитията „нанапред“ или „назад“. В двете възможни състояния имаме следи, които ни казват, че в състояние 8 не може „напред“, а в състояние 2 не може „назад“. Ако и в двете състояния не можеше „напред“, то тогава събитието „напред“ би нарушило алгоритъма. В случая, в едното състояние може, а в другото не може. Тоест, събитието „напред“ е разрешено, но когато то се случи състоянието 8 ще престане да бъде активно и недетерминираността ще се разреши. (На фигура 11 сме отбелязали само следите „не може напред“ и „не може назад“.)

 

Figure 11

 

Най-сложен е алгоритмът на царицата, защото той е съчетание от алгоритмите на топа и на офицера. Алгоритмът на пешката не е сложен, но имаме четири такива алгоритъма, защото имаме различни алгоритми за бяла и за черна пешка, като и за преместена и за непреместена пешка.

5. 4. Машината на Тюринг

Описахме алгоритмите на движение на шахматните фигури като Event-Driven модели. Можем ли да приемем, че всеки алгоритъм може да се представи като Event-Driven модел? Дали машината на Тюринг може да се представи по този начин?

 

Ще опишем един свят, който представлява машина на Тюринг. Първото нещо, което трябва да опишем в този свят е безкрайната лента. В играта шах описахме шахматното табло като подвижната следа на някакъв Event-Driven модел с 64 състояния. Тук отново ще използваме подвижната следа, но ще ни е нужен модел с изброимо много състояния. Да вземем модела от фигура 4. Това е модел на лента с осем клетки. Трябва ни същият модел, пак да има две събития (наляво и надясно), но да не е ограничен отляво и отдясно. Получава се Event-Driven модел с безкрайно много състояния. Досега използвахме ED модели само с крайно много състояния. Сега ще ни се наложи да добавим и някои безкрайни ED модели, но които имат проста структура като този. В случая моделът представлява просто един брояч, който помни едно цяло число (т.е. елемент на ℤ). Броячът има две операции (минус едно и плюс едно) или (наляво и надясно). Добавянето на този безкраен брояч разширява езика, но както казахме ние ще разширяваме езика, за да покрием световете, които искаме да опишем.

 

Каква ще е паметта на този свят? Трябва да запомним стойността на брояча (коя клетка от лентата гледа главата на машината). Това е произволно цяло число. Освен това ще трябва да запомним и какво има записано върху лентата. За целта ще ни трябва безкрайна последователност от нули и единици, което е равномощно на континуум. Обикновено използваме Машините на Тюринг, за да изчисляваме функции от ℕ в ℕ. В този случай бихме могли да се ограничим само с конфигурации, при които е използвана само крайна част от лентата, тоест бихме могли да се ограничим само с изброимо много конфигурации, но всички възможни конфигурации на лентата са континуум много.

 

Забележка: Представата на агента за състоянието на света ще е изброима дори ако паметта на света е континуум. Казано по друг начин, агентът няма как да си представи всички възможни конфигурации върху лентата, а само изброима част от тези конфигурации. При горното разсъждение използваме това, че си мислим агента като абстрактна машина с безкрайна памет. Ако агента си го мислим като реален компютър с крайна памет, тогова в горното разсъждение трябва да заменим „изброима“ с „крайна“. Все пак, ако агентът е програма на реален компютър, то тази крайна памет е толкова голяма, че за по-просто ще си я мислим за изброима.

 

Описахме безкрайната лента на машината на Тюринг с един безкраен ED модел. За да опишем главата на машината (самия алгоритъм) ще ни трябва още един ED модел. Втория ED модел ще го построим използвайки машината на Тюринг.

 

Предположихме, че машината използва две букви {0, 1}. Ще направим Event-Driven модел с четири събития:

write(0),

write(1),

move left,

move right.

 

Тогава всяка от командите на машината ще изглежда така:

 

if observe(0) then write Symbol_0, move Direction_0, goto Command_0

if observe(1) then write Symbol_1, move Direction_1, goto Command_1

 

Тук Symbol_i, Direction_i и Command_i са заменени с конкретни стойности. Например:

if observe(0) then write(1), move left, goto s₃

if observe(1) then write(0), move right, goto s₇

 

Всяка команда ще заменим с четири състояния, които ще я опишат. Горната команда ще изглежда така:

Figure 12

На фигура 12 входа е по събитието „move right“. Всъщност, ще се влиза от много места, понякога по събитието „move left“, а понякога по събитието „move right“. Важното е, че входът ще е недетерминиран, но веднага тази недетерминираност ще се разреши, защото първите две състояния имат следа. В горното задължително трябва да се случи събитието „observe(0)“, а в долното задължително това събитие не трябва да се случва.

 

Тоест, всяко от състоянията на автомата се заменя с четири състояния, както е показано на фигура 12, след това отделните четворки се свързват помежду си. Например, четворката от фигура 12 се свързва с четворката съответстваща на s₃ чрез стрелки по събитието „move left“ и с четворката съответстваща на s₇ чрез стрелки по събитието „move right“.

 

Трябва да добавим още малко следа. За всяко едно от състоянията е възможно само едно от четирите събития. Трябва да добавим като следа, че другите три събития са невъзможни. Това е, ако искаме алгоритмът да е от тип „релсов път“. Ако предпочитаме да е от тип „планинска пътека“ трябва добавим следа, която да казва че ако се случи някое от другите три събития, ще настъпят съответните последствия. Ако искаме типът да е „отивам си вкъщи“, тогава другите три събития трябва да водят до прекратяване на алгоритъма.

 

По този начин представихме машината на Тюринг с Event-Driven модел. По-точно с два ED модела, първия с безкрайно много състояния и втория с краен брой (четири пъти повече от състоянията на машината).

 

Кой изпълнява алгоритъма на машината на Тюринг? Може да предположим, че четирите събития са действия на агента и че той е този, който изпълнява алгоритъма. Може да предположим, че тези събития ги изпълнява друг агент или че те просто се случват. Тогава агента не изпълнява алгоритъма, а е само наблюдател. В общият случай, една част от събитията на алгоритъма ще са действия на агента, а останалата част няма да са. Например, „сипвам вода“ е действие на агента, а „водата завира“ не е негово действие. Агентът може да влияе и на събитията, които не са негови действия. Това е описано в [6]. Спрямо тези събития той може да има някакво „предпочитание“ и чрез това „предпочитание“ той би могъл на влияе на това дали тези събития ще се случат.

5. 5. Related work

Важно е, че в тази статия е дефинирано понятието алгоритъм. Много малко са хората, които въобще си задават въпроса какво е алгоритъм. Единствените опити за дефиниция на алгоритъм, които са ми известни са направени от Moschovakis [14, 15]. В тези трудове Moschovakis казва, че повечето автори дефинират алгоритъма чрез някаква абстрактна машина и отъждествяват алгоритмите с програмите за тази абстрактна машина. Moschovakis формулира каква дефиниция на алгоритъм на нас ни е необходима. Той иска да създаде едно общо понятие, което да не зависи от конкретната абстрактна машина. Такова понятие е изчислимата функция, но това понятие е твърде общо за Moschovakis и той иска да направи по-специализирано понятие, което да отразява това, че една изчислима функция може да се изчисли от много принципно различни алгоритми. В [14] не е постигната високата цел поставена от Moschovakis. Това, което той е направил може да се приеме за една нова абстрактна машина. Наистина тази машина е много интересна и е по-абстрактна от повечето известни машини, но отново имаме недостатъка, че програмата на машината може безсмислено да се усложни като се получи друга програма реализираща същия алгоритъм. Макар, че в [14] не се постига целта да бъде създадена обща дефиниция на алгоритъм, самият Moschovakis казва, че за него по-важното е да постави въпроса, дори и да не успее да му отговори. Точните думи на Moschovakis са: „my chief goal is to convince the reader that the problem of founding the theory of algorithms is important, and that it is ripe for solution.“

6. Обекти

6. 1. Свойства

След понятието алгоритъм ще се опитаме да дефинираме още едно фундаментално понятие. Това ще е понятието свойство. За дефиницията на това понятие отново ще използваме Event-Driven модели. Свойствата са явленията, които се наблюдават когато се наблюдава обект със съответното свойство. Явленията са зависимости, които не се наблюдават постоянно, а само от време на време. Щом другите зависимости се представят с Event-Driven модели, естествено е и свойствата да се представят по същия начин.

 

Разликата между зависимост и свойство ще бъде, че зависимостта ще е активна постоянно (т.е. ще се наблюдава постоянно) докато свойството ще се наблюдава понякога (когато наблюдаваме съответния обект).

6. 2. Какво е обект

Базовото понятие ще е свойство, а обектът ще е абстракция от по-висок ранг. Например, ако в света на играта шах се наблюдават свойствата „бял“ и „кон“, може да се направи извода, че има обект „бял кон“, който се наблюдава и който има тези две свойства. Може и да не стигаме до тази абстракция и да си мислим, че просто някакви свойства се местят. Тоест, че някакви явления се появяват и изчезват.

6. 3. Второ кодиране

Изходът на агента се състои само от четири букви и затова използвахме кодиране за да представим осемте възможни действия на агента. Входът също е ограничен до четири букви. Вярно е, че входът трябва да ни даде информация само за едно от квадратчетата, а не за цялото табло. Въпреки това четири букви са твърде малко, защото в квадратчето може да има шест различни фигури с два различни цвята. Освен това, трябва ни допълнителна информация като това дали пешката е местена и дали от този квадрат не е вдигнатата фигура. Как да представим всичката тази информация с четири букви?

 

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

 

Тези зависимости ще наречем свойства и ще предполагаме, че агента може да разпознава (да хваща) тези зависимости. Ще предполагаме още, че той може да хване няколко зависимости, дори когато те са една върху друга. Например, агентът трябва да може да хване свойствата „бял“ и „кон“ дори когато те се проявяват едновременно.

 

Как изглеждат свойствата? Зависимостите и алгоритмите за движение на фигурите са написани от човек, който има идея какви са правилата на играта шах и как се движат фигурите. Свойствата не са написани от човек, а са генерирани автоматично. Например на фигура 13 е изобразено свойството „пешка“. Това свойство изглежда доста странно и нелогично. Това е така, защото, както казахме, то е генерирано автоматично по случаен начин. Това свойство не е написано от нас, защото ние не знаем как би изглеждала пешката. Не е важно как изглежда тя. Важното е пешката да изглежда по някакъв начин и да може тя да бъде разпозната от агента. Тоест, пешката трябва да си има лице, но не е важно как ще изглежда нейното лице.

 

Figure 13

В нашата програма [7] има 10 свойства и всяко едно от тях си има някаква следа. Когато няколко свойства са активни едновременно, тогава всяко едно от тях влияе (чрез следата си) на входа на агента. Понякога тези влияния могат да бъдат противоречиви. Например, едно свойство ни казва, че следващият вход трябва да е буквата x, а друго свойство ни казва обратното (че не трябва да е x). Тогава въпросът се решава с гласуване. Светът брои колко гласа има за всяко решение и избира решението, което е събрало най-много гласове. Що се отнася до противоречивите препоръки, те взаимно се обезсилват.

6. 4. Детерминиран свят

Описахме света на играта шах където агентът играе сам срещу себе си. Описанието се състои от 24 модула (Event-Driven модели), два масива (подвижни следи) и още 7 допълнителни правила. Тези правила ни дават допълнителна информация за това как се променя състоянието на света. Например, първото от тези правила ни казва, че ако вдигнем фигура, на нейното място ще се появи свойството „Lifted“. Тези правила ние можем да формулираме благодарение на това, че вече имаме контекста на шахматната дъска (подвижната следа от фигура 6). Ако не знаехме за съществуването на тази дъска, нямаше как да формулираме правила за поведението на фигурите върху дъската. Написахме компютърна програма [7], която емулира този свят. В тази демонстрационна програма агентът играе случайно (random). Разбира се, действията на агента не са интересни. Интересното е, че ние сме описали функцията f″. Тоест, описали сме света.

 

Описанието, което получихме, е детерминирано. Тоест, началния отговор е детерминиран и функцията f″ също е детерминирана. Детерминирано описанието означава, че в описания свят няма случайност. Трябва ли описанието на света да е детерминирано? Да се ограничим ли само с такива описания? Въобще не е сигурно, че светът е детерминиран, а дори и да е такъв, не е нужно да се ограничаваме само с детерминирани описания.

 

Ако опишем недетерминиран свят с детерминистично описание, то много скоро това описание ще покаже своето несъвършенство. Обратното, света може да е детерминиран, но тази детерминираност да е твърде сложна и да не можем да я разберем (да я опишем). Затова може вместо детерминистично описание на света да намерим едно недетерминистично, което да работи достатъчно добре.

 

Обикновено светът е недетерминиран. Когато стреляме по мишена може да не уцелим. Това означава, че не всяко наше действие води до резултат и че резултатите понякога могат да бъдат различни.

 

Ще допускаме, че функцията f може да е недетерминирана. Повечето автори, когато говорят за недетерминираност, предполагат, че всяка възможна стойност на функцията има точно определена вероятност. В [4] и в [6] показахме, че това последното е твърде детерминирано. Би било твърде силно изискването за всяко събитие да можем да кажем точната вероятност, с която то ще се случи. Затова ще предполагаме, че не знаем точната вероятност, а знаем само интервала [a, b], в който е тази вероятност. Обикновено интервалът ще е [0, 1] и тогава няма да имаме никаква идея с каква вероятност ще се случи събитието.

7. Шах с двама играчи

Ще усложним света на играта шах, като добавим още един агент. Това ще е противникът, който играе с черните фигури. Това ще доведе до недетерминираност, защото няма да можем да кажем точно как ще играе противникът. Дори противникът да е детерминиран, тази детерминираност може да е прекалено сложна и да не можем да я опишем. Затова ще опишем света с една недетерминистична функция f″.

7. 1. Невъзможни събития

Казахме, че светът би бил по-интересен, ако не играем сами срещу себе си, а ако има още един агент, който да мести черните фигури.

 

За целта ще променим петия Event-Driven модел (този, който ни казва дали играем с белите или с черните фигури). Този модел има две състояния, които се превключват от събитието „change“. Това събитие е дефинирано като събитието „real_move“ (това е когато играем реален ход, а „fake_move“ е когато само докосваме някоя фигура). Ще променим дефиницията на това събитие и ще го дефинираме като „never“ (това е обратното на „every time“).

 

Има ли смисъл в модела да описваме събития, които няма как да се случат? Отговорът е, че има смисъл, защото тези събития може да се случват мислено. Тоест, тези събития са ни нужни за да разберем света, макар, че те не се случват. Например, ние не можем да летим и да си сменим пола, но мислено можем да го направим. Примерът не е много добър, защото ние вече можем да летим и да си сменим пола. Тоест, ние може да си мислим за невъзможни събития, освен това в един момент тези събития може от невъзможни да станат възможни.

 

Ще използваме невъзможното събитие „change“, за да добавим правилото, че нямаме право да играем ход, след който ще сме шах (след който могат да ни вземат царя). На фигура 14 е изобразен алгоритмът, който описва как сменяме (обръщаме дъската) и взимаме царя. Ако този алгоритъм е възможен, тогава ходът не е коректен.

 

Figure 14

Този алгоритъм в по-голяма степен отговаря на представата ни за това как изглеждат алгоритмите. Докато алгоритмите на фигурите представляваха ориентирани графи с много разклонения, този алгоритъм представлява само един път без разклонения. Тоест, този алгоритъм е просто една последователност от действия без разклонения.

 

Този алгоритъм се нуждае още от някои ограничения (следи), които не сме отбелязали на фигура 14. Например, в състоянието 1 не можем да се движим в никоя от четирите посоки (иначе бихме могли да се преместим и да изиграем друг ход). Събитието „change“ не може да се случва в никое от състоянията освен състоянието 2. В състоянието 4 имаме ограничението „not observe(King) => not down“. Това последното означава, че единственият ход, който можем да направим, е да вземем цар.

 

В този алгоритъм участва невъзможното действие „change“. Както казахме, това действие е невъзможно, но можем да го извършим мислено. Това събитие може да участва в дефиницията на алгоритми, които няма да изпълняваме, а за които ще е важно само дали съществува изпълнение.

 

Забележка: В тази статия, когато казваме, че алгоритъм може да бъде изпълнен, имаме предвид, че той може да бъде изпълнен успешно. Това означава, че изпълнението може да завърши в крайно (приемащо) състояние или с изходящо събитие (с успешен изход).

7. 2. Втори агент

Алгоритмът от фигура 14 би се опростил, ако допуснем съществуването на втори агент. Идеята е вместо да сменяме цвета на фигурите (да обръщаме дъската), да сменим агента с такъв, който винаги играе с черните фигури. Ще се получи алгоритъм изпълняван от повече от един агент, но такива алгоритми са естествени. Например: „Дадох пари на един човек и той купи нещо с тези пари“. Това е пример за алгоритъм изпълнен от двама агенти.

 

По важното е, че ще искаме, когато ние преместим бяла фигура, някой друг (друг агент) да премести черна фигура. В предишния случай си задавахме само въпроса „възможен ли е определен алгоритъм“, а тук ще искаме някакъв алгоритъм реално да бъде изпълнен. Не е все едно алгоритмът да е възможен и той реално да бъде изпълнен. Не е все едно „може ли някой да направи палачинки“ или „жена ви да ви направи палачинки реално“. В единия случай знаете нещо за света, а във втория случай реално ядете палачинки. Когато някой агент реално изпълнява даден алгоритъм, не е все едно кой е агентът, който ще изпълни алгоритъма. Например, предполагаме, че жена ви ще направи палачинките по-добре отколкото вие бихте ги направили.

 

Ще предполагаме, че след всеки наш „real_move“ агентът, който играе с черните фигури, ще изпълни алгоритъма от фигура 15.

 

Figure 15

Един алгоритъм не се изпълнява за една стъпка, а за това са нужни много стъпки. Тук обаче ще предполагаме, че противника ще играе с черните фигури веднага (за една стъпка). Хората, когато си мислят, че някой ще направи нещо, обикновено си представят резултата, без да отчитат, че това се извършва в продължение на известно време. Например, когато си мислите: „Днес имам рожден ден и жена ми ще ми направи палачинки“. При това разсъждение вие приемате палачинките за направени без да отчитате, че това отнема време.

 

Както казахме, не е все едно кой е агентът, който играе с черните фигури. Много важно е дали ни е съюзник или противник (дали ще ни помага или ще ни пречи). Също така, важно е доколко е умен (защото той може да има някакви намерения, но до колко ще ги осъществи зависи от това доколко е умен). Важно е още какво знае и какво вижда агентът. При играта шах предполагаме, че агентът вижда всичко (цялото табло), но в други светове бихме могли да предположим, че агентът знае и вижда само част от информацията. Може да е важно и къде се намира агентът. Тук предполагаме, че това не е важно. Предполагаме, че където и да се намира агентът, той може да се придвижи до произволно квадратче и да вдигне фигурата, която е там. Бихме могли да предположим, че позицията на агента има значение и че за по-близките фигури е по-вероятно да бъдат преместени, отколкото по-далечните.

7. 3. Собствено състояние

Тук предположихме, че вторият агент си има собствено състояние на света. Тоест, има си собствена позиция <x, y> на таблото (квадратчето, което наблюдава). Също така предполагаме, че той играе с черните, за разлика от главния герой, който играе с белите.

 

Предполагаме, че двамата агенти променят света, чрез една и съща функция f″, но паметта на функцията (състоянието на света) е различна за двамата агенти. Бихме могли да предположим, че двете състояния на света нямат нищо общо, но тогава действията на втория агент по никакъв начин няма да влияят на света на главния герой. Затова ще предполагаме, че позицията на таблото е обща (т.е. обща е следата от фигура 6). Ще предполагаме, че всеки агент си има собствени координати и собствен цвят, с който играе (т.е. Event-Driven моделите 2, 3 и 5 имат различни активни състояния при двамата агенти). За останалите ED модели, както и за следата от фигура 7 също ще предполагаме, че те са отделни за отделните агенти, макар че нищо не пречи да предположим и обратното.

 

Ако предполагахме, че двамата агенти споделят едно и също състояние на света, тогава алгоритъма от фигура 15 щеше да е много по-сложен. Противника първо щеше да обърне дъската („change“), после щеше изиграе своя ход и пак да обърне дъската, за да остави света на главния герой непроменен. Освен това противникът трябваше да се погрижи да се върне на същите координати <x, y>, от които е тръгнал (това са координатите на главния герой). Би било много неестествено различните агенти да са съвсем еднакви и да се намират на едно и също място. Много по-естествено е предположението, че агентите са различни и че имат различно състояние на света, но че част от състоянието е обща. Например, „В момента аз правя палачинки и жена ми прави палачинки.“ Може ние да правим едни и същи палачинки, а може моите палачинки да нямат нищо общо с нейните.

 

Забележка: Не е много точно да казваме, че света има две различни състояния за двата агента. Светът е един и неговото състояние е едно единствено. По-точно ще е да кажем, че сме променили света и вече имаме свят с по-сложно състояние. Нека новото множество от състояния да е S‴. Можем да предполагаме, че S‴ = S″⨯ S″. Въпросите, които са общи за двамата агенти са си останали непроменени, но другите въпроси са се раздвоили. Например въпросът „Къде съм?“ е заменен от въпросите „Къде е главният герой?“ и „Къде е противникът?“. От функцията f″, която е дефинирана в S″, сме направили новата функция f‴, която е дефинирана в S‴. Разликата между S″ и S‴ е, че състоянията в S″ описват състоянието на един агент (без да се казва кой е той), докато състоянията в S‴  описват състоянието на двата агента. Общото състояние на света също се описва. Функцията f‴ описва света чрез двата агента и това как те променят състоянието си чрез функцията f″. Въпреки всичко, по-лесно е да си мислим, че света има различни състояния за двата агента и че тези агенти променят състоянията си чрез функцията f″, която работи само с отговорите на въпросите, които са само за единия агент.

7. 4. Неизчислим свят

Описахме първия свят, в който агентът играеше сам срещу себе си и направихме програмата [7], която емулира този свят. Програмата [7] представлява функцията f″, която е описание на първия свят. Описахме и втори свят, в който агентът играе срещу някакъв противник. Можем ли да направим емулираща програма и за втория свят?

 

Във втория свят добавихме твърдение от вида „този алгоритъм може да бъде изпълнен“. (Това твърдение трябваше да го добавим още в първия свят, защото и там не е позволено да се играе ход, ако след хода сме шах. За момента програмата [7] позволява да играем такива ходове.) Във втория свят добавихме и операция от вида „противникът изпълнява алгоритъм“. Това твърдение и тази операция в общия случай са неразрешими (по-точно те са полуразрешими).

 

Да вземем например твърдението „този алгоритъм може да бъде изпълнен“. В конкретния случай става дума за това дали противника може да ни вземе царя и това е напълно разрешимо, защото шахматната дъска е крайна и има крайно много позиции и всички алгоритми работещи над шахматната дъска са разрешими. В общия случай алгоритмът може да бъде машина на Тюринг и тогава това твърдение е равносилно на стоп проблема (halting problem).

 

Същото може да се каже и за операцията „противникът изпълнява алгоритъм“. Алгоритмът може да се изпълни по много различни начини, но задачата да намерим поне един от тези начини е полуразрешима. В конкретния случай, когато имаме играта шах, лесно можем да намерим един от начините, по които се изпълнява алгоритмът. Тук дори можем да намерим всички начини (това са всички възможни ходове), но в общия случай тази задача е полуразрешима.

 

Тоест, в конкретния случай ние можем да напишем програма, която емулира този втори свят. Само трябва да изберем поведението на противника, защото за това поведение има много възможности. С други думи казано, за да създадем програма, която да емулира света на играта шах, трябва вътре в нея да вградим програма емулираща шахматен играч.

 

В общия случай обаче ние няма да можем да напишем програма емулираща описаният от нас свят. Тоест, езика за описание на светове вече описва такива светове, които няма как да бъдат емулирани с компютърна програма. Още в началото казахме, че функцията f″ може да се получи неизчислима. Няма как да напишем програма, която да изчислява неизчислима функция.

 

Това, че не можем да напишем програма емулираща описания от нас свят не е голям проблем, защото нашата цел не е да емулираме света, а да напишем програмата ИИ, която на базата на това, че е разбрала света (намерила е описанието му) ще планира успешно бъдещите си ходове. Разбира се, ИИ би могла да процедира като направи една емулация на света и да разиграе няколко от възможните бъдещи развития, като избере това, което е най-доброто. (По същество така работи алгоритмът Min-Max, с който шахматните програми играят.) Тоест, ако можем да направим емулация на света, няма да е лошо, макар и да не е задължително.

 

ИИ не само, че няма да може да направи пълна емулация на света (когато функцията f″ е неизчислима), но дори ИИ може да не разбере кое точно е текущото състояние на света (когато възможните състояния са континуум много). Въпреки това, ИИ ще може да направи частична емулация и да разбере състоянието на света частично. Например, ако в света има безкрайна лента и върху нея има безкрайно много информация, тогава няма как ИИ да разбере текущото състояние на света, но може да опише някаква крайна част от лентата и информацията върху тази крайна част.

 

Дори и Min-Max алгоритмът не е пълна емулация, заради комбинаторната експлозия. Вместо това, Min-Max прави частична емулация като обхожда само първите няколко хода. Когато в описанието на света има полуразрешимо правило, тогава ИИ ще използва това правило само в едната посока. Например правилото „Ако съществува доказателство, тогава твърдението е вярно“. Хората използват това правило, когато има доказателство и когато те са го намерили. Когато няма доказателство, тогава това правило не се използва, защото няма как да разберем, че доказателство действително няма.

8. Агенти

Следващата абстракция, това е агентът. Също като обектите, агентите няма да можем да ги засечем директно. Тях ще ги наблюдаваме индиректно чрез техните действия. Откриването на агенти е трудна задача. Хората успяват да открият агенти, но за целта те ги търсят навсякъде. Когато нещо се случи, хората веднага намират обяснение в някакъв агент, който го е извършил. Зад всяко събитие хората виждат като извършител или човек, или животно, или божество. Много рядко приемат, че това се е случило от само себе си. ИИ трябва да подходи по същия начин като хората и да търси агентите навсякъде.

 

Когато ИИ намери агент трябва да започне да го изучава и да се опитва да се свърже с него. Да намери агент, значи да го измисли. Когато ИИ измисли съществуващ агент, тогава можем да кажем, че го е намерил. Когато си измисли несъществуващ агент, тогава е по-добре да кажем, че си е измислил нещо несъществуващо. Дали агентите са реални или измислени няма голямо значение. Важното е описанието на света получено чрез тези агенти да е адекватно и да дава добри резултати.

8. 1. Взаимодействие между агенти

ИИ ще изучава агентите като ги класифицира като приятели и като врагове. Ще отбелязва дали са умни и дали са благодарни (съответно отмъстителни). ИИ ще се опитва да се свързва с агентите. За целта първо трябва да разбере към какво се стреми всеки от тях и да му предложи това, което иска агентът и в замяна да се опита да получи нещо полезно за себе си. Тази размяна на блага се нарича изпълнение на коалиционна стратегия. Обикновено се предполага, че агентите се срещат извън света и там се уговарят каква да бъде тяхната коалиционна стратегия. Тъй като няма как агентите да се срещнат извън света, ние ще предполагаме, че те общуват вътре в света. Принципът на общуването е: „Ще ти направя добро и очаквам да ми го върнеш.“ Другият принцип е: „Аз ще се държа предсказуемо и очаквам ти да разбереш какво е моето поведение и да започнеш да изпълняваш коалиционна стратегия (да се държиш така, че и за двама ни да има полза).“

 

По този начин ние общуваме с кучетата. Даваме им кокал и веднага се сприятеляваме. Какво получаваме в замяна? В замяна те не ни лаят и не ни хапят, а това никак не е малко. По-нататък може да се достигне до по-сложни комуникации. Може да покажем на агента алгоритъм и да искаме от него той да го изпълни. Така може да научим кучето да дава лапа. Още по-нататък може да се достигне до език като се асоциират обекти с явления. Например, произнесената дума е явление и ако това явление се асоциира с даден обект или алгоритъм, тогава агентът може като чуе думата да изпълни алгоритъма. Например, кучето, като си чуе името, може да дойде при вас или ако чуе „чехли“ може да ви донесе чехлите.

 

В тази статия ние стигнахме до понятието агент и следващата стъпка трябва да бъде да изучим взаимодействието между агентите. Основните въпроси при взаимодействието са „Кои са ни приятелите?“ и „Кой колко е умен, силен, умел, какво вижда и колко знае?“.

8. 2. Сигнали между агенти

За да говорим за взаимодействие или за преговори, трябва да имаме някаква комуникация. Тук стигаме до въпроса за подаването на сигнали между агентите. Не става въпрос за предварително уговорени сигнали, а за такива, които един от агентите решава да подава, а другите успяват да отгатнат, на базата на наблюдението, което правят. Като пример ще дадем „Кучето на Павлов“ [16]. Павлов е агентът, който решава да подава сигнал звънейки със звънче преди да нахрани кучето. Другият агент е кучето, което успява да разбере сигнала.

 

Когато един агент подава сигнал на друг, не е задължително вторият да разбира, че това е сигнал и че този сигнал е подаден от някой друг, който иска нещо да му каже. Например, кучето на Павлов въобще не разбира, че Павлов е този, който звъни със звънчето и че иска да му каже, че обядът е готов. Кучето просто свързва събитието звънене със събитието храна. Тоест, когато подаваме сигнал, можем да останем анонимни. Тоест, можем да повлияем на другия агент без той въобще да разбира, че някой му влияе.

 

Друг начин за подаване на сигнал е да покажем нещо (да дадем някаква информация). За да покажем нещо трябва да сме наясно кога и какво вижда другият агент. Например, когато кучето ни се озъби, то ни показва зъбите си. Ние виждаме, че кучето има зъби, а това е факт, който ние по принцип знаем, но виждаме, че кучето е решило да ни напомни за този факт и разбираме посланието така: „Кучето ни предупреждава, че може да използва зъбите си срещу нас“.

 

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

8. 3. Обмен на информация

Когато агентите комуникират, те могат да обменят информация, да съгласуват действията си или да преговарят. Пример за обмен на информация е, когато един агент споделя някакъв алгоритъм с друг агент. Алгоритмът може да бъде описан на естествен език, тоест може да бъде представен като последователност от сигнали (думи), всеки от които се асоциира с обект, явление или алгоритъм. Например, ако искаме да кажем на някого как да стигне до магазина, ние описваме този алгоритъм с думи. Когато казваме „отвори вратата“ разчитаме, че другият агент асоциира думата „врата“ с обекта „врата“ и думата „отвори“ с алгоритъма „отвори“. Тоест, разчитаме, че другият агент знае думите и има представа за обектите асоциирани с тези думи.

 

Ако приемем, че агентът пази алгоритмите в паметта си под формата на Event-Driven модели, тогава той трябва да може от описанието на естествен език да постои ED модел (ако разбере смисъла), както и обратното, да може да направи описание на естествен език на някакъв ED модел (стига да разполага с нужните думи).

8. 4. Related work

Има много статии, които се занимават с въпроса за взаимодействието между агентите. Тези статии не казват как ИИ ще открие агента, а приемат агента за вече открит и определят правила за разумно взаимодействие. Например в [9] се разглежда случаят, когато всички агенти са приятели и всички са безкрайно умни. В [9] агентите комуникират на базата на това, че се досещат какво би направил другият (разчита се на това, че те са приятели и че са достатъчно умни, за да се сетят кое е от полза за всички). Най-интересното в [9] е, че там се поставят въпросите за йерархия между агентите (кой е по-важен) и за това кой бърза повече (кой колко е търпелив). Това са принципи, които се използват от реалните хора в реалния свят и е логично ИИ също да ги използва.

 

Взаимодействието между агентите е толкова сложно, колкото взаимодействието между хората. Например в [13] агентите преговарят помежду си и дори мога да се лъжат един друг.

 

В [10] се разглежда случая, когато агентите взаимодействат помежду си и образуват коалиции. Дори тези коалиции са временни и могат да се променят по време на играта. За съжаление в [10] не се казва как агентите взаимодействат помежду си и как уговарят коалициите, а се предполага, че те се уговарят на някакъв език извън играта (извън света). Тоест, въпросът за уговарянето не е разгледан, а е прието че това се е случило по някакъв начин.

 

В статията [11] както и в настоящата статия се разглежда много-агентна система при която агентите не виждат всичко (Partial Observability). Основната разлика между [11] и настоящата статия е, че в [11] светът е даден (описан е чрез една релация) докато в настоящата статия светът не е даден и това е което се търси.

9. По-нататъшна работа

В тази статия ръчно описахме един свят (играта шах) и направихме компютърна програма [7], която на базата на това описание емулира света. Следващата задача, която искаме да решим е обратната. Искаме да направим програма, която автоматично да намери същото това описание на света, което описахме ръчно. Програмата, която ще търси описанието ще използва емулацията на света [7], благодарение на тази емулация програмата ще „живее“ вътре в света и ще трябва да го разбере (т.е. да го опише).

 

В този случай бихме могли да шмекеруваме, защото правим програма, която трябва да намери нещо, а ние предварително знаем какво е това нещо, което тя трябва да намери. Разбира се, не трябва да шмекеруваме, защото ако го направим ще получим програма, която би разбрала единствено и само този конкретен свят. Хубаво би било направената от нас програма да е в състояние да разбере (да опише) произволен свят. Последното изискване е твърде силно, защото това означава да постоим ИИ. Затова няма да искаме програмата да може да разбере произволен свят, но ще искаме да е в състояние да разбере дадения свят [7] и световете, които са близки до него. Колкото по-голям клас от светове е в състояние да разбере направената от нас програма, толкова по-умна ще е тя.

10. Заключение

Задачата е да разберем света. За да го разберем, трябва да го опишем, а за да го опишем ни е нужен специален език за описание на светове.

 

Сведохме задачата за създаването на ИИ до една чисто логическа задача. От нас сега се иска да създадем език за описание на светове и този език ще е логически, защото на него ще могат да се опишат неизчислими функции. Ако езика описваше само изчислими функции, тогава това щеше да е език за програмиране, а не логически език.

 

Основните градивни елементи на нашия нов език това са Event-Driven моделите. Това са простите модули, които ще откриваме един по един. С тези модули ще представим зависимости, алгоритми и явления.

 

Направихме една абстракция като въведохме обектите. Обектите не могат да бъдат наблюдавани директно, а ги засичаме индиректно като наблюдаваме техни свойства. Свойството е специално явление, което се наблюдава когато наблюдаваме обект с това свойство. Тоест, свойството също се представя с ED модел.

 

Следващата абстракция, която въведохме са агентите и те също не могат да бъдат наблюдавани директно, а ги засичаме индиректно чрез техни действия.

 

Създадохме език за описание на светове. Това е не е напълно завършен език, а е само неговата първа версия, която се нуждае от допълнително развитие. Не дадохме формално описание на създадения от нас език, а го представихме с три примера. Тоест, вместо формално да описваме езика ние написахме описанията на три конкретни свята. Тава са два варианта на играта шах (с един и с двама агенти) и свят, който представя работата на Машина на Тюринг.

 

Забележка: Не е голям проблем да се направи формално описание на език, което да покрива трите свята, които сме използвали като пример, но целта е друга. Целта е да се направи език, който може да опише произволен свят и този универсален език да се опише формално. Това е по-трудна задача, която не сме решили.

 

Показахме, че езикът за описание на светове може чрез простите модули, от които се състои, да описва доста сложни светове с много агенти и сложни взаимоотношения помежду им. Това, което надграждаме над простите модули не може да виси във въздуха и трябва да стъпи на някаква стабилна основа. Именно Event-Driven моделите са основата, която ще изгради езика за описание на светове и базата, на които ще изградим всички по-сложни абстракции.

References

 

[1] Xi-Ren Cao (2005). Basic Ideas for Event-Based Optimization of Markov Systems. Discrete Event Dynamic Systems: Theory and Applications, 15, 169–197, 2005.

 

[2] Xi-Ren Cao, Junyu Zhang (2008). Event-Based Optimization of Markov Systems. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 53, NO. 4, MAY 2008.

 

[3] Dimiter Dobrev (2013). Giving the AI definition a form suitable for the engineer. arXiv:1312.5713 [cs.AI].

 

[4] Dimiter Dobrev (2018). Event-Driven Models. International Journal "Information Models and Analyses", Volume 8, Number 1, 2019, pp. 23-58.

 

[5] Dimiter Dobrev (2019). Minimal and Maximal Models in Reinforcement Learning. International Journal “Information Theories and Applications”, Vol. 26, Number 3, 2019, pp. 268-284.

 

[6] Dimiter Dobrev (2019). Before we can find a model, we must forget about perfection. arXiv:1912.04964 [cs.AI].

 

[7] Dimiter Dobrev (2020). AI Unravels Chess. http://dobrev.com/software/AI_unravels_chess.zip.

 

[8] Dimiter Dobrev (2020). Strawberry Prolog, version 5.1. http://dobrev.com/ .

 

[9] Valentin Goranko, Antti Kuusisto, Raine Rönnholm (2020). Gradual guaranteed coordination in repeated win-lose coordination games. 24th European Conference on Artificial Intelligence - ECAI 2020, Santiago de Compostela, Spain, Frontiers in Artificial Intelligence and Applications, Volume 325, pp. 115-122.

 

[10] Dimitar Guelev (2020). Reasoning about Temporary Coalitions and LTL-definable Ordered Objectives in Infinite Concurrent Multiplayer Games. Presented at the 8th International Workshop on Strategic Reasoning, arXiv:2011.03724 [cs.LO].

 

[11] Dilian Gurov, Valentin Goranko, Edvin Lundberg (2021). Knowledge-Based Strategies for Multi-Agent Teams Playing Against Nature. arXiv:2012.14851 [cs.MA].

 

[12] Gianfranco Lamperti, Marina Zanella, Xiangfu Zhao (2020). Diagnosis of Deep Discrete-Event Systems. Journal of Artificial Intelligence Research, Vol. 69, 2020, pp. 1473-1532.

 

[13] Johnathan Mell, Gale M. Lucas, Sharon Mozgai, Jonathan Gratch (2020). The Effects of Experience on Deception in Human-Agent Negotiation. Journal of Artificial Intelligence Research, Vol. 68, 2020, pp. 633-660.

 

[14] Yiannis N. Moschovakis (2001). What is an algorithm? Mathematics unlimited – 2001 and beyond, edited by B. Engquist and W. Schmid, Springer, 2001, pages 919-936.

 

[15] Yiannis N. Moschovakis (2018). Abstract recursion and intrinsic complexity. Cambridge

University Press, Lecture Notes in Logic, Volume 48, ISBN: 9781108415583.

 

[16] Ivan Pavlov. (1897/1902). The work of the digestive glands. London: Charles Griffin & Compa-ny, Limited.

 

[17] Michael Schofield, Michael Thielscher (2019). General Game Playing with Imperfect Information. Journal of Artificial Intelligence Research, Vol. 66, 2019, pp. 901-935.