Перестановка игрового редукса

20

Это повторение предыдущего вопроса .

Рассмотрим следующую беспристрастную идеальную информационную игру между двумя игроками, Алисой и Бобом. Игроки получают перестановку целых чисел от 1 до n. На каждом ходу, если текущая перестановка увеличивается, текущий игрок проигрывает, а другой игрок выигрывает; в противном случае текущий игрок удаляет одно из чисел, и игра переходит к другому игроку. Алиса играет первой. Например:

  • (1,2,3,4) - Боб выигрывает немедленно, по определению.

  • (4,3,2,1) - Алиса выигрывает после трех ходов, независимо от того, как кто-либо играет.

  • (2,4,1,3) - Боб может выиграть в свой первый ход, независимо от того, как играет Алиса.

  • (1,3,2,4) - Алиса немедленно выигрывает, удаляя 2 или 3; в противном случае Боб может выиграть в свой первый ход, убрав 2 или 3.

  • (1,4,3,2) - Алиса в конечном итоге выигрывает, если она берет 1 в свой первый ход; в противном случае Боб может выиграть в свой первый ход, не убрав 1.

Существует ли алгоритм полиномиального времени, чтобы определить, какой игрок выигрывает в этой игре по заданной начальной перестановке, предполагая идеальную игру ? В более общем плане, поскольку это стандартная беспристрастная игра, каждая перестановка имеет значение Спраг-Гранди ; например, (1,2,4,3) имеет значение * 1 и (1,3,2) имеет значение * 2. Насколько сложно вычислить это значение?

Очевидные работает алгоритм отслеживания в обратном направлении в O (N!) Время, хотя это может быть сведено к О(2NпоLY(N)) времени с помощью динамического программирования.

Jeffε
источник
4
Мне кажется, что наивный алгоритм выполняется за O (2 ^ n⋅poly (n)) времени.
Цуёси Ито
Из ваших примеров очевидно, что Алиса всегда побеждает, если последовательность убывает, а Боб всегда побеждает, если последовательность возрастает. Эта проблема напоминает мне об анализе алгоритмов сортировки, которые были тщательно изучены и позволяют использовать широкий арсенал инструментов.
chazisop
1
@chazisop: «Алиса всегда выигрывает, если последовательность идет по убыванию»: это имеет место тогда и только тогда, когда n четно.
Цуёси Ито
@ Jɛ ff E в случае 3, как Боб выигрывает в свой первый ход?
Суреш Венкат
2
@Suresh: В случае (2,4,1,3) представление графа является линейным графом на 4 вершинах (2-1-4-3). Если Алиса удаляет конечный узел, это оставляет линейный граф на 3 вершинах; Боб выигрывает, удаляя центральную вершину (таким образом, 3 отвечает 1, а 2 отвечает 4). Если Алиса удаляет внутренний узел, это оставляет две соединенные вершины и изолированный узел; Боб выигрывает, удаляя любую из двух соединенных вершин (поэтому 1 отвечает 3 или 4, а 4 отвечает 1 или 2).
mjqxxxx

Ответы:

7

«Игра перестановок» изоморфна следующей игре:

Отключить. Игроки поочередно удалять вершины из графа . Игрок, который создает полностью отключенный граф (т. Е. Граф без ребер), становится победителем.грамм

Граф соответствующий конкретной начальной перестановке π S n, содержит только те ребра ( i , j ), для которых i - j и π ( i ) - π ( j ) имеют противоположные знаки. То есть каждая пара чисел в неправильномграммππSN(я,J)я-Jπ(я)-π(J)порядок в перестановке связан с ребром. Очевидно, что разрешенные ходы изоморфны ходам в игре с перестановками (удалить число = удалить узел), и условия победы также изоморфны (нет пар в порядке убывания = нет ребер).

Дополнительный вид получается путем рассмотрения вопроса о «двойной» игре на дополнении графа , которое содержит те ребра ( i , j ), для которых i и j находятся в правильном порядке в перестановке. Двойная игра для отключения:граммπсзнак равнограммр(π)(я,J)яJ

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

В зависимости от конкретной перестановки одна из этих игр может показаться более простой, чем другая, для анализа. Преимущество представления графа состоит в том, что ясно, что несвязанные компоненты графа являются отдельными играми, и поэтому можно надеяться на некоторое снижение сложности. Это также делает симметрию положения более очевидной. К сожалению, условия победы нестандартны ... игра перестановок всегда заканчивается до того, как все ходы израсходованы, что придает ей что-то вроде мизерного характера. В частности, значение nim не может быть вычислено как nim-сумма (двоичное значение XOR) значений nim отключенных компонентов.


Для отключения, то не трудно заметить , что для любого графа и любого четного п , игра G ˉ K является безреберных, то первый игрок сразу же проигрывает (обе игры закончились). В противном случае первый игрок может перейти в любой из G , а второй игрок может скопировать свой ход в другой (уменьшив до G + G ¯ KграммN эквивалентна G (где ˉ К п является Edgeless граф на п вершинах). Чтобы доказать это, мы должны показатьчто разделительная сумма G + G ˉ K п является победой вторых игроков. Доказательство по индукции на | G | + п . Если ГграммК¯NграммК¯NNграмм+граммК¯N|грамм|+Nграммграмм с помощью|G|=|G|-1); или, еслип2, первый игрок может двигаться в отключенном части, а второй игрок может сделать то же самое (сведение кG+G ° K п-2).грамм'+грамм'КN¯|грамм'|знак равно|грамм|-1N2грамм+граммК¯N-2

Это показывает, что любой граф эквивалентен H K p , где H G ( H H ) K p граммЧАСКпЧАС является частью без каких - либо разъединенных вершин, и р = 0 или 1 является четность числа разъединенных вершин в G . Все игры в классе эквивалентности имеют одинаковое nim-значение, и, кроме того, отношение эквивалентности учитывает операцию объединения: если G H K p и G H K p ′, то Gграммпзнак равно01граммграмм~ЧАСКпграмм'~ЧАС'Кп' . Кроме того, можно видеть, что игры в[HK0]и[HK1]имеют разные значения nim, если толькоH неявляется нулевым графиком: при игре вH+HK1первый игрок может взять изолированный вершина, оставляяH+H, а затем скопируйте ходы второго игрока после этого.GG(HH)Kpp[HK0][HK1]ЧАСH+HК1ЧАС+ЧАС

Я не знаю никаких связанных результатов разложения для Reconnect.


Два специальных типа перестановок соответствуют особо простым играм с кучей.

  1. Первый - восходящий спуск , например, . Когда π принимает эту форму, граф G π является объединением непересекающихся клик, и игра Disconnect сводится к игре на кучах: игроки поочередно удаляют один компонент из кучи, пока все кучи не будут иметь размер 1 .32165487πграммπ1
  2. Второй - это нисходящая серия восхождений , например, . Когда π принимает эту форму, граф G c π является объединением непересекающихся клик, и игра Reconnect сводится к игре на кучах: игроки поочередно удаляют один компонент из кучи, пока не останется только одна куча .78456123πграммπс

Небольшая мысль показывает, что эти две разные игры на кучах (мы можем назвать их « 1 куча» и « одна куча» при некотором риске путаницы), на самом деле сами по себе изоморфны. Оба могут быть представлены игрой на диаграмме Юнга (как первоначально предложено @domotorp), в которой игроки поочередно убирают нижний правый квадрат, пока не останется только один ряд. Это, очевидно, та же самая игра, что и 1-Heaps, когда столбцы соответствуют кучам, и та же игра, что и One-Heap, когда строки соответствуют кучам.

Ключевой элемент этой игры, который распространяется на Disconnect и Reconnect, заключается в том, что продолжительность связана с конечным состоянием игры простым способом. Когда придет ваш ход, вы выиграете, если в игре осталось нечетное количество ходов, включая тот, который вы собираетесь сделать. Так как каждый ход удаляется из одного квадрата, это означает, что вы хотите, чтобы количество квадратов, оставшихся в конце игры, имело противоположный паритет, который он имеет сейчас. Более того, число квадратов будет одинаковым на всех ваших ходах; Таким образом, вы с самого начала знаете, какой паритет вы хотите получить в конечном счете. Мы можем назвать двух игроков Евой и Отто, в зависимости от того, должен ли окончательный счет быть четным или нечетным, чтобы они выиграли. Ева всегда движется в состояниях с нечетной четностью и создает состояния с четной четностью, а Отто - противоположность.

