AlphaGo Zero: tak $Q(s_t, a)$ zdominować $U(s_t, a)$ w trudnych stanach gry?

Dec 03 2020

AlphaGo Zero

AlphaGo Zero wykorzystuje wyszukiwanie w drzewie Monte-Carlo, w którym zarządza faza selekcji $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, gdzie:

  1. parametr eksploatacyjny to $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (tj. średnia wartości $v_i$ wszystkich symulacji przechodzących przez krawędź $(s_t, a)$)
  2. parametrem eksploracji jest $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (tj. wcześniejsze prawdopodobieństwo $P(s_t, a)$ważona stałą $c_{puct}$, liczba przeprowadzonych symulacji $(s_t, a)$, a także liczbę przeprowadzonych symulacji $s_t$).

Wcześniejsze prawdopodobieństwo $P(s_t, a)$ i wartość symulacji $v_i$ oba są generowane przez głęboką sieć neuronową $f_{\theta}(s_t)$:

Ta sieć neuronowa przyjmuje jako dane wejściowe surową reprezentację tablicy s pozycji i jej historii, i generuje zarówno prawdopodobieństwa ruchu, jak i wartość (p, v) = fθ (s). Wektor prawdopodobieństw ruchu p reprezentuje prawdopodobieństwo wybrania każdego ruchu a (w tym pasowania), pa = Pr (a | s). Wartość v jest oceną skalarną, szacującą prawdopodobieństwo wygranej obecnego gracza z pozycji s.

Moje zmieszanie

Moje zamieszanie jest takie $P(s_t, a)$ i $v_i$ są prawdopodobieństwami znormalizowanymi do różnych rozkładów, w wyniku czego $v_i$ jest około 80 razy większy niż $P(s_t,a)$ średnio.

Wyjścia sieci neuronowej $(p, v)$, gdzie $p$ jest podanym wektorem prawdopodobieństwa $s_t$, znormalizowane względem wszystkich możliwych działań w tej turze. $p_a = P(s_t, a)$ to prawdopodobieństwo wyboru działania $a$ w danym stanie $s_t$. Gra w Go ma około 250 ruchów na turę, więc średnio każdy ruch ma prawdopodobieństwo$\frac{1}{250}$, tj $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$

Z drugiej strony, $v$ to prawdopodobieństwo wygrania danego stanu $s_t$, znormalizowane dla wszystkich możliwych warunków końcowych (wygrana / remis / przegrana). Dla uproszczenia załóżmy$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, gdzie gra toczy się losowo, a każdy wynik jest równie prawdopodobny.

Oznacza to, że oczekiwana wartość $v_i$ jest co najmniej 80 razy większy niż oczekiwana wartość $P(s_t, a)$. Konsekwencją tego jest to$Q(s_t, a)$ jest co najmniej 80x większy niż $U(s_t, a)$ średnio.

Jeśli powyższe jest prawdą, etap selekcji będzie zdominowany przez $Q(s_t, a)$ więc AlphaGo Zero powinno starać się unikać krawędzi bez symulacji (krawędzi gdzie $Q(s_t, a) = 0$) chyba że wszystkie istnieją $Q(s_t, a)$ terminy są bardzo małe ($< \frac{1}{250}$) lub MCTS ma w sobie tyle symulacji, że plik $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ termin w $U(s_t, a)$wyrównuje wielkości tych dwóch składników. To drugie raczej się nie wydarzy, ponieważ uważam, że AlphaGo Zero używa tylko$1,600$ symulacje na ruch, tak $\sqrt{\sum_b N(s_t, b)}$ limity na $40$.

Wybieranie tylko wykonalnych ruchów

Idealnie byłoby, gdyby MCTS nie wybierał każdego możliwego ruchu do zbadania. Powinien wybierać tylko wykonalne ruchy w danym stanie$s_t$i zignoruj ​​wszystkie złe ruchy. Pozwolić$m_t$ to liczba wykonalnych ruchów dla stanu $s_t$, i pozwól $P(s_t, a)$ = 0 dla wszystkich ruchów $a$które nie są opłacalne. Załóżmy również, że MCTS nigdy nie wybiera ruchu, który nie jest wykonalny.

Wtedy poprzedni rozdział jest częściowo złagodzony, bo teraz $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. W rezultacie,$Q(s_T, a)$ powinno być $\frac{m_t}{3}$ razy większy niż $U(s_t, a)$średnio . Zarozumiały$m_t \le 6$, to nie powinno być zbyt dużego problemu

Oznacza to jednak, że AlphaGo Zero działa idealnie tylko wtedy, gdy liczba wykonalnych ruchów jest niewielka. W stanie gry$s_t$ gdzie jest wiele wykonalnych ruchów ($>30$) (np. trudny zakręt z wieloma możliwymi wyborami), faza selekcji MCTS ulegnie pogorszeniu, jak opisano w poprzedniej sekcji.

