Using symmetry in optimizing algorithms

In some problems, symmetry can be used to optimize algorithms that solve it. Symmetry implies that there is a similarity to make our solutions more efficient. 

To make things more clear,  let’s use a simple game as an example, tic-tac-toe. In this game there are 9 squares and two players take turns picking a square  and making it. If we ignore the winning condition, there are 9! =362,880 configurations. 

If we want to make a program that plays tic-tac-toe against a human that never loses, we can do this by searching the whole 9! search space for a non-losing end state (either win or draw) 
However, we can optimize the 9! search space  by utilizing symmetry. Consider the two possible first moves.


Even though they are different positions, they are functionally the same because they are symmetric. The first option is neither better nor worse than the second option. 

Initially there are 9 possible moves the first player can do, but if we apply properties of symmetry (rotations and reflection) we can reduce the first move to just 3 distinct options (edge, corner, center). 

If we apply properties of symmetries to every move and factor in the winning condition, we can reduce the state space from 9! to just 138 (according to Wikipedia). 

As we can see, by taking advantage of symmetric properties we can make our algorithms more efficient, and sometimes it makes a lot of difference. 

Advertisements