Algorytm kłamcy - Svarog, Dorban + prekalkulacja

Mam pomysł. Pamiętacie zapewne z matematyki zasadę indukcji. Musimy pewne twierdzenie T(n) udowodnić dla n=0, a następnie udowodnić tzw. krok indukcyjny: T(n)=>T(n+1). Otóż wymyśliłem algorytm, w którym mój Svarog odpowiada T(0). A dzisiaj przyszedł mi do głowy “krok indukcyjny”. Nowy algorytm. Całkowicie analityczny i niezwiązany z sieciami neuronowymi.

Svarog jest z natury trochę ogólniejszy, ale poniżej będę wykorzystywał tylko graczy z programu “Dorban” (moje demko dla Svaroga). Dokładnie – Dorbana i wampira (Pregora pominę). To demko ma to do siebie, że, przypomnę, Dorban szuka wampira (którego chce pokonać) oraz Pregora (który może Dorbanowi pomóc), ale a priori nie wie, czy Pregor żyje, czy nie. I jeśli się przekona, że Pregor nie żyje, to szuka wampira aby go zaatakować na własną rękę.

Krok n=0: dajemy Svarogowi model “fizyki” (jak działa świat) i mówimy co dany gracz (np. Dorban) lubi, a czego unika. Następnie robimy prekalkulację tzw. policy, czyli dla każdego stanu na wejściu Dorbana ORAZ dla każdego stanu jego umysłu liczymy (w.g. algorytmu Svaroga) najlepszą pierwszą akcję. Pierwszy krok jaki Dorban wykona. Ponieważ zbiór stanów umysłu jest zbiorem ciągłym trzeba go na przykład zdyskretyzować. Ale to jest teraz mniej ważne. Obliczamy tą policy dla k kroków do przodu (horyzont). Nazwijmy tą policy P(0).

Krok n=1: tym razem z punktu widzenia wampira. Wyposażamy wampira w w model “fizyki” (wampir może się poruszać, atakować Dorbana itp.) oraz model “semantyki języka” za pomocą którego wampir może zadawać Dorbanowi pytania i/lub udzielać mu informacji. Dodatkowo dajmy mu policy P(0) i informację co wampir lubi, a czego nie. I znowu z algorytmu Svaroga liczymy optymalne akcje (tym razem dla wampira) dla k krokow do przodu. Będą wśród nich akcje podejmowane w obecności Dorbana, tj. akcje, które nie mają fizycznych konsekwencji, ale mają za cel zmianę stanu umysłu (czyli zmianę “wiary”) Dorbana. Z algorytmu Svaroga wyniknie (mam taką nadzieję!), że wampirowi opłaca się np. twierdzić, że zabił Pregora. Bo jeżeli Dorban mu uwierzy, to zgodnie z jego policy – zaatakuje wampira sam. Robimy prekalkulację policy wampira (dla k kroków do przodu). I nazywamy tą policy P(1).

Krok n=2: znowu z punktu widzenia Dorbana. Znowuż dajemu Svarogowi model “fizyki” i model “semantyki języka”. Dodatkowo dajemu mu policy P(1) (jest to policy wampira) oraz informację, co Dorban lubi a czego nie. Dorban może więc nie tylko poruszać się, atakować wampira itp. ale może też (przy spotkaniu z wampirem) komunikować się z nim. Na przykład zadawać mu pytania, albo odpowiadać na pytania wampira. Z algorytmu Svaroga wyniknie, że i Dorban może kłamać wampirowi. Dokonujemy nowej prekalkulacji policy (dla Dorbana) i otrzymujemy P(2).

Mam nadzieję w ten sposób osiągnąć “grę”, w której policy np. Dorbana (dla dostatecznie wysokiej wartości n) zawiera sensowne (w.g. algorytmu Svaroga) zachowania, nawet skomplikowane wypowiedzi. Najważniejsze, że prekalkulacja policy, która pierwotnie służyła jedynie przyspieszeniu algorytmu Svaroga stanie się integralną częścią tego nowego algorytmu – algorytmu kłamcy. Marzy mi się, żeby np. wampir był w stanie nie tylko kłamać wprost (tak, by Dorban – jeśli mu uwierzy – grał w interesie wampira), ale i kłamać pośrednio – np. sugerując, że pewną wiedzą dysponuje lub nie (gdy w istocie jest odwrotnie), albo pisząc wiadomości przeznaczone dla Dorbana, w których np. podszywa się pod Pregora itp. Jeżeli mamy trzech i więcej graczy – wówczas jeden z nich może też wprowadzać w błąd drugiego po to, aby fałszywa wiadomość dotarła do trzeciego itd.

W tym algorytmie wszyscy wiedzą jak działa świat i co kto lubi, a kłamią wyłącznie na temat wartości zmiennych ukrytych. Ale można sobie wyobrazić i kłamstwa dotyczące samej fizyki gry lub semantyki języka, jak również kłamstwa dotyczące funkcji wypłaty (optymalizowanej przez algorytm Svaroga).

http://www.perkun.org
https://sourceforge.net/projects/dorban/

W pierwszym czytaniu brzmi jak gra stochastyczna na gruncie teorii gier.