pytania

Myślę, że moje pytania to:

  1. Czy moje rozumienie jest prawidłowe, czy też gdzieś popełniłem błąd (y)?
  2. Robi $Q(s_t, a)$ zwykle dominują $U(s_t, a)$o tyle w praktyce, gdy stan gry ma wiele wykonalnych ruchów? Czy faza selekcji jest zwykle zdominowana przez$Q(s_t, a)$ podczas tych stanów gry?
  3. Czy fakt, że $Q(s_t, a)$ i $U(s_t, a)$ bycie w tak różnych rzędach wielkości (gdy stan gry ma wiele wykonalnych ruchów) wpływa na jakość algorytmu MCTS, czy też MCTS jest odporny na ten efekt i nadal tworzy wysokiej jakości polityki?
  4. Jak często zdarza się, że stan gry ma wiele wykonalnych ruchów (> 30) w Go?

Odpowiedzi

2 DennisSoemers Dec 05 2020 at 03:08

Myślę, że niekoniecznie popełniłeś jakieś prawdziwe błędy w swoich obliczeniach lub coś w tym rodzaju, to wszystko wydaje się dokładne. Nie mogę z całą pewnością odpowiedzieć na Twoje pytania dotyczące „Czy X zwykle się zdarza?” lub „Jak często występuje X?”, musielibyśmy poeksperymentować, aby to sprawdzić. Myślę, że możemy również z całą pewnością natychmiast odpowiedzieć na pytanie, czy MCTS jest solidne i nadal może tworzyć wysokiej jakości zasady, odpowiadając „tak”, ponieważ widzieliśmy najnowocześniejsze, nadludzkie wyniki w wielu grach wykorzystujących te techniki .

Ale myślę, że jest kilka ważnych szczegółów, które mogą zmienić twoje postrzeganie:

  1. MCTS nie porównuje $Q(s, a)$ wartości do $U(s, a)$wartości w fazie selekcji. Porównuje$Q(s, a) + U(s, a)$ przejawy działań $a$, do $Q(s, b) + U(s, b)$ wyrażenia dla różnych działań $b$. A więc różnica w wielkościach$Q(s, a) - U(s, a)$ nie jest tak ważna, jak różnica w wielkości $Q(s, a) - Q(s, b) + U(s, a) - U(s, b)$!

  2. Dla dowolnego stanu $s$, z pewnością nie jest tak, że spodziewamy się czegoś innego $Q$-wartości mieć ładną średnią $0.5$czy coś takiego. Prawdopodobnie będzie wiele stanów$s$gdzie już jesteśmy na tak mocnej pozycji, że możemy sobie pozwolić na popełnienie jednego lub dwóch błędów i nadal oczekiwać wygranej; wszystkie$Q$ wartości tutaj będą bliskie $1.0$. Będzie też wiele stanów, w których jesteśmy w tak okropnej sytuacji, że spodziewamy się przegrać bez względu na wszystko; wszystkie$Q$ wartości tutaj będą bliskie $0.0$. A potem będą oczywiście stany, co do których sieć nie jest pewna, a które będą miały$Q$wartości gdzieś pomiędzy. Podejrzewam, że „pomiędzy” nie często będzie jednak miłym połączeniem wszelkiego rodzaju różnych wartości. Jeśli to jest coś takiego$0.7$, a są wyższe wartości, które przyciągają więcej uwagi, podczas szkolenia sieć MCTS + prawdopodobnie będzie bardzo zainteresowana dowiedzeniem się więcej o tym stanie i bardzo szybko dowie się, czy to naprawdę powinno być $1.0$czy też należy go opuścić. Z tego powodu wyobrażam sobie, że w stanach niepewnych wartości będą miały tendencję do unoszenia się wokół$0.5$.

  3. MCTS pozwoli tylko $Q(s, a)$termin zdominuje fazę selekcji tak długo, jak długo jest przekonany, że może to rzeczywiście doprowadzić do wygranej . Jeśli to prawda i rzeczywiście prowadzi do wygranej, to świetnie, nie ma potrzeby odkrywania niczego więcej! Jeśli podczas przeszukiwania drzewa dalsze badanie tego działania doprowadzi MCTS do przekonania, że ​​w rzeczywistości jest to strata, plik$Q$ wartość spadnie (najlepiej w kierunku $0$), a wtedy automatycznie przestanie być terminem dominującym. Jeśli wyszukiwanie drzewa nie dostosuje się do tego na czas, a my i tak będziemy wędrować tą ścieżką utraty, otrzymamy sygnał wartości o wartości$0$ na koniec zaktualizuj naszą sieć wartości, a w przyszłości będziemy wiedzieć, że lepiej nie powtarzać tego błędu.