Пʼятнадцять рівнів із сіду, без ручного дизайну

9 листопада 2026 р. · 6 хв читання · Команда Тямки

Як ігри Тямки будують кожен рівень з одного 32-бітного сіду на mulberry32, навіщо кожній грі специфікація і тест-вектори від незалежного порту на Python і як розвʼязувач у «Трубах» відкидає поля з двома відповідями.

Таблиця Шульте першого рівня із сідом 42 завжди складається з рядків 7 8 2, 5 4 6 і 9 3 1. Її однаково будують телефон, браузер, сервер під Deno і окремий скрипт на Python, написаний за специфікацією, а не за нашим кодом. Жоден рівень у 15 іграх Тямки ніхто не малює руками. Поле народжується з одного 32-бітного числа, сіду, а руками ми пишемо тільки таблицю рівнів і специфікацію з тест-векторами, які будь-яка реалізація має повторити біт у біт. Нижче про те, як це влаштовано і де легко помилитися під час портування. А ще про розвʼязувач у «Трубах», через який у кожного поля одна відповідь.

Генератор, який можна переписати від руки

Усі пʼятнадцять ігор беруть випадковість з однієї функції в games/shared/random.ts.

export function nextUint32(state: number): [value: number, state: number] {
  const s = (state + 0x6d2b79f5) | 0;
  let t = Math.imul(s ^ (s >>> 15), 1 | s);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
  return [(t ^ (t >>> 14)) >>> 0, s >>> 0];
}

Це mulberry32. Увесь його стан складається з одного беззнакового 32-бітного цілого, тож сід і є початковим станом, і більше нічого зберігати не треба. Функція не тримає стан у собі, а повертає новий разом зі значенням, тому в модулях ігор немає прихованого глобального генератора. Вони не викликають Math.random і не читають годинник. Сід на кожну спробу вибирає застосунок, передає його в гру і зберігає разом із результатом. Сід завдання дня береться з дати, nextUint32(dayNumber), тож того дня всі гравці отримують ту саму гру, рівень і сід.

Перемішування поверх генератора зроблене за Фішером–Єйтсом від останнього індексу, а місце для обміну дає next() mod (i + 1). Остача від ділення трохи зміщує розподіл. За специфікацією Шульте це зміщення менше за 2⁻²⁶, і вона прямо називає його своєю частиною. Порт, який би його «виправив», будував би інші поля.

Де ламається порт

Специфікація записує mulberry32 як звичайну арифметику за модулем 2³², і порт на Python виходить майже дослівним. Ось він із tools/vector-ports/ref_prng.py.

M=0xFFFFFFFF
def imul(a,b): return (a*b)&M
def nxt(state):
    s=(state+0x6D2B79F5)&M
    t=imul(s^(s>>15), 1|s)
    t=((t+imul(t^(t>>7), 61|t))&M)^t
    return (t^(t>>14))&M, s

Майже, бо в трьох місцях мови поводяться по-різному. Множення в JavaScript відбувається в числах з рухомою комою, а добуток двох 32-бітних чисел може перевищити 2⁵³, і тоді молодші біти губляться. Тому в TypeScript стоїть Math.imul, а в Python звичайне множення з маскою, бо цілі числа там не переповнюються. Зсув праворуч у JavaScript буває знаковий >> і логічний >>>, а mulberry32 потрібен логічний. У Python після маски число невідʼємне, тож звичайний >> там уже логічний. І побітові операції в JavaScript повертають знакове 32-бітне число, тому наприкінці стоїть >>> 0, інакше приблизно половина значень вийде відʼємною.

Перевірити свій порт просто. У games/shared/vectors.json для сідів 0, 1, 42 і 4294967295 записано по три перші значення. Для сіду 0 це 1144304738, 1416247 і 958946056. Якщо збіглося, генератор той самий.

Специфікація раніше за код

Поруч із кодом кожної гри в games/ лежать spec.md, vectors.json і тест. Специфікація починається з версії, дати й речення, яке задає планку. Будь-який порт, чи то перегравання на бекенді, чи інший клієнт, має відтворити кожен вектор біт у біт.

У більшості специфікацій однакові розділи: правила, бали, як генерується рівень, таблиця рівнів і що лежить у векторах. Правила описують, що кожен ввід робить зі станом, аж до вводів, які нічого не змінюють, як-от натискання на вже знайдене число чи хід після кінця рівня. Друга реалізація теж на них натрапить, тому їх записано. Коли правило змінюється, змінюється й версія. «Протилежності» з 26 вересня мають версію 2, а в першому рядку специфікації досі сказано, чим відрізнялася перша.

Вектори від другої реалізації

