Adaptive simulation-based meta-heuristic methods in synchronous multiplayer games

Widok

Metadane zasobu

Tytuł	Adaptive simulation-based meta-heuristic methods in synchronous multiplayer games Wariant tytułu: Metaheurystyczne metody adaptacyjne bazujące na symulacjach w synchronicznych grach wieloosobowych
Osoby	Autorzy: Maciej Jakub Świechowski Partner: Instytut Badań Systemowych PAN w Warszawie
Opis	This thesis is concerned with a design of autonomous agents capable of playing many games. The framework of choice, which includes any synchronous, deterministic perfect-information game, is General Game Playing (GGP). GGP is a recent major embodiment of a multi-game playing idea. The aim is to make Artificial Intelligence methods, instead of humans, analyze and reason about the games. The idea was proposed by Stanford Logic Group at Stanford University and since 2005, there has been an annual GGP Competition organized. The winners of the competition define trends and the state-of-the-art approaches. Since 2007, the most successful players have been using Monte-Carlo Tree Search (MCTS) together with the Upper Confidence Bounds applied for Trees (UCT) algorithm. We propose a simulation-based player, called MINI-Player, which is also MCTS/UCT based. However, its unique aspects and, therefore, contributions of the thesis are several major enhancements to the baseline approach. Firstly, Monte Carlo simulations are no longer fully random but rather they are guided, in a semi-random manner, by light-weight strategies (heuristics) which make them biased toward certain behavior. We put forward a concept of Abstract Strategy as a MCTS-friendly encapsulation of such a heuristic. Secondly, the quality and suitability of the heuristics is evaluated online for each player in the played game. Four methods for this purpose are discussed. Experiments on 17 multi-player and 10 single-player games leave a clear evidence that the portfolio with dynamic adaptation increases the playing efficacy of MINI-Player by a significant margin. In addition, there are shown benefits of variety and synergy when MINI-Player has access to all the strategies. Such a player is stronger than a version using only the best evaluated strategy chosen after the initial analysis time (START clock). Thirdly, a flexible and very efficient system to deal with Game Description Language (GDL) is introduced. Ability to interpret this language is an obligatory component of every GGP agent. A low computational efficiency is the cost of built-in universality allowing users to describe any game, as long as the technical properties are satisfied, i.e, synchronicity, determinism and complete information. The fastest publicly available solutions to GDL are based on Prolog dwelling on a fact that GDL is a subset of Prolog with small modifications. The proposed interpreter of MINI-Player not only enables us to integrate the logical interpretation of GDL with the strategies but also increases speed compared to Yet Another Prolog (YAP) by a factor of four in average from 28 games. YAP is widely regarded as the fastest Prolog engine applied to GGP up to date. Moreover, to further mitigate the effect of slower simulations by applying knowledge-based strategies, we propose a novel parallelization method. The method is a combination of three ideas: Tree Parallelization, Root Parallelization and search separation on remote machines. The method is dedicated for scenarios with a huge number of consumer-grade computers (not high-end servers) and games with a large branching factor. Lastly, we report on MINI-Player, the first Polish GGP player to reach the final stage of a GGP Competition. In the current form, as described in the thesis, it achieves significantly better score in the tested games than CadiaPlayer, the winning program from 2012. A majority of the tested games come from the past competitions. Creating a successful GGP player requires many components to work in an integrated fashion. The following thesis most notably focuses on the components which were mentioned in this abstract. (Angielski) Opis w innym języku: Rozprawa dotyczy tematu opracowywania autonomicznych agentów potrafiących z powodzeniem grać w wiele gier. Konkretną wybraną domeną jest General Game Playing (GGP), która zawiera dowolne gry synchroniczne, deterministyczne z pełną informacją. GGP jest jednym z najnowszych urzeczywistnień koncepcji tworzenia uniwersalnych graczy. Celem jest przeniesienie ciężaru przeprowadzania analizy gry oraz wnioskowania w ramach danej gry z człowieka na metody Sztucznej Inteligencji. Pomysł został zaproponowany przez Zespół Logiki na Uniwersytecie Stanforda, który od 2005 roku organizuje coroczne Mistrzostwa GGP. Zwycięzcy definiują trendy oraz poszerzają aktualny stan wiedzy w dziedzinie. Od 2007 roku najskuteczniejsi gracze używają podejścia opartego na przeszukiwaniu drzewa gry metodami Monte Carlo (ang. Monte-Carlo Tree Search (MCTS)) wspartego algorytmem UCT (ang. Upper Confidence Bounds Applied for Trees). Gracz zaproponowany w niniejszej pracy, zwany MINI-Player, również bazuje na podejściu MCTS/UCT. Jednakże posiada on unikalne cechy, stanowiące zarazem główne osiągnięcia rozprawy, polegające na wielu istotnych usprawnieniach bazowego podejścia. Przede wszystkim, symulacje Monte Carlo nie są wyłącznie losowe, lecz są ukierunkowywane w pseudolosowy sposób przy pomocy lekkich strategii, zwanych również heurystykami. Definiujemy koncepcję Abstrakcyjnej Strategii jako pewnej abstrakcji sposobu zastosowania heurystyki w algorytmie MCTS. Ponadto, zarówno jakość jak i użyteczność heurystyk w danej grze jest oceniana w czasie rzeczywistym podczas rozgrywki. Do zrealizowania tego zadania rozważone zostały cztery metody. Eksperymenty przeprowadzone na 17 grach wieloosobowych oraz 10 grach jednoosobowych ukazują wyraźną przewagę gracza stosującego zestaw strategii nad graczem bazowym. Dodatkowo stawiamy i udowadniamy eksperymentalnie tezę, że MINI-Player ze wszystkimi strategiami i dynamicznym mechanizmem adaptacji jest silniejszym graczem niż wersja wyposażona tylko w najlepiej ocenioną strategię dla danej gry, po upływie czasu wstępnej analizy (START clock). Powodem może być efekt większej różnorodności przeszukiwania oraz zachodzącej synergii między strategiami. Opracowany również został elastyczny w użyciu i bardzo wydajny system do operowania językiem GDL (ang. Game Description Language). Moduł odpowiedzialny za interpretację tego języka to nieodzowny element każdego agenta GGP. Kosztem uniwersalności języka GDL, w którym można opisać dowolną grę spełniającą techniczne wymogi (synchroniczność, determinizm i pełna informacja) jest wysoki narzut obliczeniowy. Najwydajniejsze dostępne metody bazują na zastosowaniu Prologa, wykorzystując fakt, że GDL jest jego lekko zmodyfikowanym podzbiorem. Utworzony na potrzeby MINI-Playera interpreter nie tylko pozwala na zintegrowanie strategii z samym mechanizmem wywodu logicznego, ale również osiąga średnio cztery razy większą szybkość wykonywania symulacji niż Yet Another Prolog (YAP) na testowanej klasie 28 gier. YAP jest szeroko uznawany za najszybszą implementację języka Prolog wśród stosowanych w GGP. Dodatkowo, zaproponowana została nowa metoda zrównoleglenia budowy drzewa gry, aby zwiększyć wydajność czasową symulacji, która została zmniejszona przez wprowadzenie strategii (losowe przeszukiwanie jest dużo szybsze bez uwzględnienia wiedzy pochodzącej ze strategii). Metoda jest połączeniem trzech pomysłów - zrównoleglenia pełnego drzewa (ang. Tree Parallelization), zrównoleglenia przy korzeniu (ang. Root Parallelization) oraz ograniczenia przeszukiwania na zdalnych maszynach. Dedykowanym scenariuszem zastosowania dla tej metody jest przypadek dużej liczby komputerów domowej klasy oraz gry z wysokim stopniem rozgałęzienia (oczekiwaną liczbą legalnych ruchów). Wreszcie, rozprawa zawiera raport na temat MINI-Playera, pierwszego gracza z Polski, który awansował do finałowego etapu Mistrzostw GGP. W aktualnej postaci, gracz osiąga statystycznie istotnie lepszy wynik w testowanych grach niż program CadiaPlayer, który wygrał mistrzostwa w roku 2012. Zdecydowana większość testowanych gier pochodzi z dotychczasowych mistrzostw. Powodzenie w zbudowaniu gracza GGP wymaga wielu współgrających ze sobą komponentów. Niniejsza praca omawia większość z nich ze szczególnym uwzględnieniem aspektów opisanych w tym streszczeniu. (Polski)
Słowa kluczowe	"metody heurystyczne"@pl, "procesy decyzyjne"@pl, "uczenie maszynowe"@pl, "Machine Learning"@en, "sztuczna inteligencja"@pl
Klasyfikacja	Typ zasobu: praca dyplomowa Dyscyplina naukowa: dziedzina nauk technicznych / informatyka (2011) Grupa docelowa: naukowcy, studenci, przedsiębiorcy Szkodliwe treści: Nie
Charakterystyka	Miejsce powstania: Warszawa Czas powstania: 2015 Liczba stron: 152 Promotor: Jacek Mańdziuk Język zasobu: Angielski Lokalizacja: Warszawa
Licencja	CC BY-SA 4.0
Informacje techniczne	Deponujący: Anna Wasilewska Data udostępnienia: 15-10-2018
Kolekcje	Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN

