Using Strategy Improvement to Stay Alive

BRIM, Luboš and 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, p. 40-54. ISSN 2075-2180.

Basic information

Original name

Using Strategy Improvement to Stay Alive

Name in Czech

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

Authors

BRIM, Luboš (203 Czech Republic, guarantor, belonging to the institution) and Jakub CHALOUPKA (203 Czech Republic, belonging to the institution)

Edition

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

Publisher

Electronic Proceedings in Theoretical Computer Science (EPTCS)

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Czech Republic

Confidentiality degree

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

References:

URL

RIV identification code

RIV/00216224:14330/10:00044605

Organization unit

Faculty of Informatics

ISSN

UT WoS

000304003000003

Keywords in English

mean-payoff games; strategy improvement; experimental evaluation

Tags

experimental evaluation, mean-payoff games, strategy improvement

Tags

International impact, Reviewed

---

Abstract

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.

---

Links

GA201/09/1389, research and development project	Name: Verifikace a analýza velmi velkých počítačových systémů Investor: Czech Science Foundation, Verification and Analysis of Large-Scale Computer Systems
GD102/09/H042, research and development project	Name: 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: Czech Science Foundation
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
MUNI/A/0914/2009, interní kód MU	Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV) Investor: Masaryk University, Category A