Zrozumienie AlphaZero

29

Niedawno pojawiła się wiadomość, że zespół badawczy DeepMind firmy Alphabet rozszerzył swój silnik uczenia maszynowego o grę w Shogi i szachy. Najwyraźniej po zaledwie kilku godzinach samodzielnego uczenia się, co oznacza, że ​​gra się przeciwko sobie, biorąc pod uwagę zasady gry, jego wydajność w szachach już przewyższyła osiągi najpopularniejszych obecnie silników, takich jak Stockfish 8. Osobiście nie wiem jeszcze, jak dokładnie skonfigurowano mecze, ponieważ w jakich warunkach skonfigurowano Sztokfisz, ponieważ jeśli czasy obliczeń są ograniczone, silniki są w stanie działać bardzo słabo. W każdym razie jest to bardzo imponujące osiągnięcie, ponieważ nawet jeśli okaże się, że można optymalnie skonfigurować Sztokfisz, z kilkoma dodatkowymi godzinami treningu, AlphaZero ponownie przekroczy poziom gry, co oznacza, że ​​AlphaZero jest zasadniczo silniejszy niż jakikolwiek obecny standardowy silnik szachowy oparty na heurystycznych funkcjach oceny.

Teraz, w świetle tych wiadomości, byłoby wspaniale, gdyby ktoś mógł wyjaśnić główne różnice w działaniu silnika szachowego uczonego maszynowo w porównaniu ze standardowymi silnikami, do których wszyscy jesteśmy przyzwyczajeni. Bardziej konkretnie:

  1. Czy funkcja oceny, z której korzysta AlphaZero, przeszkolona metodami uczenia maszynowego, nie jest po prostu kolejną heurystyczną funkcją oceny? Jeśli tak, czy można uczciwie powiedzieć, że podstawową różnicą między funkcjami oceny dwóch silników jest fakt, że Sztokfisz ma zoptymalizowaną funkcję oceny dostosowaną ręcznie przez ludzi, co oznacza, że ​​definicja funkcji optymalizacji jest stała, podczas gdy dla AlphaZero, funkcja oceny celu jest ciągle redefiniowana poprzez dodatkowe szkolenie (na przykład poprzez samodzielną grę)? Dzięki temu drugie podejście jest znacznie bardziej dynamiczne.
  2. Ostatecznie, niejasno mówiąc, silnik taki jak Sztokfisz, stosuje swoją funkcję oceny do drzewa możliwych ruchów, decydując, które gałęzie zatrzymać, a które opadać, a następnie poprzez głębszy betonAnaliza każdej gałęzi, ponownie poprzez funkcję oceny, dowiaduje się, która gałąź przyniosła najwyższą wartość, i która staje się główną odmianą (oczywiście istnieje wiele zaawansowanych technik wokół tego procesu, aby skutecznie przycinać to duże drzewo). Oznacza to, że dla każdej pozycji ta niezwykle konkretna procedura musi zostać powtórzona, aby Sztokfisz mógł podjąć decyzję. W przeciwieństwie do tego, wyobrażam sobie, że AlphaZero robi coś bardzo odmiennego, a mianowicie nie polega na konkretnej analizie drzewa możliwych ruchów w danej pozycji, zamiast tego jego funkcja oceny zasadniczo przypisuje wartość do tej pozycji (która intuicyjnie jest podobna do stawiania aktualna pozycja analogicznie do wszystkich innych pozycji, dla których została wyszkolona), bez konieczności wykonywania konkretówanaliza w taki sposób, jak robi Sztokfisz, a nawet człowiek. Czy to w ogóle dźwiękowy obraz działania AlphaZero lub podobnie wyszkolonych silników uczenia maszynowego?

  3. Wiemy, że przestrzeń pozycji szachowych jest na tyle duża, że ​​każda próba próbkowania wszystkich pozycji w niej byłaby w zasadzie całkowicie daremna (złożoność WYPŁATY), co sugerowałoby, że żadna ilość treningu poprzez grę własną nie byłaby wystarczająca, aby zbadałem wszystkie pozycje, więc w jaki sposób wynik końcowy może być dobry, mimo że potencjalnie zbadałem niewielki ułamek pozycji w przestrzeni poprzez grę własną? Jaki jest tutaj kluczowy pomysł w grze?

  4. Domyślam się, że AlphaZero ma bardzo optymalny sposób porównywania dowolnej pozycji, nawet jeśli nowej, z wcześniej odwiedzoną w swoim zestawie treningowym, im bliższe porównanie, tym bardziej wiarygodna ocena może być wyciągnięta z porównania. Na przykład, kiedy grał ruch Bg5 w grze 5 , musiał zbadać podobną strukturę podczas treningu, tj. Jest w stanie rozpoznać, że ta pozycja jest zasadniczo równoważna (być może całkowicie) innej pozycji badanej podczas treningu, w analogia do tego, w jaki sposób rozpoznawanie twarzy jest osiągane przez uczenie maszynowe, i w rezultacie stwierdza, że ​​Bg5 powinien być najlepszym posunięciem, tak jak miało to miejsce na tej (lub tych) innych podobnych pozycjach. Czy to w ogóle poprawne przypuszczenie? Nie mam pojęcia, jak to porównanie jest zrobione, ponieważ na pewno nie jest możliwe zapamiętanie wszystkich wyszkolonych pozycji i ich analizowanie za każdym razem.

