SteveDraper
commented
9 years ago I would tend to consider this a low priority, because game symmetries will break very quickly along most lines of play, so utility is likely only gained for a very few moves at the start of games. However, that's just an intuitive assessment, so I could be wrong ;-)
We could prune the search space by detecting symmetries. Especially likely to be of use in the first move. Might be worth re-computing for subsequent moves if cheap, but unlikely to find symmetries as more moves are played.
I believe we already have machinery in place to deal with moves with identical outcomes. So, the remaining issue is to find the symmetries (and convert to a usable format).
The underlying problem is the Graph Automorphism problem (v. closely related to the Graph Isomorphism Problem).
Several programs deal with this. See automorphism article, but the description of Bliss looks good. In particular, Bliss can deal with coloured graphs. This is a good fit because we could give each type of component its own colour - e.g.
It also has Java bindings although they aren't high performance. It might be better to re-implement in native Java (if the code isn't too difficult to understand).
The general graph isomorphism problem is NP-complete. The complexity class of the automorphism problem isn't known, but no worst-case polynomial time algorithm exists. However, efficient algorithms exist to solve many cases. As well as Bliss, Nauty/Traces & Saucy may also be suitable.