Implementation of Multi Color Knights by Claude

multi_color_knights.py

"""
Multi-player generalization of the Red & Black Knights construction.

Same square spiral, same "smallest unoccupied cell not threatened by a
hostile piece" rule, but the number of players, the move set of each
player's piece, and the directed threat relation between players are all
configurable. The two-knight case (OEIS A392177) is recovered with two
knight players that mutually threaten each other.

See https://jonka364.github.io/stendhal/stendhal.html for Karlsson's gallery
of variants, including the three-knight case implemented here.
"""

import math
from dataclasses import dataclass, field
from collections import namedtuple

from red_black_knights import cell_to_xy, KNIGHT_OFFSETS


# Other piece types from Karlsson's gallery, in case you want to experiment.
# Each piece's "offsets" are the squares it can attack from its current cell.
PIECES = {
    "knight":   [( 1,  2), ( 1, -2), (-1,  2), (-1, -2),
                 ( 2,  1), ( 2, -1), (-2,  1), (-2, -1)],
    "fers":     [( 1,  1), ( 1, -1), (-1,  1), (-1, -1)],
    "vazir":    [( 1,  0), (-1,  0), ( 0,  1), ( 0, -1)],
    "camel":    [( 1,  3), ( 1, -3), (-1,  3), (-1, -3),
                 ( 3,  1), ( 3, -1), (-3,  1), (-3, -1)],
    "zebra":    [( 2,  3), ( 2, -3), (-2,  3), (-2, -3),
                 ( 3,  2), ( 3, -2), (-3,  2), (-3, -2)],
    "antelope": [( 3,  4), ( 3, -4), (-3,  4), (-3, -4),
                 ( 4,  3), ( 4, -3), (-4,  3), (-4, -3)],
    "satrap":   [( 2,  0), (-2,  0), ( 0,  2), ( 0, -2)],
    "aspbad":   [( 2,  2), ( 2, -2), (-2,  2), (-2, -2)],
    "spehbed":  [( 3,  0), (-3,  0), ( 0,  3), ( 0, -3)],
}


@dataclass
class Player:
    name: str
    color_rgb: tuple        # (r, g, b) for visualization
    offsets: list           # attack vectors of this player's piece


SimResult = namedtuple("SimResult", ["players", "owner_of_cell", "xy_of_cell",
                                     "cells_by_player"])


def simulate(players, threatens, num_moves):
    """Run the multi-player construction for `num_moves` total turns.

    `threatens[i][j]` should be truthy iff a piece of player i threatens a
    piece of player j (and therefore player j must avoid squares attacked by
    player i's existing pieces). The diagonal is conventionally False
    (a piece doesn't threaten itself).

    Players move in round-robin order: turn k is taken by player k % len(players).
    """
    n = len(players)
    assert len(threatens) == n and all(len(row) == n for row in threatens)

    owner_of_cell = {}        # cell index -> player index
    xy_of_cell = {}           # cell index -> (x, y)
    cells_by_player = [[] for _ in range(n)]
    # For each player j, the set of (x, y) squares that *some hostile piece*
    # currently threatens. (Hostile to j, that is.)
    threats_against = [set() for _ in range(n)]
    # Per-player pointer: smallest cell index this player might legally take.
    pointer = [0] * n

    for turn in range(num_moves):
        pi = turn % n
        p = players[pi]
        my_threats = threats_against[pi]

        c = pointer[pi]
        while True:
            if c not in owner_of_cell:
                xy = cell_to_xy(c)
                if xy not in my_threats:
                    break
            c += 1

        owner_of_cell[c] = pi
        xy_of_cell[c] = xy
        cells_by_player[pi].append(c)

        # This new piece extends the threat sets of every player it threatens.
        for j in range(n):
            if threatens[pi][j]:
                tj = threats_against[j]
                x0, y0 = xy
                for dx, dy in p.offsets:
                    tj.add((x0 + dx, y0 + dy))

        pointer[pi] = c + 1

    return SimResult(players, owner_of_cell, xy_of_cell, cells_by_player)


