\Section{Игры на графах}{13 ноября 2017}{Сергей Копелиович}

\Subsection{Основные определения}

\begin{Def}Игра на орграфе:
по вершинам графа перемещается фишка, 
за ход игрок {\it должен} сдвинуть фишку по одному из рёбер.\\
{\bf Симметричная игра} -- оба игрока могут ходить по всем рёбрам\\
{\bf Несимметричная игра} -- каждому игроку задано собственное множество рёбер\\
Проигрывает игрок, который не может ходить.
\end{Def}

\begin{Ex}
Пусть по условию игры ``{\it некоторые вершины являются выигрышными или проигрышными для некоторых игроков}''. Такую игру можно вложить в определение выше.
\end{Ex}

Результат симметричной игры определяется графом $G$ и начальной вершиной $v \in G$.\\
Игру будем обозначать $(G,v)$, результат игры $r(G,v)$, или для краткости $r(v)$.\\
Классифицируем $v \in G$: в зависимости от $r(G,v)$ назовём вершину $v$ \\
{\it проигрышной} (\t{L}), {\it выигрышной} (\t{W}) или {\it ничейной} (\t{D}).\\
Также введём множества: 
$\t{WIN} = \{v\,|\,r(v) = \t{W}\}$, 
$\t{LOSE} = \{v\,|\,r(v) = \t{L}\}$,
$\t{DRAW} = \{v\,|\,r(v) = \t{D}\}$.

\begin{Rem}
В несимметричных играх, если вершина, например, проигрышна, ещё важно добавлять,
какой игрок ходил первым: ``проигрышная для 1-го игрока''.
\end{Rem}

% Коротко вершины будем помечать \t{W} (выигрышная), \t{L} (проигрышная), \t{D} (ничейная).

% Также будем использовать обозначения для множеств -- \t{WIN}, \t{LOSE}, \t{DRAW}

\begin{Lm}\label{lm@games}
	Если для вершины в условии задачи не указан явно её тип, то:
\begin{smallformula}
	$$W \EQ \exists\text{ ход в L}, \quad L \EQ \red{\text{ все ходы в W}}$$
\end{smallformula}
\end{Lm}

\vspace*{-1.7em}
\Subsubsection{Решение для ациклического орграфа}

Граф ацикличный $\SO$ вспомним про динамическое программирование.

\t{dp[v]} $= r(G, v)$; изначально ``\t{-1}'', т.е. ``не посчитано''.

База: пометим все вершины, информация о которых дана по условию.

Далее ленивая динамика:
\begin{code}
int result( int v ) {
	int &r = dp[v];
	if (r != -1) return r;
	r = L; // `например, если исходящих рёбер нет, результат уже верен`
	for (int x : edges[v])
		if (result(x) == L) // `ищем ребро в проигрышную`
			r = W; // `добавь break, будь оптимальнее!`
	return r;
}
\end{code}

\begin{Rem}
Чтобы не придумывать ничего отдельно для несимметричных игр,
обычно просто вводят новый граф, вершины которого -- пары $\q{v, who}$
(вершина и, кто ходит).
\end{Rem}

\pagebreak
\vspace*{-1.5em}
\Subsubsection{Решение для графа с циклами (ретроанализ)}

Будем пользоваться \autoref{lm@games}.
Цель: как только есть вершина, которая по лемме должна стать \t{W}/\t{L}, 
делаем её такой и делаем из этого некие выводы.
Процесс можно реализовать через dfs/bfs. \\
Мы выберем именно bfs, чтобы в будущем вычислить {\it длину игры}.
Итак, ретроанализ:

%\pagebreak

\begin{code}
queue <-- `\color{black}{все вершины, которые по условию}` W/L.
while !queue.empty()
	v = queue.pop()
	for x in inner_edges[v]: // `входящие в \t{v} рёбра`
		if lose[v]: 
			make_win(x, d[v]+1)
		else: 
	 		if ++count[x] == deg[x]: // `в count считается число проигрышных рёбер`
	 			make_lose(x, d[v]+1)
\end{code}
Функции \t{make\_win} и \t{make\_lose} проверяют, что 
вершину помечают первый раз, если так, добавляют её в очередь.
Второй параметр -- обычное для \t{bfs} расстояние до вершины.\\
Все помеченные вершины по \autoref{lm@games} помечены правильно. \\
Непомеченные вершины, чтобы им было не обидно, пометим \t{D}.
\begin{Thm}
Ничейные -- ровно вершины с пометкой \t{D}.
\end{Thm}
\begin{proof}
Из вершины $v$ типа \t{D} есть рёбра только в \t{D} и \t{W} (в \t{L} нет, т.к. \\
тогда бы наш алгоритм пометил $v$, как \t{W}).
Также из любой \t{D} есть хотя бы одно ребро в \t{D}.\\
Мы игрок, мы находимся в \t{D}. Каков у нас выбор? Если пойдём в \t{W}, 
проиграем. \\
Проигрывать не хотим $\SO$ пойдём в \t{D} $\SO$ вечно будем оставаться в \t{D} $\SO$ ничья.
\end{proof}

