Number of non-symetric patterns in Go

In a tweet published yesterday, the Go pro player Ryu Si Hoon 9 dan asked what's the number of different games of Go after N moves if we discard the symmetric ones. I've found the question interesting and gave it a try, which I'll explain in this article.

I take the following assumptions:

- I consider a 19*19 board (but it's irrelevant to the logic and can be set to any size)
- I do not take into account captured stones (anyway, the time necessary to calculate the solution increases so fast that even the minimum number of move to a first catch, 7, is unmanageable with the current implementation). Same for invalid moves.
- I consider the following symmetry: vertical, horizontal, along the two diagonals, rotation by 90, 180 and 270 degrees

The symmetric of a move can be calculated as follow:

The main function consists in looping on the number of move and counting the corresponding number of game:

The counting is achieved with a recursive function. The first steps of the recursion build up the possible boards, move after move, discarding the symmetric ones. The last step of the recursion actually perform the count by enumerating the last possible move. The algorithm is as follow:

- iterate on the unoccupied and unflagged intersections of the board
- for each type of symmetry, if the board respect that symmetry, flag the symmetric of the intersection (flags are the recursion step level)
- if we are at the last step of the recursion, increment the counter
- if we are not at the last step of the recursion, create a copy of the board with the intersection marked as occupied, and call the next step of the recursion on this new board for the next move

This is implemented as follow:

The function to flag the symmetric moves consists of:

- for each type of symmetry
- if there is no intersection on the board that breaks that symmetry, then flag the symmetric of the move according for this symmetry
- if there is at least one intersection on the board that breaks that symmetry, there is nothing to flag cause the symmetric of the move doesn't make a symmetric of the current board plus the move

This is implemented as follow:

The whole code becomes:

And the results are (only the 4 first moves, the code above is rather straight forward and it would take some serious optimisation to go further):

Edit on the 2022-02-22. Right after publishing the previous article I thought of a simple optimisation: the symmetry of the board doesn't need to be calculated for each move in FlagSymmetrics, it can be done once in CountPattern and reused. As follow:

It saves quite a lot of work and allowed me to calculate the number of patterns after 5 moves:

Edit on the 2022-03-01. The results above were reproduced for the 3 first moves with a different method by Masahide Kashiwagi, cf this thread.

2022-02-21

in All, C programming,

177 views

You've liked this article ? Please consider supporting me:

in All, C programming,

177 views

You've liked this article ? Please consider supporting me: