Дві гри на злиття, одне питання: чи можна зіграти будь-яку з них бездоганно? Відповідь пролягає через кут дошки, суперника, який так і не з’являється, і число заввишки в сімнадцять показників степеня.
Написано й відредаговано англійською. Цю українську версію створено машинним перекладом; там, де важлива точність, авторитетним є англійський оригінал. Читати оригінал англійською →
Почнімо з гри, яку знають усі. 2048 — чотири напрямки, сітка 4×4, плитки, що подвоюються при зіткненні, — строго кажучи, не розв’язана. Ніхто не написав алгоритму, який грає в неї ідеально. Ми маємо лише дуже сильні наближення. Пошук expectimax, що зазирає приблизно на вісім ходів уперед і оцінює кожну дошку за кількома вручну налаштованими евристиками — вільні клітинки, великі плитки, притиснуті до краю, плавність, — досягає плитки 32768 більш ніж у третині партій, 1 а найсильніший загальнодоступний рушій доходить до плитки 65536 у кількох відсотках випадків. 2 Якщо узагальнити гру до дошки m×n, то навіть просто визначити, чи досяжна цільова плитка, — NP-складна задача. 3 Сильна гра — не те саме, що розв’язана.
Як високо може піднятися одна плитка? На шістнадцяти клітинках відповідь — невеликий елегантний підрахунок. Розкладіть дошку як спадні сходи: 65536, 32768, 16384 і так далі донизу аж до самотньої 2. Кожна плитка рівно на один степінь двійки нижча за сусідню, тож шістнадцять різних степенів від 21 до 216 ідеально заповнюють дошку, а 65536 = 216 стоїть на вершині: по одному показнику на клітинку. Така стеля, якщо гра завжди дає вам лише двійки. Але 2048 один раз із десяти породжує 4, і одна вчасна четвірка протягує сімнадцятий показник, піднімаючи справжній максимум до 131072 = 217 — степені на сімнадцять плиток, упаковані в шістнадцять клітинок. 4 Жодна людина її не збудувала; кілька ШІ ледь її торкнулися.
Чому ці дошки винагороджують звичку заховати найбільшу плитку в кут? Плитку посередині можна штовхнути в чотири боки, і її раз у раз розлучають із плитками, з якими вона хоче поєднатися. Кутова плитка торкається двох стін; поштовхи в бік стін, до яких вона вже притиснута, не можуть її зрушити, і доки ви не штовхаєте від них, вона стоїть на місці, поки все інше впорядковується навколо неї. Вишикуйте решту в монотонну «змійку» — найбільша в куті, далі вона згинається туди й назад у спадному порядку, — і один змах може запустити каскад злиттів. 1 Саме ця евристика панує у звичайній людській грі, і саме її майже повторно відкривають ШІ, коли їм дозволяють самим налаштовувати свої ваги.
Гра на злиття з випадковою появою плиток не має суперника — лише погоду. «Розв’язати» її означає перемогти кубики в середньому, а не перемогти розум.
Тепер нахиліть дошку в три виміри. 3927 — кубічна родичка 2048: ґратка 3×3×3 із 27 клітинок, шість напрямків зсуву замість чотирьох і плитки, що зливаються трійками — 3 у 9, 9 у 27, 27 у 81, — основа три там, де в 2048 основа два. 5 Чи переживає стратегія кутового складання додатковий вимір? Куб має вісім кутів, а кутова клітинка тепер торкається трьох граней, а не двох, — вона мала б бути ще стійкішою, притиснута трьома стінами одразу, хоча шість напрямків дають дошці більше способів розхитати вашу структуру. «Змійка» перетворюється на складений шлях, що проходить крізь усі три шари. Наскільки мені вдалося з’ясувати, ніхто не перевірив, чи справді ця аналогія справджується, — це міркування, а не вимірювання.
А стеля? Правило «один показник на клітинку» підказало б 327 ≈ 7,6 трильйона як грубу верхню межу. Але аналогія сильно тріщить. Додатковий показник 2048 узявся зі щасливої четвірки; 3927 завжди породжує лише найменшу плитку, голу 3, тож жодного бонусу немає. Гірше того, потрійне злиття потребує трьох плиток, вишикуваних у лінію, а кожен рядок, стовпець і стовп у кубі 3×3×3 має рівно три клітинки завдовжки, тож кожне злиття поглинає цілу лінію. Це обмеження кусає набагато сильніше за будь-що в пласкій грі й майже напевно тягне справжній максимум значно нижче за 327. Яке те справжнє число, я ніде не знайшов обчисленим. (Це чітко позначене міркування; описану вище механіку взято з проєктної документації гри.)
Ось тонкощі, через які «ідеальна гра» стає слизьким поняттям. Гра на злиття з випадковою появою плиток — це однокористувацька стохастична гра, пасьянс проти кубика, а не дуель. Ніщо не обирає найгіршу появу плитки, щоб вас погубити; є лише байдужий генератор випадкових чисел. Тож правильне поняття оптимальної гри — expectimax: максимізувати очікуваний результат за розподілом появи плиток. Це рішуче не minimax: minimax передбачає супротивника, і якщо справді дозволити йому ставити кожну плитку («злісна 2048», evil 2048), гра стає жорстокішою — такою, в якій вас можна змусити програти. Оскільки кубики в принципі можуть видати будь-яку послідовність, стратегії, яка гарантує певну плитку, може просто не існувати. Тож чесна відповідь на питання «чи існує ідеальна стратегія?» така: для стохастичної гри найкраще, що взагалі можна визначити, — це стратегія, найкраща в середньому, і точно обчислити її для 2048 неможливо, 6 а для 3927 це питання цілком відкрите.