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:

#define SIZE 19 typedef struct {int i; int j;} Move; typedef Move (*symFun_t)(Move m); #define NB_SYM 7 Move SymVert(Move m) {return (Move){ SIZE-m.i-1, m.j };} Move SymHor(Move m) {return (Move){ m.i, SIZE-m.j-1 };} Move SymDiagPos(Move m) {return (Move){ SIZE-m.j-1, SIZE-m.i-1 };} Move SymDiagNeg(Move m) {return (Move){ m.j, m.i };} Move SymRot90(Move m) {return (Move){ SIZE-m.j-1, m.i };} Move SymRot180(Move m) {return (Move){ SIZE-m.i-1, SIZE-m.j-1 };} Move SymRot270(Move m) {return (Move){ m.j, SIZE-m.i-1 };} symFun_t syms[NB_SYM] = { SymVert, SymHor, SymDiagPos, SymDiagNeg, SymRot90, SymRot180, SymRot270};

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

int main() { for (int nbMove = 0; nbMove < NB_MOVE; ++nbMove) { char board[SIZE*SIZE] = {0}; unsigned long int nbPattern = CountPattern(board, nbMove); printf("Number of patterns after %d moves: %lu\n", nbMove+1, nbPattern); } }

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:

unsigned long int CountPattern(char *board, int iMove) { unsigned long int nbPattern = 0; char flags[SIZE*SIZE] = {0}; for (int i = 0; i < SIZE; ++i) for (int j = 0; j < SIZE; ++j) { if (board[i*SIZE+j] == 0 && flags[i*SIZE+j] == 0) { FlagSymmetrics(board, flags, (Move){i, j}); if (iMove == 0) { ++nbPattern; } else { char nextBoard[SIZE*SIZE]; memcpy(nextBoard, board, SIZE*SIZE); nextBoard[i*SIZE+j] = 1 + iMove % 2; nbPattern += CountPattern(nextBoard, iMove - 1); } } } return nbPattern; }

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:

void FlagSymmetrics(char *board, char *flags, Move m) { for (int iSym = 0; iSym < NB_SYM; ++iSym) { int isSym = 1; for (int i = 0; i < SIZE && isSym; ++i) for (int j = 0; j < SIZE && isSym; ++j) { char status = board[i*SIZE+j]; Move mSym = syms[iSym]((Move){i,j}); char statusSym = board[mSym.i*SIZE+mSym.j]; if (statusSym != status) isSym = 0; } if (isSym) { Move mSym = syms[iSym](m); flags[mSym.i*SIZE+mSym.j] = 1; } } }

The whole code becomes:

#include "stdio.h" #include "string.h" #define NB_MOVE 4 #define SIZE 19 typedef struct {int i; int j;} Move; typedef Move (*symFun_t)(Move m); #define NB_SYM 7 Move SymVert(Move m) {return (Move){ SIZE-m.i-1, m.j };} Move SymHor(Move m) {return (Move){ m.i, SIZE-m.j-1 };} Move SymDiagPos(Move m) {return (Move){ SIZE-m.j-1, SIZE-m.i-1 };} Move SymDiagNeg(Move m) {return (Move){ m.j, m.i };} Move SymRot90(Move m) {return (Move){ SIZE-m.j-1, m.i };} Move SymRot180(Move m) {return (Move){ SIZE-m.i-1, SIZE-m.j-1 };} Move SymRot270(Move m) {return (Move){ m.j, SIZE-m.i-1 };} symFun_t syms[NB_SYM] = { SymVert, SymHor, SymDiagPos, SymDiagNeg, SymRot90, SymRot180, SymRot270}; void FlagSymmetrics(char *board, char *flags, Move m) { for (int iSym = 0; iSym < NB_SYM; ++iSym) { int isSym = 1; for (int i = 0; i < SIZE && isSym; ++i) for (int j = 0; j < SIZE && isSym; ++j) { char status = board[i*SIZE+j]; Move mSym = syms[iSym]((Move){i,j}); char statusSym = board[mSym.i*SIZE+mSym.j]; if (statusSym != status) isSym = 0; } if (isSym) { Move mSym = syms[iSym](m); flags[mSym.i*SIZE+mSym.j] = 1; } } } unsigned long int CountPattern(char *board, int iMove) { unsigned long int nbPattern = 0; char flags[SIZE*SIZE] = {0}; for (int i = 0; i < SIZE; ++i) for (int j = 0; j < SIZE; ++j) { if (board[i*SIZE+j] == 0 && flags[i*SIZE+j] == 0) { FlagSymmetrics(board, flags, (Move){i, j}); if (iMove == 0) { ++nbPattern; } else { char nextBoard[SIZE*SIZE]; memcpy(nextBoard, board, SIZE*SIZE); nextBoard[i*SIZE+j] = 1 + iMove % 2; nbPattern += CountPattern(nextBoard, iMove - 1); } } } return nbPattern; } int main() { for (int nbMove = 0; nbMove < NB_MOVE; ++nbMove) { char board[SIZE*SIZE] = {0}; unsigned long int nbPattern = CountPattern(board, nbMove); printf("Number of patterns after %d moves: %lu\n", nbMove+1, nbPattern); } }

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):

