  Parity games are abstract infinite-round games that take an important role in
formal verification. In the basic setting, these games are two-player,
turn-based, and played under perfect information on directed graphs, whose
nodes are labeled with priorities. The winner of a play is determined according
to the parities (even or odd) of the minimal priority occurring infinitely
often in that play. The problem of finding a winning strategy in parity games
is known to be in UPTime $\cap$ CoUPTime and deciding whether a polynomial time
solution exists is a long-standing open question. In the last two decades, a
variety of algorithms have been proposed. Many of them have been also
implemented in a platform named PGSolver. This has enabled an empirical
evaluation of these algorithms and a better understanding of their relative
merits. In this paper, we further contribute to this subject by implementing,
for the first time, an algorithm based on alternating automata. More precisely,
we consider an algorithm introduced by Kupferman and Vardi that solves a parity
game by solving the emptiness problem of a corresponding alternating parity
automaton. Our empirical evaluation demonstrates that this algorithm
outperforms other algorithms when the game has a a small number of priorities
relative to the size of the game. In many concrete applications, we do indeed
end up with parity games where the number of priorities is relatively small.
This makes the new algorithm quite useful in practice.
