The maximum liberty of a group on a Go board

Question

Bounty

One of the convincing conjectures, by Loopy Walt is,

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

Loopy Walt's post below explains how this conjecture is derived, and contains a partial proof.

AnttiP and I will award 250 point bounty each to anyone who proves or disproves this conjecture.

I will award 50~500 point bounty for any other provable fast solution, depending on how fast it is.

Introduction

The problem is about the game of Go. I will explain the basics you need to understand the problem, but if you are already familiar with this game, the problem is basically the following sentence.

Compute the function \$\operatorname{maxlib}(n)\$ for a natural number \$n\$, whose output is the maximum number of liberties a group can have on an \$n\times n\$ Go board.

\$\operatorname{maxlib}(n)\$ has an OEIS sequence (A320666). The currently known values is only up to \$n=24\$.

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

Go is a board game played on an \$n\times n\$ square grid, with two players, black and white, placing a stone alternately on an empty intersection of the grid. In this challenge we will only consider the black stones (X).

On this \$4\times4\$ board, black has \$3\$ groups.

X X . .
X . X .
X X . X
. . X X

A group is a group of stones that are connected horizontally or vertically.

Let's denote each group with different alphabets.

A A . .
A . B .
A A . C
. . C C

Group A has \$5\$ liberties. Group B has \$4\$ liberties, and group C has \$3\$ liberties. Liberty is the number of empty spaces connected horizontally or vertically to a group.

. . .
. X .
. . .

. . .
X X .
. . .

. . .
X X X
. . .

There are three \$3\times3\$ boards each with a single black group. Counting the liberties, it is \$4\$, \$5\$, and \$6\$, respectively. In fact, on a \$3\times3\$ board with nothing else than \$1\$ black group, \$6\$ is the maximum number of liberties that group can have.

Challenge

Compute the function \$\operatorname{maxlib}(n)\$ for a natural number \$n\$, whose output is the maximum number of liberties a group can have on an \$n\times n\$ Go board.

Example Output up to \$n=6\$

X 
1 -> 0

X . 
. . 
2 -> 2

. . . 
X X X 
. . . 
3 -> 6

. . X . 
. . X . 
X X X . 
. . . . 
4 -> 9

. . . . . 
. X X X X 
. X . . . 
. X X X . 
. . . . . 
5 -> 14

. X . . X . 
. X . . X . 
. X . . X . 
. X . . X . 
. X X X X . 
. . . . . . 
6 -> 22

You don't have to print the board positions.

Scoring

I will run your program for 30 minutes on my computer, not exclusively on a single core. The maximum \$n\$ you can reach within this time is your score, starting from \$n=1\$ incrementing by \$1\$. Your program must reach at least \$n=6\$, and I will not run your program if this seems unlikely.

The maximum score you can get is 10000.

The OS is Linux, and here is my CPU information.

Answer 1

Rust, score ≈ 15 in 37 minutes

This uses dynamic programming to run in \$O((1 + \sqrt5)^n n^{3/2})\$ time (much faster than a brute-force \$2^{n^2}n^{O(1)}\$ solution). The idea is that if we fill the grid row-by-row and column-by-column with stones or holes, trying each of these two decisions at each step, the only state we need to remember is

• whether the last point in each column has a stone or a hole,
• if it has a stone, which other stones it’s been connected to so far,
• if it has a hole, whether it’s already been counted as a liberty, and
• how many liberties have been counted so far;

and we can use a hash table to collapse states that are identical up to the number of counted liberties. The number of distinct states we need to store grows as \$\frac{5(1 + \sqrt{5})^{n + 5/2}}{4\sqrt[4]{5}\sqrt{2\pi}n^{3/2}}\$.

Build with cargo build --release and run with cargo run --release.

Cargo.toml

[package]
name = "liberty"
version = "0.1.0"
edition = "2021"

[dependencies]
mimalloc = { version = "0.1.28", default-features = false }

[profile.release]
codegen-units = 1
lto = true
panic = "abort"

src/main.rs

use mimalloc::MiMalloc;
use std::collections::HashMap;

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

#[derive(Copy, Clone, Eq, Hash, PartialEq)]
enum Point {
    Unused,
    Used,
    Stone(u32),
}

