Project Abstract

Parity games are a heavily contributed subject that have many applications for integral areas in mathematics and computer science, such as model checking and control synthesis. Although there are many algorithms on solving them, there is yet to be proof of a solution with worst-case polynomial runtime complexity. This research proposes the idea of using AI to “play” parity games in the hopes to find a more efficient solution that could not be obtained through classical methods. A series of Graph Neural Networks (GNNs), trained on 2100 randomly generated parity games and tested on another 900, are employed to find winning regions as an abstraction of solving them. This is achieved through message passing layers, which take constant time per vertex, hence produces predictions in linear time with relation to the number of vertices in the graph. From this, we find the GNNs’ performances vary through a number of factors but show promise in their accuracy at identifying winning regions. Built from the foundation of previous work, I present a prototypical implementation of parity game networks using the PyTorch Geometric library, allowing anyone to run the GNNs to train, predict, or be evaluated on their measure of completeness. This concludes with the encouragement of applying AI involved methods to solve problems of similar nature and uncover answers that previously seemed well-beyond our reach.

Keywords: Theoretical Computer Science, Game Theory, Machine Learning

 Conference Details

Session: Poster Session A at Poster Stand 117

Location: Sir Stanley Clarke Auditorium at Tuesday 7th 13:30 – 17:00

Markers: Arno Pauly, Jiaxiang Zhang

Course: BSc Computer Science, 3rd Year

Future Plans: I’m continuing studies