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:

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:

This is implemented as follow:

The function to flag the symmetric moves consists of:

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, Igo,
233 views
Copyright 2021-2024 Baillehache Pascal