| Life In 19x19 http://lifein19x19.com/ |
|
| The maximum liberty of a group on a Go board http://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, 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 |
|
| 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. |
|
| Author: | Cassandra [ Fri Apr 15, 2022 2:46 am ] |
| Post subject: | Re: The maximum liberty of a group on a Go board |
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 Group http://www.phpbb.com/ |
|