В своем ответе @PeterShor дает полный анализ One-Heap. Без повторения доказательства получается следующее:

  • Отто нравится кучу и 2- кучу, и может терпеть одну большую кучу. Он выигрывает, если он может сделать все размеры кучи, кроме одного2 , по крайней мере, не давая Еве немедленного выигрыша в форме ( 1 , n ) . Оптимальная стратегия для Отто - всегда брать из второй по величине кучи, кроме случаев, когда состояние равно ( 1 , 1 , n > 1 ) , когда он должен брать из n . Отто проиграет, если будет слишком много бобов в больших кучах.122(1,N)(1,1,N>1)N
  • Ева не любит кучи. Она выигрывает, если она может сделать все размеры кучи 2 . Оптимальная стратегия для Евы - всегда брать из 1- кучи, если она есть, и никогда не брать из 2- кучи. Ева проиграет, если будет слишком много 1- кучи для начала.12121

Как уже отмечалось, это дает оптимальные стратегии и для 1-кучи, хотя они несколько более неуклюжи для фразы (и я вполне могу допустить ошибку в перво-двойственном «переводе»). В игре 1-Кучи:

  • Отто любит одну или две большие кучи и может терпеть любое количество куч. Он выигрывает, если сможет сделать все, кроме двух самых больших куч, 1- кучами, по крайней мере, не дав Еве немедленного выигрыша в форме ( 1 , 1 , , 1 , 2 ) . Оптимальная стратегия для Отто - всегда брать из третьей по величине кучи или из меньшей кучи, когда есть только две кучи.11(1,1,...,1,2)
  • Ева не любит разрыв между самой большой и второй по величине кучей. Она выигрывает, если сможет сделать две самые большие кучи одинакового размера. Оптимальная стратегия для Евы - всегда брать из самой большой кучи, если она уникальна, и никогда, если точно есть два самых больших размера.

Как отмечает @PeterShor, не ясно, как (или если) эти анализы можно распространить на более общие игры Disconnect и Reconnect.

mjqxxxx
источник
2
Я думаю, что такие игры все вместе называют «играми с удалением вершин». Но я согласен с вами, что условие выигрыша совершенно нестандартно в том смысле, что оно относится к глобальному свойству графа, а не к локальным свойствам, таким как степень вершина.
Цуёси Ито
4
Построенный граф в литературе называется графом перестановок ( en.wikipedia.org/wiki/Permutation_graph ). Некоторые структурные свойства могут помочь.
Ёсио Окамото
1
@Yoshio: Это хороший момент. Игра перестановок изоморфна игре графов, но начальные графы не произвольны. Таким образом, даже если общую игру с графами трудно анализировать, возможно, что когда она ограничена этим подклассом графов, она станет проще.
mjqxxxx
2
С другой стороны, более общую формулировку легче доказать сложно. Известно, что варианты игр с удалением вершин являются PSPACE- сложными
Джефф
2
Я добавил вопрос об этой игре специально на math.SE ( math.stackexchange.com/questions/95895/… ). Кстати, поскольку графы перестановок являются круговыми, альтернативная формулировка следующая: игроки по очереди удаляют аккорды из начального набора; игрок, который оставляет непересекающийся набор аккордов, является победителем.
mjqxxxx
7

В своем ответе domotorp предлагает проанализировать особый случай игры. Этот особый случай возникает, когда перестановка представляет собой серию возрастающих последовательностей, каждая из которых больше следующей, такой как (8,9,5,6,7,4,1,2,3). В этой игре вы начинаете с набора кучи камней, а игроки поочередно убирают один камень из кучи. Игрок, который оставляет одну кучу, побеждает. Скажем, у есть кучаi камней, и предположим, что h i даны в порядке убывания. Например, для приведенной выше перестановки h ihihihi3,3,2,1. Я попытался дать анализ этой игры в комментариях к ответу domotorp, но (а) я ошибся и (б) в комментариях недостаточно места, чтобы дать реальное доказательство.

