[Computer-go] Maximum number of strings on a go board

Ton Hospel computer-go at ton.iguana.be
Wed Nov 27 16:01:45 PST 2013

```Back in 2006 there were a number of messages about the maximum number of strings on a 19x19 board. As noted then the answer is 277.

In the mean time there has been progress on this issue in the context of placing dominoes on a board which is an equivalent problem. A number of papers from 2011 basically solved this issue.

(usefull to statically size your group list if you ever play on weird board size)

Here is a table for all rectangular boards up to size 19:

Chain table
1|   0
2|   1   2
3|   2   4   6
4|   2   5   8  12
5|   3   7  11  14  18
6|   4   8  13  17  22  26
7|   4  10  15  21  26  31  37
8|   5  11  17  24  29  36  42  48
9|   6  13  20  26  33  40  47  54  61
10|   6  14  22  30  37  44  53  60  68  76
11|   7  16  24  33  41  49  58  66  75  83  92
12|   8  17  26  36  44  54  63  72  82  91 100 109
13|   8  19  29  39  48  58  69  78  88  99 108 118 129
14|   9  20  31  42  52  63  74  84  95 106 117 128 138 149
15|  10  22  33  45  56  68  79  91 102 114 125 137 148 160 172
16|  10  23  35  48  60  72  85  97 109 122 134 146 159 171 183 196
17|  11  25  38  51  63  76  90 103 116 129 142 155 168 182 195 208 221
18|  12  26  40  54  67  81  95 109 123 137 151 165 179 192 206 220 234 248
19|  12  28  42  57  71  86 101 115 130 145 159 174 189 203 218 233 248 262 277

(the diagonal are the numbers for square boards)

Below this is a simple perl program that calculate the values for any m x n size board with the function "chains". It also has a simple generator for a table like the above one.

==============================================================================
#!/usr/bin/perl -w
use strict;
use warnings;

# Determine the maximum number of chains on any m x n board

# Based on information from
#  Computing the Domination Number of Grid Graphs
#  Saturated Domino Coverings
#    http://arxiv.org/pdf/1112.2115v1
#  The Domination Number of Grids
#    http://arxiv.org/pdf/1102.5206v1

our \$VERSION = "1.000";

my \$MAX = 19;

sub naive {
my (\$m, \$n) = @_;

return int((\$m+2)*(\$n+2)/5-4);
}

sub gamma {
my (\$m, \$n) = @_;

(\$m, \$n) = (\$n, \$m) if \$m > \$n;

my \$result;
if (\$m == 1) {
\$result = (\$n+2) / 3;
} elsif (\$m ==  2) {
\$result = (\$n+2)/2;
} elsif (\$m ==  3) {
\$result = (3*\$n+4) / 4;
} elsif (\$m ==  4) {
\$result = \$n;
\$result++ if \$n == 5 || \$n == 6 || \$n == 9;
} elsif (\$m ==  5) {
\$result = (6*\$n+8)/5;
\$result = 9 if \$n == 7;
} elsif (\$m ==  6) {
if (\$n % 7 == 1) {
\$result = (10*\$n+10)/7;
} else {
\$result = (10*\$n+12)/7;
}
} elsif (\$m ==  7) {
\$result = (5*\$n+3)/3;
} elsif (\$m ==  8) {
\$result = (15*\$n+14)/8;
} elsif (\$m ==  9) {
\$result = (23*\$n+20)/11;
} elsif (\$m == 10) {
if (\$n % 13 == 0 || \$n % 13 == 3 and \$n != 13 && \$n != 16) {
\$result = (30*\$n+37)/13;
} else {
\$result = (30*\$n+24)/13;
}
} elsif (\$m == 11) {
if (\$n == 11 || \$n == 18 || \$n == 20 || \$n == 22 || \$n == 33) {
\$result = (38*\$n+21)/15;
} else {
\$result = (38*\$n+36)/15;
}
} elsif (\$m == 12) {
\$result = (80*\$n+66)/29;
} elsif (\$m == 13) {
if (\$n % 33 == 14 || \$n % 33 == 15 || \$n % 33 == 17 || \$n % 33 == 20) {
\$result = (98*\$n+111)/33;
} else {
\$result = (98*\$n+78)/33;
}
} elsif (\$m == 14) {
if (\$n % 22 == 18) {
\$result = (35*\$n+40)/11;
} else {
\$result = (35*\$n+29)/11;
}
} elsif (\$m == 15) {
if (\$n % 26 == 5) {
\$result = (44*\$n+27)/13;
} else {
\$result = (44*\$n+40)/13;
}
} else {
\$result = naive(\$m, \$n);
}
return int(\$result);
}

sub chains {
my (\$m, \$n) = @_;

return \$m*\$n - gamma(\$m, \$n);
}

sub show_gamma_table {
my (\$max) = @_;

for my \$n (1..\$max) {
printf "%2d|", \$n;
for my \$m (1..\$n) {
printf " %3d", gamma(\$m, \$n);
}
print "\n";
}
}

sub show_chain_table {
my (\$max) = @_;

for my \$n (1..\$max) {
printf "%2d|", \$n;
for my \$m (1..\$n) {
printf " %3d", chains(\$m, \$n);
}
print "\n";
}
}

sub show_tiddly_table {
my (\$max) = @_;

print "|m\\n|";
for my \$n (1..\$max) {
printf " !%d|", \$n;
}
print "\n";

for my \$n (1..\$max) {
printf "| !%d|", \$n;
for my \$m (1..\$n) {
my \$c = chains(\$m, \$n);
my \$s = \$m*\$n - naive(\$m, \$n);
if (\$s > \$c) {
print "bgcolor(green):";
} elsif (\$s < \$c) {
print "bgcolor(red):";
}
printf " %d|", \$c;
}
for my \$m (\$n+1..\$max) {
print "|";
}
print "\n";
}
}

if (0) {
print "Gamma table\n";
show_gamma_table(\$MAX);
print "\n\n";
}

print "Chain table\n";
show_chain_table(\$MAX);
print "\n\n";

if (0) {
print "Tiddly table\n";
show_tiddly_table(\$MAX);
print "\n\n";
}

```