It is currently Tue Aug 09, 2022 10:49 am

 All times are UTC - 8 hours [ DST ]

 Page 1 of 1 [ 4 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: The maximum liberty of a group on a Go board #1 Posted: Wed Apr 13, 2022 3:27 am
 Beginner

Posts: 6
Liked others: 3
Was liked: 2
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

 Post subject: Re: The maximum liberty of a group on a Go board #2 Posted: Fri Apr 15, 2022 1:01 am
 Lives with ko

Posts: 208
Liked others: 297
Was liked: 7
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

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

Posts: 1576
Liked others: 139
Was liked: 439
As said in the OP, this group has 229 liberties.

`[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

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

Posts: 1270
Liked others: 14
Was liked: 147
Rank: German 1 Kyu
`[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: https://igohatsuyoron120.de/index.htm
Igo Hatsuyōron #120 (really solved by KataGo)

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Life In 19x19.com General Topics    Introductions and Guidelines    Off Topic    Announcements    General Go Chat    Beginners    Amateurs    Professionals       Lee Sedol vs Gu Li    Go Rules    Forum/Site Suggestions and Bugs    Creative writing    Tournaments       Ride share to tournaments Improve Your Game    Game Analysis    Study Group    Teachers/Club Leaders       Teacher advertisements    Study Journals L19²GO (Malkovich)    1-on-1 Malkovich games    Big Brother Malkovich games    Rengo Games    Other versions of turn-based games Go Gear    Go Books    Go Book Reviews    Computer Go    Gobans and other equipment    Trading Post    New Products/Upgrades/Sales Go Club Forums    Go Club Discussions       Honinbo Go League    American Go Association Forum       Go Congress 2011 volunteers       AGA volunteers ( non-congress)    Australian Go Association    European Go Federation Forum    Singapore Weiqi Association    KGS    ASR League    IGS    OGS    Tygem    WBaduk    Turn Based Servers    Insei League Events    Kaya.gs       King of the Hill