On a DAG, you can solve games by working backward through terminal positions. Start at vertices with no outgoing edges, then process vertices in reverse topological order. For each vertex, check all possible moves. If any move leads to a losing position, mark the current vertex as winning.
If all moves lead to winning positions, mark it as losing. This takes time. You visit each vertex once and check each edge once. The DAG structure guarantees no cycles, so the recursion terminates.