Чтобы проанализировать эту игру, нам нужно сравнить две величины: , количество куч, содержащих отдельные камни, и t =s ; обратите внимание, что мы игнорируем самую большую кучу в сумме. Это количество камней, которое вы должны будете удалить, чтобы все кучи, кроме одного, содержали не более двух камней. Мы утверждаем, что убыточные позиции заключаются в следующем:t=i2,hi>2hi2

  1. Позиции, где содержащие нечетное количество камней.ts2

  2. Положения, в которых содержит четное количество камней.ts

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

Чтобы закончить, показывая, что это правильно, нам нужно показать, что из любой позиции, не входящей в категорию (1) или (2), первый игрок может за один ход либо достичь позиции в категории (1) или (2), или выиграть напрямую.

Есть два случая:

  1. Позиции, где содержащее нечетное количество камней. Здесь, если s > 0 , удалите камень из кучи одним камнем. Если осталась только одна куча, мы выиграли. В противном случае у нас теперь t s . Если с одним камнем нет кучи, удалите камень из кучи, по крайней мере, с тремя камнями. (Поскольку было нечетное количество камней, это возможно). Поскольку s = 0 , мы имеем t s .ts1s>0tss=0ts

  2. Позиции, где содержащее четное количество камней. Здесь, если есть какие-либо кучи с хотя бы двумя камнями, кроме самой большой кучи, удалите камень из одного из них. Если в этой куче три или более камней, t уменьшается на один. Если в нем ровно два камня, s увеличивается на один. Теперь у нас есть t ts1ts . Последний случай, когда все кучи, кроме одной, состоят из отдельных камней; в этом случае легко проверить, выигрывает ли первый игрок, если есть четное количество камней.ts2

Я пытался обобщить эту стратегию для оригинальной игры, и не понял, как это сделать.

Питер Шор
источник
1
В своем ответе я отметил, что решение этого особого случая также решает особый случай с возрастающей серией убывающих прогонов, играя в «двойную» позицию, полученную путем транспонирования диаграммы Юнга. В частности, оптимальной стратегией Евы становится «извлечение из самой большой кучи, если только нет двух таких размеров», а оптимальной стратегией Отто становится «извлечение из самой маленькой кучи».
mjqxxxx
Я уверен, что этот подход приведет к идеальному решению, но на данный момент все еще есть небольшая ошибка, например (3,1) не проигрывает, а (3,1,1) есть. Проблема в том, что определение 2. должно исключать этот случай, поскольку мы можем достичь одной позиции кучи за один шаг. Но я думаю, что это единственная проблема с 2. и, надеюсь, это не сложно исправить.
Domotorp
1
@domotorp: Для (3,1), t = 0 и s = 1, поэтому t s , а критерий (2) говорит, что это не проигрышная позиция. Для (3,1,1) t = 0 и s = 2, поэтому t s - 2, а критерий (1) говорит, что это проигрышная позиция. Я думаю, что вы пропустили, что в определении t вы игнорируете самую большую кучу.
Питер Шор
Конечно, я забыл эту часть в конце ... Тогда эта игра решена!
Домоторп
1
Не полный ответ, но все же стоит щедрость.
Джеффс
3

Я реализовал решение для быстрой проверки гипотез. Не стесняйтесь играть с ним . Если у вас нет компилятора C ++ локально, вы можете запустить его на разных входах удаленно, используя ссылку «загрузить с новым вводом».О(2NN)

@ Jɛ ff E Случилось так, что (1,4,3,2) имеет значение * 1, а не * 2, как вы предложили.

Дмитрий Кордубан
источник
Ой, моя ошибка. Исправлен вопрос: g (1,3,2) = mex {g (1,3), g (1,2), g (3,2)} = mex {0, 0, * 1} = * 2.
Джефф
N10N
@maldini: это дает надежду на то, что игра обладает хорошими свойствами, которые могут сделать ее доступной для восприятия. Интересно, что происходит с игрой, обобщенной на графы, или с игрой, которая обобщается на совершенные графы?
Питер Шор
3

