If your game graph has states that can be reached via multiple paths, use memoization to avoid recomputing the same state multiple times. Store the outcome (or minimax value) of each state in a hash map or array.
Before computing a state, check if it is already been solved. This is especially necessary for games with cycles or when the state space is a DAG but has multiple paths to the same state.