Algorytm kłamcy - Svarog, Dorban + prekalkulacja

Algorytm kłamcy - Svarog, Dorban + prekalkulacja
Paweł Biernacki
  • Rejestracja:ponad 5 lat
  • Ostatnio:22 dni
  • Postów:176
1

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/

YA
  • Rejestracja:prawie 10 lat
  • Ostatnio:około 3 godziny
  • Postów:2363
1

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

Paweł Biernacki
  • Rejestracja:ponad 5 lat
  • Ostatnio:22 dni
  • Postów:176
0
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:

Kopiuj
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:

Kopiuj
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":

Kopiuj
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.

Kopiuj
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.

SZ
  • Rejestracja:22 dni
  • Ostatnio:21 dni
  • Postów:1
1

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ą.

Zobacz pozostały 1 komentarz
SZ
Miałem ten problem na interview i też jak noob liczyłem wszystkie kombinacje i było ich nieskończoność, a wystarczyło trochę macierze pomnożyć. I dało się to skrócić bo tak masz zawsze jakieś prawdopodobieństwo pójścia w jakimś kierunku i możesz w pętli chodzić w nieskończoność bez dojścia do stanu końcowego terminal state. Bez tego algorytmu musisz brute force męczyć, jak będziesz robił 50-100 przejść to w końcu ilość kombinacji będzie zbyt duża, a ten algorytm jakoś wylicza od razu, rozprawia się z nieskończonością.
SZ
Drunkard walk, ciekawe używam tego algorytmu na co dzień i jest naprawdę skuteczny, ostatnio jakąś dziewczynę wyrwałem po drugiej wiadomości, niby niepozorny algorytm, ale działa, od razu numer dostałem.
SZ
Mój ulubiony algorytm to expectation maximization, chicken and eggs problem rozwiązuje czyli gdzie coś potrzebne do rozwiązania problemu jest potrzebne, żeby rozwiąząć i się można zapętlić. Zamiast średnich masz uogólnienie czyli każdą zmienną mnożysz razy prawdopodobieństwo i uogólniasz wszystko poziom wyżej.
SZ
Implementowałem ostatnio monte carlo particle filter, bayesa filter. Zajebisty algorytm, dane z lidara porównujesz do wirtualnych cząstek i te co najlepiej odzwierciedlają to co widać z sensorów to im dajesz większe prawdopodobieństwo bo są najbardziej zbliżone do danych z sensorów. I w tych miejsach samplujesz więcej tych cząstek gdzie jest większe prawdopodobieństwo i na końcu zostajesz tylko z miejscem gdzie znajdujesz się, tam wszystkie cząstki są skupione, tak genialny i piękny algorytm. Implementowałeś prawdopodobieństwo over function? nie pojedyncze, a całą funkcję.
SZ
Gaussian process jest zajebisty, na podstawie tego jest bayesian optymization zbudowane, czyli funkcję prawdopodobieństwa masz, a nie pojedynczą zmienną, też widzisz gdzie masz niepewność pomiarów i wiesz że samplowanie w tym miejscu poprawi bardziej funkcję niż w innych miejscach jest to szczególnie dobre jak obliczenia są kosztowne i musisz roztropnie próbkować co miejsca funkcji, co chcesz sprawdzić.
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)