\begin{Def}
$len(G,v)$ -- длина игры, сколько ходов продлится игра,
если выигрывающий игрок хочет выиграть максимально быстро, а проигрывающий максимально затянуть игру.
\end{Def}

\begin{Rem}
После ретроанализа $\t{d[v]} = len(G, v)$, так как ретроанализ: \\
1. Перебирал вершины в порядке возрастания расстояния.\\
2. Для выигрышной вершины брал наименьшую проигрышную.\\
3. Для проигрышной вершины брал наибольшую выигрышную.\\
Строго доказать можно по индукции. 
Инварианты: при обработке $v$ все вершины со строго меньшей длиной игры уже
обработаны; если посчитано $r(v)$, то посчитано верно.
\end{Rem}

\down
\begin{Rem}
На практике разбиралась садистская версия той же задачи: проигрывающий хочет 
побыстрее выиграть и начать новую партию, а выигрывающий подольше
наслаждаться превосходством (т.е. оставлять себе возможность выиграть).
Описание решения: после первого ретроанализа поменять местами смысл \t{L}/\t{W}, запустить второй ретроанализ.
\end{Rem}

\pagebreak
\vspace*{-1.5em}
\Subsection{Ним и Гранди, прямая сумма}

% Прямая сумма игр: НИМ, mex, Гранди, Эквивалентность игр
% гранди с зацикливанием

\up
\begin{Def} 
Прямая сумма графов $G_1 = \q{V_1, E_1}$ и $G_2 = \q{V_2, E_2}$ -- 
граф с вершинами \\
$\q{v_1, v_2}\,|\, v_1 \in V_1, v_2 \in V_2$ и
рёбрами 
$(a, b) \to (a, c)\,|\,(b,c) \in E_2$ и
$(a, b) \to (c, b)\,|\,(a,c) \in E_1$.
\end{Def} 

\begin{Def} 
Прямая сумма игр: $\q{G_1, v_1} \times \q{G_2, v_2} = \q{G_1 \times G_2, (v_1, v_2)}$ 
\end{Def} 

\up
По сути ``у нас есть два графа, можно делать ход в любом одном из них''.

\begin{Def} 
$mex(A) = \min x\ |\ x \ge 0, x \not\in A$.
\end{Def}
\begin{Example}
$A = \{0, 1, 7, 10\} \SO mex(A) = 2; \quad A = \{1, 2, 3, 4\} \SO mex(A) = 0$
\end{Example}
\begin{Def} 
На ацикличном орграфе можно задать Функцию Гранди $f[v]$\t{:}\\ 
Пусть из $v$ ведут рёбра в $Out(v) = \{x_1, x_2, \dots, x_k\} \overset{def}{\SO}
f[v] = mex\{f[x_1], \cdots, f[x_k]\}$.
\end{Def}

%// mex множества A считается за $\mathcal{O} |A|$

\begin{Lm}
$f[v] = 0 \EQ v \in \t{LOSE}$ (доказывается элементарной индукцией)
\end{Lm}

\begin{Example}
{\it Игра ``спички''}. На столе $n$ спичек, за ход можно брать от $1$ до $4$ спичек.
Кто берёт последнюю, проигрывает.
Проверьте, что функция Гранди: $0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, \dots$
При этом проигрывает тот, кто получает $n\,\vdots\,5$,
а чтобы выиграть, нужно взять $n \bmod 5$ спичек.
\end{Example}

\begin{Example}
{\it Игра ``Ним''}. На столе $n$ камней, за ход можно брать любое положительное число камней.
Заметим $f[n] = n$, выигрышная стратегия -- взять всё.
\end{Example}

Пока теория не выглядит полезной. Чтобы осознать полезность, рассмотрим прямые суммы тех же игр --
есть $n$ кучек спичек или $n$ кучек камней, и брать можно, соответственно, только из одной из кучек.
На вопрос ``кто выиграет в таком случае'' отвечают следующие теоремы:

\begin{Thm}
 $f[\q{v_1, v_2}] = f[v_1] \oplus f[v_2]$
\end{Thm}
\begin{proof}
Для доказательства воспользуемся индукцией по размеру графа.\\
Из вершины $v$ в процессе игры сможем прийти только в $C(v)$ -- достижимые из $v$ вершины. \\
Для любого ребра $\q{v_1, v_2} \to \q{x_1, x_2}$ верно, что $|C(\q{v_1, v_2})| > |C(\q{x_1, x_2})|$.\\
База индукции: или из $v_1$, или из $v_2$ нет рёбер.\\
Переход индукции: для всех $\q{G_1,x_1,G_2,x_2}$ с $|C(\q{x_1, x_2})| < |C(\q{v_1, v_2})|$ уже доказали 
\begin{smallformula}
$$f[\q{x_1, x_2}] = f[x_1] \oplus f[x_2]$$
\end{smallformula}
Осталось честно перечислить все рёбра из $\q{v_1, v_2}$ и посчитать $mex$ вершин, в которые они ведут.

