Игра на графе: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 28: Строка 28:
 
==Сведение игр к игре на графе==
 
==Сведение игр к игре на графе==
  
Любую симметричную игру можно свести к игре на графе, так как мы можем сделать все состояния игры вершинами и провести ребра из всех состояний в те состояния, в которые мы можем из них по попасть.
+
Любую равноправную игру можно свести к игре на графе, так как мы можем сделать все состояния игры вершинами и провести ребра из всех состояний в те состояния, в которые мы можем из них по попасть.
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}

Версия 15:30, 9 февраля 2020

Задача

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

Идеи

Мы знаем, что если из вершины есть переход в проигрышную вершину - она выигрышная.

Если из вершины все ребра идут только в выигрышные вершины - она проигрышная.

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

Решение

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

Такое решение уже работает за $O(mn)$, существуют и проще решения за такую асимптотику. Давайте придумаем, как улучшить наше решение.

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

1) Она уже помечена проигрышной или выигрышной, но тогда мы можем просто не запускаться в нее, так как из нее DFS уже был запущен.

2) Если вершина, в которую мы хотим запуститься, еще не была помечена и при этом мы сейчас запускаемся из проигрышной вершины, просто пометим вершину выигрышной.

3) Если вершина, в которую мы хотим запуститься, еще не была помечена и при этом мы сейчас запускаемся из выигрышной вершины, посмотрим все ли уже ребра были просмотрены для той вершины, в которую мы хотим запуститься.(Проверку на то что все ребра из вершины уже были просмотрены можно осуществлять с помощью вспомогательного массива $degree_{u}$, в котором мы будем хранить количество непросмотренных ребер из вершины $u$).

Тогда в конце алгоритма будут три типа вершин : проигрышные/выигрышные/вершины со степенью $degree_{u} > 0$, но как мы уже сказали, если для вершины нельзя сказать, какая она после $n$ шагов - она ничейная.

Сведение игр к игре на графе

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



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin