sab.code.lab 1c85091186 chore: восстановление репозитория из снапшота v0.3.1

Прежняя git-история утрачена при переносе проекта на машину владельца
(снапшот без .git). Хэши коммитов в docs/reports/* относятся к утраченной
истории.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

2026-08-07 09:34:02 +02:00

3.9 KiB

Raw Permalink Blame History

ADR-0002: алгоритм поиска групп и дамэ — flood fill

Дата: 2026-08-05 | Статус: принято (этап 1)

Контекст

Движку правил (packages/core) на каждый ход нужно находить группы камней и их дамэ: при проверке захватов, самоубийства, при подсчёте и в эвристике мёртвых групп. План этапа 1 предписывает выбрать между flood fill и union-find по микро-бенчмарку и зафиксировать выбор в ADR.

Альтернативы

Flood fill — обход группы стеком от стартового камня, дамэ собираются в множество. Простая реализация, локальный обход (только затронутые группы).
Union-find — массив parent на всю доску, объединение соседей одного цвета, дамэ агрегируются по корням. Теоретически эффективен при инкрементальных обновлениях, но наша позиция неизменяема: структуру пришлось бы перестраивать на каждый ход, что обнуляет его главное преимущество.

Бенчмарк

packages/core/bench/group-bench.mts (запуск: npx tsx ...): оба алгоритма находят все группы и дамэ на случайных позициях 19×19 (плотности 0.35/0.55/0.75, 40 позиций × 300 итераций на плотность, детерминированный RNG). Среда: Node.js 20, x86-64. Контрольные суммы результатов совпали.

Плотность	flood fill	union-find	u/f
0.35	230.4 мс	373.1 мс	1.62
0.55	288.5 мс	505.6 мс	1.75
0.75	328.3 мс	596.8 мс	1.82
Итого	847.1 мс	1475.5 мс	1.74

Union-find проигрывает на всех плотностях (в 1.6–1.8 раза): на маленькой доске (361 клетка) стоимость полного прохода union-find и аллокаций Map/Set по корням не окупается, а flood fill обходится дешёвыми операциями над массивом и одним множеством дамэ на группу.

Решение

Оставляем flood fill (реализован в groupAt, packages/core/src/board.ts).

Причины

Быстрее на целевом профиле (доски 9–19, обходы только затронутых групп).
Существенно проще код и меньше аллокаций; неизменяемость BoardState всё равно не даёт переиспользовать структуру union-find между ходами.
Производительности достаточно с запасом: полный пересчёт всех групп 19×19 — десятки микросекунд, а движок обходит лишь соседние с ходом группы.

Компромисс

Если этапы 3–4 (ИИ) покажут профилировкой, что пересчёт групп — узкое место (например, массовые симуляции MCTS), решение пересматривается: кандидат — инкрементальный union-find с копированием при записи или кэш групп в узлах симуляции. Точка пересмотра — бенчмарк на реальной нагрузке ИИ, не раньше.

3.9 KiB Raw Permalink Blame History Unescape Escape