\Section{Игры}{05 мая}{Винниченко Максим}

\Subsection{Симметричные игры на графе}

\Def 

орграф + выделенная вершина

ход -- сдвиг по ребру,

lose: degout 0

\Def Upgrade: 
\begin{itemize}
	\item мн-во вершин win
   
    \item мн-во вершин lose
    
    \item мн-во никаких

\end{itemize}


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

\Lm

	win $\Leftrightarrow \exists$ ход в lose
	
	lose $\Leftrightarrow \nexists$ ход в win
	
$\ $

Динамика.

База:

dp[v] = 1 $\Leftrightarrow$ win

dp[v] = 0 $\Leftrightarrow$ lose

Переход:

dp[v] = OR $\{ \!dp[u_i] \}$

Порядок вычисления: или dfs или topsort

$\ $

Замечание: можно и для upgrade


\Subsubsection{Решение с циклами (ретроанализ)}

\begin{lstlisting}
queue <- WIN, LOSE

while !queue.empty()
	v <- queue
	if lose[v]: 
		for x <- v, 
			win(x)
	if win[v]:
		for x <- v :
	 		count[x]--
	 		if !count[x] and !wiv[x]:
	 			lose(x)
\end{lstlisting}

\Lm N $\Leftrightarrow$ DRAW, где N -- не помеченные
	
	N $\nexists\ \rightarrow$ LOSE (иначе вершина попала бы в WIN)	
	
	N $\exists\ \rightarrow$ N (есть ребро и не в LOSE, и не в WIN (иначе мы вершина была бы в LOSE); можно перейти в N (ничейную))

\Subsubsection{Прямая сумма игр}

\Def прямая сумма игр: $\langle G1, v1 \rangle \times \langle G2, v2 \rangle$

 2 графа ходим либо в первом либо во втором.

\Def функция Гранди: $f[v] = mex\{f[x_1] \cdots f[x_k]\}$

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

\Lm f[v] = 0 $\Leftrightarrow$ LOSE 

Индукция, 

$0 \nexists \rightarrow 0$,

$!0 \exists \rightarrow 0$.

// Корректность показывается  так же, как и в решении для ациклического графа. 

\Thm $f(v1) \oplus f(v2) = f(\langle v1, v2 \rangle)$, без док-ва

// функция Гранди для суммы игр -- xor функций Гранди этих игр.

\Subsubsection{Ним}

	n кучек

	в i-й $a_i$ камней
	
	за 1 ход нужно взять ненулевое число камней из выбранной кучки. 
