  Graph games played by two players over finite-state graphs are central in
many problems in computer science. In particular, graph games with
$\omega$-regular winning conditions, specified as parity objectives, which can
express properties such as safety, liveness, fairness, are the basic framework
for verification and synthesis of reactive systems. The decisions for a player
at various states of the graph game are represented as strategies. While the
algorithmic problem for solving graph games with parity objectives has been
widely studied, the most prominent data-structure for strategy representation
in graph games has been binary decision diagrams (BDDs). However, due to the
bit-level representation, BDDs do not retain the inherent flavor of the
decisions of strategies, and are notoriously hard to minimize to obtain
succinct representation. In this work we propose decision trees for strategy
representation in graph games. Decision trees retain the flavor of decisions of
strategies and allow entropy-based minimization to obtain succinct trees.
However, decision trees work in settings (e.g., probabilistic models) where
errors are allowed, and overfitting of data is typically avoided. In contrast,
for strategies in graph games no error is allowed, and the decision tree must
represent the entire strategy. We develop new techniques to extend decision
trees to overcome the above obstacles, while retaining the entropy-based
techniques to obtain succinct trees. We have implemented our techniques to
extend the existing decision tree solvers. We present experimental results for
problems in reactive synthesis to show that decision trees provide a much more
efficient data-structure for strategy representation as compared to BDDs.