# --------------------------------------------------------------------------
# Self-check: the two-knight case should reproduce A392177.
# --------------------------------------------------------------------------
def verify_two_knight_matches_oeis():
    from red_black_knights import A392177_HEAD
    black = Player("Black", (17, 17, 17), PIECES["knight"])
    red   = Player("Red",   (200, 30, 30), PIECES["knight"])
    threatens = [[False, True], [True, False]]
    sim = simulate([black, red], threatens, num_moves=2 * 250)
    blacks = sorted(sim.cells_by_player[0])[:len(A392177_HEAD)]
    assert blacks == A392177_HEAD, "two-knight regression failed"
    print("two-knight self-check passed (matches A392177).")


# --------------------------------------------------------------------------
# Visualization
# --------------------------------------------------------------------------
def plot(sim, out_path, title=None, figsize=10, dpi=200):
    import numpy as np
    import matplotlib.pyplot as plt

    radius = max(max(abs(x), abs(y)) for x, y in sim.xy_of_cell.values())
    side = 2 * radius + 1
    img = np.full((side, side, 3), 255, dtype=np.uint8)

    colors = np.array([p.color_rgb for p in sim.players], dtype=np.uint8)
    for c, (x, y) in sim.xy_of_cell.items():
        row = radius - y
        col = radius + x
        img[row, col] = colors[sim.owner_of_cell[c]]

    fig, ax = plt.subplots(figsize=(figsize, figsize), facecolor="white")
    ax.imshow(img, interpolation="nearest")
    ax.axhline(radius, color="#888", linewidth=0.4)
    ax.axvline(radius, color="#888", linewidth=0.4)
    ax.set_xticks([]); ax.set_yticks([])
    for spine in ax.spines.values():
        spine.set_visible(False)
    if title:
        ax.set_title(title, fontsize=11)
    fig.tight_layout()
    fig.savefig(out_path, dpi=dpi, bbox_inches="tight")
    plt.close(fig)
    counts = "  ".join(f"{p.name} {len(sim.cells_by_player[i]):,}"
                       for i, p in enumerate(sim.players))
    print(f"wrote {out_path}  (radius {radius}, {counts})")


# --------------------------------------------------------------------------
# Pre-built scenarios
# --------------------------------------------------------------------------
def three_knights_full_enmity():
    """Three knight-players, every pair mutually hostile.
    Turn order: Black, Red, Cyan, Black, Red, Cyan, ...
    """
    players = [
        Player("Black", ( 17,  17,  17), PIECES["knight"]),
        Player("Red",   (200,  30,  30), PIECES["knight"]),
        Player("Cyan",  ( 30, 170, 200), PIECES["knight"]),
    ]
    # Full enmity: everyone threatens everyone else; nobody threatens themselves.
    threatens = [[i != j for j in range(3)] for i in range(3)]
    return players, threatens


def three_knights_cyclic_enmity():
    """Asymmetric variant: Black threatens Red, Red threatens Cyan,
    Cyan threatens Black. Each player only worries about ONE opponent.
    """
    players = [
        Player("Black", ( 17,  17,  17), PIECES["knight"]),
        Player("Red",   (200,  30,  30), PIECES["knight"]),
        Player("Cyan",  ( 30, 170, 200), PIECES["knight"]),
    ]
    threatens = [
        [False, True,  False],   # Black -> Red
        [False, False, True ],   # Red   -> Cyan
        [True,  False, False],   # Cyan  -> Black
    ]
    return players, threatens


if __name__ == "__main__":
    verify_two_knight_matches_oeis()

    for N in (60_000, 600_000):
        players, threatens = three_knights_full_enmity()
        sim = simulate(players, threatens, num_moves=N)
        plot(sim, f"/home/claude/three_knights_full_{N}.png",
             title=f"Three knights, full enmity — {N:,} moves")

    for N in (60_000, 600_000):
        players, threatens = three_knights_cyclic_enmity()
        sim = simulate(players, threatens, num_moves=N)
        plot(sim, f"/home/claude/three_knights_cyclic_{N}.png",
             title=f"Three knights, cyclic enmity (B→R→C→B) — {N:,} moves")

multi_color_knights

