Svarog - język do AI

Witam wszystkich.
Jakieś dwadzieścia lat temu odkryłem nowy algorytm planowania oparty na tzw. zmiennych ukrytych. Pięć lat temu napisałem pierwszą implementację - język Perkun (www.perkun.org). Niedawno napisałem nowy, trochę lepszy język o nazwie Svarog. Bardzo chciałbym porozmawiać o tym algorytmie. Nie mam z kim. Próbowałem już pisać o Perkunie na forum "Oceny i recenzje", ale bez większego odzewu.
Proponuję ściągnąć i zainstalować sobie Svaroga - https://www.perkun.org/resources/targz/svarog-0.0.1.tar.gz. Następnie należy wejść do katalogu examples i wstukać np. make test1. Działa też make test2 i make test3. Wszystkie one wykorzystują specyfikację Svaroga o nazwie example1_dorban.svarog. Różnią się tylko danymi wysyłanymi na wejście. Te dane np. dla testu 1 opowiadają taką historię:

Jest sobie bohater Dorban, są trzy miasta (Wyzima, Shadizar i Novigrad). W jednym z tych miast jest wampir. Również w jednym z miast jest drugi bohater Pregor, który może pomóc Dorbanowi pokonać wampira. W teście 1 Dorban od razu spotyka wampira w Wyzimie, ale nie atakuje go, idzie do Novigradu. Tam nikogo nie ma, więc Dorban spodziewa się, że Pregor musi być w Shadizarze. Idzie tam, prosi go o pomoc i następnie obaj idą do Wyzimy (tam gdzie jest wampir). Atakują wampira, z sukcesem. Atakują drugi raz - tym razem przegrywają i Pregor się odłącza. W związku z tym Dorban ponownie prosi go o pomoc. Koniec historii.

Najważniejsze jest to, że Svarog korzysta ze zmiennych ukrytych. W danym przykładzie są dwie (where_is_vampire i where_is_pregor). Odkryłem formułę w jaki sposób interpretować daną obserwację, tj. jak konstruować tzw. belief (rozkład prawdopodobieństwa nad zbiorem możliwych wartości zmiennych ukrytych). Zasadnicza cecha mojego algorytmu to to, że konstruując drzewo gry wykorzystuje tę formułę, tj. wyobraża sobie "teraz wierzę w X1", "pójdę do Novigradu", "zobaczę tam wampira/Pregora bądź nie". Zależnie od obserwacji zinterpretuję ją tak a tak. Wtedy będę wierzył w X2.

Postaram się porządnie matematycznie opisać sam algorytm, już zresztą zacząłem. Różni się od minimaxu tym, że jest tylko jeden agent (nie dwóch), że świat jest stochastyczny i że niektóre zmienne nie są obserwowalne. To tzw. hidden variables (zmienne ukryte).

Masz ode mnie plusika za nazwę języka i wykorzystanych w nim obiektów :)

Ale to co napisałeś, brzmi po prostu jak opis automatu stanowego, no może kilku automatów stanowych działających równolegle wedle zasad programowania agentowego. Co jest w tym szczególnie rewolucynego?

Bo istnieją już np. podobne do opisanych systemy zdolne pisać proste opowiadania o bohaterach (agentach), którzy posiadają własne stany psychiczne i teorie na temat innych bohaterów, oraz podejmują decyzje w oparciu o to, czego wcześniej doświadczyli ze strony innych bohaterów.

Dzięki za plusa i za odpowiedź. To prawda, że mamy do czynienia z automatem stanowym. Dla każdej kombinacji danych wejściowych mamy pewien stan widoczny (visible state). Ale rzeczywisty stan świata zależy jeszcze od wartości zmiennych ukrytych. Taka kombinacja wartości zmiennych ukrytych to stan (state). Każdy stan widoczny ma jednocześnie listę stanów. Rewolucyjne jest to, że Svarog utrzymuje belief nad taką listą, to znaczy po każdej konkretnej akcji A wykonanej w widocznym stanie VS1 i z beliefem B1 (który jest pewną funkcją, rozkładem) dla każdego nowego stanu widocznego VS2 otrzymujemy nowy belief B2=B(VS1,B1,A,VS2). I tą "sztuczkę" przeprowadzam również planując w drzewie gry, czyli gdy wyobrażam sobie, że wykonam akcję A i otrzymam jako rezultat stan widoczny VS2, to planując następny krok zakładam już w co będę wierzył PO ZINTERPRETOWANIU VS2. Czyli do kolejnej iteracji algorytmu, na kolejnym węźle drzewa gry wchodzę już z beliefem B(VS1,B1,A,VS2)!

Powiedzmy, że jestem w Wyzimie i nie widzę nikogo. Odpowiada to wejściu "none place_Wyzima false false false" (mniejsza teraz o znaczenie poszczególnych wartości). Wówczas belief będzie równy:

where_is_vampire=>place_Novigrad where_is_pregor=>place_Novigrad has_dorban_won_a_fight=>none where_is_dorban=>place_Wyzima can_dorban_see_pregor=>false can_dorban_see_vampire=>false is_pregor_following_dorban=>false 0.250000
where_is_vampire=>place_Novigrad where_is_pregor=>place_Shadizar has_dorban_won_a_fight=>none where_is_dorban=>place_Wyzima can_dorban_see_pregor=>false can_dorban_see_vampire=>false is_pregor_following_dorban=>false 0.250000
where_is_vampire=>place_Shadizar where_is_pregor=>place_Novigrad has_dorban_won_a_fight=>none where_is_dorban=>place_Wyzima can_dorban_see_pregor=>false can_dorban_see_vampire=>false is_pregor_following_dorban=>false 0.250000
where_is_vampire=>place_Shadizar where_is_pregor=>place_Shadizar has_dorban_won_a_fight=>none where_is_dorban=>place_Wyzima can_dorban_see_pregor=>false can_dorban_see_vampire=>false is_pregor_following_dorban=>false 0.250000

Po ludzku mówiąc są cztery możliwości - Pregor i wampir są w Novigradzie, albo wampir w Novigradzie a pregor w Shadizarze, albo wampir w Shadizarze a pregor w Novigradzie, albo obaj są w Shadizarze. Na pewno żadnego nie ma w Wyzimie, bo Dorban by ich widział, a nie widzi. Wykonując kolejną akcję (idź do Novigradu) nie mamy gwarancji, że spotkamy tam Pregora lub wampira. Ale idziemy tam, bo wiemy, że jest szansa na spotkanie tam Pregora. Zależnie od tego czy zobaczymy tam Pregora i wampira będziemy już w Novigradzie wiedzieli na pewno gdzie kto jest (bo miast jest tylko trzy). Załóżmy, że zobaczymy w Novigradzie Pregora a nie zobaczymy wampira. Wówczas będziemy już WIEDZIELI, że wampir jest w Shadizarze (dzięki mojej formule interpretacji obserwacji) ale nie rzucimy się od razu do Shadizaru, tylko najpierw poprosimy Pregora o pomoc. Dlatego, że sam Dorban ma przeciwko wampirowi marne szanse, ale z pomocą Pregora ma już duże szanse.

Najważniejsze jest to, że planując, w każdym węźle drzewa gry konstruujemy nowy belief dla zakładanego rezultatu. Dzięki temu Svarog jest w stanie przeprowadzać eksperymenty, nawet poświęcać bezpośredni zysk dla wartości oczekiwanej zysku w przyszłości (bo w powyższym przykładzie podróż do Novigradu jest takim eksperymentem). Eksperyment daje nam pewną obserwowalną wiedzę (visible state), którą następnie zinterpretujemy i będziemy wiedzieć, być może, więcej.

Mam nadzieję, że wyjaśniłem. Mojemu przydługiemu wywodowi odpowiada w kodzie (w pliku src/optimizer.cc) funkcja float optimizer::get_payoff_expected_value_for_consequences(const belief & b1, int n, const action & a)

Jest w niej mianowicie (w linii 439) polecenie

populate_belief_for_consequence(b1, a, **i, b2); 

I to jest właśnie miejsce, w którym konstruujemy nowy belief (b2) dla danych wejściowych: poprzedniego beliefu (b1), akcji (a) i zakładanego stanu widocznego (**i). Dalej w drzewie gry, w liniach 442 i 444 wykorzystujemy już b2, nie b1! Czyli np, idę do Novigradu, zobaczę tam wampira, ale nie Pregora, będę wtedy myślał, że Pregor jest w Shadizarze, a wampir oczywiście w Novigradzie!

Nie wiem czy dobrze zrozumiałem problem, ale mi to wygląda na powiązane z teorią gier i grami z niepełną informacją. Czy Svarog ma ułatwiać tworzenie strategii dla takich gier?

Tak, właśnie tak jest. Od tego powinienem zacząć. To algorytm optymalizacji, który w warunkach gry z niepełną informacją maksymalizuje pewną funkcję zwaną "payoff" (funkcję odpłaty).

W liniach 80-88 pliku examples/example1_dorban.svarog jest zdefiniowana funkcja odpłaty:

	payoff "payoff for winning a fight":100.0 {
		requires initial value has_dorban_won_a_fight == true;
	}
	payoff "payoff for loosing a fight":0.0 {
		requires initial value has_dorban_won_a_fight == false;
	}
	payoff "neutral payoff":50.0 {
		requires initial value has_dorban_won_a_fight == none;
	}

Algorytm ją maksymalizuje, czyli Dorban lubi wygrywać z wampirem (100 punktów), nie lubi przegrywać (0 punktów) i jest neutralny wobec wartości "none" (50 punktów). W Perkunie trzeba było funkcję odpłaty zdefiniować dla wszystkich możliwości, dlatego Perkun jest trochę słabszy od Svaroga.

