Language for Description of Worlds

We will reduce the task of creating AI to the task of finding the right language for description of the world. This language will not be a programming language because the programming languages ​​describe only computable functions, while this language will describe a slightly wider class of functions. Another feature of this language will be that the description can be divided into separate modules. This will allow us to search the world description automatically by detecting it module by module. Our approach to creating this new language will be to start from one particular world and write a description of that particular world. Our idea is that the language that can describe this particular world will be appropriate to describe arbitrary world.

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

Въведение

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

За да създадем този специален език, първо трябва да си отговорим на въпроса: „Какво представлява светът?“ Ще видим, че света може да си го мислим като някаква функция f, която е от ℝ в ℝ. Функцията f заедно с началното състояние на света са достатъчни за пълното му описание. Това описание е детерминистично, което е хубаво, защото ние искаме да предскажем бъдещето максималното точно. Лошото е, че това описание може да се окаже прекалено сложно и трудно за намиране. Освен това, сложното описание не е много достоверно, защото според принципа на Окам ние трябва да изберем възможно най-простото описание.

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

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

Чрез отговор на въпрос ще дефинираме недетерминистичната функция f. Ще усложним тази дефиниция като я представим чрез отговор на група от въпроси (в тази статия терминът „група“ се използва като синоним на „множество“).

Ще предположим, че не задаваме ненужни въпроси. За да бъде един въпрос нужен, неговият отговор трябва да зависи от миналото и от отговора му трябва да зависи бъдещето. Дефиницията на света съществено ще зависи от групата въпроси, които сме задали. Ще предполагаме, че сме задали достатъчно въпроси, вследствие на което можем да представим света като Markov decision process изпълняващ свойството на Марков.

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

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

Изчислима ли е функцията g, която ни описва света? Ако тази функция беше изчислима, тогава езикът за описание на светове щеше да е някакъв език за програмиране. Ще се окаже, че изчислимите функции не са ни достатъчни и затова ще опишем един малко по-широк клас от функции.

Ще покажем, че от езика за описание на светове, лесно можем да направим Изкуствен Интелект. За да разберем света, трябва да намерим неговото описание. Бихме могли да търсим, като изброим всички възможни описания (exhaustive search or brute-force search), но това търсене не би успяло. Ние ще подходим по-интелигентно като предположим, че описанието на света е разделено на отделни модули, които могат да бъдат откривани един по един.

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

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

Конкретният свят, който ще опишем, ще бъде светът, в който агентът играе шах. Написали сме програмата [8], която съдържа просто описание на този свят и чрез това описание го емулира. Можете да стартирате тази програма и да видите колко просто се е получило описанието на този свят (на играта шах). Описанието се състои от 24 модула, които представляват Event-Driven модели (това са ориентирани графи с по десетина състояния всеки). Освен ED моделите имаме още две подвижни следи (т.е. два масива). ED моделите са три вида (5 зависимости, 9 алгоритъма и 10 свойства, което прави общо 24). Освен 24-те модула и двата масива ни се е наложило да добавим още седем прости правила, които допълнително описват света.

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

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

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

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

Следващите две зависимости ще са Horizontal и Vertical. Тези зависимости ще ни дадат x и y координатите на наблюдаваното квадратче. Декартовото произведение на тези два модела ще е модел на цялото шахматно табло.

Следата на това декартово произведение ще бъде позицията на шахматната дъска. Тази следа ще е „подвижна“, защото позицията на дъската не е постоянна, а се променя.

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

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

Много малко са авторите, които се опитват да дефинират понятието алгоритъм. Единствените опити за дефиниция на алгоритъм, които са ни известни са направени от Moschovakis [1, 2].

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

Ще представим машината на Тюринг като отделен свят. Описанието на този свят ще се състои от два Event-Driven модела. Първият модел ще опише безкрайната лента. Вторият модел ще опише самата машина на Тюринг. Алгоритмът на практика ще е вторият ED модел, защото първият просто описва безкрайната лента. За да имаме алгоритъм, той трябва да има нещо върху което да се прилага. За да имаме машина на Тюринг, трябва да имаме безкрайна лента, върху която да работи машината.

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

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

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

