Validate the graph word and evaluate the game tree by a depth-first stack. The encoded stack is cubically bounded, and each transition is compiled from a polynomially bounded word program. Reusing its cleared workspace gives a single polynomial space bound for the entire terminating search. The archived stack-to-tape compiler provides the required deterministic read-only-input work-tape machine.