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

I made this post to make sure the computer-go community knows about this
(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
#    http://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p141/pdf
#  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";
}



More information about the Computer-go mailing list