Cytowanie

Skopiowano

Maciej Jakub Świechowski. Adaptive simulation-based meta-heuristic methods in synchronous multiplayer games. [praca dyplomowa] Dostępny w Atlasie Zasobów Otwartej Nauki, . Licencja: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Data dostępu: DD.MM.RRRR.

Podobne zasoby

Splunk - konfiguracja, rozpoznawanie i wizualizacja informacji o incydentach i zagrożeniach

Arkadiusz Kotynia, Julia Jancelewicz, Urszula Warmińska, inny dokument, Politechnika Wrocławska, Dziedzina nauk inżynieryjno-technicznych / automatyka, elektronika i elektrotechnika (2018)

Sztuczna inteligencja w świecie rzeczywistym

Sylwia Majchrowska, wideo, Politechnika Wrocławska, dziedzina nauk technicznych / informatyka (2011)

Metody znakowania morfosyntaktycznego i automatycznej płytkiej analizy składniowej języka polskiego

Adam Radziszewski, praca dyplomowa, Politechnika Wrocławska, dziedzina nauk technicznych / informatyka (2011)

Uczenie maszynowe na podstawie przykładów w przypadku błędów w danych

Grażyna Szkatuła, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / informatyka (2011)

Theory and practice of artificial intelligence for control: artificial intelligence for control

O. C. L. Haas, A. J. Koshkouei, książka, Politechnika Wrocławska, dziedzina nauk technicznych / informatyka (2011)

Korpus nagrań próbek mowy do celów budowy modeli akustycznych dla automatycznego rozpoznawania mowy w języku polskim, cz. 8

Teresa Sas, zbiór, baza danych, Politechnika Wrocławska, Dziedzina nauk inżynieryjno-technicznych / informatyka techniczna i telekomunikacja (2018)

Zobacz więcej