Life In 19x19http://lifein19x19.com/ The maximum liberty of a group on a Go boardhttp://lifein19x19.com/viewtopic.php?f=15&t=18688 Page 1 of 1

 Author: xiver77 [ Wed Apr 13, 2022 3:27 am ] Post subject: The maximum liberty of a group on a Go board 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, otherwiseThis 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..XCode: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 02 23 64 95 146 227 298 389 5110 6111 7412 9213 10514 12215 14516 16117 18218 21019 22920 25421 28722 30923 33824 376

 Author: Elom0 [ Fri Apr 15, 2022 1:01 am ] Post subject: Re: The maximum liberty of a group on a Go board 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?

 Author: jlt [ Fri Apr 15, 2022 2:28 am ] Post subject: Re: The maximum liberty of a group on a Go board 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]

 Author: Cassandra [ Fri Apr 15, 2022 2:46 am ] Post subject: Re: The maximum liberty of a group on a Go board 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.

 Page 1 of 1 All times are UTC - 8 hours [ DST ] Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Grouphttp://www.phpbb.com/