论文标题
通过图神经网络预测平价游戏中的获胜区（扩展摘要）
Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)
论文作者
论文摘要
解决平价游戏是反应性程序验证和综合中众多应用的主要基础。尽管在实践中可以有效地解决它们，但没有已知的方法具有多项式最差的运行时复杂性。我们提出了一种不完整的多项式时间方法，用于通过图神经网络确定平等游戏的获胜区域。 我们对900个随机生成的平价游戏的评估表明，这种方法在实践中是有效效率的。它正确地确定了$ \ sim $ 60 \％在我们的数据集中的获胜区域，仅在其余的游戏集中遇到一个小错误。我们认为，这种方法也可以扩展到有效地解决平等游戏。
Solving parity games is a major building block for numerous applications in reactive program verification and synthesis. While they can be solved efficiently in practice, no known approach has a polynomial worst-case runtime complexity. We present a incomplete polynomial-time approach to determining the winning regions of parity games via graph neural networks. Our evaluation on 900 randomly generated parity games shows that this approach is effective and efficient in practice. It correctly determines the winning regions of $\sim$60\% of the games in our data set and only incurs minor errors in the remaining ones. We believe that this approach can be extended to efficiently solve parity games as well.
