Język do Sztucznej Inteligencji o nazwie Perkun

Mam wielką prośbę. Napisałem sobie język do Sztucznej Inteligencji o nazwie Perkun i nie mam z kim o tym pogadać. Prosiłbym o ocenę.

Język można sobie ściągnąć z https://sourceforge.net/projects/perkun/.
Dla użytkowników Windows mam installer:http://www.pawelbiernacki.net/perkun.msi.

Mam też grę, która jest oparta na Perkunie. To słaba gra ale dobrze prezentuje jak można korzystać z Perkuna jako z biblioteki C++ (czyli jak zagnieżdżać go we własnych programach). Tą grę można ściągnąć z https://sourceforge.net/projects/perkunwars/.

Sercem Perkuna jest (mój) algorytm optymalizacji oparty na tzw. zmiennych ukrytych. Perkun buduje drzewo gry, trochę jak minimax, tylko że w świecie Perkuna nie mamy pełnej informacji o stanie gry, środowisko jest stochastyczne i jest tylko jeden gracz.

Może wyjaśnię na przykładzie w jaki sposób Perkun działa. Ściągnijcie sobie i rozpakujcie plik http://www.pawelbiernacki.net/programmer.zip. W środku są trzy pliki, najważniejsza jest specyfikacja w Perkunie o nazwie programmer_final.perkun. Można go uruchomić:

perkun programmer_final.perkun

Wejdziemy wtedy do trybu interaktywnego. W tej akurat specyfikacji mamy do czynienia z prymitywnym językiem, w którym istnieją tylko dwie możliwe instrukcje: instruction_if_then, instruction_print. Program, który piszemy składa się jedynie z dwóch komend. Istnieją więc cztery możliwe programy:

instruction_if_then, instruction_if_then
instruction_if_then, instruction_print
instruction_print, instruction_if_then
instruction_print, instruction_print

Nie przejmujcie się semantyką tych programów, nazwy instrukcji są tylko tak dla ustalenia uwagi.

W każdym kroku na wejście należy wpisać wartości zmiennych wejściowych (dwóch) reprezentujących aktualny program a następnie wartość zmiennej "it_works", która może być "none", "true" lub "false". Na przykład można zacząć od:

perkun> instruction_print instruction_print none

Perkun ma w tej specyfikacji dwie zmienne wyjściowe, których wartość będzie ustawiał tak, żeby "wygrać", tj. doprowadzić Was do wstukania jako "it_works" wartości true. Czasem się zdarzy, że zażyczy sobie wykonania programu (execute_the_program). Wtedy spodziewa się jako "it_works" albo true albo false. W pozostałych wypadkach "it_works" powinno być none. Jeżeli zażyczy sobie change_instruction_to_if_then albo change_instruction_to_print, wówczas w następnej iteracji należy odpowiednio zmienić wejście na instruction_if_then albo instruction_print. Druga zmienna wyjściowa steruje tym, co należy zmienić.

W tym przykładzie Perkun przechodzi przez wszystkie możliwe "programy" i prosi o ich wykonanie. Możecie oczywiście dla każdego dać false. Jeżeli dla któregoś dacie true wówczas Perkun nabierze przekonania, że ten właśnie program jest poprawny i będzie w kółko prosił o jego wykonanie.

W katalogu perkun-0.1.7/examples znajdziecie więcej przykładów Perkuna, m.in. pochodzące z tej gry (Perkun Wars) pliki example2_dorban.perkun
example3_pregor.perkun. To jest może bardziej przemawiające do wyobraźni. Wyobraźcie sobie, że są trzy miasta - Wyzima, Novigrad i Shadizar. W jednym z nich jest wampir. Dorban to jeden z bohaterów kontrolowany przez Perkuna (jeden z NPC). Jest on wiedźminem i poluje na wampira. Uruchomcie:

perkun example2_dorban.perkun

Przejdziemy do trybu interaktywnego. Pierwsza zmienna wejściowa to lokalizacja (miasto poprzedzone napisem "place_"). Druga zmienna wejściowa mówi, czy widzimy wampira. Wstukajcie "place_Wyzima false". Perkun zdecyduje, że Dorban ma iść do Shadizaru. Wstukajcie teraz "place_Shadizar false". Kolejna decyzja - idź do Novigradu (Perkun jest teraz przekonany, że wampir jest właśnie tam). Wstukajcie "place_Novigrad true". Decyzja będzie teraz brzmiała "nic nie rób" (do_nothing). Z kolei w pliku example3_pregor.perkun mamy specyfikację dla NPC, który unika wampira. Różni się ona głównie tzw. funkcją odpłaty (payoff).

To tyle na razie, mam nadzieję, że kogoś zainteresowałem. Ten algorytm to moje odkrycie, nie mam na niego dowodu, ale wydaje się, że działa. Gdyby ktoś był zainteresowany samym algorytmem - jest w pliku src/optimizer.cc.