yarel napisał(a):

W pierwszym czytaniu brzmi jak gra stochastyczna na gruncie teorii gier.

Tak. Masz rację, to gra stochastyczna w warunkach niepełnej informacji. Ja niestety niewiele wiem o Teorii Gier, muszę się dokształcić. Ten "pierwszy krok", który nazywam prekalkulacją policy już zrobiłem. Pisałem o tym w innym wątku. Zdaje się jest to związane z POMDP (Partially Observable Markov Decision Process).

Zaobserwowałem, że optymalna akcja, którą należy wykonać zależy w takiej grze od tego, co gracz widzi (danych na wejściu), oraz od tego, w co wierzy (stanu umysłu - inaczej "wiary"). Jeżeli można wpłynąć na to, w co gracz wierzy, to można nim, w pewnym zakresie, sterować. W moim demku (Dorban) w katalogu svarog można znaleźć specyfikację Svaroga (plik o nazwie dorban.svarog). Prekalkulowana policy zaczyna się w tym pliku w linii 694 (to sekcja "precalculated"). Zwróćcie uwagę na linię 926:

on visible state ({has_dorban_won_a_fight=>false ,where_is_dorban=>place_Warszawa ,can_dorban_see_pregor=>false ,can_dorban_see_pregor_is_alive=>none ,can_dorban_see_vampire=>true ,is_pregor_following_dorban=>false })
	{
amount_of_possible_states = 8.00000;
max_amount_of_beliefs = 255.000;

Ten kod opisuje pewną sytuację (Dorban jest w Warszawie, nie widzi Pregora, widzi za to wampira). Prekalkulacja polega na obliczeniu optymalnej akcji oraz wartości oczekiwanej funkcji wypłaty dla pewnych wybranych "wiar" (stanów umysłu). W linii 930 mamy na przykład optymalną decyzję, jeżeli Dorban myśli, że Pregor jest w Krakowie, ale nie żyje. Wówczas optymalną decyzją jest zaatakować wampira:

on belief ({
case {where_is_vampire=>place_Warszawa ,where_is_pregor=>place_Krakow ,is_pregor_alive=>false }:1.00000;
}
)
		{
		action {optimal_action=>attack_vampire } :    8.00000;
		}

Linia 937 - jeżeli Dorban jest przekonany, że Pregor jest w Krakowie i żyje - optymalna akcja "idź do Krakowa":

on belief ({
case {where_is_vampire=>place_Warszawa ,where_is_pregor=>place_Krakow ,is_pregor_alive=>true }:1.00000;
}
)
		{
		action {optimal_action=>goto_Krakow } :    51.3000;
		}

Linia 944 jest ciekawa. Dorban jest przekonany, że Pregor jest w Krakowie, ale nie wie, czy Pregor żyje, czy nie.

on belief ({
case {where_is_vampire=>place_Warszawa ,where_is_pregor=>place_Krakow ,is_pregor_alive=>false }:0.500000;
case {where_is_vampire=>place_Warszawa ,where_is_pregor=>place_Krakow ,is_pregor_alive=>true }:0.500000;
}
)
		{
		action {optimal_action=>goto_Krakow } :    27.6500;
		}

W takim wypadku, gdyby wampir dysponował technologią pozwalającą na bezpośrednie wpływanie na stan umysłu Dorbana i gdyby miał w tym interes (np. dlatego, że łatwiej pokona Dorbana samego niż gdyby mu ktoś pomagał), może udzielić mu fałszywej informacji "is_pregor_alive=>false", która sprowokuje Dorbana do samotnego ataku na wampira. Obliczenie takiej policy dla głębokości 4 kroków naprzód w tej akurat grze trwa kilka dni, przynajmniej na moim komputerze. Opisałem dość szczegółowo w https://www.perkun.org/resources/pdf/triglav_0_0_0.pdf w jaki sposób można wykonać taką prekalkulację (rozdział 4.3.1). Trzeba oczywiście wcześniej stworzyć model fizyki gry i zapisać go w języku Svarog. Ten pomysł, który opisuję w niniejszym wątku polega na wyposażeniu wampira w wiedzę na temat policy Dorbana i zastosowaniu jej w charakterze uproszczonego modelu samego Dorbana. Jeśli prekalkulacja trwa kilka dni i miałbym mechanizm tworzenia kolejnych semantyk języka, w którym rozmawiają ze sobą wampir i Dorban, to w ciągu rozsądnego czasu (powiedzmy - miesiąca, dwóch miesięcy) mógłbym wyprodukować policy dla Dorbana na przykład dla n=6. Takie, które sterowałoby jego postępowaniem zarówno na płaszczyźnie fizycznej, jak i semantycznej - w celu wyciągania od wampira informacji, dezinformowania go itp. To już byłoby wspaniale.

Jak to maszyna stanów z losowym przejściem prawdopodobieństwa, to robić brute force to jak strzał w stopę z broni, tutaj musisz użyć absorbing markov chain i zredukujesz nieskończoną ilość przejść stanów do po prostu jego właściwego prawdopodobieństwa jakbyś w nieskończoność szedł daną ścieżką.