Efficient parallel strategy improvement for parity games

DOI10.1007/978-3-319-63390-9_8MaRDI QIDQ2164217zbMATH OpenOpenAlexFDO

Authors John Fearnley

Publication date 12 August 2022

Full work available at URL https://arxiv.org/abs/1705.02313

zbMATH Keywords

Bellman-Ford algorithmparity gamespseudo-treestrategy improvement algorithmswitchable edges

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Games involving graphs (91A43)

Abstract: We study strategy improvement algorithms for solving parity games. While these algorithms are known to solve parity games using a very small number of iterations, experimental studies have found that a high step complexity causes them to perform poorly in practice. In this paper we seek to address this situation. Every iteration of the algorithm must compute a best response, and while the standard way of doing this uses the Bellman-Ford algorithm, we give experimental results that show that one-player strategy improvement significantly outperforms this technique in practice. We then study the best way to implement one-player strategy improvement, and we develop an efficient parallel algorithm for carrying out this task, by reducing the problem to computing prefix sums on a linked list. We report experimental results for these algorithms, and we find that a GPU implementation of this algorithm shows a significant speedup over single-core and multi-core CPU implementations.

Recommendations

• Local strategy improvement for parity game solving
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• scientific article; zbMATH DE number 1670778
• Improving parity games in practice
• Two local strategy iteration schemes for parity game solving

Cited in

(13)

• Inclusion problems in parallel learning and games
• Non-oblivious strategy improvement
• A Parallel Game Tree Search Algorithm With A Linear Speedup
• Semantic labelling and learning for parity game solving in LTL synthesis
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Improved Rounding for Parallel Repeated Unique Games
• A parity game tale of two counters
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Local strategy improvement for parity game solving
• Solving Parity Games on the GPU
• A Multi-Core Solver for Parity Games
• Guessing winning policies in LTL synthesis by semantic learning
• The worst-case complexity of symmetric strategy improvement

This page was built for publication: Efficient parallel strategy improvement for parity games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164217)