Магия: Сбор Тьюринга завершен?

24

Я знаю, что это очень специфический вопрос, и я сомневаюсь, что на него ответит любой, кто еще не знаком с правилами Магии. Перекрестная публикация на Draw3Cards . Вот исчерпывающие правила игры Magic: The Gathering . Смотрите этот вопрос для получения списка всех магических карт. У меня вопрос - игра Turing Complete?

Для более подробной информации, пожалуйста, смотрите сообщение на Draw3Cards .

ripper234
источник
1
(1) Что является входом? Предполагаете ли вы, что знаете содержание и порядок карт в колодах обоих игроков? (2) Чтобы проанализировать ее сложность, задача должна иметь бесконечно много возможных входных данных. Например, мы не можем сказать, что шахматы являются EXP-полными (даже если мы так говорим, это означает, что обобщение шахмат на доску n × n является EXP-полными). Как вы обобщаете игру? (3) Игра может быть слишком сложной, чтобы анализировать ее сложность, но я не знаю.
Цуёси Ито
1
@ Даниель: Спасибо. На самом деле я тоже это проверил, но не был уверен, что кто-то захочет проанализировать игру, где каждая карта, кроме карт земли, ограничена максимум четырьмя копиями, и может расти только количество карт земли.
Цуёси Ито
1
@ Даниель: Не уверен, что логика работает таким образом, потому что есть несколько разных типов карт земли. В конце концов, сама игра может быть достаточно сложной, чтобы завершить Тьюринг. Что я не уверен, так это то, хочет ли Аскер действительно анализировать игру, где почти все карты в колоде обязательно являются картами земли. Я буду ждать ответа от автора.
Цуёси Ито
4
@ Дэниел: Это не разумное возражение! Большинство снижений жесткости для игр дают нечто, похожее на уменьшение, чем в оригинальной игре. (Гамильтоновы циклы, естественно, не возникают в черновиках, например.)
Джефф
1
@ Tsuyoshi - я думаю, что будет вопрос, можно ли решить Магию. Для того чтобы этот вопрос имел смысл, вы могли бы предположить, что точная информация - все библиотеки и раздачи раскрыты, а все случайные броски монет и тому подобное предопределены. Можно ли из каждой позиции Магии определить, кто является победителем?
ripper234

Ответы:

21

Алекс Черчилль (@AlexC) опубликовал решение, которое не требует сотрудничества между игроками, а скорее моделирует полное выполнение универсальной машины Тьюринга с двумя состояниями и 18 символами ленты. Для получения подробной информации см. Https://www.toothycat.net/~hologram/Turing/ [ архив ].

оборота Джеффс
источник
1
Ссылка мертва для меня. Должны ли мы восстановить решение в ответе, чтобы быть полным?
Артем Казнатчеев
1
На данный момент решение размещено на toothycat.net/~hologram/Turing .
AlexC
15

Хорошо, у меня есть решение, которое позволяет избежать проблемы с сжиганием маны, с которой я столкнулся. Это своего рода хак, так как мне нужно сделать предположение, что игроки могут идентифицировать конкретные земли, что, я не думаю, рассматривается в правилах. На практике это имеет место, так как они могут быть расположены в линию в зависимости от порядка их воспроизведения.

Сначала полное описание проблемы с сайта Draw3Cards:

Положительный ответ будет состоять из следующих компонентов:

  1. Вычислимая функция fM от машин Тьюринга до упорядоченных волшебных колод (где порядок библиотеки имеет значение)
  2. Две четко определенные детерминированные и вычислимые стратегии для игры в Магию (которые не зависят от колоды). Давайте назовем их Стратегия TS (Стратегия Тьюринга) и Стратегия IS (Стратегия ввода).
  3. Вычисляемый способ для кодирования любой строки нулей и единиц в качестве колоды Magic Input. Одним из таких способов было бы взять число Гёделя в строке и поместить столько островов во входную колоду.

Дополнительное условие, которое должно быть выполнено, таково: учитывая TM Turing Machines, давайте рассмотрим результат игры Magic между стратегией TS, играющей с колодой fM (TM), против стратегии TI, играющей с колодой fI (I), когда библиотеки не тасуется до начала игры. Эту игру должен выиграть первый игрок, если и только если TM (I) = true.

Итак, вот идея. У нас есть 2 игрока, A и B. B предоставит вход, в то время как A непосредственно реализует машину Тьюринга. Колоды будут состоять почти полностью из земли, но также и из карты Gemstone Array, чтобы уничтожить сжигание маны. А будет иметь 3 типа земель: острова, горы и леса. Основная идея состоит в том, чтобы использовать повернутую землю для представления 1, а неиспользуемую землю для представления 0. Острова будут использоваться для представления состояния ленты, горы - для индексации текущего положения вдоль ленты, а леса - для представления внутреннего состояния 24. символ 2 состояния машины Тьюринга (я считаю, что есть универсальный благодаря Рогожину).

Колоды располагаются следующим образом: колода А: артефакт драгоценного камня; 6 лесов (с плюс дополнительный лес); Для m = 0 до бесконечности: островов, за которыми следуют 1 горы. Обратите внимание, что количество гор (которые могут быть как повернуты, так и нет) всегда является числом, необходимым для индексации каждого острова, плюс состояние остановки.2 м + 125=32>242m+1