Jest to jedynie próba uzyskania tak wglądu w funkcjonowanie AlphaZero i w jaki sposób podejmowana jest decyzja na danym stanowisku.

użytkownik929304
źródło

Odpowiedzi:

18
  • Jak AlphaZero wybiera ruch w wyszukiwaniu?

Jest to bardzo oczywiste z pracy.

Każda symulacja przebiega przez wybranie w każdym stanie ruchu z małą liczbą odwiedzin, wysokim prawdopodobieństwem ruchu i wysokim wyborem doliny ...

Co to znaczy? AlphaZero wyszkolił prawdopodobieństwo każdego ruchu (koniec strony 2 w pracy) z głębokiej sieci neuronowej. Podczas wyszukiwania wybiera ruch proporcjonalny do tego prawdopodobieństwa, a także węzły o niskiej liczbie (aby zapewnić zbadanie przestrzeni próbkowania). To nie jest nowa koncepcja, Monte Carlo Tree Search było w literaturze zanim istniało Google.

------ (Bardzo) Szorstki przykład ------

Mamy pozycję i mamy dwa legalne ruchy.

  • Ruch 1 jest dobry i rozsądny
  • Ruch 2 naraża twojego króla na niebezpieczeństwo bez odszkodowania

Według artykułu wyszkolony model głęboki może oszacować prawdopodobieństwo na (0,90; 0,10). Załóżmy, że AlphaZero używa 4 iteracji w Monte Carlo. Iteracje mogą wyglądać następująco:

Iteracja 1 : Wybierz ruch 1, ponieważ ma największe prawdopodobieństwo. Wykonaj symulację z ruchu 1. Iteracja 2 : Wybierz ruch 1, ponieważ ma największe prawdopodobieństwo. Wykonaj symulację z ruchu 1. Iteracja 3 : Wybierz ruch 1, ponieważ ma największe prawdopodobieństwo. Wykonaj symulację z ruchu 1.

Teraz jesteśmy w iteracji 4. Chociaż ruch 1 ma większe oszacowane prawdopodobieństwo, ale ruch 2 nie został przeszukany („mała liczba odwiedzin” w dokumencie), teraz AlphaZero wybierze ruch 2 i wykona symulację.

Oba ruchy zostaną wzięte pod uwagę, ale AlphaZero zwiększy zasoby obliczeniowe na ruch 1 (dobra rzecz).

AlphaZero wybierze następnie ruch z najlepszym oczekiwanym rezultatem.

------------------ Twoje pytania: ------------------

Czy funkcja oceny, z której korzysta AlphaZero, przeszkolona metodami uczenia maszynowego, nie jest po prostu kolejną heurystyczną funkcją oceny?

Wprawne Funkcja oceny jest głęboka sieć neuronowa, to nie zbiór reguł heurystycznych, jak to, co można zobaczyć w Sztokfisz. Nikt nie rozumie w pełni (nawet zespół Google) wyszkolonej sieci, to po prostu działa. Tak ogólnie działa NN.

podczas gdy w AlphaZero funkcja oceny celu jest ciągle redefiniowana poprzez funkcję oceny celu jest ciągle redefiniowana poprzez dodatkowe szkolenie.

Funkcja oceny w AlphaZero to zestaw wyszkolonych neuronów (obciążenie + obciążenia). Zespół Google użył bardzo potężnych maszyn do szkolenia parametrów. Ogólnie rzecz biorąc, im więcej zasobów możesz zainwestować w szkolenie modelu głębokiego uczenia się, tym lepsze parametry uzyskasz.

(2).