Тест-вектор Шульте містить рівень, сід, кожне натискання з часом, поле до і після, наслідок кожного натискання й підсумковий рахунок. Важливо, звідки ці числа. Випадки з назвою generated: порахував незалежний порт на Python, написаний за специфікацією, а не за TypeScript. Випадки hand: це крайні ситуації, пораховані вручну. Якщо TypeScript проходить вектор, який видав Python, дві реалізації прочитали специфікацію однаково. Це сильніша перевірка, ніж тест, написаний поруч із кодом, який він перевіряє.

Файли ще й підтверджують один одного. Спільний вектор перемішування перетворює числа від 1 до 9 із сідом 42 на 7 8 2 5 4 6 9 3 1. Перший рівень Шульте починається з перемішування саме цих девʼяти чисел, тож поле з першого абзацу і є цим вектором, розкладеним на три рядки.

«Труби», де відповідь одна

У «Трубах» плитки повертають, поки кожен отвір не зустріне інший і всі плитки не зʼєднаються в одну мережу. Гра перевіряє саме це правило, тож прийняла б і другий розвʼязок. Але поле з двома відповідями неможливо розвʼязати самим міркуванням. До того ж, коли час вичерпано, гра показує збережений розвʼязок і позначає кожну плитку, що від нього відрізняється. Це чесно лише тоді, коли іншого розвʼязку немає.

Тому генератор вирощує випадкове остовне дерево від центральної плитки, без хрестовин на чотири отвори, і питає розвʼязувач, скількома способами можна повернути його плитки так, щоб поле склалося. Якщо не рівно одним, дерево відкидається, і з того самого потоку випадкових чисел росте наступне. Лише потім кожну плитку повертають на випадковий кут, а якщо поле вийшло вже складеним, повертають ще раз. Як таке поле розвʼязує гравець, розповідає стаття як розвʼязати головоломку з трубами.

Розвʼязувач countSolutions у games/pipe-connect/pipe-connect.ts тримає для кожної клітинки 16-бітну множину масок, які ще може мати її плитка. Поширення обмежень викидає маску з отвором у бік сусіда, який не може відкритися назустріч, і маску без такого отвору, якщо сусід мусить відкритися сюди. Це повторюється, поки нічого не змінюється, і результат не залежить від порядку обходу. Якщо вибір лишився, пошук розгалужується на клітинці з найменшою кількістю варіантів. За рівності береться та, що має менший індекс, а маски перебираються за зростанням. Він зупиняється на другому розвʼязку або після 20 000 вузлів. Повний набір поворотів зараховується, лише якщо кожна плитка зʼєднана з джерелом, тож замкнені кільця окремо від решти не проходять.

Через фіксований порядок кількість вузлів детермінована. Її записано у вектори, і порт на Python збігся з нею точно. Для першого поля рівня 1 із сідом 42 це один вузол, тобто поширення обмежень розвʼязує поле без жодного розгалуження. У векторах це поле записано числами. Кожна плитка є 4-бітною маскою (вгору 1, праворуч 2, вниз 4, ліворуч 8). Число 14 вгорі означає отвори праворуч, вниз і ліворуч, а 13 у центрі це джерело з отворами вгору, вниз і ліворуч.

розвʼязок    старт
 2 14 12      4  7  9
 6 13  1      6 14  4
 1  3  8      4  6  1

Ліміт у 20 000 вузлів потрібен, щоб телефон ніколи не завис на поганому полі, і до нього не доходить. Найважче отримати єдину відповідь там, де труби виходять за край поля і заходять з протилежного боку. 9 листопада ми знову прогнали 15-й рівень, найбільше таке поле, на сідах від 0 до 1999. Найдовший пошук, разом із відкинутими деревами, зайняв 927 вузлів, стільки ж, скільки записано в специфікації у вересні. На рівні 11, полі 4×4 із таким загортанням, генератор відкидає більш ніж два дерева на кожну головоломку, яку залишає. «Потрібні суми» роблять так само, лише рахують розвʼязки повним перебором.

Що це дає серверу

Рівень повністю задають гра, номер рівня і сід, тому сервер може його відбудувати. Перевірка рахунку запускає ті самі модулі ігор під Deno, переграє ходи гравця і зберігає рахунок, який отримала сама. Докладніше про це в записі про перегравання партії на сервері. Для завдання дня сервер ще й сам обчислює гру, рівень і сід цього дня і відхиляє партію, яка з ними не збігається.

Є й межа. Для звичайного рівня сід вибирає застосунок, тож скрипт може перебирати сіди, поки не знайде легке поле. Наступний крок у тому, щоб сід видавав сервер.

Що досі робиться руками

Таблиці рівнів, від розміру поля й лімітів часу до рівня, з якого в «Трубах» починається загортання. Шульте зупиняється на 7×7, бо це найбільше поле, де клітинка ще має 44 pt на телефоні завширшки 375 pt. Більшість специфікацій прямо називає ці числа гіпотезами до плейтестів. Решта ігор на логіку побудована так само, кожна за своєю специфікацією.