Колода B: артефакт драгоценного камня; 6 лесов (с плюс дополнительный лес); Для m = 0 до бесконечности: Входные земли, за которыми следуют 1 горы. Еще раз обратите внимание, что число гор (которые могут быть повернуты или нет) всегда является числом, требуемым для индексации каждого острова, удерживаемого A, плюс состояние остановки. Входными землями считаются равнины (для представления 0 во входной строке), Болото (для представления 1 во входной строке) и острова (которые используются после достижения конца входной строки.2 м + 125=32>242m+1

Стратегия: A и B разыгрывают по одной земле за ход в том порядке, в котором они разыгрываются. Когда каждый рисует 4 леса, они играют артефакт драгоценного камня. Примечание А идет первым, поэтому уже имеет Остров, когда Б дро играет свою первую входную карту.

A и B просто продолжают размещать свои карты в порядке, пока B не исчерпает свои Равнины и Болота и не разыграет свой первый Остров. На его следующем пути, A для всех, кого я касаюсь его ih Остров, если Bs ith Входная Земля была болотом. А инициализирует свою машину Тьюринга, нажимая на свои первые Лес и Гору. Если он нажал нечетное количество карт, он нажимает на свой дополнительный форрест и использует всю эту ману, чтобы добавить жетоны в массив драгоценных камней. С этого момента игра продолжается следующим образом: B использует свой ход, чтобы просто отразить состояние маны А. B стучит по i-му входному полю, если i-й остров А повернут. Точно так же B стучит по своему i-му Лесу (Горе), если i-ый Лес (Гора) задействован. Как A всегда выбирает четное количество карт, так и B, и мана используется для добавления жетонов в Gemstone Array.

На ходу А вся мана А становится неиспользованной, поэтому А смотрит на состояние маны Б, представляет состояние маны А на предыдущем ходу. A применяет правило перехода в соответствии с универсальным (24,2) автоматом к состоянию B, чтобы получить его новое состояние.

Игра продолжается таким образом, пока машина Тьюринга не остановится. В этот момент А переводит свои горы в зарезервированное «законченное» состояние (полностью неиспользованное состояние). Если машина Тьюринга остановилась в принимающем состоянии, B копирует состояние гор А, но использует всю оставшуюся землю, пренебрегая использованием массива драгоценных камней, тем самым начиная процесс самоубийства из-за сжигания маны. На ходу А, если горы Б находятся в «готовом» состоянии, а все другие земли Б задействованы, А просто ничего не делает (обратите внимание, что его горы автоматически находятся в «готовом» состоянии). Если горы А находятся в завершенном состоянии, но больше ничего не обнаружено, В продолжает самоубийство от сожжения маны. Это повторяется до тех пор, пока B не умрет.

Однако, если машина заканчивается в состоянии отклонения, B оставляет все свои карты неиспользованными. Если все карты B не раскрыты, A стучит по всем его картам, начиная тот же процесс самоубийства с помощью сжигания маны. Если все карты А, не являющиеся Горами, разыграны, а горы развернуты, B оставляет все свои карты неиспользованными. Это заставит А продолжать самоубийство сжиганием маны, пока он не проиграет игру.

Это должно соответствовать критериям, заданным в вопросе, и, следовательно, когда это упорядочение разрешено, я считаю, что игра завершена по Тьюрингу в смысле, описанном в вопросе.

Джо Фитцсимонс
источник
2
Круто. Дополнительная мысль: пока любой игрок выбирает более 1 земли за ход, вы можете использовать заряды на массиве драгоценных камней, чтобы избежать сжигания маны. Например, если мне нужно нажать 3 земли, я превращаю две маны в заряд, трачу заряд, чтобы сгенерировать одну ману, а затем трачу две оставшиеся маны, чтобы создать новый заряд. - Конечно, вы все равно решили эту проблему. :)
Даниэль Апон
2
Aewsome! Также может быть проще смоделировать машину с двумя счетчиками (используя различные типы маны в качестве счетчиков) вместо прямого моделирования машины Тьюринга: en.wikipedia.org/wiki/…
Джефф
3
Ваше сокращение также подразумевает, что (кооперативная) Магия с конечным числом карт является PSPACE-трудной.
Джефф
3
@Joe - в Магии больше нет сжигания маны. Вы можете использовать Platinum Angel, чтобы избежать проигрыша из-за нехватки карт на вашем кладбище.
ripper234
1
@Joe - вы пропустили мой комментарий ранее о том, что концепция сжигания маны полностью удалена из правил. Вы можете это исправить, если у каждого игрока есть копия Огненного шара в своей колоде.
ripper234
7

Алекс Черчилль, Стелла Бидерман и Остин Херрик опубликовали эту статью, показывающую, что магия завершается

Abstract — Magic: The Gathering - популярная и сложная игра в карты о магических боях. В этой статье мы показываем, что оптимальная игра в реальной магии, по крайней мере, так же трудна, как и проблема остановки, решая проблему, которая была открыта в течение десятилетия [1], [10]. Для этого мы представляем методологию для встраивания произвольной машины Тьюринга в игру Магии так, чтобы первый игрок гарантированно выиграл игру, если и только если машина Тьюринга остановится. Наш результат относится к тому, как разыгрывается настоящая Магия, может быть достигнут с использованием стандартных колод для турниров и не зависит от стохастичности или скрытой информации. Наш результат также весьма необычен в том, что все ходы обоих игроков вынуждены в строительстве. Это показывает, что даже распознать, кто выиграет игру, в которой ни один из игроков не принял нетривиальное решение для остальной части игры, невозможно решить. В заключение мы обсудим последствия для единой вычислительной теории игр и замечания по поводу возможности игры на такой доске в турнирных условиях.

DerMolly
источник