Sztokfisz używa alfa-beta, a AlphaZero używa Monte-Carlo. Są to dwa bardzo różne algorytmy. Algorytm alfa-beta zakłada dolną / górną granicę, podczas gdy Monte-Carlo tworzy symulacje od nasady do liścia.

zbadać wszystkie pozycje, więc w jaki sposób wynik końcowy może być dobry, mimo że potencjalnie zbadałem niewielki ułamek pozycji w przestrzeni poprzez grę własną? Jaki jest tutaj kluczowy pomysł w grze?

Google nie twierdził, że rozwiązali szachy, nawet ich potężne maszyny nie są w stanie wyliczyć wszystkich pozycji w szachach. Ale nie musieli ... o to chodzi w uczeniu maszynowym, model „uczy się” z zestawu szkoleniowego. W tym przypadku zestaw treningowy pochodzi z gry własnej. Kluczową ideą jest rozegranie jak największej liczby gier dobrej jakości przeciwko sobie i jak najszybciej.

Na przykład, kiedy grał ruch Bg5 w grze 5, musiał zbadać podobną strukturę podczas treningu,

Nie sądzę, żeby AlphaZero napotkał dokładnie taką samą pozycję w grach szkoleniowych. Myślę, że szybkie przeczytanie Monte-Carlo jest dobrym pomysłem:

https://chessprogramming.wikispaces.com/Monte-Carlo+Tree+Search

AlphaZero był w stanie zagrać ruch osiągając wystarczającą głębokość. Algorytm szacuje oczekiwane prawdopodobieństwo wygranej dla każdego ruchu, najwyraźniej ruch Bg5 dał najwyższe oczekiwane prawdopodobieństwo.

Można pomyśleć, że AlphaGo był w stanie tak dobrze przeszukać, że zobaczył, że prawdopodobieństwo wygranej jest najwyższe po Bg5, podczas gdy Sztokfisz nie traktował tego ruchu poważnie (i dlatego przegrał).

SmallChess
źródło
2
„Wyszukiwarka drzew w Monte Carlo istniała w literaturze zanim Google istniał”. Mogę prześledzić MCTS tylko do około 2006 roku.
CodesInChaos
2
@CodesInChaos MCTS nie jest nową techniką. Google z pewnością nie wynalazł Monte Carlo.
SmallChess,
4
Brügmann 1993 to oczywiście tylko MC. MC Go Dev. (2003) łączy MC i drzewa, ale w prymitywny sposób. Chang (2005) jest dość blisko, ale w innym kontekście i myślę, że wciąż brakuje mu odpowiedniego wyboru węzła do rozszerzenia i propagacji oszacowań. Wydajna selektywność i operatory tworzenia kopii zapasowych w MCTS Remi Coulom (2006) jest właściwym MCTS, o ile mogę powiedzieć, pierwszym.
CodesInChaos
1
@SmallChess Części twojej odpowiedzi wydają się być sprzeczne: „teraz AlphaZero wybierze ruch 2 i wykona symulację. Oba ruchy zostaną wzięte pod uwagę, ale AlphaZero zwiększy zasoby obliczeniowe na ruch 1 (dobra rzecz)”. zaprzecza stwierdzeniu Każda symulacja przebiega przez wybranie w każdym stanie ruchu z małą liczbą odwiedzin ... jak w twoim przykładzie byłoby to 2 zamiast 1. Szczerze mówiąc, artykuł nie zawiera żadnych użytecznych informacji zrozumienie, ponieważ nie pokazują one sposobu na odtworzenie eksperymentu ani nie dają żadnego wglądu w faktyczny sposób, w jaki szkolą sieci.
gented
1
To, co oni robią, to w zasadzie stwierdzenie „zastosowaliśmy algorytm X i działa” - co zapewnia niewiele lub wcale brak zrozumienia samych metod, więc nie skupiałbym się zbytnio na samym papierze, aby dowiedzieć się, co on naprawdę robi.
gented
0

Myślę, że moim pytaniem byłoby, w jaki sposób sieć neuronowa „uczy się”, co robić w pozycji, z którą się nie spotkała. Powiedzenie, że rzeczywisty AZ wykonuje MCTS za pomocą obciążników + obciążenia z wyuczonej sieci neuronowej, po prostu przesuwa go o krok wstecz w tym, jak sieć neuronowa oblicza te wartości. Jeśli to przez losową grę własną, bez ludzkiej wiedzy, to jak decyduje, jak zważyć pozycję, której nigdy nie widział?

Roy Koczela
źródło
1
Myślę, że mogę ci odpowiedzieć, ale nie tutaj. Rozpocznij nowe pytanie.
SmallChess,