Kilka wątpliwości dotyczących zastosowania nauki wzmacniającej w grach takich jak szachy

9

Wynalazłem szachową grę planszową. Zbudowałem silnik, aby mógł grać autonomicznie. Silnik jest w zasadzie drzewem decyzyjnym. Składa się z:

  1. Funkcja wyszukiwania, która w każdym węźle znajduje wszystkie możliwe legalne ruchy
  2. Funkcja oceny, która przypisuje wartość liczbową do pozycji na planszy (dodatnia oznacza, że ​​pierwsi gracze zdobywają przewagę, ujemna oznacza, że ​​drugi gracz wygrywa)
  3. Algorytm przycinania algorytmu negamax

Głównym problemem związanym z tym silnikiem jest to, że optymalizacja funkcji oceny jest naprawdę trudna. Nie wiem, jakie czynniki wziąć pod uwagę i jakie wagi włożyć. Jedyny sposób, w jaki widzę ulepszenie silnika, to iteracja gier, za każdym razem próbujących różnych kombinacji czynników i wag. Jednak obliczeniowo wydaje się to bardzo trudnym wyczynem (czy mogę się rozpropagować bez korzystania z głębokiego uczenia się?).

Chciałbym wykorzystać uczenie się przez wzmocnienie, aby ulepszyć silnik, grając przeciwko sobie. Czytałem o tym temacie, ale nadal jestem dość zdezorientowany.

Jaka inna nagroda jest w grze częścią wygranej lub przegranej (1 lub 0)? Jeśli korzystam z innych nagród, takich jak dane wyjściowe z funkcji oceny na każdym kroku, jak mogę to zaimplementować? Jak zmodyfikować funkcję oceny, aby zapewnić lepszą iterację nagród po iteracji?

Pigna
źródło

Odpowiedzi:

6

Chciałbym wykorzystać uczenie się przez wzmocnienie, aby ulepszyć silnik, grając przeciwko sobie. Czytałem o tym temacie, ale nadal jestem dość zdezorientowany.

Uwaga: uczenie się przez zbrojenie to bardzo złożony temat. Chociaż może cię to ominąć od botów do grania, możesz uczyć się podstaw RL. Dobrym miejscem do rozpoczęcia jest Sutton & Barto Reinforcement Learning: An Introduction

Jaka inna nagroda jest w grze częścią wygranej lub przegranej (1 lub 0)?

W zależności od twojej gry, to zwykle jest to. W rzeczywistości w grze typu wygrana / remis / przegrana, takiej jak szachy, nagroda za każdą akcję wynosi 0, z wyjątkiem wygranej (+1) lub przegranej (-1) na końcu. W grze o sumie zerowej ładnie dopasowuje się to do minimax, przycinania alfabety itp.

Reinforcement Learning ma na celu reagowanie na środowiska z opóźnionymi nagrodami. Dodanie nagród „pomocniczych” dla tymczasowych celów bez celu zwykle przynosi efekt przeciwny do zamierzonego.

Jeśli korzystam z innych nagród, takich jak dane wyjściowe z funkcji oceny na każdym kroku, jak mogę to zaimplementować?

Zazwyczaj nie. Zastosowanie samoregulacji RL sprawi, że nauczysz się funkcji powrotu (zwanej czasem użytecznością ), która przewiduje oczekiwanie całkowitej nagrody + 1/0 / -1 do końca gry. Użyłbyś tego zamiast aktualnej heurystyki dla wyszukiwania minimax. Lub potencjalnie dostosowałbyś obecną funkcję heurystyczną do wyjścia w tym samym zakresie i użyłbyś RL do optymalizacji jej wag, aby jak najlepiej zbliżyć się do prawdziwej optymalnej funkcji powrotu do gry (która jest prawdopodobnie zbyt skomplikowana, aby ją dokładnie obliczyć).

Jak zmodyfikować funkcję oceny, aby zapewnić lepszą iterację nagród po iteracji?

To jest to, co różne podejścia RL podchodzą do wszystkich, istnieje wiele różnych rozwiązań. Nie ma krótkiego sposobu, aby to wyjaśnić. Możesz zacząć od prostej metody, takiej jak Q-Learning . Q-Learning uczy się szacunków Q (s, a) (nazywanych wartością akcji), która jest oczekiwanym zwrotem w stanie s i podejmowaniu działania a, a następnie zgodnie z optymalną polityką. Na początku można dowolnie zgadywać i udoskonalać ją bliżej prawdziwej wartości z każdym krokiem w środowisku uczenia się. Proste tabelaryczne osoby uczące się Q dokonują tego udoskonalenia, po prostu przechowując duży stół wszystkich stanów i działań z najlepszym jak dotąd oszacowaniem prawdziwej wartości i uśredniając każde nowe oszacowanie, jakie jest doświadczane.

Możliwe jest także połączenie metody RL dla heurystyki z wybiegającym w przyszłość wyszukiwaniem minimax - tak właśnie zrobiła oryginalna AlphaGo i to, co AlphaGo Zero robi podczas treningu. Jest to potężne podejście, ponieważ wyszukiwanie minimax będzie działać w celu podwójnego sprawdzenia heurystyki generowanej przez RL. Chociaż w przypadku dość prostych gier RL może nauczyć się doskonałej heurystyki i potrzebujesz tylko wyszukiwania lokalnego (jaki powinien być następny ruch).

O ile twoja gra nie jest bardzo prosta (wszystkie możliwe stany zmieściłyby się w pamięci), będziesz potrzebować pewnego rodzaju aproksymatora funkcji wewnątrz algorytmu RL. Sieci neuronowe są standardowym wyborem. Posiadanie czegoś dla tej części jest nieuniknione - chociaż innym dobrym wyborem jest zdefiniowanie szeregu funkcji proxy (które można wykorzystać do ręcznego skonstruowania heurystyki) i użycie liniowego przybliżenia - tylko ważona suma wszystkich funkcji. Może to działać wystarczająco dobrze i zostało wykorzystane na przykład w warcabach (przeciągach) graczy przeszkolonych przy użyciu RL.

W rzeczywistości, pod warunkiem, że twoja własna funkcja heurystyczna nie jest zbyt niezwykła, prawdopodobnie możesz potraktować ją jak przybliżenie liniowe i użyć RL, aby dowiedzieć się dla niej najlepszych wag.

Neil Slater
źródło
„Uczenie się przez wzmacnianie ma na celu reagowanie na środowiska z opóźnionymi nagrodami. Dodanie nagród„ pomocniczych ”dla tymczasowych celów innych niż cele jest zwykle odwrotne od zamierzonych”. Chciałbym zauważyć, że istnieje artykuł, który próbuje rozwiązać problem rzadkich nagród poprzez wprowadzenie celów pośrednich „ Hindsight Experience Replay ”.
nbro
1
@nbro: Istnieje wiele prób rozwiązania rzadkich nagród, jest to duże otwarte pytanie w RL, jednym ze sposobów na zwiększenie wyzwania związanego z problemem jest uczynienie nagród bardziej rzadkimi. Ślady kwalifikowalności to kolejna próba, Hierarchical RL to kolejny obiecujący obszar. . . Nie sądzę jednak, że chcę dodać te techniki do odpowiedzi tutaj, ponieważ chodzi bardziej o wykonalność problemu OP i wprowadzenie do tematu
Neil Slater,