Using Strategy Improvement to Stay Alive

BRIM, Luboš a Jakub CHALOUPKA. Using Strategy Improvement to Stay Alive. In Games, Automata, Logics and Formal Verification (GandALF) 2010. Neuveden: Electronic Proceedings in Theoretical Computer Science (EPTCS), 2010, s. 40-54. ISSN 2075-2180.

Základní údaje

Originální název

Using Strategy Improvement to Stay Alive

Název česky

Přežívání pomocí techniky zlepšování strategie

Autoři

BRIM, Luboš (203 Česká republika, garant, domácí) a Jakub CHALOUPKA (203 Česká republika, domácí)

Vydání

Neuveden, Games, Automata, Logics and Formal Verification (GandALF) 2010, od s. 40-54, 15 s. 2010

Nakladatel

Electronic Proceedings in Theoretical Computer Science (EPTCS)

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Kód RIV

RIV/00216224:14330/10:00044605

Organizační jednotka

Fakulta informatiky

ISSN

UT WoS

000304003000003

Klíčová slova anglicky

mean-payoff games; strategy improvement; experimental evaluation

Štítky

experimental evaluation, mean-payoff games, strategy improvement

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

We design a novel algorithm for solving Mean-Payoff Games (MPGs). Besides solving an MPG in the usual sense, our algorithm computes more information about the game, information that is important with respect to applications. The weights of the edges of an MPG can be thought of as a gained/consumed energy -- depending on the sign. For each vertex, our algorithm computes the minimum amount of initial energy that is sufficient for player Max to ensure that in a play starting from the vertex, the energy level never goes below zero. Our algorithm is not the first algorithm that computes the minimum sufficient initial energies, but according to our experimental study it is the fastest algorithm that computes them. The reason is that it utilizes the strategy improvement technique which is very efficient in practice.

---

Návaznosti

GA201/09/1389, projekt VaV	Název: Verifikace a analýza velmi velkých počítačových systémů Investor: Grantová agentura ČR, Verifikace a analýza velmi velkých počítačových systémů
GD102/09/H042, projekt VaV	Název: Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů Investor: Grantová agentura ČR, Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
MUNI/A/0914/2009, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty