Research

Magic: The Gathering офіційно визнали найскладнішою грою в світі

Magic: The Gathering - це карткова гра, в якій чарівники касти заклинання, закликають істот і використовують магічні об'єкти, щоб перемогти своїх супротивників. В процесі гри два або більше гравців збирають по колоді з 60 карт з різними силами. Колоди збираються з пулу більше 20 000 карт, створених у міру розвитку гри. Хоча Magic: The Gathering схожа на рольові фентезійних ігри на зразок Dungeons and Dragons, в ній набагато більше карт і більш складні правила, ніж у інших карткових ігор.

Що призводить до цікавого питання: наскільки складна MTG, якщо порівнювати її з іншими реальними іграми (тобто тими, в які люди насправді грають, а не якимись теоретичними)? Відразу обмовлюся, під складністю тут маються на увазі не складність розуміння ігрового процесу, а складність як глибина і багатогранність гри.

Наскільки складна Magic: The Gathering? Складніше не буває

Відповідь дала робота Алекса Черчілля, незалежногодослідника і дизайнера настільних ігор з Кембриджа, Великобританія, Стелли Бідерман з Технологічного інституту Джорджії і Остіна Херрік з Університету Пенсільванії.

Його команда виміряла обчислювальну складністьгри, закодований її так, щоб її можна було відтворити на комп'ютері або машині Тьюринга. «Ця конструкція встановила, що Magic: The Gathering - сама обчислювально складна гра реального світу, відома в літературі», заявили вчені.

Але спершу трохи передісторії. Дуже важливим завданням в інформатиці є визначення того, чи може проблема бути вирішена в принципі. Наприклад, рішення того, чи є два числа відносно простими (іншими словами, їх найбільший спільний дільник повинен бути більше одиниці) - це завдання, яке можна виконати за кінцеве число чітко визначених кроків і, отже, розрахувати.

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

Але хоча обидві ці проблеми обчислюваності, ресурси, необхідні для їх вирішення, сильно різняться.

Ось, де з'являється поняття обчислювальної складності. Це ранжування, засноване на ресурсах, необхідних для вирішення проблем.

В даному випадку рішення про те, чи є двачисла відносно простими, може бути знайдено за кілька кроків, які пропорційні полиномиальной функції вхідних чисел. Якщо вхідний значення дорівнює x, найважливіший член полиномиальной функції буде в формі Cx ^ n, де C і n - константи. Це відноситься до класу P, що означає поліноміальний час.

Навпаки, шахова задача повинна вирішуватисяметодом грубої сили, і кількість необхідних кроків збільшується пропорційно експоненційної функції вхідних даних. Якщо введенням буде x, найважливіший член експоненційної функції має вигляд Cn ^ x, де C і n - константи. Тут ми маємо справу з категорією більшої складності EXP, або експоненціального часу.

Крім цього існують різні інші категорії з різною складністю, а також завдання, для вирішення яких немає алгоритмів. Вони називаються невичіслімимі.

З'ясувати, до якої категорії складності відносятьсягри - справа непроста. Більшість реальних ігор мають обмежені межі складності, такі як розмір ігрового поля. І це робить багато хто з них тривіальними з точки зору складності. «Більшість досліджень в області алгоритмічної теорії реальних ігор в основному стосувалося узагальнень популярних ігор, а не реальних версій», говорить Черчілль.

Таким чином, лише кілька реальних ігор мають нетривіальну складність. Сюди входять «Палички» (або «Точки і квадрати»), Дженга і тетріс.

Робота вчених показала, що Magic: the Gathering набагато складніша, ніж ці три. Метод підрахунку, в принципі, простий. Черчілль і його компанія почали з перетворення сил і властивостей кожної карти в набір кроків, які можна закодувати.

Потім вони розіграли партію між двома гравцямина машині Тьюринга. І, нарешті, показали, що визначення того, у якого з гравців є виграшна стратегія, еквівалентно відомої в інформатиці «проблеми зупинки».

Це проблема визначення того, чи закінчитькомп'ютерна програма з певним введенням роботу або буде працювати вічно. У 1936 році Алан Тьюринг довів, що жоден алгоритм не зможе визначити відповідь. Іншими словами, це завдання невичісліма.

Тому результат Черчілля показує, щовизначення результату в грі Magic: the Gathering не піддається розрахунку. «Це перший результат, який показує, що існує реальна гра, для якої визначення виграшної стратегії не піддається обчисленню», кажуть вчені. Це цікава робота, яка піднімає важливі фундаментальні питання теорії ігор. Наприклад, Черчилль і співавтори кажуть, що провідна формальна теорія ігор передбачає, що будь-яка гра повинна бути обчислюваною. Magic: the Gathering не відповідає припущенням, які зазвичай роблять комп'ютерні вчені при моделюванні ігор.

А ви грали в цю гру? Розкажіть в нашому чаті в Телеграма.