dorban - demo dla biblioteki Svarog - Sztuczna Inteligencja

Witam wszystkich,
Zarwałem noc, ale dokończyłem pierwszą wersję Dorbana, to demo oparte na moim języku o nazwie Svarog, o którym już Wam pisałem. Dorbana można ściągnąć z https://sourceforge.net/projects/dorban/ a Svaroga (będzie potrzebny) z https://github.com/pawelbiernacki/svarog.

Celem zabawy jest zabicie wampira. Tak naprawdę nie da się go zabić, można tylko starać się go atakować. Chodzi o to, żeby mieć możliwie duże szanse. Jest pięć miast połączonych krawędziami, taki prosty graf. Użytkownik gra Pregorem, który ma nadludzkie możliwości (może nawet teleportować się do dowolnego miasta niezależnie od tego gdzie jest). Może też się zabić i zmartwychwstać. Drugim graczem jest Dorban, kontrolowany przez interpreter Svaroga. Stara się on namówić Pregora, żeby mu towarzyszył, a poza tym stara się znaleźć wampira i atakować go. Wampir się nie rusza, ale i tak jest ciekawie. Jeżeli Dorban namówi Was, żeby mu towarzyszyć należy używać menu itema "follow orders" żeby wykonywać jego polecenia. Zawsze można zmienić zdanie i po prostu odejść.

To demo jest przeznaczone raczej dla osób, które interesują się Sztuczną Inteligencją.

Na mojej stronie www.perkun.org opisuję jak skonfigurować Svaroga tak, żeby działał trochę szybciej, przy użyciu svarog-daemon'ów. To się odnosi również do Dorbana. Niestety Dorban jest stosunkowo wolny, ja korzystam z trzech/czterech maszyn i jeden ruch potrafi zająć kilkadziesiąt minut.

Choć projekt wygląda interesująco, to mam problem ze zrozumieniem w jaki sposób działa (nie mówiąc już o uruchomieniu lokalnie) - myślę, że nie zaszkodziłby jakiś poradnik tłumaczący co, jak i po co :-)

Rozumiem, że nie chce Wam się zajmować programem, który działa tak wolno. Ale dokonałem pewnego odkrycia, które znacznie przyspieszy dorbana. To delikatna kwestia, ale pozwolę sobie na takie porównanie - odkryłem coś w rodzaju "religii" dla moich inteligentnych agentów.

Dzisiaj zrobiłem release nowego Svaroga (wersja 0.0.4), która potrafi z normalnej specyfikacji zrobić specyfikację zawierającą "prekalkulowaną wiedzę" w formie reguł, W praktyce piszemy najpierw specyfikację, a potem zapuszczamy komputer na kilka dni żeby ją przeanalizował. W rezultacie mamy zbiór reguł postaci:

<stan_widoczny> x <belief> -> <optymalna_akcja>

Ten pierwszy zbiór jest niewielki, w przypadku dorbana zawiera 120 elementów. Drugi (zbiór beliefów) jest niestety ciągły i, zależnie od ilości możliwych stanów dla danego stanu widocznego jest n-wymiarową hiperkulą. Wpadłem na pomysł, żeby go zdyskretyzować. Na przykład dla trzech stanów i parametru, który nazywam granularity (ziarnistość) o wartości 2 mamy następujące punkty w tej hiperkuli:

(0,0,1)
(0,1,0)
(0,1,1)
(1,0,0)
(1,0,1)
(1,1,0)
(1,1,1)

Właściwie to jest hiperkostka (hypercube), akurat tutaj trójwymiarowa. Po normalizacji (bo beliefy są rozkładami) otrzymujemy:

(0.0,0.0,1.0)
(0.0,1.0,0.0)
(0.0,0.5,0.5)
(1.0,0.0,0.0)
(0.5,0.0,0.5)
(0.5,0.5,0.0)
(0.33,0.33,0.33)

Czyli w tym wypadku wystarczy siedem reguł, żeby pokryć całą trójwymiarową kostkę dla danego stanu widocznego.

Niestety zdarza się, że ilość możliwych stanów jest tak duża, że nawet dyskretyzacja nie pomaga. Wówczas Svarog zaznacza, że dany stan widoczny jest zbyt złożony (too complex). Wtedy żadnych reguł nie generuje, ale to nic nie szkodzi.

Nazywam to "religią" bo moje reguły zawierają tylko informację o optymalnej akcji, bez żadnego uzasadnienia, ale obliczoną dla dużej głębokości drzewa gry (właśnie teraz mój komputer liczy tą prekalkulowaną wiedzę dla głębokości drzewa gry 4). Jeżeli sobie ściągniecie nowego Svaroga - https://github.com/pawelbiernacki/svarog wówczas w katalogu examples znajdziecie plik example6_precalculated.svarog. On zawiera właśnie taką prekalkulowaną wiedzę, niestety tylko dla głębokości 1.

Po dyskretyzacji zbioru beliefów mamy pewną ilość reguł z n-wymiarowymi punktami reprezentującymi beliefy. Łatwo więc w trakcie planowania użyć kartezjańskiej miary dystansu od prawdziwego beliefu, na przykład dla trójki (0.25,0.25,0.5) najbliższy będzie punkt (0.33,0.33,0.33).

Taka specyfikacja z prekalkulowaną wiedzą jest wprawdzie spora, example6_precalculated.svarog zawiera 2144863 bajtów czyli trochę ponad dwa mega, ale dobra wiadomość jest taka, że już nie urośnie (po zwiększeniu głębokości drzewa gry, czyli "inteligencji"). Czyli dla dowolnej specyfikacji Svaroga możemy kazać komputerowi prekalkulować wiedzę (wygenerować nową specyfikację z tymi regułami) i choćby to trwało miesiąc - za to w czasie wykonania svarog (a więc i dorban) będzie śmigał.

Przepraszam, że piszę w sumie sam do siebie. Chciałem tylko powiedzieć, że kiedy skończę obliczenia udostępnię dorbana 0.0.1, który będzie dużo szybszy. Wtedy będziemy mogli skupić się na sensie całego eksperymentu.

Pomyślałem, że opisanie algorytmu wykorzystania prekalkulowanej wiedzy w Svarogu na przykładzie Dorbana jest jednak bardzo specyficznym problemem i nie ma co się z tym pchać na forum. W związku z tym napisałem "książkę" (a raczej taką broszurkę) na ten temat. Z myślą o szanownych Użytkownikach 4P, zawiera trochę obrazków, wzorów (mało!) i odnosi się do kodu Dorbana napisanego w Svarogu. Po polsku. Książka jest tu. Przy okazji zapraszam na odnowioną stronę www.perkun.org.

Ostatnio rozmawiałem z moim dziecięciem na ten temat i dziecię podsuneło mi pewien pomysł jak ulepszyć prekalkulację w Svarogu. Nie będę go może teraz opisywał, bo i tak mi nie uwierzycie. Ale brzmi obiecująco.