Британские учёные доказали, что Magic: The Gathering - самая сложная игра в мире! По уровню желтизны такой заголовок соответствует скорее Пикабу, чем почтенной Тесере, но не спешите делать выводы. 24 марта 2019 года на сайте arxiv.org появился препринт научной статьи под заголовком "Magic: The Gathering полна по Тьюрингу". В статье показывается, что задача поиска победной стратегии в партии Magic эквивалентна знаменитой задаче остановки, которая, как известно, неразрешима в современной теории вычислимости. Отсюда падкая на сенсации буржуазная пресса делает вывод, что наша с вами любимая мотыга бесконечно сложна.
К сожалению, мы не журналисты, а потому не можем себе позволить принять этот факт, не разобравшись. Я приглашаю вас в небольшое путешествие по теории алгоритмов, чтобы вы тоже смогли понять, на какую науку тратятся деньги западных налогоплательщиков.
"Да он кукухой двинулся", - слышу я голос с задних рядов. "Раньше он нам впаривал магию, это можно было терпеть. Теперь он хочет задвинуть университетский курс ..."
Без паники! Будет интересно! Прочитав научное изыскание, я наметил четыре основных вопроса: Что? Всё? Это? Значит? Кто такой Тьюринг, причём тут его полнота, о какой задаче остановки идёт речь и как это всё соотносится с Magic? Я постараюсь изложить материал так, что вам не потребуется специфической подготовки. Голого энтузиазма будет достаточно.
Алан Мэтисон Тьюринг широко известен двумя фактами. Первый: он выставил дураками всех криптографов нацистской Германии, предложив во время второй мировой войны метод взлома шифровальной машины "Энигма", вернее, той её модификации, которая применялась немецким флотом. Германия воевала на трёх фронтах: на западном, на восточном и на шифровальном, и вот на этом третьем Тьюринг уделал немцев в одни ворота (правда, не в одиночку. У Тьюринга был штат в 10 000 человек, а сама работа основывалась на ранних достижениях польских математиков). Эта история вошла во все возможные учебники по криптоанализу и даже легла в основу нескольких фильмов. Второй факт: Тьюринг подвергся уголовному преследованию за свою нетрадиционную ориентацию, позорящую (как считалось в послевоенной Великобритании) честь настоящего джентельмена. В 2013 году власти помиловали Алана Тьюринга и принесли ему извинения за преследование. Самому Тьюрингу, впрочем, было всё равно: его жизнь трагически оборвалась летом 1954 года в результате отравления цианидом. Что это было: самоубийство или халатность при обращении с химикатами, никто не знает.
Бенедикт Камбербэтч в роли Алана Тьюринга взламывает "Энигму" силой мысли
Во время, свободное от раскалывания военных шифров, общения с юношами и химических опытов, Тьюринг закладывал основы современной теории алгоритмов. Ещё до войны он предложил формализацию понятий "вычисления" и "алгоритмы", описав так называемую "машину Тьюринга". Представьте себе игру: у вас есть лента, на которой записаны какие-то символы. По ленте передвигается курсор, указывающий на конкретную позицию. Кроме того, у вас есть табличка, ряды которой называются "состояниями машины". Каждая запись в таблице - это команда: если курсор смотрит на символ A, запиши на его место символ B, передвинь курсор вправо или влево на C, а потом перейди в состояние D. Одно из состояний мы называем конечным: если машина попадает в него, работа завершена.
Окей, это не самая веселая игра на свете (на уровне некоторых евросухарей). Ваша задача не выполнить вычисления (это как раз делает машина Тьюринга), а составить табличку и заставить машину делать что-то полезное. Задачи, для которых можно придумать такую табличку, мы называем вычислимыми.
Теперь, что касается полноты. Как вы уже раскусили, к бодипозитиву этот термин не имеет никакого отношения. Он больше про вычисления. Машина Тьюринга - не единственный способ описать преобразование одних цепочек символов в другие. Есть ещё куча всяких заумных математических моделей, вроде регулярных грамматик, сетей Петри или клеточных автоматов. Учёных интересует вопрос: какие модели "круче"? Могут ли одни модели вычислить то, что недоступно другим? Довольно быстро выяснилось, что превзойти машину Тьюринга не так-то просто. Все модели оказываются либо такими же, либо уступают машине Тьюринга в своих возможностях. Если ваша модель может выполнять все те же вычисления, что и машина Тьюринга, она называется "полной по Тьюрингу". Вот и всё. Как правило, полнота по Тьюрингу означает, что вы можете сымитировать машину Тьюринга в рамках своей модели. Например, в виде программы на вашем любимом языке программирования. Все эти ваши Pascal, C++ и Java тьюринг-полные. Кроме того, тьюринг-полными являются такие перлы, как Brainfuck, Malbolge, Befunge и собственно Perl.
Несколько вольное представление машины Тьюринга в массовой культуре
Ну что, вы там ещё не заснули? Пора возвращаться в мир настольных игр! Если помните, статья началась с заявления "Magic: The Gathering полна по Тьюрингу". Попробуем переварить эту фразу. Выходит, Magic способна производить те же вычисления, что и машина Тьюринга. Я вижу ваше недоумение: мы точно говорим о Magic? Magic? Это где земли, гоблины, дряные расклады, отвратный арт, Ричард, что бы с ним такое сделать, Гарфилд? Да, Magic. Похоже, мы сможем смоделировать машину Тьюринга прямо на движке игры!
"Ты хочешь сказать, что играя в Magic, мы с противником сможем выполнять какие-то вычисления?" Нет! Такую штуку вы сможете провернуть на базе любой другой настолки. Я хочу сказать, что при некоторой подготовке вы сможете ввести Magic в такое состояние, что игра САМА будет выполнять эти вычисления! БЕЗ ВАС! Вы будете сидеть и смотреть как игра играет сама с собой, выполняя программу в виде карт в вашей колоде. При этом всё будет происходить в рамках правил Magic - не подумайте, что мы будем играть картами Magic во что-то другое.
Дело за малым. 1) научиться вводить игру в состояние, в котором от игроков ничего не зависит, 2) научиться представлять входные и выходные данные и 3) запустить исполнение программы. Попробуем описать первый пункт в общих чертах. Игра начинается с того, что первый игрок видит на своей руке семь конкретных карт: [ Ancient Tomb, Lotus Petal x 3, Grim Monolith, Power Artifact, Staff of Domination ]. Основная задача на первом этапе - собрать хорошо известную комбу Grim Monolith + Power Artifact, позволяющую получить произвольное число маны. С этой маны можно выставить на поле Staff of Domination, который за несколько десятков активаций возьмёт в руку все карты из колоды. Теперь можно веселиться. Веселье предполагает розыгрыш забавных карт, передачу части из них под контроль противника, опустошение его колоды, опустошение своей колоды, возвращение в свою колоду карт, которые будут "программой" для нашей машины, создание "входных данных" и, наконец, "запуск".
Стартовый набор начинающего программиста
Если помните, машина Тьюринга читает данные с некой ленты символов. Мы будем представлять эту ленту токенами существ. Тут есть одна маленькая проблема: в Magic нельзя сказать, что какое-то существо стоит "справа" или "слева" от другого существа. Нам нужно как-то исхитриться и закодировать именно порядок. К счастью, у токенов есть несколько параметров: тип, цвет, сила и выносливость. Мы будем кодировать "положение" токена относительно текущего с помощью цвета и силы. Если токен зелёный - он слева от текущего положения, если белый - то справа. Сила токена - это расстояние до текущего положения. Зелёный слоник 3/3, например, "расположен" в третьей ячейке слева от текущего положения. Где мы возьмём столько разных токенов? Хороший вопрос. К счастью у нас есть карта Riptide Replicator, как будто специально предназначенная для задания входных данных.
Репликатор умеет создавать токены любых цветов и размеров
После того, как подготовка закончилась, мы можем начинать. Игроки делают ходы как обычно, другой вопрос, что ни в один момент времени у них нет никакого выбора: все решения форсированы и однозначно определены.
- В смысле, все решения определены. Но противник же берёт карты из колоды?
- Нет не берёт. Во-первых, его колода была удалена из игры (Karn Liberated + Capsize позаботились об этом на этапе подготовки), во-вторых, мы c помощью карты Donate выдали ему Recycle, чтобы он не проиграл из-за невозможности взять карту.
У противника нет карт ни в руке, ни на поле боя, но проиграть он не может из-за Recycle
- Понятно. Но мы-то берём карту за ход?
- Сначала мы разыгрываем одну карту с руки благодаря Wild Evocation. Потом берём карту за ход. Её мы разыграть не можем, потому что нет маны.
Так мы разыгрываем карты из колоды, по одной за ход
- А почему у нас нет маны?
- Потому что наша единственная земля не разворачивается в шаге разворота благодаря комбинации карт Choke и Prismatic Omen.
Из-за этой парочки наша единственная земля никогда не разворачивается
- А если вдруг мы разыграем с Wild Evocation не ту карту? Карта-то выбирается случайным образом.
- Нет. На момент срабатывания Wild Evocation у нас в руке только одна карта.
- Но рано или поздно карты в колоде закончатся?
- Нет, у нас есть Wheel of Sun And Moon. Разыгрываемые карты уходят под низ колоды, образуя цикл.
С этой штукой на поле наша колода никогда не закончится
- Но у нас же есть существа. Почему бы не ходить ими в атаку?
- Потому что у обоих игроков на поле стоит Blazing Archon.
Этот парень запрещает игрокам ходить в атаку
- Зачем вообще тогда нужны существа на поле боя?
- Это входные данные. Разыгрывая некоторые карты, мы можем создавать и убивать существ, имитируя таким образом чтение и запись данных.
- И когда же это всё закончится?
- О, это хороший вопрос. У нас в колоде есть карта Coalition Victory, проверяющая наличие на поле боя существ всех цветов. Для того, чтобы завершить программу, нужно запрограммировать создание токенов всех пяти цветов.
Художественный текст на этой карте особенно символичен
Если вы хотите вникнуть в детали происходящего, то вот вам пара видосов, один - с доскональным разбором, а второй - интересный. Суть в любом случае одна: мы проворачиваем утомительный сетап, а затем крутим нашу колоду по кругу и ждём, когда Coalition Victory скажет "конец". Или не скажет ...
Вот! Это последний вопрос, который я бы хотел рассмотреть на сегодня. Где гарантия, что процесс вычислений когда либо остановится? Поиск такой гарантии известен в теории алгоритмов под названием "проблема остановки". Существует ли способ определить, остановится ли заданная машина Тьюринга при заданных входных данных? Ответ на этот вопрос дал сам Алан Тьюринг в 1936 году. Нет, не существует. Применительно к Magic (в которой, как вы помните, остановка машины равносильна победе игрока) это означает, что задача поиска победной стратегии алгоритмически неразрешима. Вспомните об этом, когда в следующий раз кто-то пожалуется на тупость ботов в Magic: Arena ...
Чувствую себя немного похожим на этого чувака после написания статьи ...
Ну что, вы ещё здесь? Не самая лёгкая статья для переваривания, но мы уже заканчиваем. Я верю, что многим из вас придёт в голову любимый вопрос всех студентов "а зачем всё это нужно"? Прямого ответа у меня нет. Наука есть наука - треть результатов никогда не найдёт практического применения, ещё треть - пригодится через 50 лет, про остальные напишут в СМИ уже на следующей неделе. Никакого практического смысла в машине Тьюринга на основе Magic, разумеется, нет. Теоретический смысл, однако, очевиден - всё это затевалось для доказательства алгоритмической неразрешимости игры. Похоже, я отнял у вас кучу времени только для того, чтобы сказать, что Magic ещё сложнее, чем вы думали ... На этом откланиваюсь. Спасибо за внимание!
Хочется добавить, что в реальности довольно много вещей которые являются тьюринг-полными. Ведь даже в своей статье Тьюринг уподоблял человека, вычисляющего вещественное число, машине, которая находится в конечном числе состояний. Кто-то вводит понятие тупой машины когда нужны какие-то внешние механические действия для перевода машины из одного состояния в другое. Замените ленту на столы, а числа на блюда, и у вас получится тьюринг-полный ресторан. Так что и HTML - это тоже в некотором смысле язык программирования(тьюринг-полный). Хотя кажется, что споры об этом еще ведутся.
Обожаю посты sadsido. Один из немногих оставшихся генераторов качественного контента не Тесере.
Цените!
Наполовину переведенная прошлогодняя заметка теперь называется "качественный контент"? Ну ок, видимо я отстал от жизни...
Переведённая? Вот это новость. А можно ссылку на оригинал, почитаю на досуге.
Ссылки не сохранилось, потому как это было полгода назад, но в той статье было все то же самое - кто такой Тьюринг, что есть машина Тьюринга, как оно работает, почему противник не может нам помешать...
Только там еще рассматривалось на примере, как именно оно работает.
Возможно это не перевод, а заметка "по мотивам", но стиль написания почти один-в-один.
Статья говорит о том, что гипотетически в мтг существует набор карт и механик, которые при определенных условиях могут привести к автономности партии. Ок, понятно - но как это делает игру сложной?
Начиная от того, что описанная в статье ситуация приближается к статистической невозможности в обычных условиях игры и заканчивая тем, что в тех же нормальных условиях эта хрень не эффективна на 100%.
Главный вывод из этой статьи в том, что алгоритм нахождения победной стратегии в Magic принципиально невозможен. Утверждение доказывается от противного: если бы алгоритм существовал, по построив вот это состояние игры из статьи, мы бы смогли решить задачу остановки. А это невозможно - сам Тьюринг доказал это ещё в 36 году. Значит, алгоритма нет. Отсюда мы делаем вывод о сложности Magic.
Не возможен для данного набора карт в колоде описанного в статье. А более общо утверждение - не для любой колоды в мтг есть алгоритм нахождения выйгрышного алгоритма. Так? И вопрос другой все еще остается открыт - есть ли колода для которой такой алгоритм можно найти. Или он намного проще и пример такой колоды есть?
Более общий вывод - невозможен единый общий алгоритм, позволяющий гарантированно просчитать путь к завершению партии мтг из _любой_ ситуации. Просто потому что "любая" - это в том числе и описанная в статье.
Но это до тех пор, пока в дело не вступят турнирные правила, по которым судья выдаст игроку с Wild Evocation техническое поражение. Four Horsemen передавали привет, если вы понимаете о чём я =)
Ситуация тут немного отличается от Four Horsemen. Проблема с всадниками в том, что они проворачивают некий цикл, который периодически возвращает игру в то же состояние, при этом не могут сказать, сколько именно раз они собираются это делать. Это может быть расценено как Slow Play. Наш игрок мало того что изменяет состояние поля боя (плодит токены), так ещё и пасует. Передаёт ход противнику. Более того, он хочет выиграть - у него есть Coalition Victory.
Так что засчитывать поражение ему не за что. Они потратят всё время тура, перейдут в ходы и разойдутся с ничьей =)
Игрок всадниками как раз таки хочет выиграть, причём явно сильнее Тьюринга. У него-то вероятность стремится в пределе к 100%, просто он не может заранее точно назвать количество итераций цикла и состояние открытых зон в конце.
А вот Тьюринг уже давно мог бы выиграть ещё до генерации своей адской машины, если бы так этого хотел.
Попадись они мне как судье на турнире, всадник без проблем получил бы свой заслуженный warning за slow play, а Тьюрингу пришлось бы сначала убедить меня в том, что это не stalling
Согласен в том, что "Всадник" может выиграть, но не уверен, успеет ли он. "Тьюринг" не уверен даже в том, может ли он выиграть =)
Утверждение касается алгоритма в общем виде. Его не существует. В частных случаях, которых большинство, алгоритм найти можно, зачастую он очевиден. Если силы ваших существ достаточно, чтобы пробить летальные повреждения - идите в атаку, вот и весь алгоритм.
Представьте себе шахматы. Насколько я знаю, на данный момент мы не знаем, чем закончится игра из стартовой позиции. Но для многих других позиций, особенно в эндшпиле, результат очевиден. С Magic примерно то же самое, с той лишь разницей, что в магии ответа не существует, а в шахматы мы рано или поздно решим ...
Не большинство, а все кроме приведенного в статье, не так ли?
Сложно сказать. Я уверен, что неразрешимых состояний бесконечно много, но вряд ли кто-то захочет тратить время на их поиск. Главная проблема в том, что неразрешимость-то ещё и доказать надо.
Да и зачем? Для опровержения какого-то обобщения достаточно одного контрпримера, теперь он есть. Дальше уже можно заниматься частностями, но это скорее в области искусственного интеллекта, нежели чем в теории алгоритмов.
… не понял. Но очень интересно!
Я не технарь, так что многого тут не понял, но если речь идет о том, что в результате при помощи такой колоды можно запустить автоматический алгоритм действий, не предполагающий принятие решений игроком с какого-то момента, то разве все не спотыкается в момент выбора цвета жетона, даже если договориться, что все карты и эффекты всегда разыгрываются автоматически?
Цвет-то должен кто-то выбрать, алгоритмом это не предусмотрено, правильно?
Riptide Replicator используется только для создания исходного состояния ленты. Все последующие изменения ленты генерятся безусловными триггерами Rotlung Reanimator и Xathrid Necromancer. Просто тут в посте упомянута только часть карт, используемых для создания машины, а полный список можно найти в исходной статье (ссылка есть в самом начале).
FormatCevt справедливо заметил, что процесс создания новых токенов в моей статье не описан. Там используются карты "Rotlung Reanimator" и "Xathrid Necromancer", которые на этапе подготовки были "изменены" с помощью "Artificial Evolution". Я решил, что тема и так катастрофически сложная, чтобы загружать её дополнительными деталями. Пример одного цикла работы машины вы можете найти в видео - все токены создаются автоматически и нужного цвета.