Algorithm for Two-Energy Games
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Proceedings |
| Conference | Mathematical and Engineering Methods in Computer Science (MEMICS) 2010 |
| MU Faculty or unit | |
| 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: |