Oprócz funkcji odpłaty ważny jest model, czyli opis jak działa świat. Znowu w Perkunie trzeba było jawnie podać model dla wszystkich możliwości. W Svarogu jest trochę wygodniej.

Rozumiem, że:

• definiujemy w Svarogu pewien model działania świata na zasadzie niedeterministycznego automatu (tj. STAN x ZDARZENIE -> NOWY_STAN, gdzie NOWY_STAN jest tak naprawdę zmienną losową {nowyStan z prawdopodobieństwem P1}, {nowyStan2 z prawdopodobieństwem P2} etc.) .
• prawdopodobieństwa zależą od stanu ukrytego
• funkcja wypłaty ("odpłaty" tak średnio brzmi jak dla mnie) może zależeć ukrytego stanu

Co jest efektem działania programu w Svarogu?

Chyba nie do końca rozumiem o co chodzi. Ale z terminologi której używasz wnioskuje, że zrobiłeś coś w stylu ukrytego modelu markova?

1. Ja bym to opisał tak:
   STAN x AKCJA AGENTA -> rozkład NOWYCH STANÓW

2. prawdopodobieństwa zależą od stanu ukrytego, jak najbardziej

3. funkcja wypłaty NIE ZALEŻY od ukrytego stanu, zależy wyłącznie od zmiennych wejściowych (obserwowalnych). To była świadoma decyzja.

4. Efektem działania programu w Svarogu w trybie interaktywnym jest optymalizator, który steruje agentem (wybiera wartości zmiennych wyjściowych) tak, by zmaksymalizować wartość oczekiwaną funkcji wypłaty biorąc pod uwagę wartości zmiennych wejściowych.

Można korzystać ze SVAROGA we własnych programach C++ jako z biblioteki. To trochę analogiczne do mojej gry PerkunWars, która tworzy dodatkowe procesy dla każdego NPC i w każdym takim procesie odpala interpreter Perkuna, który komunikuje się z rodzicem przez pipe'y.

Od razu zastrzegam, że nie mam dowodu na poprawność algorytmu. Nie mam nawet porządnego matematycznego opisu. Pracuję nad tym.

part napisał(a):

Chyba nie do końca rozumiem o co chodzi. Ale z terminologi której używasz wnioskuje, że zrobiłeś coś w stylu ukrytego modelu markova?

Mam wrażenie, że to coś podobnego, ale chyba nie to samo. U mnie zmienne wejściowe są zmiennymi stanu świata, tak samo jak zmienne ukryte. Obserwacja jest częścią rzeczywistości a nie jakąś zmienną losową skorelowaną z rzeczywistością. U mnie istnieje naturalne odwzorowanie ze zbioru stanów świata do zbioru obserwacji (stanów widocznych).

Łatwiej to prześledzić w Perkunie, np. model jest zapisywany jako ciąg instrukcji:
set(INITIAL_STATE,ACTION,TERMINAL_STATE,PROBABILITY);
Przy czym zarówno INITIAL_STATE jak i TERMINAL_STATE zawiera zmienne wejściowe (z wartościami) i zmienne ukryte (z wartościami). Np.

set({alpha=>true,beta=>false},{gamma=>false},{alpha=>false,beta=>true},0.3);

Przy czym beta może być zmienną ukrytą a alpha zmienną wejściową. Gamma oczywiście musi być zmienną wyjściową. Powyższa instrukcja mówi, że w razie akcji agenta {gamma=>false} prawdopodobieństwo przeskoku ze stanu {alpha=>true,beta=>false} do stanu {alpha=>false,beta=>true} wynosi 0.3. Dla mojego modelu nie ma znaczenia co agent widzi a czego nie widzi. Ważne tylko co robi.

W modelach Markowa o ile je rozumiem mamy jakąś ukrytą rzeczywistość i coś w rodzaju skorelowanej z nią obserwacji. W moich modelach agent widzi część rzeczywistości.

Nie lubię takich udziwnionych przypadków. Z tego co rozumiem problem polega na tym:
1. Masz parę dróg do przeszukania i każda ma jakieś tam prawdopodobieństwo, że jest właściwa
2. Za każdym razem kiedy przeczesujesz drogę musisz zaktualizować prawdopodobieństwa

Czyli to taki udziwniony Monty Hall? W obu przypadkach można użyć prostej sieci bayesowskiej np. Infer.Net

Może prościej - odnieś swój program do problemu Monty Halla.

Zawodnik stoi przed trzema zasłoniętymi bramkami. Za jedną z nich (za którą – wie to tylko prowadzący program) jest nagroda (umieszczana całkowicie losowo). Gracz wybiera jedną z bramek. Prowadzący program odsłania inną bramkę (co istotne – anonsując, że jest to bramka pusta), po czym proponuje graczowi zmianę wyboru. (zerżnięte z wiki)

Jak twój NPC się zachowa?