mardi 31 décembre 2019

How to find equivalent positions in board games?

I have a board (let’s say a 4x4). An example of a position would be:

1101

1111

1111

0000

Because of the rules of the game, this position is equivalent to the position

(clockwise rotation)

0111

0111

0110

0111

So, my question is if there is way to assign a unique number to each one of the 4x4 squares in order to define a position then use an algorithm that finds if this position has already been met meaning that there are equivalent positions under rotation or reflection.

The purpose of this, is that I want to brute force game positions to find a winning strategy but I don’t want to recalculate equivalent positions, so I need to just save a position and then check if another position (maybe rotated or reflected) has already been occurred.

I have thought of using complex numbers to assign in the squares and use basic algebra to rotate and reflect the board but I am sure maybe there is a better way. Am I thinking this in the wrong way? Also, is there a way that this can be generalized ? For example, if I have a triangular shaped board (I am trying to model this game here https://youtu.be/mRG2k-nOfec), how can I create such a function ?





Aucun commentaire:

Enregistrer un commentaire