Jak radzić sobie z nieprawidłowymi ruchami w uczeniu się zbrojenia?

20

Chcę stworzyć sztuczną inteligencję, która może grać w pięć w jednym rzędzie / gomoku. Jak wspomniałem w tytule, chcę do tego wykorzystać naukę wzmacniającą.

Używam metody gradientu zasad , a mianowicie REINFORCE, z linią bazową. Do przybliżenia wartości i funkcji polityki używam sieci neuronowej . Ma splotowe i w pełni połączone warstwy. Wszystkie warstwy, z wyjątkiem danych wyjściowych, są wspólne. Warstwa wyjściowa polityki ma na sobie jednostkę wyjściową $8 \times 8=64$ (rozmiar płyty) i softmax . To jest stochastyczne. Ale co, jeśli sieć ma bardzo duże prawdopodobieństwo nieprawidłowego ruchu? Nieprawidłowy ruch występuje, gdy agent chce sprawdzić kwadrat z jednym „X” lub „O”. Myślę, że może utknąć w tym stanie gry.

Czy możesz polecić jakieś rozwiązanie tego problemu?

Domyślam się, że użyję metody aktor-krytyk . Za nieważny ruch powinniśmy dać nagrodę ujemną i przekazać turę przeciwnikowi.

machine-learning reinforcement-learning game-ai combinatorial-games Molnár István
źródło

10

Po prostu zignoruj nieprawidłowe ruchy.

Do eksploracji jest prawdopodobne, że nie wykonasz ruchu z najwyższym prawdopodobieństwem, ale wybierzesz ruchy losowo w oparciu o prawdopodobieństwo wyjściowe. Jeśli tylko ukarzesz nielegalne ruchy, nadal będą zachowywać pewne prawdopodobieństwo (choćby niewielkie) i dlatego będą wykonywane od czasu do czasu (jakkolwiek rzadko). Więc zawsze zatrzymasz agenta, który czasami wykonuje nielegalne ruchy.

Dla mnie bardziej sensowne jest po prostu ustawienie prawdopodobieństwa wszystkich nielegalnych ruchów na zero i ponowna normalizacja wektora wyjściowego przed wybraniem swojego ruchu.

BlindKungFuMaster
źródło

Dziękuję Ci. Prawdopodobnie nie byłem jasny, ale wybrałem ruch losowo przez wyprowadzone probability. Spróbuję twojej porady, aby ustawić prawdopodobieństwo nielegalnych ruchów na zero i zobaczyć, co się stanie. Miłego dnia.

Molnár István

8

Zazwyczaj metody softmax w metodach gradientu polityki z wykorzystaniem aproksymacji funkcji liniowej wykorzystują następujący wzór do obliczenia prawdopodobieństwa wyboru działania $a$ . Tutaj ciężary są $\theta$ i funkcje $\phi$ jest funkcją aktualny stan $s$ oraz działania ze zbioru działań $A$ .

π (θ, a) = \frac{e^{θ ϕ (s, a)}}{\sum_{b \in A} e^{θ ϕ (s, b)}}

$\pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \in A} e^{\theta \phi(s, b)}}$

Aby wyeliminować nielegalne ruchy, ograniczono by zestaw działań tylko do tych, które były legalne, stąd $Legal(A)$ .

π (θ, a) = \frac{e^{θ ϕ (s, a)}}{\sum_{b \in L e g a l (A)} e^{θ ϕ (s, b)}}, a \in L e g a l (A)

$\pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \in Legal(A)} e^{\theta \phi(s, b)}}, \, a \in Legal(A)$

W pseudokodzie formuła może wyglądać następująco:

action_probs = Agent.getActionProbs(state)
legal_actions = filterLegalActions(state, action_probs)
best_legal_action = softmax(legal_actions)

Niezależnie od tego, czy używasz aproksymacji funkcji liniowej, czy nieliniowej (Twoja sieć neuronowa), ideą jest używanie legalnych ruchów tylko podczas obliczania softmax. Ta metoda oznacza, że agent wykona tylko prawidłowe ruchy, co jest dobre, jeśli chcesz później zmienić grę, i że różnica w wartości między ograniczonym wyborem działań będzie łatwiejsza do rozróżnienia przez agenta. Będzie także szybszy, gdy liczba możliwych akcji maleje.

Jaden Travnik
źródło

Bardzo przydatne. Dziękujemy za opublikowanie zarówno równań, jak i pseudokodu!

DukeZhou

1

Matematyka i pseudokod nie pasują tutaj. Softmax ponad prawne prawdopodobieństwa przesunięcia dostosuje względne prawdopodobieństwa. Np. (0,3, 0,4, 0,2, 0,1) przefiltrowane przy usuniętym pierwszym i trzecim elemencie byłoby (0,0, 0,8, 0,0, 0,2) według formuły, ale byłoby (0,0, 0,57, 0,0, 0,42) przy użyciu pseudokodu. Pseudokod musi pobrać logi przed obliczeniem prawdopodobieństwa działania.

Neil Slater

4

Jak obliczyć gradient przefiltrowanej wersji Softmax? Wydaje się, że byłoby to konieczne, aby propagacja wsteczna działała pomyślnie, tak?

brianberns

