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.
Paul Rossener 8:59 am on May 6, 2017 Permalink |
Clever!
LikeLike
www.sеху.luxab.ru 3:30 pm on April 2, 2018 Permalink |
+
LikeLike