A small generalization of the Red & Black Knights construction featured in
[Numberphile (May 2026)](https://youtu.be/UiX4CFIiegM) with Neil Sloane —
OEIS sequences [A392177](https://oeis.org/A392177),
[A392178](https://oeis.org/A392178), and [A395357](https://oeis.org/A395357).

The original construction has two players (Black and Red) take turns placing
knights on a square spiral, each placing on the smallest unoccupied cell not
attacked by an existing opposing knight. Same-color knights are allowed to
attack each other; only the opposing color matters. This script lifts that
into an arbitrary number of players, with arbitrary chess-piece move sets,
and an arbitrary directed threat relation between players.

The rule

Pick:

• a list of players, each with a name, a display color, and a list of
  attack offsets (e.g. the eight knight (±1,±2)/(±2,±1) moves);
• a boolean matrix threatens where threatens[i][j] is True iff a piece
  of player i threatens a piece of player j.

Players move in round-robin order. On turn k, player k % n picks the
smallest-indexed unoccupied cell on the square spiral that is not currently
attacked by any piece belonging to a player who threatens them.

The diagonal of threatens is conventionally False — a piece doesn't
threaten itself, and same-color pieces can attack each other freely.

Run it

python multi_color_knights.py

That runs the two-knight regression (matches the first 75 terms of A392177
exactly) and writes four PNGs: full enmity and cyclic enmity, at 60k and
600k moves each.

Depends on red_black_knights.py from the same repo for cell_to_xy and
the OEIS reference data, plus numpy + matplotlib for rendering.

Built-in scenarios

three_knights_full_enmity() — three knight players, every pair mutually
hostile. Produces a clean three-region territorial split with sharp
diagonal boundaries, structurally analogous to the two-knight result.

three_knights_cyclic_enmity() — three knight players in a directed
threat cycle B→R→C→B. Each player only avoids one rival, so the spiral
fills much more densely; the picture is dominated by tight zebra-stripe
patterns with chevron-shaped distortions, with the territorial split
broken.

Customizing

Different pieces. The PIECES dict has knight, fers (1,1), vazir
(1,0), camel (3,1), zebra (2,3), antelope (3,4), satrap (2,0), aspbad
(2,2), spehbed (3,0) — Karlsson's naming. Mix freely:

players = [
    Player("Black", (17, 17, 17),    PIECES["knight"]),
    Player("Cyan",  (30, 170, 200),  PIECES["antelope"]),
]
threatens = [[False, True], [True, False]]

When piece types differ, the threat relation becomes geometrically
asymmetric — X threatens Y iff X is at one of X's own offsets from Y. The
simulator handles this correctly because each player carries its own
offset list.

Different threat graphs. Any boolean matrix works. A few worth trying:

• Bipartite team play: two teams of two, hostile across teams only.
• One bully: one player threatens all others, none threaten back.
• Self-threat: set threatens[i][i] = True and same-color knights also
  block each other (this collapses to a single-color trapped-knight-style
  variant for that player).

More than three players. The simulator is n-agnostic. Whether the
territorial-split pattern survives at n=4 with full enmity is, as far as
I can tell, an open empirical question.

Scaling

Roughly 7 seconds per million half-moves, linear in N, dominated by hash
lookups into the per-player attack sets. Image side grows as $\sqrt{N}$.

Memory is the real ceiling — the attack sets hold ~5 (x, y) tuples per
placed piece on average, at ~60 bytes per tuple in a Python set:

• 1M total moves ≈ 600 MB
• 10M ≈ 6 GB
• 64M (Branicky's largest published render) won't fit in a typical Python
  process

Past ~15–20M, switch the tuple sets to a single set[int] with packed
keys like x * OFFSET + y, or move to a fixed-radius numpy boolean grid.

Reference

Karlsson's gallery of variants, including selective-enmity and mixed-piece
examples, is at https://jonka364.github.io/stendhal/stendhal.html. The
convergence proof for the two-knight case (Branicky, Karlsson, Sloane) is
in preparation as of May 2026.

Source video: https://www.youtube.com/watch?v=VgmDuBCayPw