@brianberns Czy udało Ci się znaleźć odpowiedź? Wydaje się, że byłoby to w przypadku do mnie, ale jakoś w moim przykładzie zabawek Dostaję tylko właściwą odpowiedź przy użyciu prawdopodobieństw logarytm unfilitered Softmax ...

tryingtolearn

5

IMHO pomysł nieprawidłowych ruchów sam w sobie jest nieważny. Wyobraź sobie umieszczenie litery „X” we współrzędnych (9, 9). Możesz uznać to za nieprawidłowy ruch i dać mu ujemną nagrodę. Absurd? Pewnie!

Ale w rzeczywistości twoje nieprawidłowe ruchy to tylko relikt reprezentacji (która sama w sobie jest prosta i dobra). Najlepszym sposobem ich leczenia jest całkowite wykluczenie ich z jakichkolwiek obliczeń.

To staje się bardziej widoczne w szachach:

W reprezentacji pozycyjnej możesz rozważyć ruch a1-a8, który należy do gry tylko wtedy, gdy jest wieża lub królowa a1(i istnieją inne warunki).
W innej reprezentacji możesz rozważyć przeniesienie Qb2 . Ponownie może to, ale nie musi, należeć do gry. Gdy obecny gracz nie ma Królowej, to na pewno nie.

Ponieważ nieprawidłowe ruchy są związane raczej z reprezentacją niż z grą, nie powinny być w ogóle brane pod uwagę.

maaartinus
źródło

1

Świetny punkt W grach [M], rozgrywanych na Sudoku, ograniczenia powodują, że wiele pozycji (współrzędne + wartość) jest nielegalnych po pierwszym ustawieniu. Rozważanie tych nielegalnych pozycji z punktu widzenia umiejscowienia nie ma żadnej wartości, ale ważną warstwą strategiczną jest rozpoznanie, które umiejscowienia minimalizują wartość pozostałych, niewykorzystanych pozycji. (tj. jeśli umieszczę tutaj 8, blokuje to mojemu przeciwnikowi umieszczenie 8 w tym rzędzie, kolumnie lub regionie. Zasadniczo „ile strategicznych pozycji usuwa to miejsce z planszy?”)

DukeZhou

5

Podobny problem spotkałem ostatnio w Saper.

Sposób, w jaki to rozwiązałem, polegał na całkowitym ignorowaniu nielegalnych / nieprawidłowych ruchów.

Użyj sieci Q, aby przewidzieć wartości Q dla wszystkich swoich działań (prawidłowych i nieprawidłowych)
Przetwarzaj wstępnie wartości Q, ustawiając wszystkie nieprawidłowe ruchy na wartość Q wynoszącą zero / liczbę ujemną (w zależności od Twojego scenariusza)
Użyj wybranej polityki, aby wybrać akcję spośród wyrafinowanych wartości Q (tj. Zachłannych lub Boltzmanna)
Wykonaj wybraną akcję i wznów logikę DQN

Mam nadzieję że to pomoże.

Sanavesa
źródło

1

Jedyne, co chciałbym dodać do tego, to to, że musisz pamiętać, aby wykonać backprop na DQN, gdy ustawiasz wartości Q dla par nielegalnych (a, a) na dużą wartość ujemną, więc jest wyszkolony, aby nie wybierać tych stanów, akcji pary następnym razem.

SN

Zastanawiam się jednak, jakie ustawienie dużych wartości Q celu Q wpływa na ciągłość lub kształt funkcji straty / błędu (wpływając w ten sposób na wyszukiwanie gradientowe). Jakie było twoje doświadczenie?

SN

1

@ SN Widzę twój punkt widzenia. Chodzi o to, aby wybrać akcję o najwyższej wartości Q, która nie jest niepoprawną akcją . Następnie wykonujesz tę akcję i używasz tej akcji w regule aktualizacji (tj. Trenujesz DQN, aby faworyzować tę akcję w dłuższej perspektywie). To sprawia, że przyszłe wartości Q wybranego działania są wyższe, a zatem bardziej korzystne. To będzie nie sprawiają, że nielegalne działania Q-wartość obniżyć choć, co nie ma znaczenia, ponieważ są one zawsze odfiltrowane (nie brane pod uwagę). Daj mi znać, jeśli chcesz, abym rozwinął więcej z przykładem. :)

Sanavesa,

1

@Sanavesa na pewno ma sens, zasadniczo liczysz na to, że DQN w końcu dowie się, jakie są właściwe wybory w szkole twardych puknięć. Ale w sytuacjach, gdy istnieje tylko jeden lub kilka legalnych wyborów, kończysz się bardzo powolną nauką. Podejście, które sugeruję, to sposób na włączenie domeny K do problemu, aby przyspieszyć naukę. To również, co myślałem, że robisz w swoim oryginalnym poście, w którym napisałeś o „ustawianiu nieprawidłowych ruchów na wartość Q wynoszącą zero / liczbę ujemną”

SN

1

@SNPrecisely! Oba podejścia mają swoje zalety. Zależy od aplikacji, jeśli łatwiej jest nauczyć się legalnych ruchów lub po prostu je zignorować. Wydaje mi się, że w przypadku dużych złożonych aplikacji ignorowanie nieprawidłowych ruchów jest o wiele szybsze, aby agent się nauczył, ale nie cytuj mnie.

Sanavesa,

Jak radzić sobie z nieprawidłowymi ruchami w uczeniu się zbrojenia?

Odpowiedzi: