Jak zaprojektowałbyś system uczenia maszynowego do gry w Angry Birds?

Po zagraniu zbyt dużej ilości Angry Birds zacząłem obserwować własne strategie. Okazuje się, że opracowałem bardzo specyficzne podejście do uzyskania 3 gwiazdek na każdym poziomie.

To sprawiło, że zastanawiałem się nad wyzwaniami związanymi z opracowaniem systemu uczenia maszynowego, który byłby w stanie grać w Angry Birds. Interakcja z grą i wypuszczanie ptaków jest banalna. Ale jedno pytanie, które zadałem, dotyczy „elementów składowych” systemu.

Wydaje się, że systemy uczenia maszynowego działają w oparciu o proste pojęcia lub zrozumienie problemu. Jest to często kodowane jako funkcje jako dane wejściowe. Wygląda więc na to, że system musi być w stanie zrozumieć niektóre koncepcje wysokiego poziomu, aby wygenerować strategię.

Czy to prawda? Jakie są wyzwania lub trudne części związane z opracowaniem takiego systemu?

EDYCJA 1:

Oto wyjaśnienie. Zdobycie 3 gwiazdek to trudny problem, ponieważ musisz zmaksymalizować liczbę punktów. Można to zrobić na dwa niewyłączne sposoby: 1) Minimalizując liczbę wykorzystanych ptaków (dostajesz 10 000 punktów za każdy nieużywany ptak). 2) Maksymalnie zniszczył szkło, drewno i inne przedmioty. Każdy zniszczony obiekt daje punkty. Za pomocą jednego ptaka można zniszczyć obiekty o wartości ponad 10 000 punktów.

Oto trochę więcej wyjaśnień na temat „koncepcji wysokiego poziomu”. Aby zmaksymalizować punkty opisane powyżej, musisz użyć specjalnych mocy każdego ptaka. Oznacza to więc wystrzeliwanie różnych ptaków o różnych trajektoriach, w zależności od układu mapy. Podczas gry opracowuję strategię, która niszczy określone obszary pewnymi ptakami w określonej kolejności.

Wygląda na to, że bez zrozumienia, jak wykorzystać każdego ptaka do zniszczenia określonego obszaru, system nie mógł nauczyć się zdobywać 3 gwiazdek. Jak więc zarządzasz i kodujesz coś takiego? Jak zapewnić, że system może nauczyć się tych pojęć wysokiego poziomu?

Zakładając, że możesz wprowadzić odpowiednie haczyki do oprogramowania (lub pracujesz z własną makietą), niektóre rzeczy byłyby tutaj łatwe, a inne mniej. Myślę, że to dość trudny problem. Jak wspomniano carlosdc, Reinforcement Learning (RL) jest jedną z możliwych dróg , chociaż nie jestem pewien, czy jest to właściwa droga.

Gdy zaczynasz, trzeba określić, co swoją przestrzeń stanów , przestrzeń działania , dynamika przejściowe , a funkcja nagroda są. Przestrzenie stanu / akcji mogą być ciągłe lub dyskretne, a dynamikę przejścia można podać na podstawie problemu lub modelować matematycznie. Wreszcie funkcja nagrody może być nadana z góry lub może być próbkowana (z hałasem lub bez).

Przestrzeń akcji jest prosta: to po prostu kierunek i moc, w którą strzelasz do bieżącego ptaka. Dla człowieka jest to dyskretny problem (mysz / ekran dotykowy jest cyfrowym urządzeniem wejściowym) - powiedzmy (na przykład), że istnieją 32 możliwe kierunki i 10 możliwych mocy, co daje 320 możliwych działań.

Funkcja nagrody jest również dość łatwa do uzyskania: celem jest pozbycie się wszystkich świń z najmniejszą liczbą ptaków (OK, więc są dodatkowe punkty za inne rzeczy, ale na razie zignorujmy to). Najlepszą rzeczą byłoby, gdybyśmy znali faktyczną funkcję, która generuje punkty za zabijanie świń (zależy od wielkości świni itp. IIRC) - ale dla pojedynczego poziomu można to idealnie wymodelować.