В първия свят, който описваме, има само един агент, който играе сам срещу себе си. Ще опишем втори вариант на играта шах, при който, освен главния герой, ще има още един агент. Важното е, че състоянието на света ще е различно за различните агенти. Състоянието на света е контекстът на агента. Контекстът е: „кой“, „къде“, „кога“. Може да предположим, че за всички агенти контекстът „кога“ е един и същи, но „къде“ може да е различно за различните агенти. Контекстът „кой“ също може да е различен, защото един агент може да е мъж, а друг да е жена. Един може да играе с белите, а друг с черните.

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

Какво представлява светът?

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

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

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

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

v_i = f(a_i)

Тук описахме нещата твърде опростено, като предположихме, че функцията f няма памет и не зависи от това, което се е случило до момента. Предположихме, че функцията f зависи единствено и само от последното действие на агента. Това опростяване е прекалено и с него се губи същността на задачата. Въпреки това ние споменаваме за това възможно опростяване, защото то се използва в почти всички статии за ИИ. В литературата, когато е на лице това опростяване се казва, че имаме Full Observability, а когато го нямаме се казва, че разглеждаме случая на Partial Observability. В тази статия ние ще предполагаме, че функцията 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₀. Тоест, трябва да добавим и началното състояние на света (или началната стойност на паметта). Сега вече можем да кажем, че двойката <f, s₀> е светът или поне, че това го описва достатъчно точно.

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

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

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

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

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

Прост недетерминиран свят

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

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

W = <ℝ, F, P>

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

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

За да определим функцията 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. От тези множества получаваме M_i=MÇA_i. Всяко едно от множествата M_i си има вероятност или вероятностен интервал и това е вероятността на отговора < f₂(M, a, v_i), v_i>. Тук v_i пробягва всички възможни наблюдения. Последният възможен отговор е <M_n+1, undef >. В този случай състоянието на света остава същото, тоест множеството M се ограничава до M_n+1. Тоест, следващото множество от състояния ще е M_n+1= 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₃.

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

< f₄, M₀, W>

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

Какво е въпрос?

Описахме състоянието на света по един много елементарен начин. Разделихме множеството на две части (M и S\M) и казахме, че състоянието на света е в първото множество с вероятност единица и съответно с вероятност нула е във второто.

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

Дефиниция: Въпрос ще наричаме разбиване на множеството S на крайно или на изброимо много непресичащи се подмножества Q_i, където "i P(Q_i)¹0. Всяко едно от множествата Q_i ще наричаме базов отговор.

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

Дефиниция: Група от въпроси ще наричаме крайно или на изброимо множество от въпроси.

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

Дефиниция: Отговорът „не знам“ ще бъде отговорът на въпрос, при който на всеки базов отговор съответства вероятностният интервал [0, 1]. Отговорът на група от въпроси ще бъде „не знам“, ако отговорът на всички въпроси от групата е „не знам“.

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

Дефиниция чрез въпрос

Ще опишем състоянието на света, чрез отговора на някакъв въпрос. Може да се приеме, че отговорът AQ на въпроса Q преобразува вероятностното пространство W в ново вероятностно пространство W′, където вероятността на всяко множество Q_i (на всеки базов отговор) се умножава по някакъв коефициент q_i. Как ще изчислим тези коефициенти?

q_i =AQ(Q_i)/P(Q_i)

Когато стойността на Q_i в AQ, както и вероятността на Q_i са числа, тогава q_i също е число. Когато това са вероятностните интервали [a′, b′] и [a, b], тогава q_i е интервалът от коефициенти [a′/b, b′/b].

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

Каква е вероятността p_i следващото наблюдение да е v_i, ако действието е a?

Тази вероятност е равна на вероятността на множеството A_i във вероятностно пространство W′, което може да се представи с горната сума.

Какъв ще е новият отговор AN_i на въпроса N, който ще опише състоянието на света при положение, че сме тръгнали от състояние описано с отговора AQ, изпълнили действието a и сме видели наблюдението v_i.

Тук r пробягва базовите отговори на Q, а j пробягва базовите отговори на N, а константата a_i нормира отговора AN_i.

От функцията f ще направим още една функция, която ще кръстим f₅.

<AN_i, p_i> = f₅(AQ, a, v_i, N)

