Script to generate and count all unique 3x3 'response patterns' for RocAlphaGo.

response_patterns_3x3.py

# A pattern is a length-8 tuple of values in {-3, -2, -1, 0, 1, 2, 3} where
# the sign indicates color and the magnitude indicates liberties. The center
# of the 3x3 grid must be empty to consider the location. Indices of a
# pattern:
#
#   0 1 2
#   3 4 5
#   6 7 8

WHITE = -1
BLACK = +1
EMPTY = 0
LIBERTY_VALUES = [-3, -2, -1, 0, 1, 2, 3]

# Symmetries implemented as indices such that 'sym_pattern[i] = pattern[idxs[i]]'
noop   = [0, 1, 2, 3, 4, 5, 6, 7, 8]
fliplr = [2, 1, 0, 5, 4, 3, 8, 7, 6]
flipud = [6, 3, 0, 7, 4, 1, 8, 5, 2]
diag1  = [0, 3, 6, 1, 4, 7, 2, 5, 8]
diag2  = [8, 5, 2, 7, 4, 1, 6, 3, 0]
rot90  = [2, 5, 8, 1, 4, 7, 0, 3, 6]
rot180 = [8, 7, 6, 5, 4, 3, 2, 1, 0]
rot270 = [6, 3, 0, 7, 4, 1, 8, 5, 2]

SYMMETRIES = [noop, fliplr, flipud, diag1, diag2, rot90, rot180, rot270]

# Visible neighbors of each location within the pattern.
NEIGHBORS = [
    [1, 3],     # 0 borders 1 and 3
    [0, 2, 4],  # 1 borders 0, 2, and 4
    [1, 5],     # etc..
    [0, 4, 6],
    [1, 3, 5, 7],
    [2, 4, 8],
    [3, 7],
    [4, 6, 8],
    [5, 7]
]


def apply_symmetry(pattern, sym_idxs):
    return tuple(pattern[i] for i in sym_idxs)


def uniquify(pattern):
    # Try all symmetries, keep the one that is the lowest-ordered.
    return min(apply_symmetry(pattern, sym_idxs) for sym_idxs in SYMMETRIES)


def validity_check(pattern, up_to_idx):
    if pattern[4] != EMPTY:
        return False
    for i in range(up_to_idx + 1):
        visible_liberties = 0
        for n_idx in NEIGHBORS[i]:
            neighbor = pattern[n_idx]
            # Invalid if neighbor has the same sign but different num liberties.
            if neighbor is not None and neighbor * pattern[i] > 0 and neighbor != pattern[i]:
                return False
            # If neighbor is empty, count it as a liberty.
            if neighbor == EMPTY:
                visible_liberties += 1
        # Invalid if liberties at i is less than number of visible liberties
        if pattern[i] != EMPTY and abs(pattern[i]) < visible_liberties:
            return False
    return True


def dfs_find_all_patterns():
    patterns = set()

    def dfs_step(partial_pattern, next_idx, pattern_set):
        if next_idx == 9:
            # At a leaf - add unique pattern to set.
            pattern_set.add(uniquify(partial_pattern))
        else:
            # Add each value at the given index and recurse if still valid.
            for val in LIBERTY_VALUES:
                new_pattern = partial_pattern[:next_idx] + (val,) + partial_pattern[next_idx + 1:]
                if validity_check(new_pattern, next_idx):
                    # Still valid so far. Recurse.
                    dfs_step(new_pattern, next_idx + 1, pattern_set)

    init_pattern = (None, None, None,
                    None, EMPTY, None,
                    None, None, None)
    dfs_step(init_pattern, 0, patterns)
    return patterns


all_patterns = dfs_find_all_patterns()
print "found", len(all_patterns), "unique patterns."

import pickle
with open('patterns3x3.pkl', 'w') as f:
    pickle.dump(all_patterns, f)