J 2012

Using strategy improvement to stay alive

BRIM, Luboš and Jakub CHALOUPKA

Basic information

Original name

Using strategy improvement to stay alive

Authors

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

Edition

International Journal of Foundations of Computer Science, 2012, 0129-0541

Other information

Language

English

Type of outcome

Článek v odborném periodiku

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:

Impact factor

Impact factor: 0.420

RIV identification code

RIV/00216224:14330/12:00057380

Organization unit

Faculty of Informatics

DOI

UT WoS

000304003000003

Keywords (in Czech)

mean-payoff hry; zlepšení strategie; experimentální vyhodnocení.

Keywords in English

Mean-payoff games; strategy improvement; experimental evaluation.

Tags

International impact, Reviewed
Změněno: 23/4/2013 12:15, RNDr. Pavel Šmerk, Ph.D.

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