Я задал эту проблему в MathOverflow , без какого-либо удовлетворительного ответа.
Рассмотрим следующую игру для двух игроков, которая является упрощением карточной игры Winner . (Следующая формулировка была взята из комментария Гийома Брунери о MathOverflow.)
Есть два игрока A и B. У каждого игрока есть набор карт (подмножество ), видимых от обоих игроков. Цель игры - избавиться от собственных карт. Первый игрок разыгрывает любую карту на столе, затем другой игрок должен разыгрывать (строго) большую карту, и так далее, пока один из игроков не сможет сыграть или не решит пройти. Затем карты на столе сбрасываются, и другой игрок начинает заново, разыгрывая любую карту (за которой последует карта большего размера). И так до тех пор, пока у одного из двух игроков не закончатся карты и они не выиграют игру.
Я хочу знать лучшую стратегию для игроков (если он может победить).
Формальное определение
Обозначим через конфигурацию игры, в которой набор карт первого игрока равен , набор карт второго игрока - , а самая большая карта на столе - , где означает, что на столе нет карты. Я хотел бы, чтобы алгоритм вычислял, учитывая , есть ли у первого игрока выигрышная стратегия в конфигурации .
Формально я хотел бы, чтобы алгоритм вычислял функцию определенную следующим образом:
Пусть , ,
Функция
где
Неправильные стратегии
Вот некоторые неправильные стратегии:
- Всегда разыгрывайте самую маленькую карту. Пусть , выигрышная стратегия для игрока A в конфигурации - сыграть карту . Если игрок А сыграет карту 1, он проиграет.
- Играйте наименьшую карту, если у другого игрока нет только одной карты. Это более сильная стратегия, чем стратегия 1, но она также неверна. Подумайте только о конфигурации . Если игрок А использует стратегию 2, он проиграет: , таким образом, игрок A проиграет.
источник
Ответы:
Вероятно, это должен быть комментарий, но он слишком длинный.
Родственная игра была изучена Джеффом Каном, Джеффом Лагариасом и Хансом Витсенхаузеном в серии статей «Игра в одиночку с двумя людьми I, II, III» и « На карточной игре Ласкара». В игре, которую они изучали, каждый игрок имеетN карты, сданные из карт, пронумерованных . Каждый трюк состоит из двух карт, старшая карта выигрывает, а победитель - лидер. Цель состоит в том, чтобы принять большинство трюков.2 н 1 ... 2 н
Они доказали ряд интересных фактов об оптимальной стратегии, но не смогли найти эффективный алгоритм для оптимальной игры, а также не смогли доказать, что это NP-сложный.
Для игры в Misère , где каждый человек пытается использовать наименьшее количество трюков, он смог выработать оптимальную стратегию.
По большей части эти результаты были получены, сначала посмотрев на результаты компьютерной программы, которая нашла оптимальную стратегию для небольших случаев, затем отыскивая шаблоны для получения гипотез и, наконец, доказав эти гипотезы. Я подозреваю, что это был бы также плодотворный подход к игре ОП.
источник