\down
$A = \{\underbrace{f[v_1] \oplus f[x_{21}], f[v_1] \oplus f[x_{22}], \dots}_{\text{игрок сделал ход из $v_2$}}, \underbrace{f[x_{11}] \oplus f[v_2], f[x_{12}] \oplus f[v_2], \dots}_{\text{игрок сделал ход из $v_1$}}\}$. \\
Здесь $Out(v_1) = \{x_{11}, x_{12}, \dots\}, Out(v_2) = \{x_{21}, x_{22}, \dots\}$.
Доказываем, что $mex\,A = f[v_1] \oplus f[v_2]$.

\down
Во-первых, поскольку $\forall i\,f[x_{1i}] \not= f[v_1] \wedge \forall i\,f[x_{2i}] \not= f[v_2]$, имеем
$f[v_1] \oplus f[v_2] \not\in A$.\\
Докажем, что все меньшие числа в $A$ есть. Обозначим $x = f[v_1],\,y = f[v_2],\,M = f[v_1] \oplus f[v_2]$.
Будем пользоваться тем, что из $v_1$ есть ходы во все числа из $[0, x)$, аналогично $v_2 \to [0, y)$.\\
Пусть $k$ -- старший бит $M$ и пришёл он из $x \SO$ \\
ходами $x \to [0,2^k)$ мы получим $2^k$
в $x$ различных $k$-битных чисел, т.е. все числа из $[0,2^k)$. \\
Чтобы получить числа $[2^k,M)$ перейдём от задачи $\q{x, y, M}$ к $\q{x - 2^k, y, M - 2^k}$. \\
Воспользуемся индукцией. База: $M = 0$.
\end{proof}

\begin{Cons}
Для суммы большего числа игр аналогично: $f[v_1] \oplus f[v_2] \oplus \dots \oplus f[v_k]$.
\end{Cons}

\begin{Rem}
Рассмотрим раскраску части плоскости $[0,\INF) \times [0,\INF)$. \\
В клетку $[i,j]$ ставится минимальное неотрицательное целое число, которого нет левее и ниже.\\
Получится ровно $i \oplus j$, так как мы ставим ровно $mex$ в игре Ним на кучках $\{i, j\}$.
\end{Rem}

\up
\Subsection{Вычисление функции Гранди}

Ацикличный граф $\SO$ динамика.
Осталось быстро научиться считать $mex$: \\
используем ``обнуление'' массива за $\O(1)$ и получим $\O(deg_v)$ на вычисление $mex$ вершины $v$:
\begin{code}
int cc, used[MAX_MEX]; // `изначально нули`
cc++;
for (int x : out_edges[v])
	used[f[x]] = cc; // `функция Гранди $x$ уже посчитана`
for (f[v] = 0; used[f[v]] == cc; f[v]++)
	;
\end{code}
Итого суммарное время работы $\O(V{+}E)$.

Нужно ещё оценить \t{MAX\_MEX}. Тривиальная оценка даёт $\O(\max_v \deg_v)$, можно точнее:
\begin{Lm} 
$\forall G = \q{V, E},\ \forall v\ f[v] \le \sqrt{2E}$
\end{Lm}
\begin{proof}
Пусть в графе есть вершина с функцией Гранди $k \SO$ из неё есть рёбра в вершины с функцией Гранди $0, 1, \dots, k{-}1$. А из вершины с функцией Гранди $k{-}1$ есть ещё $k{-}1$ рёбер и т.д.
Итого: $k+(k{-}1)+(k{-}2)+\dots+1 = \mfrac{k(k+1)}{2}$ рёбер $\SO k(k+1) \le 2E \SO k \le \sqrt{2E}$.
\end{proof}

\up
\Subsection{Эквивалентность игр}

Напомним, игра на графе -- пара $\q{G,v}$. 
Материал главы относится к произвольным орграфам.

\begin{Def}
Игры $A$ и $B$ называются эквивалентными, если $\forall C\ r(A \times C) = r(B \times C)$.
\end{Def}

\begin{Def}
Игры $A$ и $B$ называются эквивалентными, если $A + B$ проигрышна.
\end{Def}

На лекции вам дано второе определение, обычно используют первое... 

В любом случая важно понимать, что ``эквивалентность'' -- отдельная глава, которой мы не пользовались, выводя 
фукнцию Гранди от прямой суммы игр.

\down
\TODO


