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:

   |   |<K>|   |
   |   |   |   |
   |   | K |   |

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?

  • 3
    $\begingroup$ Use a hash table to store states which you have already processed, then check each time against the table. $\endgroup$ Mar 4, 2016 at 13:12
  • $\begingroup$ Zorbist hashing? $\endgroup$
    – Evil
    Mar 13, 2016 at 22:36

1 Answer 1


Instead of a tree you use a game graph. You maintain a set of nodes (your game states) and, if you need them, a set of edges you already explored. Each time you want to explore a new edge you check whether it leads to a node in your set of nodes. If it doesn't you just found a new node and have to add it to the set.

Your programming language of choice probably provides an efficient data structure for sets already. If it doesn't, you can use a Hash Map or a Search Tree.

However, for non-toy games (a strange concept, games that are not toys...) I don't think that this will buy you anything. The state space is huge and you can't store any significant part. A small cache of some $k$ states might still work though.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.