2
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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