The maximum liberty of a group on a Go board

xiver77 · Post by **xiver77** » Wed Apr 13, 2022 3:27 am

A simple problem came to mind a while ago, but I couldn't think of a clear solution.

What is the maximum number of liberties a group can have on an n × n Go board?

We can name a function for this as maxlib(n).

A brute force approach to compute maxlib has insane time complexity. I actually wrote and ran a program to compute this brute force, and could only reach n = 6 after about 2 hours, maybe.

I posted a programming challenge about this, and still haven't got a fast enough solution, but a user named Loopy Walt did post a convincing conjecture that,

Code: Select all

maxlib(n) = 0, if n = 1
            2, if n = 2
            6, if n = 3
            (2n - 1)⌊n / 3⌋, if n % 3 = 0
            (2n - 1)⌊n / 3⌋ + n, if n % 3 = 2
            2n⌊n / 3⌋ + 1, otherwise

This conjecture is justified although not proved by the following group patterns.

Code: Select all

n % 3 = 0
............ 
XXXXXXXXXXXX
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.

Code: Select all

n % 3 = 2
........... 
XXXXXXXXXXX
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X

Code: Select all

n % 3 = 1
.......... 
XXXXXXXXXX
.X..X..X..
.X..X..X..
.X..X..XXX
.X..X..X..
.X..X..X..
.X..X..XXX
.X..X..X..
.X..X..XX.

An OEIS sequence (A320666) exists for maxlib. The currently known values are only up to n = 24.

Code: Select all

n maxlib(n)
1 0
2 2
3 6
4 9
5 14
6 22
7 29
8 38
9 51
10 61
11 74
12 92
13 105
14 122
15 145
16 161
17 182
18 210
19 229
20 254
21 287
22 309
23 338
24 376

Elom0 · Post by **Elom0** » Fri Apr 15, 2022 1:01 am

I can't understand the programming aspects but I can glean that obviously since a 1x1 board would give zero liberties there's a non-linear component to it. However wouldn't a group with the maximum liberties be, for example on 19x19, a 63-stone near loop? So wouldn't it just be (4*(2n-2)) minus whatever constants to account for 1x1?

jlt · Post by **jlt** » Fri Apr 15, 2022 2:28 am

As said in the OP, this group has 229 liberties.

Click Here To Show Diagram Code: [go]$$ $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | X X X X X X X X X X X X X X X X X X X | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . , X . . X . , X . . X . , X . . | $$ | . X . . X . . X . . X . . X . . X X X | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . . X . . X . . X . . X . . X X X | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . , X . . X . , X . . X . , X . . | $$ | . X . . X . . X . . X . . X . . X X X | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . . X . . X . . X . . X . . X X X | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . , X . . X . , X . . X . , X . . | $$ | . X . . X . . X . . X . . X . . X X X | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . . X . . X . . X . . X . . X . . | $$ ---------------------------------------[/go]

Cassandra · Post by **Cassandra** » Fri Apr 15, 2022 2:46 am

Click Here To Show Diagram Code: [go]$$B $$ +---------------------------------------+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | X X X X X X X X X X X X X X X X X X X | $$ | . X . . . . . . . . . . . . . . . . . | $$ | . X . , . . . . . , . . . . . , . . . | $$ | . X X X X X X X X X X X X X X X X X X | $$ | . X . . X . . . . . . . . . . . . . . | $$ | . X . . X . . . . . . . . . . . . . . | $$ | . X . . X X X X X X X X X X X X X X X | $$ | . X . . X . . X . . . . . . . . . . . | $$ | . X . , X . . X . , . . . . . , . . . | $$ | . X . . X . . X X X X X X X X X X X X | $$ | . X . . X . . X . . X . . . . . . . . | $$ | . X . . X . . X . . X . . . . . . . . | $$ | . X . . X . . X . . X X X X X X X X X | $$ | . X . . X . . X . . X . . X . . . . . | $$ | . X . , X . . X . , X . . X . , . . . | $$ | . X . . X . . X . . X . . X X X X X X | $$ | . X . . X . . X . . X . . X . . X . . | $$ | . X . . X . . X . . X . . X . . X . . | $$ +---------------------------------------+[/go]

This arrangement of the stones is probably preferable for systematic reasons.

Life In 19x19

The maximum liberty of a group on a Go board

The maximum liberty of a group on a Go board

Re: The maximum liberty of a group on a Go board

Re: The maximum liberty of a group on a Go board

Re: The maximum liberty of a group on a Go board