String of '+' and '-'. Each turn, flip "++" to "--". Can't move = lose. Can first player guarantee a win? State: the string itself (or a hash of it).
Too many states? Use memoization with string keys. Transition: for each "++" substring, flip it, check if opponent loses from the new state. improvement: canonical form. The game decomposes into independent subgames. Use Sprague-Grundy theorem for large inputs.