CODEWITHSUNDEEP
algorithmmatrixoptimizationconv-neural-networklinear-algebra
user3634008
user3634008

Reputation: 35

Defining a function to make symmetric matrices equal

A bit of background

I am writing a convolutional neural network (in c++) to play tic tac toe on a 4 x 4 grid. I would like to optimize it by using the fact that tic tac toe -boards inherit rotational and dihedral symmetry. By that I mean that if you can find one optimal move for a given board, it stays the same even if you rotated or mirrored the board. So what I am looking for is a function that removes any mirroring or rotation of a matrix, so the network would see all rotated and/or mirrored boards as the same and respond to them in the same way. In other words for any matrix M let its rotated and/or mirrored versions be M', the function would return M for all M'.

This article talks about rotational and dihedral symmetry implementation inside the network architecture, but I think that in my case, where the input is a lot smaller than an image, it would be easier to implement (and would keep the network smaller) by just transforming the input. I have no hard proof that this would increase my network's performance, but I'm eager to test it.

My approach

My board contains only zeros, ones, and twos. Zeros are empty space, ones represent friendly units and twos represent your opponent's units. I have been thinking of the following approach illustrated by the next image (green: friendly, red: opponent):

Illustration

  1. calculate the average position of enemy units and the average of friendly units
  2. ensure that the clockwise angle (using the center as the third point) from enemy average to friendly average is below 180 degrees. if it is not, mirror the board
  3. rotate the board until the friendly average points to the left, or to the top left quarter of the board

and then of course handle the special cases (like when average is at the center) when required.

Now this approach would seem to work, but I doubt it is the best way. I'm wondering if there are already functions for this purpose that use matrix math or if I had missed a useful mathematical shortcut or something like that. And this is a very crucial part to optimize as this operation would be done before each network makes a move and in my training program that would mean thousands of times each second.

Upvotes: 2

Views: 82

Answers (1)

kaya3
kaya3

Reputation: 51034

A neat solution to this problem is to define a total ordering on all boards, and then given a board, define its "canonical" representation as whichever of the 8 symmetrical versions of it is "lowest" in that ordering. There are no other requirements; any total ordering will do.

A simple way to define a total order is to induce one via a mapping to the integers. Since there are 16 cells and each cell has one of three states (red, green or empty), we can map a board state to an unsigned 32-bit integer, where each cell is represented by two bits: 10 for red, 01 for green, 00 for empty, which happens to be the numeric representation you are already using for the cells in your board.

For your example:

example board

  • 01 10 00 00 10 01 00 00 01 00 00 00 00 01 00 00 is the original board.
  • 00 01 10 01 01 00 01 10 00 00 00 00 00 00 00 00 is the 90 degree clockwise rotation.
  • 00 00 01 00 00 00 00 01 00 00 01 10 00 00 10 01 is the 180 degree rotation.
  • 00 00 00 00 00 00 00 00 10 01 00 01 01 10 01 00 is the 90 degree anticlockwise rotation.
  • 00 00 10 01 00 00 01 10 00 00 00 01 00 00 01 00 is the horizontal mirror image.
  • 00 01 00 00 01 00 00 00 10 01 00 00 01 10 00 00 is the vertical mirror image.
  • 01 10 01 00 10 01 00 01 00 00 00 00 00 00 00 00 is the south-east diagonal mirror image.
  • 00 00 00 00 00 00 00 00 01 00 01 10 00 01 10 01 is the south-west diagonal mirror image.

The smallest number out of these eight is the last one, so the "canonical" version of this board is the south-west diagonal mirror image:

mirror image

Upvotes: 3

Related Questions