Many games have states that can be reached via multiple paths in their gametree.
For concreteness, consider the game of tinychess (with the obvious(I hope) rules inherited from chess), which looks like this:
/---V---V---\ | |<K>| | D---+---+---C | | | | D---+---+---C | | K | | \---A---A---/
When both your own and your opponent's King move left and right (or vice versa) the game has returned to the same state (there is no castling).
The state space of this game is rather small (even if we ignore symmetry) and amounts to only 9*8 + 9 + 9 = 90 states. But a game may last an infinite number of turns given that the kings can keep moving back and forth.
How do I go about constructing a game tree that does not duplicate any states, for this game, and more generally?