Тук AN_i е отговор на въпроса N, а p_i е вероятност или вероятностен интервал. Стойността на p_i е равна на вероятността следващото наблюдение да е v_i. Тази стойност не зависи от въпроса N. Отговорът AN_i е този, който ще ни описва новото състояние на света при положение, че наблюдението е v_i.

Дефиниция чрез въпроси

Описахме състоянието на света чрез отговора на един въпрос. Сега ще заменим отговора с група от отговори. Ще разгледаме случая когато в групата има два въпроса и когато отговорите не съдържат вероятностни интервали (т.е. когато всеки базов отговор си има точна вероятност).

Нека имаме два въпроса B и C и техните базови отговори са B_r и C_s. Нека имаме едни коефициенти k_rs, които ще зависят само от въпросите, но не и от отговорите.

Нека

Тук P′ е новата вероятност, която имаме в новото вероятностно пространство W′, което се получава след като вземем под внимание отговорите AB и AC на въпросите B и C. Трябва да намерим коефициентите t_rs. Как ще ги намерим?

Когато някой от коефициентите k е равен на нула, тогава и съответният коефициент t също е равен на нула. Когато всички коефициенти k са единица, тогава и всички коефициенти t също са единица. В общия случай коефициентите t зависят от отговорите и за да ги изчислим ще използваме равенствата:

	(1)
	(2)

Лесно ще намерим коефициенти b_r, които ще ни осигурят равенства (1). После лесно ще намери коефициенти c_s, които ще ни осигурят равенствата (2). За съжаление оправяйки равенствата (2) ще развалим равенствата (1). Затова предполагаме, че сме намерили такива коефициенти b_r и c_s, че когато t_rs=b_r.c_s тогава са изпълнени и (1) и (2).

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

< AN_i, p_i> = f₅(AG, a, v_i, N)

Тук p_i и AN_i са:

Истински недетерминиран свят

Много важно е какви въпроси ще зададем. Както казахме, не можем да зададем всички въпроси, защото те са неизброимо много. Затова ще предположим, че сме фиксирали групата от въпроси GQ. Ще предположим, че състоянието на света, както и новото състояние, са описани с отговор на тази група от въпроси. Ще дефинираме функцията f₆, като тя ще зависи от GQ, макар че GQ няма да е аргумент на f₆.

Функцията f₅ ни дава отговор на един въпрос. Чрез f₅ можем да намерим отговори на всички въпроси от GQ (един по един). Така от f₅ получаваме f₆.

< AG_i, p_i> = f₆(AG, a, v_i)

Тук AG е отговор на въпросите GQ. Отговорите AG_i също са отговори на въпросите GQ.

Използвайки детерминираната функция f₆ ще направим една недетерминирана функция.

f₇(AG, a)

Функцията f₇ ще връща n+1 възможни отговора от вида <AG_i, v_i>, като всеки от отговорите ще го връща със съответната вероятност p_i.

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

< f₇, Answer₀, GQ, W >

Тук Answer₀ е някакъв отговор на групата от въпроси GQ (началният отговор, от който ще тръгнем). Ще предполагаме, че началният отговор е възможен. Пример за невъзможен отговор е, когато отговорът е детерминиран и съответният коефициент k_rs е равен на нула. Тоест, хем не е възможно въпросите B и C да имат отговорите r и s едновременно, хем няма друга възможност.

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

Ненужни въпроси

Недетерминираният свят съществено зависи от това коя група въпроси GQ сме избрали. Ако изберем празната група от въпроси Æ, тогава ще имаме само един възможен отговор и това е празният отговор Æ. Тогава можем да си мислим, че имаме само едно състояние на света и че имаме Full Observability.

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

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

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

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

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

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

Недетерминирания свят го представихме като Markov decision process (MDP). Има три малки разлики с класическата дефиниция на MDP.

1. Тук множеството от състоянията е множеството от сеченията на базовите отговори. Това множество може да не е крайно. То може да е безкрайно и дори може да е с размера на континуум.

2. Вероятностите са заменени с вероятностни интервали.

3. Тук няма rewards, защото тук целта е само да намерим модел, а rewards са нужни когато търсим стратегия.

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

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

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

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

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

Как ще опишем света?

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

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

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

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

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

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

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

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

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

Общият вид на функцията g ще е следният:

< Answer′, p> = g(Answer, a, v)

