MTG - "самая сложная игра в мире"

[Santadir]

С точки зрения математики игры могут быть разной вычислительной сложности. Большинство игр в этом смысле просты, что позволяет создать эффективные компьютерные алгоритмы, побеждающие с высокой вероятностью. В новой работе исследователи впервые доказывают, что существует реальная игра невычислимой сложности, то есть в общем случае не существует алгоритма, который укажет на существование гарантирующей победу одному игроку стратегии. Этим свойством обладает известная карточная игра Magic: The Gathering

https://nplus1.ru/news/2019/05/08/unsolvable-magic

Кому нужен матанъ - оригинал статьи https://arxiv.org/pdf/1904.09828.pdf

[Shursh]

Так вот почему шафлер такой всратый

[canonist]

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

[TeOr]

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

[mtgshnik]

10 минут назад, canonist сказал:

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

Подвал живёт игрой!

[Амариллен]

5 минут назад, TeOr сказал:

Любая игра с рандомом и закрытой информацией машине практически неподвластна

Ну это не так

[TeOr]

6 минут назад, Амариллен сказал:

Ну это не так

Ну блин

[pingi]

@TeOr есть ощущение, что в покер компьютер обыграет человека (рандом + закрытая информация). сначала написал, потом чекнул гугл.

по Магии есть ощущение, что если компьютеру дать два деклиста, чтобы он там не обсчитывал вообще все варианты, то он тоже будет человека обыгрывать на длинной дистанции. 

[Амариллен]

Вот в этой статье Беванд 15 лет назад рассказывал, что в Магии просто намного больше микровыборов в каждый момент времени, хотя импакт каждого из них, конечно, меньше, чем в шахматах, к примеру.

Там же есть и примерный флоучарт вариаций того, что можно сделать и когда

[DeaDMopo3]

10 минут назад, pingi сказал:

@TeOr есть ощущение, что в покер компьютер обыграет человека (рандом + закрытая информация). сначала написал, потом чекнул гугл.

по Магии есть ощущение, что если компьютеру дать два деклиста, чтобы он там не обсчитывал вообще все варианты, то он тоже будет человека обыгрывать на длинной дистанции. 

сначала дай статью Василия про перезаклады

 

[SadSido]

Заголовочек, конечно, желтоват. Более точно "Учёные доказали алгоритмическую неразрешимость задачи определения победителя в Magic". Если кому-то лениво читать сорс на английском языке, то там авторы описывают способ описать состояние игры с помощью машины Тьюринга, а потом сводят задачу определения победителя к класической задаче об остановке, которая, как известно, неразрешима. В статье также высказывается смелое предположение, что не существует реальных игр, вычислительно более сложных, чем Magic. Что теперь делать с этим знанием - решать вам.

[uberburner]

Ссылка на статью была в дайджесте, кстати.
Но пока популяризаторы не напишут чего, темы на ТД не будет.
 

6 часов назад, SadSido сказал:

В статье также высказывается смелое предположение, что не существует реальных игр, вычислительно более сложных, чем Magic.

Интересно, как бы они это доказывали.
Точнее, как бы они сравнивали две игры с неразрешимым определением победителя.

[Samurai]

15 минут назад, uberburner сказал:

Интересно, как бы они это доказывали.
Точнее, как бы они сравнивали две игры с неразрешимым определением победителя.

Вероятно, количество разных объектов в магии явно превышает любую другую известную игру. Так то на базовых преконах и ХС сложнее может оказаться.

[reammaer]

10 часов назад, Samurai сказал:

Вероятно, количество разных объектов в магии явно превышает любую другую известную игру.

Думаю, Ю-ги-о с этим могла бы поспорить.

Не так давно друг предложил обучить игре в неё. И хочется сказать, что при примерно равном количестве типов карт, наличию стека и прочих схожестей, часто она бывает сложнее магии.

К примеру, там надо держать в голове не только содержание своей основной колоды из 60 карт, но и содержание двух дополнительных колод, карты в которых вызываются за дополнительные условия.

Плюс там нет понятия мана флуда/скрю из-за отсутствия понятия земель. Ну и намного чаще карты играются через рубашку вверх (точнее постоянно).

[Nazar]

12 часов назад, uberburner сказал:

Ссылка на статью была в дайджесте, кстати.
Но пока популяризаторы не напишут чего, темы на ТД не будет.
 

Интересно, как бы они это доказывали.
Точнее, как бы они сравнивали две игры с неразрешимым определением победителя.

Сравнение сложности вычислений и сравнение игр по абстрактным критериям, все-таки разные вещи. Для первого хватает методических базисов

[Bachus]

18 часов назад, SadSido сказал:

Если кому-то лениво читать сорс на английском языке, то там авторы описывают способ описать состояние игры с помощью машины Тьюринга

Немного не так - в статье указан способ моделирования  машины Тьюринга с помощью правил MTG. То, что с помощью MT можно описать правила MTG совсем не удивительно.
 

Цитата

В статье также высказывается смелое предположение, что не существует реальных игр, вычислительно более сложных, чем Magic.

Скорее, что MTG - первая обнаруженная "реальная" игра из этого класса.

[romashkovo]

2 часа назад, reammaer сказал:

Думаю, Ю-ги-о с этим могла бы поспорить.

Не так давно друг предложил обучить игре в неё. И хочется сказать, что при примерно равном количестве типов карт, наличию стека и прочих схожестей, часто она бывает сложнее магии.

К примеру, там надо держать в голове не только содержание своей основной колоды из 60 карт, но и содержание двух дополнительных колод, карты в которых вызываются за дополнительные условия.

Плюс там нет понятия мана флуда/скрю из-за отсутствия понятия земель. Ну и намного чаще карты играются через рубашку вверх (точнее постоянно).

В отличии от Магии,где если ты видишь открытую синюю ману,то сразу думаешь об отменке на руке у противника,там ты скорее, стараешься разложиться так,чтобы оппу было максимально трудно потом сломать твое поле. Поскольку маны там нет,то все упирается в то,насколько далеко ты сможешь раскрутить свою руку и колоду, поскольку туторы там почти в каждой колоде есть.  А экстра колоду ты всегда можешь смотреть,поэтому там особо и запоминать нечего. ( Говорю,как бывший опытный игрок в югио)

[reammaer]

2 часа назад, romashkovo сказал:

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

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

Но порог вхождения, как мне показалось, для новичков там выше. И дело не в механике, а в формулировке текста на карточках - в магии он намного более лаконичен и интуитивно понятен.