Хочется добавить, что в реальности довольно много вещей которые являются тьюринг-полными. Ведь даже в своей статье Тьюринг уподоблял человека, вычисляющего вещественное число, машине, которая находится в конечном числе состояний. Кто-то вводит понятие тупой машины когда нужны какие-то внешние механические действия для перевода машины из одного состояния в другое. Замените ленту на столы, а числа на блюда, и у вас получится тьюринг-полный ресторан. Так что и HTML - это тоже в некотором смысле язык программирования(тьюринг-полный). Хотя кажется, что споры об этом еще ведутся.
Ссылки не сохранилось, потому как это было полгода назад, но в той статье было все то же самое - кто такой Тьюринг, что есть машина Тьюринга, как оно работает, почему противник не может нам помешать... Только там еще рассматривалось на примере, как именно оно работает.
Возможно это не перевод, а заметка "по мотивам", но стиль написания почти один-в-один.
Статья говорит о том, что гипотетически в мтг существует набор карт и механик, которые при определенных условиях могут привести к автономности партии. Ок, понятно - но как это делает игру сложной?
Начиная от того, что описанная в статье ситуация приближается к статистической невозможности в обычных условиях игры и заканчивая тем, что в тех же нормальных условиях эта хрень не эффективна на 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". Я решил, что тема и так катастрофически сложная, чтобы загружать её дополнительными деталями. Пример одного цикла работы машины вы можете найти в видео - все токены создаются автоматически и нужного цвета.
Хочется добавить, что в реальности довольно много вещей которые являются тьюринг-полными. Ведь даже в своей статье Тьюринг уподоблял человека, вычисляющего вещественное число, машине, которая находится в конечном числе состояний. Кто-то вводит понятие тупой машины когда нужны какие-то внешние механические действия для перевода машины из одного состояния в другое. Замените ленту на столы, а числа на блюда, и у вас получится тьюринг-полный ресторан. Так что и 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". Я решил, что тема и так катастрофически сложная, чтобы загружать её дополнительными деталями. Пример одного цикла работы машины вы можете найти в видео - все токены создаются автоматически и нужного цвета.
Огонь!!!
>>мы точно говорим о Magic? Magic? Это где земли, гоблины, дряные расклады, отвратный арт, Ричард, что бы с ним такое сделать, Гарфилд?
- Поверни заклинание
- Как это - поверни заклинание?
- Ну, в смысле тапни его.
- ** твою мать, это не бейсик земля, что значит "тапни его"?!
Спасибо, что заметили :) пожалуй, это мой любимый момент в статье
Это ЧУМА, а не статья!!!!
Зачетная тема, я поржал )))
Как-то ни о чем, если честно
Статья в стиле "британские ученые установили..."
о чем и сказано в первом абзаце статьи
"Ничего не понял, но очень интересно"(с)