Тук Answer е отговор на поставените въпроси, Answer′ е новият отговор при положение, че сме играли a и сме видели v, а p е вероятност или вероятностен интервал.

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

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

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

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

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

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

Какво ще представлява ИИ?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Figure 1

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

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

Partial Observability

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

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

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

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

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

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

1, 2, 3

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

Figure 2

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

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

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

Следа

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

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

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

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

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

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

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

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

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

Подвижната следа ще я свързваме с въпрос. Например: „Котката в стаята ли е?“ Този въпрос има два отговора, които отразяват моментното състояние на света. Въпросът „Кои котки са в стаята?“ има повече отговори и броят на отговорите зависи от това колко котки имаме в къщата. Когато се появи още една котка, моделът на света ще се промени и броят на отговорите на този въпрос също ще се промени.

Horizontal и Vertical

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

Figure 3

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

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

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

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

Figure 4

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

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

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

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

Подвижна следа

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

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

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

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

Figure 5

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

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

Figure 6

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

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

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

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

Алгоритми

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Figure 7

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

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

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

Figure 8

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

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

Figure 9

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

Figure 10

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

Понятието алгоритъм

Важно е, че в тази статия е дефинирано понятието алгоритъм. Много малко са хората, които въобще си задават въпроса какво е алгоритъм. Единствените опити за дефиниция на алгоритъм, които са ми известни са направени от Moschovakis [1, 2]. В тези трудове Moschovakis казва, че повечето автори дефинират алгоритъма чрез някаква абстрактна машина и отъждествяват алгоритмите с програмите за тази абстрактна машина. Moschovakis формулира каква дефиниция на алгоритъм на нас ни е необходима. Той иска да създаде едно общо понятие, което да не зависи от конкретната абстрактна машина. Такова понятие е изчислимата функция, но това понятие е твърде общо за Moschovakis и той иска да направи по-специализирано понятие, което да отразява това, че една изчислима функция може да се изчисли от много принципно различни алгоритми. В [1] не е постигната високата цел поставена от Moschovakis. Това, което той е направил може да се приеме за една нова абстрактна машина. Наистина тази машина е много интересна и е по-абстрактна от повечето известни машини, но отново имаме недостатъка, че програмата на машината може безсмислено да се усложни като се получи друга програма реализираща същия алгоритъм. Макар, че в [1] не се постига целта да бъде създадена обща дефиниция на алгоритъм, самият 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.“

Машината на Тюринг

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

Ще опишем един свят, който представлява машина на Тюринг. Първото нещо, което трябва да опишем в този свят е безкрайната лента. В играта шах описахме шахматното табло като подвижната следа на някакъв Event-Driven модел с 64 състояния. Тук отново ще използваме подвижната следа, но ще ни е нужен модел с изброимо много състояния. Да вземем модела от фигура 3. Това е модел на лента с осем клетки. Трябва ни същият модел, пак да има две събития (наляво и надясно), но да не е ограничен отляво и отдясно. Получава се 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 11

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

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

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

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

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

Свойства

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

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

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

Второ кодиране

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

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

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

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

Figure 12

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

Детерминиран свят

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

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

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

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

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

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

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

Случайни събития

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

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

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

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

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

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

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

Figure 13

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

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

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

Втори агент

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

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

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

Figure 14

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

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

Собствено състояние

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

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

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

Забележка: Не е много точно да казваме, че света има две различни състояния за двата агента. Светът е един и неговото състояние е едно единствено. По-точно ще е да кажем, че сме променили света и вече имаме свят с повече въпроси. Въпросите, които са общи за двамата агенти са си останали непроменени, но другите въпроси са се раздвоили. Например въпросът „Къде съм?“ е заменен от въпросите „Къде е главният герой?“ и „Къде е противникът?“. От функцията g сме направили новата функция g′, която работи с отговори на новите въпроси, като функцията g′ описва света чрез двата агента и това как те променят състоянието си чрез функцията g. Въпреки всичко, по-лесно е да си мислим, че света има различни състояния за двата агента и че тези агенти променят състоянията си чрез функцията g, която работи само с отговорите на въпросите, които са само за единия агент.

Втори свят

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

References

[1] 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.

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

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

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

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

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

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

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

[8] Dimiter Dobrev (2020). AI Unravels the Chess. http://dobrev.com/software/AI_unravels_the_chess.zip.

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