andrey
36f0fa2623
- tests/test.js: 148 -> 206 проверок (разделы 23 wrap/torus, 24 зоны, 25 бюджет, 26 размеры, 27 сейв v2/миграция, 28 рендер/resize 300x300, 29 HUD 381-400px); resetGlobals сбрасывает tool/reason/winner; sleep заменён на waitCond/settleViewport. - tools/old-ref/: независимый torus-эталон (nextStepCleanWrap, CLI --torus, gen-torus.js, reference-torus.json); diff-our.js сверяет stepN при setWrap(true). - index.html: медиазапрос HUD 380->400px (убрана микро-обрезка 381-388px); инлайн-комментарий про согласованность useWrap/setWrap. - AGENTS.md: полный список контракта дополнен; useWrap-заметка уточнена; покрытие приведено в соответствие. README: скорость — константа в коде, не UI. - .gitignore: tools/old-ref/.tmp-*.txt. - Прогоны: check: OK; суита 206/206 (3 повтора); паритет clean 273/273 + torus 273/273. - Ревью-гейт R2-3 (Oracle): PASS; minor/nit закрыты.
351 lines
20 KiB
Markdown
351 lines
20 KiB
Markdown
# 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 не коммитится** (собирается локально).
|
||
|
||
```bash
|
||
cd tools/old-ref
|
||
g++ -std=c++17 -O2 -o old_ref old_ref.cpp
|
||
./old_ref > run.log # прогоняет батарею, пишет reference.json и ref-*.txt
|
||
```
|
||
|
||
CLI-режим (одно поле, без записи файлов):
|
||
|
||
```bash
|
||
# <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`
|
||
|
||
```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` прототипа (цитата, дословно)
|
||
|
||
```cpp
|
||
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`) |
|
||
|
||
Как воспроизвести (из корня репозитория):
|
||
|
||
```bash
|
||
# 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».
|