Partial methods play an important role in formal methods and beyond. Recently such
methods were developed for parity games, where polynomial-time partial solvers decide the
winners of a subset of nodes. We investigate here how effective polynomial-time partial solvers
can be in principle by studying polynomial-time interactions of partial solvers. Concretely,
we propose simple, generic composition patterns for partial solvers that preserve polynomialtime
computability. We show that an implementation of this semantic framework manually
discovers new partial solvers – including those that merge node sets that have the same but
unknown winner – by studying games that composed partial solvers can neither solve nor
simplify. We experimentally validate that this data-driven approach to refinement leads to
polynomial-time partial solvers that can solve all standard benchmarks of structured games.
For one of these polynomial-time partial solvers, we were unable to find even a sole random
game that it won’t solve completely, although we generated a few billion random games of
varying configurations to that end. However, the work presented here does not yet offer any
deeper characterisations of which games are completely solved by such partial solvers.