Правка 5 января: На самом деле игра «Одна куча», описанная ниже, является особым случаем проблемы, то есть когда числа следуют друг за другом определенным образом, так что первая группа больше второй группы, которая больше третьей и т. Д. и число в каждой группе увеличивается. Например, 8, 9, 4, 5, 6, 7, 2, 3, 1 - это такая перестановка. Поэтому я предлагаю решить этот частный случай в первую очередь.

Отказ от ответственности: я больше не утверждаю, что приведенное ниже доказательство является правильным, см., Например, комментарий Цуёси, который показывает, что удаление числа из перестановки даст диаграмму, которую нельзя получить, удалив квадрат из диаграммы перестановки. Я оставил здесь ответ, чтобы показать, что этот подход не работает, плюс он содержит еще одну простую игру.

В игре очень простая другая формулировка благодаря Young Tableaux. Я уверен, что он может быть проанализирован оттуда, как и другие игры, и он даст линейный алгоритм времени.

Сначала определите следующую игру на диаграммах Юнга: на каждом ходу, если текущая диаграмма горизонтальна (все квадраты на одной линии), текущий игрок проигрывает, а другой игрок выигрывает; в противном случае текущий игрок удаляет один из правых нижних квадратов, и игра переходит к другому игроку.

Теперь закажите последовательность чисел в Таблице Юнга. Основное утверждение состоит в том, что победитель в оригинальной игре такой же, как и победитель, в виде диаграммы, начиная с этой формы. Чтобы увидеть это, обратите внимание, что всякий раз, когда игроки удаляют число, диаграмму новой последовательности можно получить, удалив нижний правый квадрат диаграммы. Более того, любая такая диаграмма может быть достигнута путем удаления числа из соответствующего нижнего правого квадрата. Эти утверждения следуют из стандартной теории молодых таблиц.

Хотя эта игра-диаграмма достаточно проста, она тривиально эквивалентна следующей игре, которая кажется более стандартной:

Одна игра с кучей: игрокам дают кучу с несколькими камешками в каждой. На каждом ходу, если осталась только одна куча, текущий игрок проигрывает, а другой игрок выигрывает; в противном случае текущий игрок удаляет камушек из кучи, и игра переходит к другому игроку.

Если есть простое решение для игры в кучу (и я твердо верю, что оно есть), мы также получим решение для оригинальной игры: просто поместите последовательность в таблицу Юнга и преобразуйте ее диаграмму в кучу.

К сожалению, я не вижу, какие позиции в куче выигрывают / как определить значения Спрэга-Гранди. Я проверил несколько случаев вручную, и ниже приведены проигрышные позиции с максимум 6 камешками:

одна куча; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2).

Кто-нибудь может решить эту игру?

Редактировать: Питер Шор может, увидеть его ответ!

domotorp
источник
1
Можете ли вы привести хотя бы один пример, показывающий, как конкретная перестановка превращается в таблицу Юнга и как в этой таблице ведется та же самая игра (удаление числа, пока не будет достигнута восходящая последовательность)? В частности, я не понимаю, что значит убрать «один из правых нижних квадратов».
mjqxxxx
5
Вот контрпример к более слабому утверждению, что удаление числа из перестановки соответствует удалению одной из правых нижних ячеек из соответствующей диаграммы Юнга (вместо таблицы Юнга ). Пусть n = 5, и рассмотрим положение, заданное перестановкой [4,1,3,5,2] (то есть σ (1) = 4, σ (2) = 1 и т. Д.), И удалите 3 от него. Соответствующая диаграмма Юнга перед ходом - 5 = 3 + 1 + 1, но соответствующая диаграмма Юнга после хода - 4 = 2 + 2, которая не получается при удалении одной клетки из 3 + 1 + 1.
Цуёси Ито
5
И перестановка [5,4,1,2,3] имеет ту же диаграмму Юнга, что и [4,1,3,5,2], но вы не можете получить диаграмму Юнга 4 = 2 + 2 из нее. Так что игра зависит не только от формы молодой таблицы.
Питер Шор
2
Ура за конструктивное недоразумение!
Джеффс
3
@ Jɛ ff E: Да, это гораздо полезнее, чем доказательство простого недопонимания.
Tsuyoshi Ito