Number of patterns after 1 moves: 55 Number of patterns after 2 moves: 16,416 Number of patterns after 3 moves: 5,834,862 Number of patterns after 4 moves: 2,087,327,556

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:

#include "stdio.h" #include "string.h" #define NB_MOVE 5 #define SIZE 19 typedef struct {int i; int j;} Move; typedef Move (*symFun_t)(Move m); #define NB_SYM 7 Move SymVert(Move m) {return (Move){ SIZE-m.i-1, m.j };} Move SymHor(Move m) {return (Move){ m.i, SIZE-m.j-1 };} Move SymDiagPos(Move m) {return (Move){ SIZE-m.j-1, SIZE-m.i-1 };} Move SymDiagNeg(Move m) {return (Move){ m.j, m.i };} Move SymRot90(Move m) {return (Move){ SIZE-m.j-1, m.i };} Move SymRot180(Move m) {return (Move){ SIZE-m.i-1, SIZE-m.j-1 };} Move SymRot270(Move m) {return (Move){ m.j, SIZE-m.i-1 };} symFun_t syms[NB_SYM] = { SymVert, SymHor, SymDiagPos, SymDiagNeg, SymRot90, SymRot180, SymRot270}; int IsBoardSymmetric(char *board, int iSym) { int isSym = 1; for (int i = 0; i < SIZE && isSym; ++i) for (int j = 0; j < SIZE && isSym; ++j) { char status = board[i*SIZE+j]; Move mSym = syms[iSym]((Move){i,j}); char statusSym = board[mSym.i*SIZE+mSym.j]; if (statusSym != status) isSym = 0; } return isSym; } void FlagSymmetrics(char *board, char *flags, Move m, int *boardSymmetry) { #pragma omp parallel for for (int iSym = 0; iSym < NB_SYM; ++iSym) { if (boardSymmetry[iSym]) { Move mSym = syms[iSym](m); flags[mSym.i*SIZE+mSym.j] = 1; } } } unsigned long int CountPattern(char *board, int iMove) { unsigned long int nbPattern = 0; char flags[SIZE*SIZE] = {0}; int boardSymmetry[NB_SYM]; for (int iSym = 0; iSym < NB_SYM; ++iSym) boardSymmetry[iSym] = IsBoardSymmetric(board, iSym); for (int i = 0; i < SIZE; ++i) for (int j = 0; j < SIZE; ++j) { if (board[i*SIZE+j] == 0 && flags[i*SIZE+j] == 0) { FlagSymmetrics(board, flags, (Move){i, j}, boardSymmetry); if (iMove == 0) { ++nbPattern; } else { char nextBoard[SIZE*SIZE]; memcpy(nextBoard, board, SIZE*SIZE); nextBoard[i*SIZE+j] = 1 + iMove % 2; nbPattern += CountPattern(nextBoard, iMove - 1); } } } return nbPattern; } int main() { for (int nbMove = 0; nbMove < NB_MOVE; ++nbMove) { char board[SIZE*SIZE] = {0}; unsigned long int nbPattern = CountPattern(board, nbMove); printf("Number of patterns after %d moves: %lu\n", nbMove, nbPattern); } }

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

Number of patterns after 1 moves: 55 Number of patterns after 2 moves: 16,416 Number of patterns after 3 moves: 5,834,862 Number of patterns after 4 moves: 2,087,327,556 Number of patterns after 5 moves: 745,127,544,474

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.