Algorytm uczenia maszynowego do gry w Connect Four

14

Obecnie czytam o uczeniu maszynowym i zastanawiałem się, jak zastosować go do gry w Connect Four .

Moja obecna próba to prosty klasyfikator wieloklasowy wykorzystujący model funkcji sigmoid i metodę jeden na wszystkich.

Moim zdaniem cechami wejściowymi musi być stan (dysk odtwarzacza 1, dysk odtwarzacza 2, pusty) pól siatki 7x6 = 42.

Dane wyjściowe to numer wiersza, w którym ma zostać włożona płyta. Ponieważ jest to liczba dyskretna od 1 do 7, myślę, że można to potraktować jako problem klasyfikacji wieloklasowej.

Ale jak wygenerować przykłady szkoleń przydatne w uczeniu nadzorowanym?

Głównym celem jest zwycięstwo w grze, ale wynik nie jest oczywiście znany przy każdej kolejce oprócz ostatniej. Jeśli po prostu pozwolę dwóm graczom, którzy losowo decydują, co robić ze sobą tysiące razy, czy wystarczy po prostu wziąć wszystkie tury wykonane przez zwycięzcę każdej rundy gry jako przykłady treningu? Czy też muszę to robić w zupełnie inny sposób?

Edycja: Jak sugerowano w komentarzach, przeczytałem trochę o uczeniu się przez wzmocnienie. Z tego co wiem rozumiem, Q-Learning powinien załatwić sprawę, tj. Muszę przybliżyć funkcję Q bieżącego stanu i działanie, które należy podjąć, aby być maksymalną skumulowaną nagrodą rozpoczynającą się w tym stanie. Następnie każdym krokiem byłoby wybranie akcji, która skutkuje maksymalną wartością Q. Jednak ta gra ma zbyt wiele stanów, aby to zrobić, np. Jako tabela przeglądowa. Jaki jest więc skuteczny sposób modelowania tej funkcji Q?

Tomek
źródło
2
Google „Reinforcement Learning”
George
Okej, chyba tak naprawdę dotyczy tego problemu. Wygląda na to, że przed nami dużo czytania. Jakieś bardziej szczegółowe wskazówki lub zalecenia?
Tom
1
Gdybym wiedział więcej, opublikowałbym to jako odpowiedź :) Niestety nie mam doświadczenia w uczeniu się wzmacniającym. Zacznę od książki „Machine Learning” Toma Mitchella. Jest to bardzo dobra książka wprowadzająca, a także rozdział na temat nauki o wzmocnieniu.
George
1
To drugie, jestem ciekawy uczenia maszynowego i próbowania go poznać.
Tom
1
@Tom, istnieją lepsze sposoby „poznania” technik uczenia maszynowego. Zacznę od bardziej podstawowych technik klasyfikacji i regresji i odtąd będę kontynuować. Możesz pobrać zestawy danych z repozytorium danych uczenia maszynowego UCI, przejrzeć notatki z kursu uczenia maszynowego Andrew Ng (Stanford) i rozpocząć wdrażanie. Przejście od razu do rozwiązania problemu z połączeniem 4 za pomocą uczenia wzmacniającego wydaje się dość niezręczne i zbyt skomplikowane.
Nick

Odpowiedzi:

8

Aby zaoferować prostszą alternatywę dla uczenia się przez wzmacnianie, możesz użyć podstawowego algorytmu minimax do wyszukiwania dobrych ruchów i użyć uczenia maszynowego do oceny pozycji na planszy.

Aby to wyjaśnić, minimax buduje drzewo gry, w którym każdy węzeł jest oznaczony wynikiem od liści (1 = gracz A wygrywa, 0 = gracz B wygrywa), zakładając, że A wybiera ruchy, które maksymalizują tę liczbę, a B wybiera ruchy które to minimalizują.

O ile gra nie jest bardzo prosta, nie będziesz w stanie zbudować całego drzewa gry aż do terminali. Zamiast tego będziesz musiał zatrzymać się na niedokończonych pozycjach na planszy i ocenić heurystycznie liście (zasadniczo prawdopodobieństwo, że gracz A wygra z danej pozycji). Możesz pozwolić algorytmowi uczenia maszynowego, np. Sieci neuronowej, spróbować poznać to prawdopodobieństwo na podstawie połączenia czterech pozycji o znanych wynikach.

Aby wygenerować przykłady treningów, możesz zbudować odtwarzacz minimax za pomocą prostej heurystyki, pozwolić sobie grać tysiąc razy, używać tych gier do trenowania pierwszej sieci neuronowej, a następnie pozwolić sobie na tysiąc gier i tak dalej. Przy odrobinie szczęścia system poprawi się z każdym pokoleniem.

Piotr
źródło
2

Niedawno napisałem wpis na blogu o używaniu minimax do grania w connect cztery. Możesz zobaczyć kod w akcji tutaj . Jeśli potrzebujesz trenować swoje modele, być może możesz pozwolić, aby zagrało kilka tysięcy gier przeciwko mojej implementacji minimax.

Lukas Vermeer
źródło
Zapraszam do rozwidlenia mojego kodu na Github. github.com/lukasvermeer/minimax
Lukas Vermeer
Witamy w Stack Exchange. To jest strona pytań i odpowiedzi . Przeczytaj nasze często zadawane pytania , w szczególności jak odpowiedzieć . W szczególności nie chcemy postów zawierających wyłącznie link do odpowiedzi. Dziękujemy za Twój wkład, ale czy mógłbyś tutaj streścić główne punkty swojego posta na blogu?
Gilles 'SO - przestań być zły'
Przykro mi, ale pierwotne pytanie brzmiało: „Jak wygenerować przykłady szkoleń przydatne w uczeniu nadzorowanym?”. Podałem linki do działającego kodu, którego można użyć do ich wygenerowania. Nie widzę, jak napisanie większej ilości tekstu powyżej pomogłoby odpowiedzieć na pierwotną potrzebę.
Lukas Vermeer
„Link do potencjalnego rozwiązania jest zawsze mile widziany, ale dodaj kontekst wokół niego, aby inni użytkownicy mieli pojęcie, co to jest i dlaczego. Zawsze podawaj najistotniejszą część ważnego linku, na wypadek gdyby strona docelowa jest nieosiągalny lub zostaje na stałe offline ”. Myślę, że zrobiłem to pierwsze. To ostatnie byłoby nieistotne. Pierwotne pytanie wymaga przykładowych gier, a nie wyjaśnienia, jak wdrożyć rozwiązanie.
Lukas Vermeer