It is currently Sun May 29, 2022 3:53 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 4 posts ] 
Author Message
Offline
 Post subject: The maximum liberty of a group on a Go board
Post #1 Posted: Wed Apr 13, 2022 3:27 am 
Beginner

Posts: 4
Liked others: 3
Was liked: 1
A simple problem came to mind a while ago, but I couldn't think of a clear solution.
Quote:
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:
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:
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:
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:
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:
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


This post by xiver77 was liked by: Elom0
Top
 Profile  
 
Offline
 Post subject: Re: The maximum liberty of a group on a Go board
Post #2 Posted: Fri Apr 15, 2022 1:01 am 
Lives with ko

Posts: 153
Liked others: 227
Was liked: 5
Rank: Weak
OGS: Elom0
Online playing schedule: I'll mostly play against myself, will because I haven't started my Alpha-Zero style self-play yet.
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?

Top
 Profile  
 
Offline
 Post subject: Re: The maximum liberty of a group on a Go board
Post #3 Posted: Fri Apr 15, 2022 2:28 am 
Gosei
User avatar

Posts: 1551
Liked others: 137
Was liked: 432
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]

Top
 Profile  
 
Offline
 Post subject: Re: The maximum liberty of a group on a Go board
Post #4 Posted: Fri Apr 15, 2022 2:46 am 
Lives in sente
User avatar

Posts: 1269
Liked others: 14
Was liked: 146
Rank: German 1 Kyu
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.

_________________
The really most difficult Go problem ever: http://igohatsuyoron120.de/index.htm
Igo Hatsuyoron #120 (still unresolved by professionals, maybe solved by four amateurs, really solved by KataGo)

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group