Algorithms for Mean-Payoff and Energy Games - Chaloupka, Jakub; Brim, Luboš, 1952-; Masarykova univerzita. Fakulta informatiky (2011)
Mean-payoff game (MPG) je hra dvou hráčů hraná na konečném ohodnoceném orientovaném grafu. Tito dva hráči, Max a Min, do nekonečna pohybují žetonem po hránách grafu. Maxův cíl je maximalizovat průměrnou hodnotu projitých hran, zatímco Min ji chce minimalizovat. Energy game (EG) je také hrána na konečném ohodnoceném orientovaném grafu, ale hra je obohacena neohraničeným čítačem. Čítač má nějakou danou nezápornou počáteční hodnotu a hodnota každé projité hrany je k němu přičítána. Maxův cíl je udržet čítač nezáporný, zatímco Min chce aby šel pod nulu. EGs můžou být zobecněny pro k čítačů, kde k je libovolné přirozené číslo. Ohodnocení hran jsou k-tice celých čísel a každá komponenta každé projité hrany je přičtena k příslušnému čítači. Max chce všechny čítače udržet nezáporné, zatímco Min chce alespoň jeden poslat pod nulu. Mean-payoff a energy games jsou silným nástrojem s mnoha aplikacemi, zejména v syntéze, analýze a verifikaci počítačových systémů.
A mean-payoff game (MPG) is a two-player infinite game played on a finite weighted directed graph. The two players, named Max and Min, move a token along the edges of the graph ad infinitum. Max's aim is to maximize the average weight of the traversed edges, while Min wants to minimize it. An energy game (EG) is also played on a finite weighted directed graph, but the game is enhanced with an unbounded counter. The counter has some given non-negative initial value and the weight of each traversed edge is added to the counter. Max's aim is to keep the counter non-negative, while Min wants to make it go below zero. EGs can be generalized to k counters, where k is an arbitrary natural number. The weights of the edges are k-tuples of integers and each component of the weight of each traversed edge is added to the respective counter. Max wants to keep all counters non-negative, while Min wants to make at least one go negative. Mean-payoff and energy games are a powerful tool with many applications, especially in the synthesis, analysis, and verification of compute systems.
Vedoucí práce: Luboš Brim
Dizertace (Ph.D.)--Masarykova univerzita, Fakulta informatiky, 2011
Keywords: hry; paralelní algoritmy; algoritmy (programování); grafové algoritmy; algorithms; games; parallel algorithms; graph algorithms; disertace; dissertations