Игра на паритет

Математическая игра, разыгрываемая на ориентированном графе

Игра на четность. Круглые узлы принадлежат игроку 0, прямоугольные узлы принадлежат игроку 1. С левой стороны находится выигрышная область игрока 0, с правой стороны — выигрышная область игрока 1.

Игра на четность проводится на цветном ориентированном графе , где каждый узел раскрашен в соответствии с приоритетом — одним из (обычно) конечного числа натуральных чисел . Два игрока, 0 и 1, перемещают (один, общий) токен вдоль рёбер графа. Владелец узла, на который попадает токен, выбирает узел-последователя (делает следующий ход). Игроки продолжают перемещать токен, в результате чего образуется (возможно, бесконечный) путь , называемый игрой.

Победителем в конечной игре становится игрок, противник которого не может сделать ход. Победитель в бесконечной игре определяется приоритетами, появляющимися в игре. Обычно игрок 0 выигрывает в бесконечной игре, если наибольший приоритет, который бесконечно часто встречается в игре, является четным. В противном случае выигрывает игрок 1. Это объясняет слово «четность» в названии.

Паритетные игры лежат на третьем уровне иерархии Бореля и, следовательно, определены . ^[1]

Игры, связанные с играми на четность, неявно использовались в доказательстве Рабина разрешимости монадической теории второго порядка n преемников ( S2S для n = 2), где была доказана определенность таких игр. ^[2] Теорема Кнастера–Тарского приводит к относительно простому доказательству определенности игр на четность. ^[3]

Более того, игры на паритет определяются без учета истории. ^{[3] [4] [5]} Это означает, что если у игрока есть выигрышная стратегия, то у этого игрока есть выигрышная стратегия, которая зависит только от текущей позиции на доске, а не от истории игры.

Решение игры

Нерешенная проблема в информатике :

Можно ли решить игры на четность за полиномиальное время?

(еще нерешенные проблемы в информатике)

Решение игры на четность, разыгрываемой на конечном графе, означает решение для заданной начальной позиции, какой из двух игроков имеет выигрышную стратегию. Было показано, что эта задача находится в NP и co-NP , точнее UP и co-UP, ^[6] , а также в QP ( квазиполиномиальное время ). ^[7] Остается открытым вопрос, разрешима ли эта задача принятия решений в PTime .

Учитывая, что игры на четность определяются без истории, решение данной игры на четность эквивалентно решению следующей простой на вид задачи теории графов. Дан конечный цветной ориентированный двудольный граф с n вершинами и V , раскрашенный в цвета от 1 до m , существует ли функция выбора, выбирающая одно исходящее ребро из каждой вершины , такая, что полученный подграф обладает свойством, что в каждом цикле наибольший встречающийся цвет является четным. ${\displaystyle V=V_{0}\cup V_{1}}$ ${\displaystyle V_{0}}$

Рекурсивный алгоритм решения игр на четность

Зеленка описал рекурсивный алгоритм, который решает игры на четность. Пусть будет игрой на четность, где соответственно — это наборы узлов, принадлежащие игроку 0 соответственно 1, — это набор всех узлов, — это общий набор ребер, а — это функция назначения приоритетов. ${\displaystyle G=(V,V_{0},V_{1},E,\Omega )}$ ${\displaystyle V_{0}}$ ${\displaystyle V_{1}}$ ${\displaystyle V=V_{0}\cup V_{1}}$ ${\displaystyle E\subseteq V\times V}$ ${\displaystyle \Omega :V\rightarrow \mathbb {N} }$

Алгоритм Зелонки основан на обозначении аттракторов. Пусть будет набором узлов и будет игроком. i -аттрактор U — это наименьший набор узлов, содержащий U, такой, что i может заставить посетить U из каждого узла в . Его можно определить с помощью вычисления неподвижной точки: ${\displaystyle U\subseteq V}$ ${\displaystyle i=0,1}$ ${\displaystyle Attr_{i}(U)}$ ${\displaystyle Attr_{i}(U)}$

${\displaystyle {\begin{aligned}Attr_{i}(U)^{0}&:=U\\Attr_{i}(U)^{j+1}&:=Attr_{i}(U)^{j}\cup \{v\in V_{i}\mid \exists (v,w)\in E:w\in Attr_{i}(U)^{j}\}\cup \{v\in V_{1-i}\mid \forall (v,w)\in E:w\in Attr_{i}(U)^{j}\}\\Attr_{i}(U)&:=\bigcup _{j=0}^{\infty }Attr_{i}(U)^{j}\end{aligned}}}$

Другими словами, мы начинаем с начального набора U. Затем для каждого шага ( ) мы добавляем все узлы, принадлежащие игроку 0, которые могут достичь предыдущего набора ( ) с помощью одного ребра, и все узлы, принадлежащие игроку 1, которые должны достичь предыдущего набора ( ) независимо от того, какое ребро выберет игрок 1. ${\displaystyle Attr_{i}(U)^{j+1}}$ ${\displaystyle Attr_{i}(U)^{j}}$ ${\displaystyle Attr_{i}(U)^{j}}$

Алгоритм Зелонки основан на рекурсивном спуске по числу приоритетов. Если максимальный приоритет равен 0, то сразу видно, что игрок 0 выигрывает всю игру (с произвольной стратегией). В противном случае пусть p будет наибольшим, а пусть будет игроком, связанным с приоритетом. Пусть будет набором узлов с приоритетом p , а пусть будет соответствующим аттрактором игрока i . Теперь игрок i может гарантировать, что каждая игра, которая посещает A бесконечно часто, выигрывается игроком i . ${\displaystyle i=p{\bmod {2}}}$ ${\displaystyle U=\{v\mid \Omega (v)=p\}}$ ${\displaystyle A=Attr_{i}(U)}$

