life-game/tools/old-ref/README.md

old-ref — независимый эталон клеточного автомата из старого прототипа

Автономный C++ harness (без Qt), который точно воспроизводит Life::nextStep() из old/life/life.cpp и печатает эталонные состояния поля.

Задача harness — зафиксировать поведение прототипа как есть, включая баг parent[] (массив объявлен вне циклов и не обнуляется на каждую клетку). Ничего не «улучшается».

Файлы

Файл	Что это
old_ref.cpp	исходник harness (порт + эталон «чистое большинство» + варианты для анализа)
old_ref	скомпилированный бинарник (в git не коммитится — собирается g++)
reference.json	главный эталон: массив {name,w,h,steps:[ascii0..asciiN]} (выходы ПРОТОТИПА)
ref-<name>.txt	те же выходы по одному кейсу в человекочитаемом виде (=== step k ===)
run.log	полный лог прогона (генерируется, в git не коммитится — .gitignore: *.log)
ce1.txt	минимальный контрпример отдельным файлом (3×3)
gen-clean.js / reference-clean.json	генератор и эталон чистого правила (наша спецификация)
gen-torus.js / reference-torus.json	генератор и эталон чистого правила на торе (wrap) — независимая проверка опции «Замкнутая карта»
gen-fixture.js	пересборка tests/parity-fixture.json для суиты
diff-our.js	дифтест index.html против reference-clean.json/reference.json (+reference-torus.json, если есть)

Оси и индексация

Поле — QVector<QVector<unsigned char>> field; инициализация: field.resize(wid); for i field[i].resize(hei).

field[i][j], где i — X (столбец, 0..wid-1), j — Y (строка, 0..hei-1). Подтверждено:

• painter.cpp: drawRect(i*sclx + 1, j*scly + 1, ...) — i по горизонтали, j по вертикали;
• life.cpp mouseEvent: xi = x*wid, yi = y*hei; field[xi][yi].

ASCII в harness: число строк = hei (Y), число символов в строке = wid (X), ascii[j][i] = field[i][j]. То есть строка ASCII = j (Y сверху вниз), позиция в строке = i (X слева направо). . = 0 (мёртвая), 1 = игрок 1, 2 = игрок 2.

Порядок обхода клеток в nextStep: X-мажорный — внешний цикл i (X), внутренний j (Y). Порядок опроса 8 соседей: left, up, right, down, up-left, down-left, up-right, down-right (сначала 4-соседство, затем диагонали).

Сборка и запуск

Harness сохранён в репозитории в tools/old-ref/. Исходник old_ref.cpp самодостаточен (без Qt и без old/), компилируется любым g++ из C++17. Готовый бинарник old_ref в git не коммитится (собирается локально).

cd tools/old-ref
g++ -std=c++17 -O2 -o old_ref old_ref.cpp
./old_ref > run.log          # прогоняет батарею, пишет reference.json и ref-*.txt

CLI-режим (одно поле, без записи файлов):

# <file.txt> <steps> [--proto|--clean|--swap|--torus]
printf '..2\n2.1\n1..\n' > ce1.txt
./old_ref ce1.txt 3 --proto   # точный порт прототипа
./old_ref ce1.txt 3 --clean   # эталон «чистое большинство из 3» (жёсткие границы)
./old_ref ce1.txt 3 --torus   # то же чистое правило, но заворот через края (wrap)
./old_ref ce1.txt 3 --swap    # тот же прототип, но обход клеток Y-мажорный

--torus — эталон для новой опции «Замкнутая карта»: в прототипе old заворотов не было (см. разведку exp-3), поэтому независимого прототипного эталона нет; правило рождения — то же чистое «большинство из 3», но соседи берутся с противоположной стороны.

Формат reference.json

[
  {
    "name": "cc_3x3_stale",
    "w": 3,
    "h": 3,
    "steps": [
      "..2\n2.1\n1..\n",
      ".2.\n...\n.2.\n",
      "...\n...\n...\n"
    ]
  }
]

steps[0] — стартовое поле, steps[k] — поле после k шагов nextStep() прототипа. Строки разделены \n; поле w×h (строк h, символов в строке w).

