REPORT A PROBLEM
LINKS
Resource link (short)
http://www.zasobynauki.pl/zasoby/21390Resource link (repository)
https://id.e-science.pl/records/21390Resource metadata
Title |
Adaptive simulation-based meta-heuristic methods in synchronous multiplayer games Title variant: Metaheurystyczne metody adaptacyjne bazujące na symulacjach w synchronicznych grach wieloosobowych |
---|---|
Persons |
Authors:
Maciej Jakub Świechowski
Partner: Systems Research Institute Polish Academy of Sciences, Warsaw |
Description |
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. (English) Description in another language: 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. (Polish) |
Keywords | "metody heurystyczne"@pl, "procesy decyzyjne"@pl, "uczenie maszynowe"@pl, "Machine Learning"@en, "sztuczna inteligencja"@pl |
Classification |
Resource type:
thesis Scientific discipline: dziedzina nauk technicznych / informatyka (2011) Destination group: scientists, students, entrepreneurs Harmful content: No |
Characteristics |
Place of creation: Warszawa
Creation time: 2015 Number of pages: 152 Supervisor: Jacek Mańdziuk Resource language: English Location: Warszawa |
License | CC BY-SA 4.0 |
Technical information |
Submitter: Anna Wasilewska Availability date: 15-10-2018 |
Collections | Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN |
Similar resources
Splunk - konfiguracja, rozpoznawanie i wizualizacja informacji o incydentach i zagrożeniach
Arkadiusz Kotynia, Julia Jancelewicz, Urszula Warmińska, other document, Wrocław University of Science and Technology, Dziedzina nauk inżynieryjno-technicznych / automatyka, elektronika i elektrotechnika (2018)
Sztuczna inteligencja w świecie rzeczywistym
Sylwia Majchrowska, video, Wrocław University of Science and Technology, dziedzina nauk technicznych / informatyka (2011)
Metody znakowania morfosyntaktycznego i automatycznej płytkiej analizy składniowej języka polskiego
Adam Radziszewski, thesis, Wrocław University of Science and Technology, dziedzina nauk technicznych / informatyka (2011)
Uczenie maszynowe na podstawie przykładów w przypadku błędów w danych
Grażyna Szkatuła, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, dziedzina nauk technicznych / informatyka (2011)
Theory and practice of artificial intelligence for control: artificial intelligence for control
O. C. L. Haas, A. J. Koshkouei, book, Wrocław University of Science and Technology, 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, dataset, database, Wrocław University of Science and Technology, Dziedzina nauk inżynieryjno-technicznych / informatyka techniczna i telekomunikacja (2018)