Algorithm for Two-Energy Games

Investor logo
Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CHALOUPKA Jakub

Year of publication 2010
Type Article in Proceedings
Conference Mathematical and Engineering Methods in Computer Science (MEMICS) 2010
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords energy games; games on k-dimensional vector addition systems with states; algorithm design
Description A two-energy game (TEG) is a two-player game consisting of finite weighted directed graph and two unbounded counters. The weights of the edges are pairs from the set {-1, 0, 1}x{-1,0,1}. The two players, named Box and Diamond, move a token along the edges of the graph ad infinitum, and the weight of each traversed edge is added to the two counters. Box's aim is to keep both counters non-negative, while Diamond wants to make at least one of the counters go below zero. TEGs have applications in resource scheduling, and it has been recently shown (Chaloupka, 2010) that deciding the winner in two-energy games is in the complexity class P. This encourages searching for efficient algorithms for TEGs. In this paper, we design a novel algorithm for TEGs and evaluate it in a preliminary experimental study.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.