Przestrzeń stanu i dynamika przejścia są znacznie trudniejsze. Aby poprawnie to wymodelować, musielibyśmy znać cały układ mapy i fizykę gry. Dynamika przejścia mówi „jeśli jestem w stanie x i wykonam akcję y , wyląduję w stanie z ”. Możesz zobaczyć trudność tego, po pierwsze, ponieważ złożona fizyka układu oznacza, że ​​będzie to niezwykle trudne do dokładnego modelowania, a po drugie, ponieważ istnieje tak wiele możliwych stanów wynikowych nawet po pierwszej rundzie (320), a dzieje się tak, jeśli zakładamy, że nie ma stochastyczności w silniku fizyki, który po odtworzeniu go podejrzewam. Myślę, że na tym etapie poddasz się i wrócisz do domu.

Innym podejściem jest traktowanie go jak człowiek na samym początku - tj. Prób i błędów. Człowiek, przynajmniej na początek, strzela praktycznie losowo (chociaż z dość silną siłą przed wysłaniem ptaków w kierunku świń, ale można to łatwo zakodować), dopóki nie znajdzie się szereg dobrych działań. To bardziej przypomina wielorękiego bandytęoprawa. „Ramiona” bandytów to możliwe działania. Algorytm próbuje zrównoważyć eksplorację i eksploatację - tj. Eksplorację przestrzeni akcji i wykorzystywanie dobrych akcji, gdy zostaną znalezione. W tym celu nie musisz nic wiedzieć o podstawowej dynamice - musisz jedynie wiedzieć o działaniach i nagrodach. Aby to zrobić w pełni, musisz mieć ramię dla każdej możliwej akcji we wszystkich rundach (np. Masz 5 ptaków * 320 akcji = 320 ^ 5 = około 10 ^ 12 akcji), więc pole akcji jest bardzo duże! Możesz jednak użyć kilku sztuczek, aby to poprawić, jeśli wiesz trochęo przestrzeni stanu. Na przykład, prawdopodobnie możesz wykluczyć działania, które odciągają ptaka od świń, w ziemię lub bez wystarczającej mocy, aby dosięgnąć któregokolwiek z nich. Musisz także dotrzeć do piątego ptaka, jeśli nie zabiłeś świń w poprzednich rundach, więc część stanów akcji nie jest w rzeczywistości możliwa. Przypomina to nieco podejście zastosowane w algorytmie MoGo , który jest programem komputerowym do grania w Go opartym na granicach Górnej Pewności stosowanym do Drzew , jedno podejście do rozwiązania problemu wielorękiego bandyty.

Fajne pytanie!

Wygląda na to, że pytanie dotyczy naturalnej techniki tego rodzaju problemu. Myślę, że naturalną techniką tego typu problemów jest uczenie się przez wzmacnianie (RL). RL mówi o tym, jak agent powinien podejmować działania w środowisku, aby zmaksymalizować pewne pojęcie skumulowanej nagrody. Być może najbardziej znanym algorytmem dla RL jest Q-learning . Myślę, że to pierwsze pytanie na tej stronie o uczeniu się przez wzmacnianie.

Myślę, że to, o co pytasz, jest prawdą, jeśli próbujesz traktować to jako klasyfikację / regresję, ale nie wydają się one odpowiednim narzędziem dla tego problemu. Jest to oczywiście problem RL, w którym należy wziąć pod uwagę sekwencje działań i wyników.

Sprawdź tutaj, jak robią to inni lub weź udział: Angry Birds AI Challenge http://ai2012.web.cse.unsw.edu.au/abc.html

właśnie wspomniałem o tym w meta. Koza zastosowała pionierskie algorytmy genetyczne do rozwiązania gry Pacman. skonstruował algorytmiczne prymitywy, które potrafiły wyczuwać i działać. o ile pamiętam, zostały one połączone w drzewa podobne do Lisp, aby stworzyć większe algorytmy. krzyżowanie z drzewami Lisp obejmuje podstawianie lub wymianę poddrzewa reprezentującego wyrażenia algorytmu. funkcją sukcesu jest coś takiego jak „zjedzone kropki” lub „kropki plus zjedzone duchy” lub „czas pozostał przy życiu”. wciąż jest trochę pracy w tym obszarze. w dalszej części tego artykułu znajduje się odnośnik do koza. czas szkolenia może być bardzo długi, a „zbieżność” bardzo stopniowa w przypadku tego rodzaju problemów.

Nauka gry w Pac-Man: Ewolucyjne podejście oparte na regułach autorstwa Gallaghera i Ryana