Games on Graphs — Retrograde Analysis

Label each position WIN / LOSE / DRAW. Seed terminals as LOSE, propagate backward over reverse edges with out-degree counters; leftovers are DRAW.

step 0

Position graph

WIN LOSE DRAW unknown blue arrow = reverse edge being followed

Worklist (BFS queue) & labels

queue (front → back):
labels & out-degree counters:
Press Step to begin. Terminals (out-degree 0) are seeded LOSE; then we pop nodes and update predecessors over reverse edges.
Self-contained visualization. A node becomes WIN the instant a LOSE child is popped (one good move suffices); it becomes LOSE only when its out-degree counter reaches 0 (every move led to WIN). Whatever the backward wave never reaches stays DRAW. Runs in O(V + E). See middle.md and professional.md for the proof.