przydałaby sie historia poprzednich komend w interpreterze, tzn klikam strzałke do gory: chciałabym zobaczyć ostatnio wpisaną komende a nie ^[[A. No i tab autocompletion: wpisuje instruction_if[TAB] i reszta komendy zostaje automatycznie wpisana

lambdadziara napisał(a):

przydałaby sie historia poprzednich komend w interpreterze, tzn klikam strzałke do gory: chciałabym zobaczyć ostatnio wpisaną komende a nie ^[[A. No i tab autocompletion: wpisuje instruction_if[TAB] i reszta komendy zostaje automatycznie wpisana

Dzięki za odzew. Jestem bardzo wdzięczny. Zrobiłem to (użyłem biblioteki readline). Nowa funkcjonalność jest w Perkunie 0.1.8. Zmiana dotyczyła głównie funkcji optimizer_with_all_data::get_input. Ten pakiet zawiera też język o nazwie Wlodkowic, który jest nieco bardziej skomplikowany. Zmiany zrobiłem tu i tu. Sprawdziłem też, że Perkun Wars kompiluje się z nowym Perkunem (tylko trzeba odpalić configure).

https://sourceforge.net/projects/perkun/

Nie wiem o ch chodzi ale wygląda na to, że masz łeb, więc chociaż plusa moge dać :D

baant napisał(a):

Nie wiem o ch chodzi ale wygląda na to, że masz łeb, więc chociaż plusa moge dać :D

Pomyślałem, że powinenem może przedstawić lepiej sam algorytm. Znajdziecie go w implementacji klasy perkun::optimizer, w pliku src/optimizer.cc. Składa się z czterech funkcji:

populate_belief_for_consequence
get_consequence_probability
get_payoff_expected_value_for_consequences
get_optimal_action

Kiedy Perkun wykonuje instrukcję "loop" (wchodzi do trybu interaktywnego) wówczas wywołuje w pętli funkcję get_optimal_action dla każdego inputu. Ta funkcja iteruje sobie po wszystkich możliwych akcjach i zwraca argmax z funkcji get_payoff_expected_value_for_consequences. Payoff to to co maksymalizujemy. To jest tzw. funkcja odpłaty (znajdziecie ją w każdej specyfikacji Perkuna). Na przykład Dorban "lubi widzieć" wampira, więc ma payoff 100.0 dla wartości true zmiennej do_I_see_vampire. Inne NPC odwrotnie - unikają wampira (mają payoff 100.0 dla wartości false tej zmiennej).

Funkcja get_payoff_expected_value_for_consequences iteruje po wszystkich stanach widocznych (visible states). Na przykład jeśli Dorban jest w Wyzimie i rozważa akcję "goto_Novigrad", to w funkcji get_payoff_expected_value_for_consequences rozważamy dwa możliwe stany widoczne:

place_Novigrad true
place_Novigrad false

Dla wszystkich innych stanów widocznych funkcja get_consequence_probability zwróci 0.0. Zatem po "goto_Novigrad" będziemy w Novigradzie i albo będziemy widzieć wampira albo nie. Teraz jest najciekawsze - ten fragment kodu:

belief b2(**i);
// populate the belief
populate_belief_for_consequence(b1, a, **i, b2);
		
// get optimal action
const action * a1 = get_optimal_action(b2, n-1);
			
sum += cp*((*i)->get_payoff()+get_payoff_expected_value_for_consequences(b2, n-1, *a1));

Tutaj tworzymy nowy belief (to jest rozkład prawdopodobieństwa nad możliwymi wartościami zmiennych ukrytych) i odpalamy dla tego nowego beliefu funkcję populate_belief_for_consequence. Innymi słowy zastanawiamy się jak ZINTERPRETUJEMY hipotetyczną obserwację. Jeżeli znajdziemy się w Novigradzie i zobaczymy wampira to zinterpretujemy to tak, że wampir jest właśnie w Novigradzie. A jeżeli go nie zobaczymy (a i w Wyzimie go nie było) to nasza nowa interpretacja hipotetycznej obserwacji będzie brzmiała tak: wampir jest na pewno w Shadizarze. Następnie jak widać w powyższym kodzie zastanawiamy się jaką optymalną akcję możemy wykonać WTEDY (czyli wywołujemy get_optimal_action) i doliczamy do wyniku wartość oczekiwaną funkcji payoff i wywołujemy tą samą funkcję (get_payoff_expected_value_for_consequence) dla nowego beliefu (b2).

Algorytm jest może nieco zagmatwany, ale najważniejsze jest to, że w każdym węźle drzewa gry wyobrażamy sobie interpretację hipotetycznej obserwacji i odpalamy planowanie dla tej nowej interpretacji. W minimaksie na przykład nie ma czegoś takiego, bo nie ma żadnych zmiennych ukrytych (cały stan gry jest widoczny - jak w szachach na przykład).

Jak wspominałem nie mam dowodu dla samej matematyki, która tkwi w tym algorytmie. Ja po prostu odgadłem wzór na interpretowanie obserwacji i nawet go porządnie matematycznie nie zapisałem. Mój algorytm (pętla loop) po każdej nowej obserwacji interpretuje ją na nowo - czyli odpala populate_belief_for_consequence (łatwo to znaleźć w pliku src/perkun_c.cc, funkcja perkun_loop). Czasem się zdarza, że nie może zinterpretować obserwacji, na przykład był pewny, że wampir będzie w Shadizar, a okazało się, że go tam nie było. Wtedy zatrzymuje przetwarzanie (rzuca wyjątek). Jeśli byście korzystali z Perkuna we własnych programach wówczas można to obsłużyć w nieco bardziej elastyczny sposób (w grze Perkun Wars na przykład wampir od czasu do czasu się rusza, i wtedy może się zdarzyć taka niespodzianka z interpretacją).

Zdaję sobie sprawę, że to może być ciężkie do przyswojenia, dlatego zacząłem od Perkuna jako "czarnej skrzynki" żeby Wam pokazać jak sobie radzi z optymalizacją.