\pdfminorversion=4
\documentclass[16to10]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[MeX]{polski}

\usepackage{pgfpages}
\setbeameroption{show notes on second screen}

\usepackage{wrapfig}
\usepackage{mathtools}
%\usepackage{movie15}
\usepackage{hyperref}

\usepackage{buildinggraph}
\usepackage{subcaption}
\usepackage{multirow}
\usepackage{xcolor}
\usepackage{colortbl}
\usepackage{tikz}
\usepackage{algorithm2e}
\usepackage{biblatex}
\bibliography{prez}

\usetikzlibrary{positioning,shapes,calc,through,intersections,fit,matrix}

\tikzset{
  flowchart/.style={
      process/.style={rounded rectangle, draw,align=center},
      decision/.style={diamond, aspect=2, draw,align=center},
      transition/.style={draw,->},
      dataflow/.style={->,dashed},
    },
    mnemonic/.style={
      label={[fill=blue!30]120:#1}
    }
}


\DeclareMathOperator*{\argmax}{arg\,max}


\hypersetup{unicode=true}

\setbeamertemplate{navigation symbols}{} 

\graphicspath{{},{aruntimes/},{games/}, {img/}}

\newcommand{\rplotscale}{.43}

\newcommand{\dice}{
  \begin{tikzpicture}[
    point/.style={fill=black, inner sep=0, minimum width=.2em, circle}
    ]
    \draw[black,draw] (0,0) -- (2em, 0) -- (2em, 2em) -- (0, 2em) --
    cycle;
    \draw[black,draw] (0,2em) -- (1em, 3em) -- (3em, 3em) -- (2em,
    2em);
    \draw[black, draw] (2em, 0em) -- (3em, 1em) -- (3em, 3em);

    \node[point] at (2.5em, 1.5em) {};
    \node[point] at (0.66em, 0.66em) {};
    \node[point] at (0.66em, 1.33em) {};
    \node[point] at (1.33em, 0.66em) {};
    \node[point] at (1.33em, 1.33em) {};
    \node[point] at (0.8em, 2.3em) {};
    \node[point] at (2.2em, 2.7em) {};
    
  \end{tikzpicture}
}

\usetheme{Madrid}
%\usecolortheme{seagull}
\setbeamercovered{dynamic}

\definecolor{darkgreen}{rgb}{.15,.4,.15}
\definecolor{mediumgreen}{rgb}{.2,.6,.2}
\usecolortheme[named=darkgreen]{structure}


\begin{document}

\title[]{Zastosowanie metody UCT i drzewa strategii
behawioralnej do aproksymacji stanu równowagowego Stackelberga
w grach wielokrokowych}
\author{Jan Karwowski} 
\institute[MiNI]{Zakład Sztucznej Inteligencji i Metod Obliczeniowych\\Wydział Matematyki i Nauk Informacyjnych PW}
\date{17 I 2018}

\frame{\titlepage}

\begin{frame}{Plan}
  \tableofcontents
  \note[item]{Zwrócić uwagę na długi wstęp do teorii gier}
\end{frame}

\section{Motywacja}

\begin{frame}{Cele}
  \begin{block}{Equilibrium Stackelberga: Istniejące rozwiązania}
    \begin{itemize}
    \item Oparte o LP i MILP
    \item Uniwersalne ale wolne i pamięciożerne lub
    \item wykorzystujące własności konkretnych gier do przyspieszenia
      i aproksymacji wyniku
    \item Macierze rosną wykładniczo względem liczby rund
    \end{itemize}
  \end{block}
  \begin{block}{Nowe podejście}
    \begin{itemize}
    \item Metoda dobrze działająca z dyskretnymi grami wielokrokowymi
    \item Metoda dobrze skalująca się z długością gry (szczególnie pamięć)
    \item Metoda łatwa do dostosowania do różnych rodzajów gier
    \item Rozwiązania przybliżone
    \end{itemize}
  \end{block}
  \note[item]{Podkreślić wielokrokowość jako potencjalny postęp}
  \note[item]{Powiedzieć o strategiach Markova}
\end{frame}

\section{Equilibrium Stackelberga}

\begin{frame}{Postać normalna gry o sumie (nie)zerowej}
  \begin{columns}
    \begin{column}{.45\linewidth}
  \begin{block}{Macierz wypłat \onslide<2>{gracza P1}}
  \begin{tabular}{c|cccc}
    \textbf{P1/P2} & a & b & c & d \\
    \hline
    A & 6 & 4 & $-2$ & 1 \\
    B & 0 & 0 & 2 & 3 \\
    C & $-3$ & $-2$ & $-1$ & $-1$ \\
  \end{tabular}

  \begin{itemize}
    \item $U_{P1}(A,b)=4$
    \item<1> $U_{P2}(A,b)=-4$ 
  \end{itemize}
\end{block}
\end{column}
\begin{column}{.45\linewidth}
\pause
  \begin{block}{Macierz wypłat gracza P2}
  \begin{tabular}{c|cccc}
    \textbf{P1/P2} & a & b & c & d \\
    \hline
    A & $-6$ & \alert{3} & $2$ & $-1$ \\
    B & 0 & 0 & $-2$ & $-3$ \\
    C & \alert{$-3$} & $2$ & \alert{$0$} & $1$ \\
  \end{tabular}
  \begin{itemize}
    \item 
    \item $U_{P2}(A,b)=3$ 
  \end{itemize}
\end{block}
\end{column}


\end{columns}

\end{frame}

\begin{frame}{Strategia mieszana}
  \begin{tabular}{c|cc}
    E & H & T \\
    \hline
    H & 1 & $-1$ \\
    T & $-1$ & $1$ \\
  \end{tabular}
  \hspace{3cm}
  \begin{tabular}{c|cc}
    O & H & T \\
    \hline
    H & $-1$ & $1$ \\
    T & $1$ & $-1$ \\
  \end{tabular}

  \begin{itemize}
  \item Strategia podstawowa (wybór jednego ruchu) -- $\pi$
  \item Strategia mieszana -- rozkład prawdopodobieństwa nad $\pi$ -- $\sigma$
  \end{itemize}
  \note[item]{Podkreślić oznaczenia}
\end{frame}

\begin{frame}{Równowaga Stackelberga}
  \note[item]{Zwrócić uwagę, że remis jest tylko kryterium brzegowym i
    bez niego jest supremum zamiast maksimum,a w punkcie jest po
    prostu źle określony}
    \begin{itemize}
  \item Asymetryczni gracze: \emph{Leader}, \emph{Follower}
  \item \emph{Follower} zna \textbf{strategię} \emph{Leadera} w
    momencie wyboru swojej strategii. (Ale niekoniecznie wykonuje
    \textbf{ruch} po leaderze).
  \item \emph{Follower} rozstrzyga remisy (swojej wypłaty) na korzyść \emph{Leadera}
  \end{itemize}
  \begin{block}{Gra}
    \centering
    \begin{tabular}{r||c|c}
      &F1&F2\\
      \hline
      \hline
      L1&-15&3 \\
      \hline
      L2&3&-15 \\
    \end{tabular}\hspace{1cm}
    \begin{tabular}{r||c|c}
      &F1&F2\\
      \hline
      \hline
      L1&\alert{30}&0 \\
      \hline
      L2&0&\alert{20} \\
    \end{tabular}
  \end{block}
\alt<1>{
  \begin{columns}
    \begin{column}{.48\linewidth}
  \begin{block}{Equilibrium}
    \resizebox{\linewidth}{!}{
    \begin{tabular}{r|r|r}
      \multicolumn{3}{c}{Leader}\\
      \hline
      Pr. & & $U_l$ \\
      \hline
      $0.4$&L1&$-15$\\
      $0.6$&L2&$3$\\
    \end{tabular}
    \hspace{.3cm}
    \begin{tabular}{r|r|r|r}
      \multicolumn{4}{c}{Follower}\\
      \hline
      Pr. & & $U_f$ & $U_l$\\
      \hline
      $1$&F1&$12$&\cellcolor{green!30}$-4.2$ \\
      $0$&F2&$12$&$-7.8$ \\
    \end{tabular}
    }
  \end{block}
\end{column}
\begin{column}{.48\linewidth}
  \begin{block}{Zaburzone equilirbium}
    \resizebox{\linewidth}{!}{
    \begin{tabular}{r|r|r}
      \multicolumn{3}{c}{Leader}\\
      \hline
      Pr. & & $U_l$ \\
      \hline
      $0.39$&L1&$3$\\
      $0.61$&L2&$-15$\\
    \end{tabular}
    \hspace{.1cm}
    \begin{tabular}{r|r|r|r}
      \multicolumn{4}{c}{Follower}\\
      \hline
      Pr. & & $U_f$ & $U_l$ \\
      \hline
      $0$&F1 &$11.7$ & $-4$\\
      $1$&F2 &\cellcolor{green!30}$12.2$ & $-8$\\
    \end{tabular}
}
  \end{block}
\end{column}
\end{columns}
}{  
  \begin{block}{Dwupoziomowy problem optymalizacyjny}
    $$ \argmax_{\sigma_l \in \Sigma_l} U_l(\sigma_l, R_f(\sigma_l)) $$
    $ R_f(\sigma_l) = \argmax_{\sigma_f \in \Sigma_f} U_f(\sigma_l, \sigma_f) $ --
    funkcja schodkowa
    \note[item]{W dwupoziomowym problemie nie zapisałem warunku remisów -- trzeba by rozrzeczyć
    $R_a$ do zbioru i zrobić dodatkowe maksimum}
  \end{block}
}
\pause
\end{frame}

\begin{frame}{Strategie followera}
  Można pokazać, że dla dowolnego equilirbium $(\sigma_l, \sigma_f)$
  układ $(\sigma_l, \pi_f)$ dla dowolnego $\pi_f$ mającego niezerowe
  prawdopodobieństwo w $\sigma_f$ też jest equilibrium.

  Wniosek: wystarczy rozważać tylko strategie podstawowe followera
  (ale mieszane leadera!!).
  \note[item]{Zwrócić uwagę, że w zasadzie tylko dzięki temu potrafimy
    rozwiązywać te gry}
\end{frame}

\begin{frame}[allowframebreaks]{Gry wielokrokowe}
  \note[item]{Zwrócić uwagę, że gra jako taka jest deterministyczna}
  \note[item]{Zwrócić uwagę na materializowanie się wiedzy w różnych
    momentach}
  \note[item]{Przypomnieć że follower zna strategie leadera}
  \note[item]{Perfect recall i równoważność strategii behawioralnej i mieszanej}
  \begin{block}{Gra}
    \resizebox{\textwidth}{!}{
      \input{igame.tex}
    }
  \end{block}
  \begin{columns}
    \begin{column}{.44\textwidth}
      \begin{block}{Gracz $\circ$}
        \input{ogame.tex}
        \vspace{-0.7em}
      \end{block}
    \end{column}
    \begin{column}{.55\textwidth}
      \begin{block}{Gra}
        \resizebox{\textwidth}{!}{
          \input{igame.tex}
        }
      \end{block}
    \end{column}
  \end{columns}
  
  \begin{itemize}
  \item Strategia podstawowa --- przypisanie akcji do każdego punktu
    decyzyjnego (information setu). Strategia zredukowana --- tylko
    potencjalnie osiągalne IS. 
  \item Strategia mieszana --- rozkład prawdopodobieństwa nad
    strategiami podstawowymi
  \item Strategia behawioralna --- przypisanie rozkładu
    prawdopodobieństwa akcji w każdym punkcie decyzyjnym
  \end{itemize}
\end{frame}

\begin{frame}{Security Games}
\begin{itemize}
\item Obrońcy i atakujący
\item Asymetria graczy
\item Różne rodzaje przestrzeni
\item Zwykle obrońca ma większą przestrzeń decyzyjną
\item Brak jednolitej definicji
\item {\small Zazwyczaj} równowaga Stackelberga
\end{itemize}
\note[item]{Aktualnie popularny temat: obrona granic, lotnisk, także
  green security games}
\end{frame}

\section{Metoda oparta o drzewo strategii}

\begin{frame}{Typowe podejście}
  \note[item]{Pokazać gdzie zaszyty jest wybór atakującego w milpie i
    że do wyboru i wymuszenia atakującego używamy tylko ograniczeń}
  \note[item]{Uwaga: To jest poniekąd odwrócenie problemu}
  \begin{itemize}
  \item Przegląd wszystkich strategii followera i rozwiązanie LP
    poszukującego dobrego leadera
  \item MILP, który łączy przegląd followera i poszukiwanie leadera
  \end{itemize}

  \begin{block}{MILP}
    \small
        \[
      \begin{array}{rlr}
        &\multicolumn{2}{l}{\max_{q,z,a}  \sum_{i\in X} \sum_{j \in Q} R_{ij}z_{ij} }\\
        \text{s.t.} & \sum_{i \in X} \sum_{j \in Q} z_{ij} = 1\\
        (\forall_{i \in X})& \sum_{j \in Q} z_{i,j} \leq 1\\
        (\forall_{j \in Q})& q_j \leq \sum_{i \in X} z_{ij} \leq 1\\
        & \sum_{j \in Q} q_j = 1 & \\
        (\forall_{j \in Q})&\multicolumn{2}{l}{0\! \leq \! (a\! -\! \sum_{i \in X} C_{ij}(\sum_{h\in
                             Q} z_{ih}))\!}\\
                (\forall_{j \in Q})&\multicolumn{2}{l}{(a\! -\! \sum_{i \in X} C_{ij}(\sum_{h\in
            Q} z_{ih}))\! \leq\! (1\! -\! q_j)M}\\
        &\\
        & z_{ij} \in [0,1] , q_j \in \{0,1\} , a \in \mathbb{R} \\
      \end{array}
    \]
    \fullcite{paruchuri2008efficient}
\end{block}
\end{frame}


\begin{frame}{Pomysł}
  Heurystyka wyboru interesujących strategii folllowera + przybliżone
  znalezienie strategii obrońcy.

  \begin{block}{Szukanie leadera}
    Strategia obrońcy musi spełniać ograniczenie wymuszające założoną
    odpowiedź followera. 
  \end{block}
\end{frame}

\begin{frame}[allowframebreaks]{Przegląd strategii followera z użyciem
    UCT}
  \note[item]{Odrobinę o słabościach i sukcesach UCT}
  \begin{block}{UCT}
    \fullcite{UCT}\\
    \alert{Metaheurystyka wyboru najlepszego ruchu w grze.}
    \input{ucttree}
  \end{block}
  \begin{block}{Gra}
    \begin{itemize}
    \item Stany etykietowane potencjalnie osiągalnymi stanami followera
    \item Wykonanie ruchu oznacza ustalenie decyzji w strategii
      podstawowej.
    \item Wynikiem gry jest zredukowana strategia podstawowa
    \end{itemize}
  \end{block}
  \begin{block}{Przegląd}
    \small
    \input{../mcts-evaluate-flowchart}
  \end{block}
\end{frame}

\begin{frame}{Drzewo strategii obrońcy}
  \note[item]{Nie wszystkie ruchy są w drzewie}
  \note[item]{Nie wszystkie stany osiągalne z ruchu są w drzewie}
  \note[item]{Dla pozostałych przyjmuję rozkład jednostajny}
  \input{../mixed-strategy-tree}
\end{frame}

\begin{frame}[allowframebreaks]{Dostosowanie strategii}
  \begin{block}{Zarys metody}
    \small
    \input{mixed-strategy-flowchart-sm}
  \end{block}
  \begin{block}{Dostosowanie strategii w punkcie}
    \begin{enumerate}
    \item \dice Dodaj nowy ruch wraz ze ścieżką do liścia wychodzący z węzła
    \item \dice Zejdź do potomków
    \item \dice Dostosuj strategię w węźle
    \end{enumerate}
  \end{block}
\end{frame}

\begin{frame}{Metoda dostosowywania węzła}
  \begin{block}{Struktury danych}
    \begin{itemize}
    \item Moment -- wektor o długości równej liczbie ruchów
    \item Współczynnik normalizacji momentu
    \end{itemize}
  \end{block}
  
\begin{algorithm}[H]
  \SetAlgoLined

  \KwData{$prob\in {[0,1]}^M$ probabilities vector,
    $mom\in {(R^+\cup\{0\})}^M$ momentum vector, $w$ -- momentum
    normalization factor, $as\in \mathbb{R}^M$ assessments vector. All
    vectors contain values for $i$-th move at $i$-th position}

  $mom \gets mom + as$\;
  $w \gets w + L_1(as)$\;

  $prob \gets max\{prob+mom/w, 0\}$\tcp{max at each
    position}

  $prob \gets normalizeOrEqual(prob)$\tcp{Normalize vector values so
    their sum is 1 or as a fallback assign uniform probability}
  
\end{algorithm}
\end{frame}

\begin{frame}{Problemy}
  \begin{itemize}
  \item Czy zbiega do optymalnej strategii
  \end{itemize}
\end{frame}

\section{Wyniki}
\begin{frame}{MILP:\@ metoda do porównań}
  \note[item]{Uwaga o problemach numerycznych}
  \begin{columns}
    \begin{column}{.65\linewidth}
      \begin{block}{MILP}
        $$
      \begin{array}{rlr}
        &\multicolumn{2}{l}{\max_{q,z,a}  \sum_{i\in X} \sum_{j \in Q} R_{ij}z_{ij} }\\
        \text{s.t.} & \sum_{i \in X} \sum_{j \in Q} z_{ij} = 1\\
        (\forall_{i \in X})& \sum_{j \in Q} z_{i,j} \leq 1\\
        (\forall_{j \in Q})& q_j \leq \sum_{i \in X} z_{ij} \leq 1\\
        & \sum_{j \in Q} q_j = 1 & \\
        (\forall_{j \in Q})&\multicolumn{2}{l}{0\! \leq \! (a\! -\! \sum_{i \in X} C_{ij}(\sum_{h\in
                             Q} z_{ih}))\!}\\
                (\forall_{j \in Q})&\multicolumn{2}{l}{(a\! -\! \sum_{i \in X} C_{ij}(\sum_{h\in
            Q} z_{ih}))\! \leq\! (1\! -\! q_j)M}\\
        &\\
        & z_{ij} \in [0,1] \\
        & q_j \in \{0,1\} \\
        & a \in \mathbb{R} \\
      \end{array}
      $$
\end{block}
\end{column}
\begin{column}{.33\linewidth}
  \begin{block}{Złożoność}
    $|X|$ -- liczba strategii (sekwencji) leadera, $|Q|$ -- liczba
    strategii (sekwencji) followera

    \begin{itemize}
      \item $O(|X|\cdot |Q|)$ zmiennych, w tym  $|Q|$ binarnych.
      \item $O(|X|+|Q|)$ ograniczeń
    \end{itemize}
  \end{block}
\end{column}
\end{columns}
\end{frame}


\begin{frame}{Gra na grafie i generator budynków}
  \note[item]{Nawiązanie do security games}
  \note[item]{Podkreślenie roli wielokrokowości gry, szczególnie z
    punktu widzenia atakującego}
\begin{itemize}
\item Każdy z graczy operuje jednostkami chodzącymi po grafie
\item Obaj wykonują ruch jednocześnie
\item Nie widzą siebie nawzajem
\end{itemize}

\begin{columns}
  \begin{column}{.48\linewidth}
\begin{block}{Przykładowa gra}
\includegraphics[width=\linewidth]{test3c}
\end{block}
\end{column}
\begin{column}{.48\linewidth}
  \begin{block}{Generator budynków}
    \centering
\resizebox{.92\linewidth}{!}{
  \buildinggraph{smallbuilding-102}
  }
\end{block}
\end{column}
\end{columns}
\end{frame}



\begin{frame}[plain]
  \resizebox{\textwidth}{!}{
    \begin{tabular}{c|>{\columncolor{blue!20}}c>{\columncolor{green!30}}cccc|cc|c|cc|c|>{\columncolor{blue!20}}c}
      game&\multicolumn{5}{c|}{New}&\multicolumn{2}{c|}{MixedUCT}&R&\multicolumn{2}{c|}{MILP}&Sc&Sc\\
          &payoff&p. max&sd&time&sd&payoff&time&payoff&payoff&time&MU&new\\
      game1-5&0.54&0.54&0&3108&136&0.51&1778&-10.46&0.54&28053&1&1\\
      game2-5&0.08&0.08&0&922&13&0.07&1661&-7.21&0.08&107&1&1\\
      game3a-5&-4.5&-4.5&0&1299&33&-4.51&1480&-13.97&-4.5&31926&1&1\\
      game3d-5&0.9&0.9&0&1047&15&0.9&1053&-4.61&0.9&37870&1&1\\
      game6-5&-4.87&-4.87&0&1197&53&-4.87&1211&-13.91&-4.87&5313&1&1\\
      game6a-5&-6&-6&0&1251&106&-6&1403&-13.84&-6&5949&1&1\\
      game6b-5&0.79&0.79&0&992&33&0.76&851&-0.81&0.79&5547&0.98&1\\
      sb-1-5&-0.76&-0.08&1.33&2888&85&-0.2&1151&-2.79&0.03&232&0.92&0.72\\
      sb-2-5&0&0&0&1574&38&0&1724&-15.08&0&255&1&1\\
      sb-20-5&1.29&1.29&0&1063&51&1&1050&-1.28&1.29&0&0.89&1\\
      sb-24-5&1.54&1.54&0.01&1889&44&0.92&1874&0.08&1.55&0&0.57&0.99\\
      sb-3-5&0.47&0.49&0.03&1166&58&0.5&1002&-8.55&0.5&0&1&1\\
      sb-35-5&0.5&0.5&0&1027&22&0.5&1582&-0.89&0.5&339&1&1\\
      sb-39-5&0.05&0.06&0.01&1423&77&0.03&2100&-17.06&0.09&0&1&1\\
      sb-41-5&-2.88&-2.88&0&1255&28&-2.88&2240&-5.07&-2.85&0&0.99&0.99\\
      sb-42-5&0&0&0&1947&44&0&1440&-16.53&0&0&1&1\\
      sb-56-5&1.09&1.1&0.01&2638&48&1.01&1676&0.52&1.6&0&0.45&0.53\\
      sb-59-5&0.6&0.6&0&2718&44&0.6&1321&-7.39&0.62&0&1&1\\
      sb-64-5&0.12&0.13&0.01&1568&64&0.12&1698&-11.81&0.16&0&1&1\\
      sb-7-5&-0.77&-0.77&0&1909&54&-1&1053&-9.7&-0.77&0&0.97&1\\
      sb-78-5&0.5&0.5&0&2017&167&0.31&1208&-9.28&0.5&0&0.98&1\\
      sb-82-5&0&0&0&3338&82&0&2498&-10.66&0&0&1&1\\
      sb-85-5&-0.89&-0.89&0&1472&27&-0.95&1456&-1.79&-0.89&0&0.93&1\\
      sb-87-5&0.8&0.8&0&936&23&0.7&1202&-1.66&0.8&0&0.96&1\\
      sb-91-5&-5.62&-5.62&0&2325&51&-5.62&1852&-5.97&-5.62&0&1&1\\
      sb-96-5&0.12&0.19&0.08&788&15&0.13&1876&-10.15&0.19&0&0.99&0.99\\
      sb-98-5&0&0&0&930&8&0&1102&-13.02&-0.3&0&1.02&1.02\\
    \end{tabular}
}
\end{frame}  

\begin{frame}{Dalsze badania}
  \begin{itemize}
  \item Gwarancje zbieżności
  \item Skalowanie się wraz ze wzrostem liczby kroków w grze
  \item Porównanie skalowania z innymi metodami
  \end{itemize}
  \note[item]{Zmiany w modelu: Bounded rationality, większa dynamika}
\end{frame}

\begin{frame}{*}
\end{frame}

\begin{frame}{ }
  (Koniec)
\end{frame}

\end{document}