fn lib(n: usize) -> u32 {
    let mut states = HashMap::from([(vec![Point::Used; n], 0)]);

    let mut best = 0;

    for _i in 0..n {
        for j in 0..n {
            let mut states1 = HashMap::new();
            let mut add = |state: Vec<Point>, count: u32| {
                states1
                    .entry(state)
                    .and_modify(|c| *c = count.max(*c))
                    .or_insert(count);
            };
            for (state, count) in states {
                if state[j] != Point::Stone(j as u32) {
                    let mut state = state.clone();
                    let used = matches!(state[j], Point::Stone(_))
                        || (j != 0 && matches!(state[j - 1], Point::Stone(_)));
                    state[j] = if used { Point::Used } else { Point::Unused };
                    add(state, count + used as u32);
                } else if let Some(k) = state[j + 1..]
                    .iter()
                    .position(|&point| point == Point::Stone(j as u32))
                    .map(|k| j + 1 + k)
                {
                    let mut state = state.clone();
                    for point in &mut state[k..] {
                        if *point == Point::Stone(j as u32) {
                            *point = Point::Stone(k as u32);
                        }
                    }
                    state[j] = Point::Used;
                    add(state, count + 1);
                } else if !state[..j]
                    .iter()
                    .chain(&state[j + 1..])
                    .any(|state| matches!(state, Point::Stone(_)))
                {
                    best = best.max(count);
                }

                let mut state = state;
                let used0 = state[j] == Point::Unused;
                let used1 = j != 0 && state[j - 1] == Point::Unused;
                if used1 {
                    state[j - 1] = Point::Used;
                }
                if let Some(Point::Stone(k)) = j.checked_sub(1).map(|j1| state[j1]) {
                    if let Point::Stone(l) = state[j] {
                        if l < k {
                            for point in &mut state[k as usize..j] {
                                if *point == Point::Stone(k) {
                                    *point = Point::Stone(l);
                                }
                            }
                        } else if l > k {
                            for point in &mut state[j..] {
                                if *point == Point::Stone(l) {
                                    *point = Point::Stone(k);
                                }
                            }
                        }
                    } else {
                        state[j] = Point::Stone(k);
                    }
                } else if let Point::Stone(_) = state[j] {
                } else {
                    state[j] = Point::Stone(j as u32);
                }
                add(state, count + used0 as u32 + used1 as u32);
            }
            states = states1;
        }
    }

    for (state, count) in states {
        let mut it = state.into_iter();
        if let Some(j) = it.find_map(|point| {
            if let Point::Stone(j) = point {
                Some(j)
            } else {
                None
            }
        }) {
            if it.all(|point| {
                if let Point::Stone(k) = point {
                    j == k
                } else {
                    true
                }
            }) {
                best = best.max(count);
            }
        }
    }

    best
}

fn main() {
    for n in 0.. {
        println!("{n} {}", lib(n));
    }
}

Answer 2

Python 3, Using pnlwc (Probably Definitely not loopy Walt's conjecture)

def pnlwc(n):
    if n<4:return[0,0,2,6][n]
    if n%3==0:return n//3*(2*n-1)
    if n%3==2:return n//3*(2*n-1)+n
    return n//3*2*n+1

Try it online!

Conjectured optimal group

The conjectured formula seems to hold for all test cases larger than 3. It is definitely a lower bound, see the corresponding groups below.

n = 0 mod 3

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

n = 2 mod 3

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

n = 1 mod 3

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

Partial proof:

The n=0 mod 3 case is actually comparatively easy to prove:

Start with a few easy observations:

1. We can assume that all squares are either stone or lib. Proof: (easy) exercise. Hint: trade squares that are neither against adjacent libs.
2. As a consequence, we can either maximise libs or minimise stones.
3. Another consequence is that each of the four corners must neighbour at least one stone. It follows that at least one pair of opposite edges (E and W, say) must be connected by a stone path.
4. (Arithmetic 101:) (a) the stone-to-lib ratio is at least 1:2. Indeed, the E-W path if it is straight has exactly this ratio. If it meanders, (b) each turn knocks off one lib. (c) 3-way (4-way) branch points knock off 3 (6) libs. (d) Ends gain 1 lib if in the open and are neutral at a wall. In either case they incur a net loss because they necessitate a branch point. Finally, (e) a straight hugging a wall or (f) running parallel to another straight less than 2 squares away loses 1 lib per length unit (2 if parallel and directly touching).

Note: the reader is encouraged to verify themselves that the group can indeed be thought of as assembled from connected horizontal and vertical straights.

Inspecting the claimed optimal pattern we see that it has no turns and exactly n/3 3-way branch points. It has n/3 x (n+1) stones and n/3 x (2n-1) libs which is as predicted by our arithmetic 101 exactly n short of doubling the stones.

We will now show that this is as good as it gets:

The group must contain either at least n/3 horizontal or at least n/3 vertical straights. If it doesn't there is a y coordinate y0 where there is no stone or lib caused by a horizontal straight and similar for x coordinates and vertical straights. But this would mean square y0,x0 is neither stone nor lib which we have ruled out.

Let's say WLOG that it is n/3 verticals. Generally, connecting k horz displaced vert straights will cost at the very least 2xk-2 libs as all but 2 vert straights must connect to at least two others each. Indeed, the cheapest way would be through two horz straights each connected via a turn to either end of the vert.

That does, however, not work for the case at hand because the horizontal ends of this construction do not line up flush (cf. fig) and there is not enough slack in the system to create compensating elements. For example, just pushing the bridging horz all the way to the wall costs too much (101.e).

. . . . . . . .
. . O O O O . .
O O X X X X O O
O O X O O X O O
O O X O O X O O 
O O X O O X O O 
X X X O O X X X
O O O . . O O O 
. . . . . . . .

The next cheapest way of joining is branching off from a single horz which costs exactly n libs and is in fact precisely what the reference pattern does.

Note 1: This argument does not work for n=3 which may be viewed as a reason why the formula needs a special value there.

Note 2: The proof is relatively straight forward because for n=0 mod 3 the very small number of lost libs puts strong constraints on eligible patterns. The n=2 mod 3 and are considerably more forgiving and therefore tricky.