Набор кейсов: пустое поле, блок 2×2, блинкер (гор./верт.), глайдер, одиночная клетка, смешанные цвета (mix_2_1, mix_row_121), рождения по 3 соседям (birth_112/122/121/221), несколько рождений за шаг (multi_births), спец-случай залежавшегося parent[] (stale_split, cc_3x3_stale), детерминированные «плотные» LCG-поля 5×5…12×12 (seed'ы без rand()), одноцветные поля.

Что именно делает nextStep прототипа (цитата, дословно)

void Life::nextStep() {
	int num;
	int parent[8];
	for (int k=0; k<8; k++) parent[k]=0;          // обнуляется ОДИН раз, не на клетку
	for (int i = 0; i < wid; i++) {                // i = X
		for (int j = 0; j < hei; j++) {            // j = Y
			num = 0;
			if (i>0) if(field[i-1][j]>0) num++,parent[num-1] = field[i-1][j];
			if (j>0) if(field[i][j-1]>0) num++,parent[num-1] = field[i][j-1];
			if (i<wid-1) if(field[i+1][j]>0) num++,parent[num-1] = field[i+1][j];
			if (j<hei-1) if(field[i][j+1]>0) num++,parent[num-1] = field[i][j+1];
			if (i>0 && j>0) if(field[i-1][j-1]>0) num++, parent[num-1] = field[i-1][j-1];
			if (i>0 && j<hei-1) if(field[i-1][j+1]>0) num++, parent[num-1] = field[i-1][j+1];
			if (i<wid-1 && j>0) if(field[i+1][j-1]>0) num++, parent[num-1] = field[i+1][j-1];
			if (i<wid-1 && j<hei-1) if(field[i+1][j+1]>0) num++, parent[num-1] = field[i+1][j+1];
			if (field[i][j] == 0) {
				if (num == 3) {
					int firstp=0,secondp=0,p=0;
					for (int n=0; n<8; n++) {
						if (parent[n]>0) {
							if (firstp == 0) firstp = parent[n];
							else {
								if (secondp == 0) secondp = parent[n];
								else {
									if (parent[n] == secondp) p=secondp;
									else p = firstp;
								}
							}
						}
					}
					tmp[i][j] = p;
				}
			} else {
				if (num < 2 || num > 3) tmp[i][j] = 0;
				else tmp[i][j] = field[i][j];
			}
		}
	}
	field = tmp;
}

Границы жёсткие: соседи за краем не считаются (условия i>0, i<wid-1, j>0, j<hei-1).

Разбор правила рождения (пока данных нет — «чистый» случай)

parent[0..2] — цвета 1-го, 2-го и 3-го живых соседей в порядке опроса. Логика firstp/secondp/p в чистом виде (нет залежавшихся значений) эквивалентна правилу «цвет большинства из 3 соседей» для двух игроков:

3 соседа	firstp	secondp	3-й (parent[2])	p	итог
1,1,2	1	1	2	1	1
1,2,1	1	2	1	1	1
2,1,1	2	1	1	1	1
1,2,2	1	2	2	2	2
2,1,2	2	1	2	2	2
2,2,1	2	2	1	2	2

Анализ (пункт 4)

4.1. Совпадает ли прототип с «чистым большинством из 3»?

НЕТ. На батарее — 78 расхождений (шаг × кейс). Расхождения возникают только в полях со смешанными цветами 1 и 2, где ранее в порядке обхода встречалась клетка с ≥4 живыми соседями (она заполняет parent[3..7]), а затем встречается клетка с ровно 3 соседями. На одноцветных полях, блоке, блинкере, глайдере и «изолированных» рождениях (birth_*) расхождений нет.

Причина — баг parent[]: массив не обнуляется на каждую клетку. Для клетки с num==3 реально записываются только parent[0..2], но индексы parent[3..7] содержат цвета 4..8-го соседей последней ранее обработанной клетки, у которой их было больше. Цикл for (n=0; n<8; n++) видит эти «протухшие» значения. Итоговый p определяется последним ненулевым элементом parent[0..7]: p = (parent[last] == secondp) ? secondp : firstp — т.е. 3-й реальный сосед игнорируется, если есть залежавшееся значение.

4.2. Минимальный контрпример

Поле 3×3 (cc_3x3_stale в reference.json, файл ce1.txt):

..2
2.1
1..

Шаг 1:

Ожидалось (чистое большинство)   Прототип (факт)
.2.                              .2.
...                              ...
.1.                              .2.

Расходятся клетки (x=1, y=2) (внизу по центру): «чистое большинство» даёт 1, прототип — 2.

Трассировка. Сканирование X-мажор: (0,0),(0,1),(0,2),(1,0),(1,1),(1,2),…

• (0,0): 1 сосед → parent=[2,…];
• (0,1),(0,2): по 1 соседу;
• (1,0): 3 соседа [2,2,1] → рождение 2 (совпадает у обоих);
• (1,1): 4 соседа [2,1,1,2] → не рождается, но пишет parent[3]=2 (это залежавшееся значение);
• (1,2): реальные соседи (в порядке опроса) (0,2)=1, (0,1)=2, (2,1)=1 → parent=[1,2,1], num=3 → рождение. Но parent[3] всё ещё =2 от клетки (1,1). Цикл: firstp=1, secondp=2, parent[2]=1≠2 → p=1, затем parent[3]=2==secondp → p=2. → tmp[1][2]=2. Ошибка: 3-й (реальный) сосед перекрыт залежавшимся parent[3].

Ещё один найденный случайный контрпример (5×5):

2.2.
..1.
2..1
..1.
1...

4.3. Зависит ли результат от порядка обхода клеток?

ДА, зависит. Тот же код с обходом j внешний / i внутренний (--swap) даёт 60 расхождений на батарее. Пример — rnd_5x5_s1, шаг 1, клетка (x=0, y=2):

X-мажор (прототип)   Y-мажор (swap)
..1.2                ..1.2
.....                .....
1....                2....    <- здесь 1 vs 2
.1.22                .1.22
.....                .....

При этом сам прототип детерминирован: parent инициализируется нулями, все записи детерминированы, rand()/неинициализированной памяти нет. Зависимость — только от фиксированного порядка обхода (X-мажор), который и зашит в прототип.

4.4. Бывают ли «протечки» цвета (цвет не из соседей)?

НЕТ. p может принять только firstp (цвет 1-го живого соседа) или secondp (цвет 2-го живого соседа) — оба гарантированно реальные соседи (при num==3 индексы parent[0] и parent[1] всегда записаны текущей клеткой). Залежавшиеся значения могут лишь переключить выбор между этими двумя реальными цветами, но не подставить посторонний цвет. Эмпирически: на 300 000 случайных полей 2 378 830 рождений — «цвет не среди соседей»: 0.

Итог: прототип никогда не даёт клетке цвет, отсутствующий среди её 3 живых соседей; он лишь иногда выбирает не тот из двух присутствующих (меньшинство вместо большинства).

Что должна реализовать новая игра

По AGENTS.md новая игра намеренно исправляет баг: правило — «цвет новорождённой = цвет большинства из 3 живых соседей, tie-break — наименьший id».

Чтобы точно повторить прототип (байт-в-байт), нужно было бы воспроизвести баг:

parent[8] = {0,...,0}                    // ОДИН раз на весь шаг
for i in 0..wid-1:                       // X-мажор
  for j in 0..hei-1:
    num = 0
    for каждого соседа в порядке [left,up,right,down,up-left,down-left,up-right,down-right]:
      if сосед жив: parent[num] = цвет соседа; num++
    if cell == 0:
      if num == 3:
        firstp = secondp = p = 0
        for n in 0..7:                   // включает залежавшиеся parent[3..7]
          if parent[n] > 0:
            if firstp == 0: firstp = parent[n]
            elif secondp == 0: secondp = parent[n]
            elif parent[n] == secondp: p = secondp
            else: p = firstp
        next[i][j] = p
    else:
      next[i][j] = (num==2 || num==3) ? cell : 0
    // мёртвые без рождения: next[i][j] остаётся значением из копии field (== 0)
field = next

Но это НЕ то, что зафиксировано в AGENTS.md для новой игры. Спецификация требует чистое правило «большинство из 3 живых соседей» (баг прототипа явно назван багом и воспроизводить его не нужно). Поэтому:

• Правильная реализация новой игры = nextStepClean() из old_ref.cpp: собрать ровно 3 живых соседа, взять цвет, встретившийся ≥2 раз (при двух игроках всегда однозначно). Именно эти выходы (--clean) и есть эталон для новой игры.
• reference.json содержит выходы прототипа (с багом) — он нужен, чтобы понимать фактическое поведение старого кода и объяснять расхождения.
• Для сверки новой реализации с «правильным» правилом используйте --clean (или независимо посчитанное большинство): на всех кейсах, кроме случайных смешанных полей и cc_3x3_stale, прототип и чистое правило совпадают.

Дифтест с новой реализацией

Дополнительные файлы (рядом с harness):

Файл	Что это
gen-clean.js	генерирует reference-clean.json из CLI --clean для всех кейсов reference.json
reference-clean.json	эталон чистого правила (та же структура {name,w,h,steps})
gen-torus.js	генерирует reference-torus.json из CLI --torus (чистое правило + заворот)
reference-torus.json	эталон чистого правила на торе (независимая проверка wrap)
diff-our.js	дифтест: index.html (headless) против reference-clean.json, reference.json и reference-torus.json
gen-fixture.js	делает компактную фикстуру паритета для суиты (tests/parity-fixture.json)

Как воспроизвести (из корня репозитория):

# 1) собрать harness
g++ -std=c++17 -O2 -o tools/old-ref/old_ref tools/old-ref/old_ref.cpp

# 2) (при необходимости) пересобрать эталон чистого правила
cd tools/old-ref
node gen-clean.js        # reference-clean.json (28 кейсов, 273 сравнения)
node gen-torus.js        # reference-torus.json (чистое правило + wrap)

# 3) дифтест новой игры; exit 0 — наш step == clean (и torus, если файл есть)
node diff-our.js
CHROMIUM=/usr/bin/chromium-browser node diff-our.js   # при необходимости — путь к Chromium

# 4) обновить фикстуру для суиты
node gen-fixture.js      # -> tests/parity-fixture.json

diff-our.js автоматически берёт index.html из корня репозитория, а gen-fixture.js пишет фикстуру в tests/parity-fixture.json (пути считаются от tools/old-ref/, от корня репо всё работает как есть).

Результат (батарея из 28 кейсов, по 10 шагов; cc_3x3_stale — 3 шага):

• наш step == clean на всех 273 (кейс × шаг) полях — 273/273, 0 расхождений, 0 pageerror. То есть новая реализация точно соответствует чистому правилу «большинство из 3 живых соседей + tie-break наименьший id».
• наш step vs proto (баг parent[]): 195/273 совпало, 78 расхождений в тех же 10 кейсах, где proto ≠ clean: cc_3x3_stale, rnd_5x5_s2, rnd_6x6_s1, rnd_6x6_s2, rnd_8x8_s1, rnd_8x8_s2, rnd_10x10_s1, rnd_10x10_s2, rnd_12x12_s1, rnd_12x12_s2. Это ожидаемое поведение (баг прототипа намеренно исправлен), а не дефект новой игры.
• Классика (пустое поле, блок 2×2, блинкеры, глайдер, одиночная клетка, смешанные mix_*, рождения birth_*, multi_births, stale_split, rnd_5x5_s1, одноцветные поля): proto == clean == наш.
• Опция «Замкнутая карта» (wrap/torus): наш step == torus-эталон 273/273 (0 расхождений), gen-torus.js/reference-torus.json. 133 из 273 (кейс×шаг) полей на торе отличаются от жёстких границ — эталон содержателен. Заворот — новая опция (в прототипе old её не было), поэтому эталон считает сам harness строго по чистому правилу с соседями через край.

Паритет закреплён в headless-суите: tests/parity-fixture.json (6 кейсов: классика + плотные смешанные двухцветные + cc_3x3_stale) и проверки в tests/test.js (раздел 16). Известное расхождение с proto зафиксировано там как ожидаемое — наравне с требованием «наш == clean».