Рассмотрим игру, в которой все узлы и затронутые ребра A удалены. Теперь мы можем решить меньшую игру с помощью рекурсии и получить пару выигрышных наборов . Если пусто, то так же будет и для игры G , поскольку игрок может решить только сбежать из A , что также приведет к победе игрока i . ${\displaystyle G'=G\setminus A}$ ${\displaystyle G'}$ ${\displaystyle W'_{i},W'_{1-i}}$ ${\displaystyle W'_{1-i}}$ ${\displaystyle W_{1-i}}$ ${\displaystyle 1-i}$ ${\displaystyle W_{i}'}$

В противном случае, если не пусто, мы точно знаем, что игрок может выиграть , так как игрок i не может уйти из в A (так как A является i -аттрактором). Поэтому мы вычисляем аттрактор и удаляем его из G , чтобы получить меньшую игру . Мы снова решаем ее с помощью рекурсии и получаем пару выигрышных наборов . Из этого следует, что и . ${\displaystyle W'_{1-i}}$ ${\displaystyle 1-i}$ ${\displaystyle W'_{1-i}}$ ${\displaystyle W'_{1-i}}$ ${\displaystyle B=Attr_{1-i}(W'_{1-i})}$ ${\displaystyle G''=G\setminus B}$ ${\displaystyle W''_{i},W''_{1-i}}$ ${\displaystyle W_{i}=W''_{i}}$ ${\displaystyle W_{1-i}=W''_{1-i}\cup B}$

В простом псевдокоде алгоритм можно выразить так:

функция  p  := максимальный приоритет в G, если return else U  := узлы в G с приоритетом p , если return return ${\displaystyle solve(G)}$    ${\displaystyle p=0}$   ${\displaystyle W_{0},W_{1}:=V,\{\}}$    ${\displaystyle i:=p{\bmod {2}}}$  ${\displaystyle A:=Attr_{i}(U)}$  ${\displaystyle W_{0}',W_{1}':=solve(G\setminus A)}$   ${\displaystyle W_{1-i}'=\{\}}$   ${\displaystyle W_{i},W_{1-i}:=V,\{\}}$  ${\displaystyle B:=Attr_{1-i}(W_{1-i}')}$  ${\displaystyle W_{0}'',W_{1}'':=solve(G\setminus B)}$   ${\displaystyle W_{i},W_{1-i}:=W_{i}'',W_{1-i}''\cup B}$

Связанные игры и проблемы их решения

Небольшая модификация вышеприведенной игры и связанной с ней проблемы теории графов делает решение игры NP-трудным . Модифицированная игра имеет условие принятия Рабина , и, таким образом, каждая вершина окрашена набором цветов вместо одного цвета. Соответственно, мы говорим, что вершина v имеет цвет j, если цвет j принадлежит цветовому набору v . Бесконечная игра выигрывает для игрока 0, если существует i, такое, что бесконечно много вершин в игре имеют цвет 2i , но конечное множество имеют цвет 2i+1 .

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

Обратите внимание, что в отличие от игр на четность эта игра больше не симметрична относительно игроков 0 и 1.

Связь с логикой и теорией автоматов

Наиболее распространенные приложения решения игр на четность.

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

Ссылки

1. DA Martin : Борелевская определенность, Анналы математики, том 102, № 2, стр. 363–371 (1975)
2. Рабин, М. О. (1969). «Разрешимость теорий второго порядка и автоматов на бесконечных деревьях». Труды Американского математического общества . 141. Американское математическое общество: 1–35. doi :10.2307/1995086. JSTOR  1995086.
3. EA Emerson и CS Jutla: Древовидные автоматы, мю-исчисление и определенность, IEEE Proc. Основы компьютерной науки, стр. 368–377 (1991), ISBN 0-8186-2445-0 
4. А. Мостовский: Игры с запрещенными позициями, Гданьский университет, Технический отчет 78 (1991)
5. Зелонка, В. (1998). «Бесконечные игры на конечно окрашенных графах с приложениями к автоматам на бесконечных деревьях». Теор. комп. наук . 200 (1–2): 135–183. doi : 10.1016/S0304-3975(98)00009-7 .
6. Марцин Юрдзински (1998), «Определение победителя в играх на равенство происходит в UP∩ co-UP» (PDF) , Information Processing Letters , 68 (3), Elsevier: 119–124, doi :10.1016/S0020-0190(98)00150-1
7. Калуд, Кристиан С.; Джейн, Санджай; Хуссаинов, Бахадыр; Ли, Вэй; Стефан, Франк, «Решение игр на четность за квазиполиномиальное время» (PDF) , Stoc 2017

• Эрих Грэдель, Фокион Г. Колайтис, Леонид Либкин , Маартен Маркс, Джоэл Спенсер , Моше Й. Варди , Иде Венема, Скотт Вайнштейн (2007). Теория конечных моделей и ее приложения . Springer. ISBN 978-3-540-00428-8.{{cite book}}: CS1 maint: multiple names: authors list (link)

Дальнейшее чтение

• E. Grädel, W. Thomas, T. Wilke (ред.): Автоматы, логика и бесконечные игры , Springer LNCS 2500 (2003), ISBN 3-540-00388-6 
• В. Зелонка: Бесконечные игры на конечно окрашенных графах с приложениями к автоматам на бесконечном дереве , TCS, 200(1-2):135-183, 1998

Внешние ссылки

Ниже приведены два современных набора инструментов для решения игр на четность:

• Коллекция PGSolver
• Хрю