\documentclass[12pt,oneside]{fithesis2}
\usepackage[czech] {babel}      % Multilingual support
\usepackage[utf8]{inputenc}       % UTF-8 encoding
\usepackage[T1]{fontenc}          % T1 font encoding


\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\theoremstyle{definition}
\newtheorem{defn}{Definice}[section]
\newtheorem{alg}[defn]{Algoritmus}
\newtheorem{my}{Věta}
\newcommand{\veta}[1]{\begin{my}#1 \end{my}}

\usepackage{float}

\usepackage{url}

\newcommand{\tab}[1]{\hspace{.1\textwidth}\rlap{#1}}
\newcommand{\itab}[1]{\hspace{.3\textwidth}\rlap{#1}}



\usepackage[ruled,czech,longend]{algorithm2e}
\SetKwFor{For}{for}{do}{end~for}

\usepackage[                      % A sans serif font that blends well with Palatino
  scaled=0.86
]{berasans}
\usepackage[                      % A tt font if you do not like LM's tt
  scaled=1.03
]{inconsolata}
\usepackage[                      % Clickable links
  plainpages = false,               % We have multiple page numberings
  pdfpagelabels                     % Generate pdf page labels
]{hyperref}
\usepackage{blindtext}            % Lorem ipsum generator

\usepackage{hyperref}
\usepackage{afterpage}
\usepackage{tablefootnote}

\thesislang{cz}                   % The language of the thesis
\thesistitle{Má Člověče, nezlob se výherní strategii?}       % The title of the thesis
\thesissubtitle{Diplomová práce}  % The type of the thesis
\thesisstudent{Petr Konvalinka}          % Your name
\thesiswoman{false}                % Your gender
\thesisfaculty{fi}                % Your faculty
\thesisyear{Jaro \the\year}     % The academic term of your thesis defense
\thesisadvisor{doc. RNDr. Jiří Barnat, Ph.D.}   % Your advisor

\usepackage[              %% When typesetting the bibliography, the
  backend=biber,          %% `numeric` style will be used for the
  style=numeric,          %% entries and the `numeric-comp` style
  citestyle=numeric-comp, %% for the references to the entries. The
  sorting=none,           %% entries will be sorted in cite order.
  sortlocale=auto         %% For more unformation about the available
]{biblatex}               %% `style`s and `citestyles`, see:
%% <http://mirrors.ctan.org/macros/latex/contrib/biblatex/doc/biblatex.pdf>.
\addbibresource{my.bib} %% The bibliograpic database within

\usepackage{array}  
\renewcommand{\arraystretch}{1.3}




\newcommand{\hjedna}{\emph{hráč 1}}
\newcommand{\hdva}{\emph{hráč 2}}
\newcommand{\hejedna}{\emph{hráče 1}}
\newcommand{\hedva}{\emph{hráče 2}}
\newcommand{\pravd}{\emph{pravděpodobnostní}}

\newcommand{\vst}{v_{\sigma,\tau}}
\newcommand{\vost}{\overline{v}_{\sigma,\tau}}
\newcommand{\gst}{G_{\sigma,\tau}}

\renewcommand\floatpagefraction{0.9}

\begin{document}

    %% We will define several mathematical sectioning commands.
\newtheorem{theorem}{Theorem}[section] %% The numbering of theorems
                               %% will be reset after each section.
\newtheorem{lemma}[theorem]{Lemma}     %% The numbering of lemmas
\newtheorem{corr}[theorem]{Corrolary}  %% and corrolaries will
                                %% share the counter with theorems.
                                


  \FrontMatter                    % The front matter
    \ThesisTitlePage                % The title page
    
   \afterpage{\null\newpage}
    
    \begin{ThesisDeclaration}       % The declaration
      \DeclarationText
      \AdvisorName
    \end{ThesisDeclaration}
    \begin{ThesisThanks}            % The acknowledgements (optional)
     Rád bych poděkoval doc. RNDr. Jiřímu Barnatovi, Ph.D. za jeho cenné rady a připomínky při vedení této diplomové práce.
    \end{ThesisThanks}
    \begin{ThesisAbstract}          % The abstract
      Práce se zabývá hrami se dvěma a půl hráče. Nejprve se definují důležité pojmy a následně se probírájí dva algoritmy pro výpočet optimální strategie ve zmíněných hrách. Cílem práce je také navrhnout C++ framework pro řešení takovýchto her. Součástí je i implementace prototypového řešení hry Člověče, nezlob se využívající vytvořený framework.
    \end{ThesisAbstract}
    \begin{ThesisKeyWords}          % The keywords
      Hry se dvěma a půl hráče, SSG, QT, C++, Člověče, nezlob se
    \end{ThesisKeyWords}
    \tableofcontents                % The table of contents
     \listoffigures                  % The list of figures (optional)
    
%   \listoftables                   % The list of tables (optional)
  
  
  \MainMatter                     % The main matter
    \chapter{Úvod}          % Chapters
     \label{chap:uvod}
     
     \emph{Hry se dvěma a půl hráče} jsou speciálním druhem her z~odvětví \emph{toerie her}. Využívají se zejména v~ekonomice, biologii, inženýrství a počítačových vědách. Zachycují chování hráčů ve strategických situacích, ve kterých dva hráči dělají rozhodnutí, které mohou ovlivnit zájmy druhého hráče. Hráči se v~těchto situacích řídí podle tzv. strategií. Pokud oba hráči použijí svou nejlepší možnou strategii, mluvíme o~tzv. \emph{optimálních strategiích}. Kromě dvou hráčů do hry vstupuje i náhoda, což je tzv. \emph{půlhráč}. Hlavním cílem naší práce je zjistit, jak se nejlépe zachovat ve zmíněných strategických situacích, tedy vypočítat hráčům jejich \emph{optimální strategie}.
     
     Práce se zabývá \emph{hrami se dvěma a půl hráče} a studuje algoritmy pro jejich řešení. Cílem práce je také navrhnout \texttt{C++} framework pro řešení takovýchto her. Na základě tohoto frameworku pak vytvoříme prototypové řešení hry \emph{Člověče, nezlob se}, které jej bude využívat.
     
     V~první kapitole se seznámíme s~pojmem \emph{Hry se dvěma a půl hráče} a \emph{Simple Stochastic Games (SSG)}. Vysvětlíme zde  teoretické základy nutné pro pochopení dalších částí práce. Popíšeme zde také převod \emph{Her se dvěma a půl hráče} na \emph{SSG}, pro jejichž výpočet je známo nemálo algoritmů. 
     
     Druhá kapitola se zabývá dvěma vybranými algoritmy pro řešení \emph{SSG}. Algoritmy byly vybrány různým způsobem tak, aby každý využíval jinou techniku. Prvním z~nich je \emph{Randomizovaný Hoffman--Karp} algoritmus využívající techniku zlepšování strategie. Druhým je \emph{Shapleyho} iterační algoritmus.
     
     Ve třetí kapitole budeme vyvíjet \texttt{C++} knihovnu pro řešení \emph{her se dvěma a půl hráče}, která bude využívat dva algoritmy probrané v~předchozí kapitole. Knihovna dostane na vstup graf \emph{Hry se dvěma a půl hráče}. Jejím výstupem pak budou vypočítané \emph{optimální strategie} a \emph{optimální hodnoty} (tzv. pravděpodobnosti výhry).
     
     Čtvrtá kapitola se zabývá vývojem prototypu na základě vytvořené knihovny. Prototyp bude mít dvě hlavní funkce. První z~nich je možnost sestrojení grafu \emph{Hry se dvěma a půl hráče} v~interaktivním grafickém prostředí  a následné spočtení výsledků. Druhou, důležitější částí, je namodelování deskové hry \emph{Člověče, nezlob se}. Uživatel si bude moci nastavit plán hry. Aplikace hru následně převede na graf \emph{Hry se dvěma a půl hráče} a vypočítá právděpodobnost výhry, pokud by hráč táhl jednotlivými figurkami. Zjistíme tedy, kterou figurkou je nejvýhodnější v~dané situaci táhnout. 
     
     Poslední kapitola se zaobírá experimentováním s~vyvinutým prototypem. Vyzkoušíme různé příklady hry \emph{Člověče, nezlob se}. Zjistíme, jak dlouho výpočet potrvá a kolik bude mít uzlů graf \emph{Hry se dvěma a půl hráče}, na který se hra transformuje.
     
     
   
     \chapter{Diskrétní hry se dvěma a půl hráče} \label{hry}
     Tato úvodní kapitola nás seznámí s~teoretickými základy nutnými pro zvládnutí dalších částí práce.
     
      \section{Úvod do teorie her}
    V~této podkapitole stručně shrneme pojem  \emph{teorie her}  a velmi obecně vysvětlíme některé termíny, které  jsou s~touto vědní disciplínou nutně spjaté, a které budeme používat v~dalších částech práce. Nejdůležitější pojmy jsou shrnuty v~tabulce \ref{tab1}
    
    \medskip
     \emph{Teorie her} je speciální disciplína aplikované informatiky. Řeší široké spektrum konfliktních rozhodovacích situací s~více účastníky -- hráči. Pojem \emph{hra} má velmi obecný význam. Každý si jistě představí deskové hry jako \emph{šachy} nebo \emph{Člověče, nezlob se}. Do tohoto oboru můžeme ale zařadit téměř jakoukoli konfliktní situaci
mezi jedinci, podniky, armádami, státy, politickými stranami a biologickými druhy. Teoretické modely se pak snaží tyto konflikty nejen analyzovat, ale sestavením matematických modelů  a pomocí výpočtů se snaží nalézt co nejlepší strategie pro účastníky takových konfliktů. 

V~průběhu rozhodovacích situací hráči vybírají \emph{\textbf{strategii}} ze svého \emph{prostoru strategií} podle hodnot výplatní funkce (angl. \emph{payoff}), laicky řečeno: \uv{\emph{Kolik mohu získat}}. Tato výplatní funkce ovšem nezávísí pouze na samotném hráči, ale i na rozhodnutí ostatních hráčů. Výplatní funkce proto musí zohlednit všechny možné kombinace rozhodnutí ostatních hráčů. Např. pokud budeme hrát šachy, není vhodné popojet jezdcem tak, že vytvořím šach, ale soupeř mi jej vezme v~následujícím tahu dámou. Strategie, která mi v~dané konfliktní situaci zajistí nejvyšší dosažitelnou hodnotu výplatní funkce, se nazývá \emph{\textbf{optimální strategie}}. Právě určení  \emph{optimální strategie} je jedním z~hlavních výpočetních problémů, které budeme řešit i my v~naší práci.

Ve většině her je důležitým předpokladem, že jsou hráči inteligentní (chovají se racionálně) -- tedy chtějí maximalizovat hodnotu své výplatní funkce. Jako je tomu např. u~hry \emph{Člověče, nezlob se}. 

Hry můžeme rozdělit na hry: s~\emph{dokonalou informací} (angl. \emph{perfect information}) a nedokonalou informací (angl. \emph{imperfect information}). U~her s~dokonalou informací může v~jednom okamžiku hrát pouze jeden hráč, který zná všechny tahy, které byly provedeny do tohoto okamžiku. Např. u~hry \emph{šachy} víme, jakým tahem hrál soupeř a jakým předtím my. Naopak u~her s~nedokonalou informací mohou hrát hráči nezávisle na sobě. 

Dalším dělení her je na hry s~\emph{nulovým součtem} (angl. \emph{zero--sum})  a \emph{nenulovým součtem} (angl. \emph{non--zero--sum}). Hru nazveme s~\emph{nulovým součtem}, pokud v~každé rozhodovací situaci je součet výplatních funkcí roven nule. Jinak řečeno, přesně to, co já získám, tak druhý zratí (v~případě hry dvou hráčů).  

V~nadpisu této kapitoly se vyskytuje pojem \emph{diskrétní}. Hra je \emph{diskrétní}, pokud je konečná. Tzn., že musí obsahovat konečné množství hráčů, kteří mají na výběr z~konečného množství strategií. 

Řekneme-li, že hra je \emph{tahová}, znamená to, že se hráči ve hře střídají. Jinak řečeno hráč musí vyčkat, dokud není na řadě.

V~naší práci se budemě věnovat diskrétním tahovým hrám s~\emph{dokonalou informací} a \emph{nulovým součtem}, jako jsou např. již zmíněné \emph{šachy} nebo \emph{Člověče, nezlob se}.

 \bigskip
 V~této podkapitole je využito informací ze zdrojů \parencite{uvodDoHer}  a \parencite{uvodDoHerTurocy}.
 
 
 
 \begin{table}[ht]
\begin{center}
        \catcode`\-=12
	\begin{tabular}{| m{6cm} | m{6cm} |} \hline		
            
 	  
          \emph{hra}  & rozhodovací situace, konflikt  \\ \hline
            \emph{hráč} & účastník konfliktu, rozhodovatel, jedinec, politická strana   \\ \hline
          \emph{strategie}  & konkrétní alternativa, kterou může hráč zvolit  \\ \hline   
           \emph{prostor strategií}  & seznam všech možných alternativ, které jsou hráči dostupné  \\ \hline 
          \emph{výplatní funkce}  & výsledek hry, tj. užitek, výhra hráče v~závislosti na zvolených strategiích  \\ \hline 
           \emph{optimální strategie} & strategie, která hráč zajistí co nejvyšší užitek \\ \hline              
           \emph{hra s~dokonalou informací} & v~jednom okamžiku může hrát pouze jeden hráč, který zná historii všech rozhodovacích situací  \\ \hline 
           \emph{hra s~nulovým součtem} & hráč získává na úkor ostaních \\ \hline
             \emph{diskrétní hra} & hra je konečná, má konečný počet hráčů, tahů atd. \\ \hline  
              \emph{tahová hra} & hráči se v~tazích postupně střídají \\ \hline
	\end{tabular}
	\caption{Základní pojmy teorie her \parencite{uvodDoHer} } \label{tab1}
\end{center}
\end{table}
    
      \section{Tahové hry se dvěma a půl hráče s~dokonalou informací}
      Naše práce je zaměřená na  \emph {tahové hry s~dokonalou informací}. Hráči se tedy ve hře střídají a mají dokonalý přehled o~hře. Hra probíhá v~grafu, kde každý uzel znamená nějaký stav ve hře. Hra může probíhat na nekonečně mnoho kol. V~každém kole se stav hry změní pomocí hrany do následujícího uzlu (tzv. následníka). Uzly jsou rozděleny na uzly \hejedna{}, uzly \hedva{} a \pravd{} uzly (to je tzv. půl hráč). V~uzlech \hejedna{} vybírá \hjedna, jaký bude následník a v~uzlech \hedva{} zase vybírá \hdva{} svého následníka. V~\pravd \emph{ch} uzlech je následník volen podle pravděpodobnostní funkce, která může být, ale také nemusí, rovnoměrně rozložena mezi všechny následníky.
      
      \begin{defn} \label{graf} 
\emph{Graf se dvěma a půl hráče} $G=((V,E),(V_1,V_2,V_P),\delta)$ se skládá z~orientovaného grafu $(V,E)$, množiny vrcholů $V$, která je rozdělena na tři podmnožiny $V_1,V_2,V_P \subseteq V~$, a pravděpodobnostní přechodové funkce $\delta: V_P \rightarrow Dist(V)$. $Dist(V)$ je pravděpodobnostní rozložení na $V$, $\delta: V~\rightarrow [0,1]$ takové, že $\sum_{v \in V}^{} \delta (v) = 1$ . Prostor vrcholů $V$ je konečný. Vrcholy $V_1$ jsou vrcholy \hejedna, vrcholy $V_2$ jsou vrcholy \hedva{} a vrcholy $V_P$ jsou \pravd{} vrcholy. Pro všechny vrcholy $v \in V$, definujeme $E(v) = \{t \in V~| (v,t) \in E\}$ jako množinu možných následníků. Je vyžadováno $E(v) \neq \emptyset $ pro všechny nepravděpodobnostní stavy $s \in V_1 \cup V_2$, . Ve stavech \hejedna{} vybírá \hjedna{} následníka z~$E(s)$. Ve stavech \hedva{} vybírá \hdva{} následníka z~$E(v)$ a v~pravděpodnostních stavech $S \in S_P$ je následník vybírán podle pravděpodobnostní přechodové funkce $\delta(v)$.

\end{defn}

 Pro určení vítěze hry musí existovat nějaký cíl. Tedy to, co musí hráč udělat proto, aby vyhrál. Cílem může být např. dosáhnout nějakého stavu anebo se nějakému stavu vyhnout. V~našem případě se budeme chtít dostat do nějakého stavu (např. ve hře \emph{Člověče, nezlob se} dostat se do cílového domečku). Budeme tedy používat tzv. \emph {dosažitelné cíle hry}. 
 
 \begin{defn} \label{cile} 
     \emph {Dosažitelné cíle} $T \subseteq S$ jsou stavy, kterých musíme ve hře dosáhnout, aby jsme vyhráli.
  \end{defn}
 
 Další důležité pojmy, jako \emph {hrací strategie} a \emph {hrací hodnoty}, budou vysvětleny v~následující kapitole o~\emph {Simple stochastic games.} 
 
 V~této kapitole je čerpáno z~\parencite{survey}.
 
 \section{Simple stochastic games}
 
 \emph {Simple stochastic games} (česky \emph jednoduchá pravděpodobnostní hra, zkráceně \emph{SSG}) jsou speciální druhem diskrétních her se \emph{dvěma a půl hráče} s~dosažitelnými cíli. Pro tento typ hry je známo hodně algoritmů, které dokaží řešit problém nalezení optimální strategie. Narozdíl od \emph{Her se dvěma a půl hráče} obsahuje každý uzel v~grafu přesně dvě výstupní hrany. \emph{Graf se dvěma a půl hráče} ale jde převést na \emph{SSG} graf, více v~kapitole \ref{prevod}. 
  
   \begin{defn} \label{ssg} 
     \emph {Simple stochastic games} (\emph{SSG}) je oritentovaný graf $G= (V,E) $ s~následujícími vlastnostmi. Množina vrcholů V~je spojením množin $V_{max}$, $V_{min}$, $V_{average}$ společně se dvěma speciálními uzly nazývanými $0--sink$ a $1--sink$. Jeden vrchol z~$V$ je nazýván \emph {startovní vrchol} (ve kterém začíná hra). Každý vrchol z~$V$ má přesně dvě výstupní hrany, kromě Sink vrcholů (ty nemají žádné). 
  \end{defn}    
     
  Hra začíná ve startovním vrcholu. Představme si, že hrají dva hráči. Jeden si říká Max a druhý Min. Když je hra ve vrcholu $V_{max}$, tak je na řadě hráč Max a vybere jednu ze dvou výstupních hran (tedy další vrchol, ve kterém bude hra pokračovat). Když je hra ve vrcholu $V_{min}$, tak následníka vybírá hráč Min. Pokud je hra ve vrcholu $V_{average}$, tak je následník zvolen náhodně.
  
  \begin{defn} \label{strat} 
   \emph{Maximální} a \emph{minimální strategie}. Maximalní strategie $\sigma$ je množina hran z~$E$, kde počáteční vrchol $v$ z~hrany je z~množiny $V_{max}$ a pro každý takový vrchol v~existuje pouze jediná hrana $(v,z)$ v~$\sigma$. Kdykoli je pak hra ve vrcholu $v$ a hráč Max bude hrát podle strategie $\sigma$, tak se hra přesune do vrcholu $z$. Stejným způsobem je definována minimální strategie $\tau$, pouze vrcholy jsou z~$V_{min}$. Podgrafem grafu G je pak graf $\gst$, který obsahuje pouze hrany z~$\sigma$ a  $\tau$. 
   \end{defn}
     
     \begin{defn} \label{strat}
     \emph{Hodnota} $\vst(i)$ každého vrcholu $i$ z~grafu $G$ je pravděpodobnost, že hráč Max vyhraje hru, když bude hrát podle strategie $\sigma$ a hráč Min podle strategie $\tau$. \emph{Optimální hodnota} vrcholu $i$ je definována jako $\underset{\sigma}{max}  \hspace{0.1cm} \underset{\tau}{min} \hspace{0.1cm}  \vst(i)$.
     \end{defn}
     
     Předpoklad hry \emph{SSG} je, že se zastaví. Znamená to, že v~grafu $\gst$ existuje z~každého vrcholu cesta do Sink uzlu.
     
     \begin{lemma} \label{strat}
     Nechť $G$ je SSG graf s~$n$ vrcholy a strategiemi $\sigma$, $\tau$ 
hráčů Max, Min, vzájemně. Předpokládejme, že vrcholy grafu $\gst$ (kromě sink uzlů) jsou očíslovány $\{1,\dots,t\}$
 a nechť vektor hodnot $\vost = (\vst(1), \dots, \vst(t))$. Pak existuje $t$ $x$  $t$ matice $Q$ a t--vektor $\overline{b}$ takový, že $\vost$ je unikátním řešením rovnice:
    \begin{equation} \label{rov}
               \vost = Q\vost +  \overline{b}        
 \end{equation}
   $Q$ je matice, u~které $ij$--tý prvek je $q_{ij}$, což je pravděpodobnost dosažení vrcholu $j$ z~vrcholu $i$ v~jednom kroku. $\overline{b}$ je vektor, u~kterého $i$--tý prvek je $q_{i}$, což je pravděpodobnost dosažení 1--sinku v~jednom kroku. 
   \end{lemma}   
 Důkaz je obsažen v~\parencite{con92}.

Pomocí této rovnice můžeme tedy vypočítat hodnoty vrcholů za použití nějakých strategií hráče Max a hráče Min. 
\bigskip

 \textbf{Zobecnění hry o~více Sink vrcholů}. Ve hře je někdy potřeba použít více, než dva Sink vrcholy s~různými hodnotami. Hru \emph{SSG} můžeme zobecnit tak, že může mít více Sink vrcholů. Každý Sink vrchol $s$ má hodnotu $p(s) \in (0,1)$. Když se tedy hra dostane do vrcholu $s$, tak hráč Max zvítězí s~pravděpodobností $p(s)$. \parencite{somla}

\begin{defn} \label{opthod}
   \emph{Optimální vektor hodnot} $\overline{v}_{opt}$ je vektorem \emph{optimálních hodnot vrcholů} grafu G. \emph{Optimální vektor hodnot} je unikátním řešením následujících omezení (předpoklad je, že se hra zastaví):\parencite{somla}
    \begin{align*}
        & v(i) = max(v(j), v(k))  & \text{  Když $i$ je Max vrchol s~následníky $j$ a $k$} \\
        &  v(i) = min(v(j), v(k))  & \text{  Když $i$ je Min vrchol s~následníky $j$ a $k$} \\
        &    v(i) = 1/2(v(j) + v(k))  & \text{  Když $i$ je Ave vrchol s~následníky $j$ a $k$} \\ 
        &  v(i) = p(s)  & \text{Když $i$ je Sink vrchol} \\       
   \end{align*}
  \end{defn} 
  
    \begin{defn} \label{stab}
       Vektor $\overline{v}$ je \emph{stabilní}, pokud pro každý jeho vrchol platí omezení jako definici \ref{opthod}.  \emph{Stabilní} vektor je tedy zároveň \emph{optimální}.      
       \end{defn} 
  
      
     \begin{defn} \label{opt}
       Max strategie $\sigma$ je \emph{optimální s~respektem} k~Min strategii $\tau$, když pro všechny Max vrcholy $i$ s~následníky $j$ platí: $\vst(i) \geq\vst(j)$. Stejným způsobem Min strategie $\tau$ je \emph{optimální s~respektem} k~Max strategii $\sigma$, když pro všechny Min vrcholy $i$ s~následníky $j$ platí: $\vst(i) \leq\vst(j)$.     
       \end{defn} 
       
       \begin{defn} \label{opt2}
       Maximální strategie $\sigma$ je \emph{optimální}, když pro všechny vrcholy $i$ platí, že $min_{\tau} \hspace{0,1cm}  \vst(i) $ je rovno optimální hodnotě $v(i)$ v~grafu G. Podobně Minimální strategie $\tau$ je \emph{optimální}, když pro všechny vrcholy $i$ platí, že $max_{\sigma} \hspace{0,1cm}  \vst(i) $ je rovno optimální hodnotě $v(i)$ v~grafu $G$. 
       \end{defn}        
       
        \begin{defn} \label{switch} Vrchol i je \emph{přepínatelný}, pokud má následníky $j$, $k$ a platí následující: když $i$ je Max vrchol a $v(i) < max (v(j), v(k))$ nebo když $i$ je Min vrchol a $v(i) > min (v(j), v(k))$.  Pokud strategie $\sigma(\tau)$ obsahuje hranu $(i,j)$, řekneme, že strategie $\sigma'(\tau')$ je získána  \emph{přepnutím} vrcholu $i$. $\sigma'(\tau') = \sigma(\tau) - \{(i,j)\} + \{(i,k)\}$.   
       \end{defn} 
      V~této kapitole je čerpáno z~\parencite{somla} a \parencite{con93} .
      
     \section{Převod grafu se dvěma a půl hráče na SSG} \label{prevod}
     Nevýhodou \emph{SSG} je, že vrcholy obsahují přesně dvě výstupní hrany. V~naší práci budeme chtít řešit případy, kdy grafy budou mít i více výstupních hran a nebo pouze jednu. Takovéto grafy tedy musíme převést pomocí následujících úprav na graf \emph{SSG}. 
     
     \bigskip
      \begin{enumerate}
    \item \textbf{Vrchol má pouze jednu výstupní hranu. }
    
    V~takovémto případě jednoduše přídáme ještě jednu výstupní hranu, která povede do stejného uzlu. Úprava je stejná pro Max, Min a Ave  vrcholy. Viz. obrázek \ref{upr1}.
    
     \begin{figure}[H] 
\begin{center}
\includegraphics{obr/upr1.png} 
\caption{Úprava grafu s~jednou výstupní hranou} \label{upr1}
\end{center}
\end{figure}
 \item \textbf{Max nebo Min vrchol má více než dvě výstupní hrany. }
    
    Pokud má Max nebo Min uzel (počáteční) více než dvě hrany (následníky), tak provedeme transformaci podle následujícího postupu. Počátečnímu uzlu přidáme prvního z~následníků a jako dalšího následníka mu přidáme nově vytvořený uzel. Tomuto nově vytvořenému uzlu dáme druhého následníka počátečního uzlu a pokud zbývá ještě více než jeden následník, tak vytvoříme znovu nový uzel atd. Transformaci můžete vidět na obrázku \ref{upr2}, kdy byly nově přidány vrcholy Max 6 a Max 7.
    
   \begin{figure}[H] 
\begin{center}
\includegraphics{obr/upr2.png} 
\caption{Úprava grafu s~více než dvěma výstupními hranami} \label{upr2}
\end{center}
\end{figure}

 \item \textbf{Ave vrchol s~více než dvěma výstupními hranami. }
    
    Poslední úprava a také nejsložitější je, pokud máme pravděpodobnostní uzel s~více než dvěma výstupními hranami. Musíme totiž zajistit, aby pravděpodobnost každého uzlu byla zachována. Když máme čtyři následníky, tak každý z~nich má 25\% (1/4) pravděpodobnost, že hra bude pokračovat na něm.  
    
   Ave uzel $i$ má $x$ následníků. Označme si pravděpodobnosti všech následníků ve formě $1/x$. Pak určíme proměnnou $t$ podle vztahu $2^t < x \leq 2^{t + 1}$. Uzel $i$ je pak nahrazen kompletním binárním stromem Ave uzlů šířky $t+1$ s~kořenem $i$.  Prvních $x$ listů stromu má výstupní hranu do $x$ následníků, zbývající listy stromu mají hranu do kořene stromu (počátečního uzlu) $i$. Prvních $x$ listů může být rovnou nahrazeno následníky, abychom ušetřili prostor. \parencite{con92}
    
    Příklad transformace s~pěti následníky můžete vidět na obrázku \ref{upr3}. 
     \end{enumerate}
    
         \begin{figure}[ht] 
\begin{center}
\includegraphics{obr/upr3.png} 
\caption{Úprava grafu s~více než dvěma výstupními hranami} \label{upr3}
\end{center}
\end{figure}    
   
      
     \chapter{Algoritmy pro řešení SSG} \label{algo}
     
     V~této kapitole uvedeme dva algoritmy pro výpočet optimální strategie v~\emph{SSG}, které později naprogramujeme. Všechny důležité pojmy a definice, které se v~algoritmech  objeví, jsme vysvětlili v~předchozí kapitole. Algoritmy pro výpočet optimální strategie v~\emph{SSG} můžeme rozdělit na čtyři části:
     \begin{itemize}
      \item \textbf{Iterační} -- algoritmy začínají s~určitým iniciálním vektorem a postupně ho v~každé iteraci vylepšují.
      \item \textbf{Se zlepšující se strategií} -- algoritmy začínájí s~iniciálními strategiemi $\sigma$ a $\tau$ pro hráče Max a Min. Poté je v~každé iteraci strategie jednoho z~hráčů zlepšena pomocí \emph{přepnutí vrcholu}.      
       \item \textbf{Matematicko--optimizační} -- problém nalezení optimální strategie je redukován na matematicko--optimizační problém, jako je např. kvadratické programování.
       \item \textbf{Randomizované} -- tyto algoritmy jsou většinou kombinací některého z~předešlých typů. Využívají i náhodu. 
     \end{itemize}     
      
      Abychom vyzkoušeli co nejvíce metod, zvolil jsem dva úplně odlišné algoritmy. První je zástupce iteračních algoritmů -- \emph{Shapleyho}. Jako druhého jsem zvolil \emph{randomizovaný algoritmus Hoffman--karp}, který ale využívá i zlepšující se strategii. Pokryjeme tedy tři části algoritmů. 
      
      \section{Randomizovaný Hoffman--Karp algoritmus}
      
       \emph{Randomizovaný Hoffman--Karp algoritmus} je vylepšením zakládního strategii zlepšujícího algoritmu, který vymysleli pánové Hoffman a Karp. Tento randomizovaný algoritmus je od Anne Condon \parencite{con93}. Condon ukázala, že v~očekávaný počet iterací tohoto algortimu je $2^{n-f(n)} + 2^{o(n)} )$ pro jakoukoli funkci f(n) = o(n), kde $n$ je počet uzlů v~grafu.
     
     
  \begin{algorithm}[ht]
\SetKwInOut{Input}{Vstup}
	\SetKwInOut{Output}{Výstup}
\Input{Graf SSG $G$ }
\Output{Optimální pár strategií $(\sigma,\tau)$ a optimální vektor hodnot $v_{opt}$ }
\Begin{

\BlankLine
\Indp {
    Nechť $\sigma,\tau$ jsou libovolné strategie pro hráče MAX, MIN
   
    \While{ ($\overline{v}_{\sigma,\tau}$ není stabilní) }
	{Vyber náhodně a jednotně $2n$ neprázdných podmožin z~$V_{MAX}$, které jsou $\overline{v}_{\sigma,\tau}$-přepínatelné  \\
	Nechť $\sigma_1,\dots,\sigma_{2n}$ jsou strategie získané \emph{přepnutím} z~těchto podmožin \\
	Nechť optimální strategie hráče MIN vzhledem k~$\sigma_1,\dots,\sigma_{2n}$, jsou strategie $\tau_1,\dots,\tau_{2n}$  \\	
	Nechť $1 \leq k~\leq 2n$ jsou indexy takové, že platí $\sum_{x = 1}^{n} \overline{v}_{\sigma_k,\tau_k}(x) \geq \sum_{x = 1}^{n} \overline{v}_{\sigma_l,\tau_l}(x) $ pro všechny  $1 \leq l \leq 2n$   \\
	Nechť $\sigma \leftarrow \sigma_k$ a $\tau \leftarrow \sigma_k$     	
	
    }   
} 

\Return{strategie $\sigma$,$\tau$ a optimální vektor $\overline{v}_{\sigma,\tau}$ }

}

\caption{Randomizovaný Hoffman-Karp algoritmus \parencite{con93} } \label{hof}
\end{algorithm}

\bigskip
Na začátku algoritmu se vyberou dvě libovolné \emph{maximální} a \emph{minimální} strategie. Libovolnou strategii můžeme vytvořit např. tak, že do ní dáme vždy první hranu vystupující z~vrcholu (každý Max a Min uzel má přesně dvě hrany). Dále probíhá cyklus, dokud nezískáme \emph{stabilní vektor $\overline{v}$} - tedy zároveň i \emph{optimální} vektor. 

V~cyklu nejprve musíme zjistit, které Max uzly jsou \emph{přepínatelné}. Poté z~takovýchto uzlů vytvoříme náhodně $2n$ podmnožin, které nemusí být nutné odlišné. Z~každé podmnožiny pak získáme novou strategii $\sigma'$, která vznikne přepnutím uzlů, které jsou v~podmnožině. Ke každé nově získané strategii $\sigma'$ musíme vypočítat minimální strategii, která je k~ní \emph{s~respektem optimální}. K~výpočtu \emph{optimální minimální strategie s~respektem} k~určité strategii $\sigma$ je zvláštní algoritmus \ref{LP} popsaný níže. Následně ze všech nově získaných strategií $\sigma'$ vyberu tu, která má největší součet \emph{vektoru hodnot} $\vost$. Pokud zjistím, že \emph{vektor hodnot} $\vost$ podle vybraných strategií je stabilní, tak končím výpočet a vracím \emph{optimální strategie}. 

\bigskip

Pro výpočet \emph{optimální minimální strategie s~respektem k~maximální strategii $\sigma$} můžeme použít algoritmus, který počítá \emph{optimální vektor hodnot} v~grafu, který obsahuje pouze Ave a Min uzly. My v~grafu sice máme Max uzly, ale každý má pouze jednu výstupní hranu (podle strategie), takže Max uzly můžeme transformovat na Min uzly (které při výpočtu pouze převezmou hodnotu ze svého následníka). 

  \begin{algorithm}[ht]
\SetKwInOut{Input}{Vstup}
	\SetKwInOut{Output}{Výstup}
\Input{Graf SSG $G$ pouze s~MIN a AVE uzly }
\Output{Optimální vektor hodnot $v_{opt}$ }
\Begin{

\BlankLine

    Maximalizuj  $\sum_{x = 1}^{n} v(x) $ \\
    
    podle omezení: \\
    
    \Indp
         $  v(x) \leq v(y) $       \hspace{14ex}         \textbf{if}  $ x \in V_{MIN}, (x,y) \in E $ \\
         $ v(x) \leq \frac{1}{2} \cdot v(j)  + \frac{1}{2} \cdot v(k) $   \hspace{2ex}    \textbf{if}  $ x \in V_{AVE}, (x,y),(x,z) \in E$      \\
           $  v(x) = p(x) $       \hspace{14ex}        $x \in SINK $ \\
           $  v(x) \geq 0 $       \hspace{17ex}        $x \in V~$ \\      
       
   \Indm Vyřeš omezení pomocí lineárního programovaní
    
\Return{optimální vektor $\overline{v}_{\sigma,\tau}$ }

}

\caption{LP Algoritmus pro SSG pouze s~MIN a AVE uzly \parencite{con92} } \label{LP}

\end{algorithm}

Algoritmus počítá optimalizační problém lineárního programování s~omezeními tak, že \emph{hodnoty vrcholů} maximalizuje.



\section{Shapleyho algoritmus}

\emph{Shapleyho} algoritmus má mnohem jednodušší princip než \emph{randomizovaný Hoffman--Karp} algoritmus.  Algoritmus patří mezi iterační algoritmy. Vymyslel jej matematik Loyd Shapley. Anne Condon \parencite{con93} ukázala, že v~nejhorším případě algoritmus proběhne na $\Omega(2^n)$ iterací, kde $n$ je počet uzlů v~grafu. Algoritmus má tedy také exponenciální složitost.
     
  \begin{algorithm}[ht]
\SetKwInOut{Input}{Vstup}
	\SetKwInOut{Output}{Výstup}
\Input{Graf SSG $G$ }
\Output{optimální vektor hodnot $v_{opt}$ }
\Begin{

\BlankLine

    Inicializujeme následovně vektor hodnot $\overline{v}$: \\    
  
    Pro každé $x \in V$ platí:     
   \begin{equation*}
      v(x) = \begin{cases}
         1& \text{\textbf{if }} x \in V_{MAX} \\
         0 & \text{\textbf{if }} x \in V_{MIN} \\
         \frac{1}{2} \cdot v(y)  + \frac{1}{2} \cdot v(z) & \text{  \textbf{if}}  x \in V_{AVE}, (x,y),(x,z) \in E\\
         p(x) & \text{\textbf{if }} x \in SINK \\
      \end{cases}
    \end{equation*}       
    \While{ ($\overline{v}_{\sigma,\tau}$ není stabilní) }
	{Nechť $v'$ je definováno následovně:
	 \begin{equation*}
      v'(x) = \begin{cases}
         \text{max}\{v(y), v(z)\} & \text{\textbf{if }} x \in V_{MAX}, (x,y),(x,z) \in E\\
         \text{min}\{v(y), v(z)\} & \text{\textbf{if }} x \in V_{MIN}, (x,y),(x,z) \in E \\
         \frac{1}{2} \cdot v(y)  + \frac{1}{2} \cdot v(z) & \text{  \textbf{if}}  x \in V_{AVE}, (x,y),(x,z) \in E\\
         v(x) & \text{\textbf{if }} x \in SINK \\
      \end{cases}
    \end{equation*}
	
	Nastav $v \leftarrow v'$ 		
	
    }   
 

\Return{optimální vektor $\overline{v}$ }

}

\caption{Shapleyho algoritmus \parencite{valkanova} } \label{shap}

\end{algorithm}

 Algoritmus začíná tak, že se nainiciliazuje \emph{vektor hodnot} podle daných pravidel (viz alg. \ref{shap}). Následně probíhá cyklus, dokud \emph{vektor hodnot $\overline{v}$} není \emph{stabilní}. V~každé iteraci se pro každý vrchol spočítá nová hodnota $v$. \emph{Hodnota} Max uzlu je maximum z~\emph{hodnot} svých následníků. Podobně \emph{hodnota} Min uzlu je minimum z~\emph{hodnot} svých následníků. \emph{Hodnota} Ave uzlu je polovina ze součtu hodnot svých synů. \emph{Hodnota} Sink uzlů se nemění. 
 
 Nevýhodou tohoto algoritmu je, že nám zároveň nespočítá i  \emph{optimální strategie}. Po vypočítání \emph{optimálního vektoru} je tedy musíme ještě dopočítat. Můžeme to udělat tím způsobem, že se u~každého Max (Min) vrcholu podíváme na optimální hodnoty svých následníků. Optimální strategie pak povede do toho následníka, který bude mít stejnou hodnotu, jako náš Max (Min).
     
 \chapter{Framework pro řešení her se dvěma a půl hráče}
 Úkolem naší práce je vytvořit framework pro řešení  \emph{her se dvěma a půl hráče}. Práce proběhne klasickým způsobem SW vývoje. Nejprve zanalyzujeme požadavky, podle kterých vytvoříme návrh a nakonec knihovnu implementujeme.
 
 \section{Požadavky}
 Jako jsme popsali v~kapitole \ref{hry}, hra se  \emph{dvěma a půl hráče} je graf, který obsahuje čtyři druhy uzlů -- Max, Min,Ave a koncové Sink. V~tomto grafu budeme chtít nalézt \emph{optimální strategie} pro oba hráče (jeden je Max a druhý Min). Zároveň budeme chtít vypočítat optimální hodnoty všech uzlů v~grafu. 
 
 Potřebujeme tedy vytvořit framework (knihovnu), kterému když zadáme graf \emph{hry se dvěma a půl hráče}, tak nám vypočte \emph{optimální strategii} i \emph{optimální hodnoty} všech vrcholů. K~výpočtu strategie by měly sloužit alespoň dva algoritmy, abychom si mohli jednoduše ověřit výsledky (od obou algoritmů musí být stejné). Knihovna by měla být nezávislá na platformě, aby se dala jednoduše použít v~jakémkoli SW projektu. 
 
 
 \section{Návrh}
 Knihovna se bude skládat z~jedné hlavní třídy, kterou nazveme \texttt{SSG}. Pro použítí knihovny tedy bude stačit získat jediný objekt této třídy (třídu můžeme tedy implementovat jako návrhový vzor \emph{Jedináček}). Třída \texttt{SSG} musí nějakým způsobem převzít graf, poté jej převést na {SSG} graf, následně výpočítat výsledek a vrátit jak výslednou \emph{optimální strategii}, tak i \emph{hodnoty} všech vrcholů. Těchto kroků je hodně a v~každém může nastat nějaká chyba. Např. při převodu na \emph{SSG} graf bychom mohli zjistit, že některý z~Max uzlů nemá následníka (každý uzel musí mít cestu v~grafu do nějakého Sink uzlu). Z~tohoto důvodu tedy výpočet nebude probíhat srkze jedinou metodu, ale bude rozdělen na následujicí čtyři metody, které můžeme nazvat rozhraním:
 \begin{itemize}
  \item \texttt{setGraph()} -- V~parametrech této metody bude graf, který se uvnitř metody transformuje na \emph{SSG} graf. Vytvoří se zde datové struktury, se kterými bude v~dalších metodách probíhat výpočet.
   \item \texttt{computeOptStrategy()} -- Pomocí této metody se zavolá výpočet optimálních strategií na graf zadaný předchozí metodou. Který algoritmus bude vybrán, je zvoleno v~parametru metody.
    \item \texttt{getOptEdges()}  -- Vrátí nám \emph{optimální strategie}. Jinak řečeno, ze kterého vrcholu do kterého povede hrana. 
     \item \texttt{getOptValues()} -- Vrátí nám \emph{optimální hodnoty} všech vrcholů.
 \end{itemize} 
 
 Zmíněné metody musí být striktně volány v~pořadí, jako jsou zde uvedené (nelze volat metodu na vrácení hodnot, když předtím neproběhl výpočet).
 
 \begin{figure}[H] 
\begin{center}
\includegraphics{obr/domena.png} 
\caption{Doménový model knihovny \texttt{SSG}} \label{domena}
\end{center}
\end{figure}  
 
 Na obrázku \ref{domena} můžeme vidět doménový diagram knihovny \texttt{SSG}. Obsahuje pouze nejdůležitější metody a atributy. Třída \texttt{TNodeSSG} znázorňuje uzel v~\emph{SSG} grafu a třída \texttt{TEdgeSSG} znázorňuje hranu v~grafu. Metoda \texttt{setGraph()} byla rozdělena na dvě možnosti. Zaprvé můžeme předat graf pomocí přechodové matice (\texttt{setGraphByMatrix()}). Druhou možností je, že ho zadáme pomocí hran (\texttt{setGraphByEdges()}). 
 
 
 \section{Implementace}
 Framework je naimplementován v~čistém jazyce \emph{C++}, aby šel zapojit do SW projektů na různých platformách a v~různých vývojových přostředích, jako je např.  \texttt{Microsoft Visual Studio} nebo \texttt{QT}. 
 
  \subsection{Použité knihovny}
  \subsubsection{Lp Solve}
 K~implementaci \emph{Hoffman--Karp} algoritmu je zapotřebí lineárního programování k~vyřešení optimizačního problému (alg. \ref{LP}). Základní frameworky jazyka \emph{C++} žádný řešič těchto úloh neobsahují, proto jsem hledal jinou volně šiřitelnou knihovnu, kterou bych mohl použít. Vše splnila knihovna \texttt{Lp Solve}. Obsahuje jak grafické prostředí pro řešení linerních omezení, tak i \emph{C++} knihovnu, kterou mohu použít ve zdrojovém kódu. 
 
 \subsubsection{Eigen}
 Eigen je volně šiřitelná knihovna jazyka \texttt{C++} pro lineární algebru. Tedy pro matice, vektory atd. V~našem programu potřebujeme násobit matice pro výpočet vektoru $\overline{v}$ v~algoritmu \emph{Hoffman--Karp}, proto zde využívám tuto knihovnu. 
 
 \subsection{Vložení grafu a jeho transformace na SSG}
 Předpoklad pro vložení grafu je, že máme uzly označeny indexy od 0 do n-1, kde n je celkový počet uzlů v~grafu. 
 
 Jak jsem již zmínil, graf lze předat do knihovny \texttt{SSG} dvojím způsobem. První je přes přechodovou matici s~následujícími parametry: \texttt{setGraphByMatrix(BMatrix matrix, vector<int> max, vector<int> min, vector<int> ave, TSinks sinks)}. Int je typ Integer. \texttt{Vector} je speciální kontejner s~předem neznámou velikostí, který používá paměť z~haldy. Nazývejme ho jednoduše pole. \texttt{BMatrix} je uživatelsky definovaný typ pro \uv{Vector Vectorů} typu \texttt{boolean} -- je to tedy matice. Pokud je v~grafu hrana z~i--tého do j--tého uzlu, tak matice na pozici [i,j] bude \texttt{True}. Další parametry -- pole integerů \texttt{max}, \texttt{min} a \texttt{ave} nám říkají pomocí indexů, které uzly v~grafu jsou typu Max, Min a Ave. Pokud tedy např. pole \texttt{max} bude obsahovat čísla 1,4,5, tak víme, že uzly s~indexy 1,4,5 jsou typu Max. Posledním parametrem je pole struktur typu \texttt{TSink}. Tato struktura obsahuje dvojci atributů -- id a hodnotu. Když máme třeba strukturu s~id 2 a hodnotou 0.5 tak to znamená, že v~grafu je uzel s~indexem 2 typu Sink a má hodnotu 0.5. Všimněte si, že v~parametrech není zadáno, kolik je uzlů v~grafu. Tento údaj totiž můžeme zjistit jednoduše podle velikosti matice. Musí platit, že počet prvků v~polích \texttt{max}, \texttt{min}, \texttt{ave} a \texttt{sinks} musí být roven počtu řádků v~matici.

Protože zadávání grafu přes matici je někdy zbytečně paměťově náročné -- většinou to je tzv. řídká matice, tak vznikla ještě jedna možnost, kterou je pole hran: \texttt{setGraphByEdges(int numNodes, vector <StructEdge> edges, vector <int> max, vector <int> min, vector <int> ave, TSinks sinks)}. První parametr \texttt{numNodes} udává počet uzlů v~grafu. Druhý parametr \texttt{edges} je pole struktur. Struktura představuje hranu. Obsahuje dvě čísla, kdy první znamená z~kterého indexu hrana pochází a druhé do kterého směřuje. Např. hrana s~čísly 1,5 udává, že v~grafu je hrana z~vrcholu s~indexem 1 do vrcholu s~indexem 5. Pole \texttt{max}, \texttt{min}, \texttt{ave} a \texttt{sinks} se neliší od předchozí metody.

Uvnitř dvou výše zmíněných metod probíhá převod na nové datové struktury, ze kterých se později bude počítat optimální strategie.  Při tomto převodu se graf rovnou převádí na \emph{SSG} graf (ve kterém má každý uzel přesně dvě výstupní hrany) pomocí transfomací popsaných v~kapitole \ref{prevod}.
 
 \subsection{Výpočet optimální strategie}
 Výpočet optimální strategie může být proveden dvěma způsoby -- \emph{randomizovaným Hoffman--Karp} algoritmem a \emph{Shapleyho} algoritmem. 
 
  \emph{Randomizovaným Hoffman--Karp} algoritmus je sestrojen v~metodě \texttt{getOptHoffmanKarp()} podle alg. popsaném v~kapitole \ref{hof}. Jako náhodnou strategii zvolí vždy první hranu vycházející z~uzlu. Když máme strategie Min a Max, tak musíme vypočítat vektor hodnot. Tento vektor vypočítáme podle rovnice \ref{rov}. V~této rovnici se používá maticové násobení, proto zde využijeme již zmíněnou knihovnu pro počítání matic \texttt{Eigen}. Metoda \texttt{isStableHoffman} zjístí, zda je vypočtený vektor hodnot optimální/stabilní podle definice \ref{opthod}. Zároveň se v~této metodě počítají \emph{přepínatelné} hrany. Vybrání náhodné množiny obsahující tyto přepínatelné hrany probíhá tak, že se všechny prochází a každá má 50\% pravděpodobnost, že bude v~množině. Nalezení optimální minimální stragie k~dané maximální strategii probíhá v~metodě \texttt{findOptMinStrategyToMax}. K~výpočtu je použito lineární programování podle omezení popsaných v~alg. \ref{LP}. Lineární programování se provádí skrze knihovnu Lp Solve.  %%%%%%%%%%%%%%
 
 \emph{Shapleyho} algoritmus je sestrojen v~metodě \texttt{getOptShapley()}. Výpočet optimálních hodnot probíhá přesně podle předpisového algoritmu \ref{shap}. Pouze na začátku při inicializaci nejsou známy hodnoty Ave uzlů, proto jim dáme hodnotu 0.5 a pak je znovu inicializujeme již podle předpisového vztahu. Metoda \texttt{isStableShapley()} zjístí, zda je vypočtený vektor hodnot optimální/stabilní. Tuto metodu nemůžeme použít stejnou jako u~\emph{Hoffman--Karp} algoritmu, protože tam jsme zároveň počítali \emph{přepínatelné} hrany. 
 
 
  \subsection{Vrácení výsledků}
  
  Pokud jsme zavolali metodu pro výpočet optimální strategie a proběhla úspěšně, tak nyní můžeme požádat o~výsledky. Pro vrácení optimální strategie slouží metoda \texttt{getOptEdges}. Vracející hodnota je pole čísel. Index v~tomto poli udává, o~který vrchol se jedná. Číslo v~poli je vrchol, do kterého optimální hrana jde. Pokud je číslo -1, tak optimální hrana nejde nikam (jedná se o~Sink nebo Ave uzel). Lépe to vysvětlíme na příkladu: je nám vráceno pole obsahující čísla 1,-1,0. Znamená to tedy, že uzel s~indexem 0 má optimální hranu do uzlu s~indexem 1. Uzel s~indexem 1 nemá žádnou optimální hranu a uzel s~indexem 2 má optimální hranu do vrcholu s~indexem 0.
  
Stejným způsobem probíhá vrácení optimálních hodnot. Zavoláním metody \texttt{getOptValues} se vrátí pole desetinných čísel. Když nám např. dojde pole 0.5,0.1,1, tak víme, že vrchol s~indexem 0 má optimální hodnotu 0.5, uzel s~indexem optimální hodnotu 0.1 a nakonec vrchol s~indexem 2 má optimální hodnotu 1. 

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \chapter{Vývoj prototypu}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 V~této kapitole se budeme zabývat vývojem prototypu, který bude využívat knihovnu \texttt{SSG} popsanou v~předchozí kapitole. Prototyp bude program, který bude obsahovat dva druhy funkčnosti. První z~nich bude v~grafickém prostředí řešit graf \emph{hry se dvěma a půl hráče}. Pomocí této funkčnosti pak budeme moci lépe otestovat knihovnu \texttt{SSG}. Druhou funkčností bude výpočet pravděpodobnosti výhry a určení strategie (kterou figurkou táhnout) u~hry \emph{Člověče, nezlob se}. Program nazveme \texttt{GW2.5P} \footnote{GW2.5P je zkratka pro Game with two and half players}. Vývoj programu bude rozdělen na čtyři části -- shrnutí požadavků, návrh aplikace, implementace a testování.
 
 \section{Požadavky}
 
 Chceme vytvořit aplikaci s~grafickým uživatelský rozhraním. V~programu půjde řešit \emph{graf se dvěma a půl hráče} a také hra \emph{Člověče, nezlob se}. Analýzu požadavků tedy rozdělíme na tyto dvě funkčnosti. 
 
 \subsection{Řešič grafu se dvěma a půl hráči}
 Uživatel si bude moci vytvořit \emph{graf se dvěma a půl hráče}. K~dispozici budou čtyři druhy uzlů -- Ave, Max, Min a Sink uzly. Tyto uzly by měly být od sebe barevně rozlišené. Při vytváčení Sink uzlu se musí zadat i jeho hodnota. Všechny uzly pak můžeme propojovat hranami. 
 U~hrany musí být patrné, který uzel je počáteční a který koncový. 
 
 Až si uživatel navolí graf, tak klikne na tlačítko k~vypočtení strategie a ta se vypočte. Lze volit mezi dvěma možnými algoritmy výpočtu. V~grafu by se pak měly zvýraznit ty hrany, které jsou v~optimální strategii. Zároveň u~každého uzlu musí být napsána vypočtená optimální hodnota. Diagram případů užití, který shrnuje všechny požadavky, můžete vidět na obrázku \ref{pripgraf}.
 
 \begin{figure}[H] 
\begin{center}
\includegraphics{obr/pripgraf.png} 
\caption{Diagram případů užití pro řešič grafu se dvěma a půl hráče} \label{pripgraf}
\end{center}
\end{figure} 

\subsection{Hra Člověče, nezlob se}  

Program bude umět vypočítat pravděpodobnost výhry ve hře  \emph{Člověče, nezlob se}. Zároveň nám oznámí, kterou figurkou bude nejvýhodnější táhnout. Pravidla hry jsou popsána v~následující podkapitole. 

Uživatel si nejprve navolí hrací pole. Může zvolit počet hráčů, počet figurek a počet hracích políček. Hrací pole se mu následně objeví v~grafickém prostředí. S~figurkami se bude moci libovolně hýbat (např. jednu figurku necháme na startu a dvě dáme do cílového domečku).

Po nastavení figurek a určení čísla na kostce, se může zahájit výpočet. Po vypočtení by uživatel měl vědět pravděpodobnosti výher, kdyby táhl jednotlivými figurkami. Figurku s~největší pravděpobností výhry je potřeba zvýraznit. Protože výpočet by mohl trvat delší dobu, je potřeba, aby program \uv{nezamrzl}, ale dával uživateli informaci, v~jakém je výpočet stavu.
 Diagram případů užítí ukazuje obrázek \ref{pripludo}.



 \begin{figure}[H] 
\begin{center}
\includegraphics{obr/{pripludo}.png} 
\caption{Diagram případů užití pro hru Člověče, nezlob se} \label{pripludo}
\end{center}
\end{figure} 

\subsubsection{Pravidla} 
Hra \emph{Člověče, nezlob se} je známá po celém světě. (v~angl. jazyce je pro ni název Ludo). Princip hry je všude stejný, ale pravidla se různě poněkud liší. Řekneme si tedy pravidla, podle kterých ji budeme hrát my -- aby jsme hru mohli převést na adekvátní \emph{graf se dvěma a půl hráče}. 

Hru hrají 2 -- 4 hráči. Každý z~nich má 2 -- 4 figurky. Figurky jsou na začátku hry umístěny ve startovních domečcích. Vyhraje ten hráč, který dostane jako první všechny své figurky do cílového domečku. Hráč, který je na tahu, hodí hrací kostkou a podle čísla, které mu padne, může popojet s~libovolnou nasazenou figurkou po hracím pláně. Pokud padne šestka, tak může prvně popojet a hází ještě jednou. Aby hráč dostal figurku ze startovního domečku, tak mu musí padnout šestka. Když hráč popojede na políčko, na kterém je figurka soupeře, tak ji vyhodí  (je vrácena zpět do jeho startovního domečku). Není dovoleno mít dvě své figurky na stejném políčku. V~cílovém domečku může figurka ještě popojíždět, dokud je před ní místo. Pokud hráč, který je na tahu, nemůže popojet žádnou figurkou, tak hraje soupeř. 
 
\section{Návrh} 
Program navrhneme tak, aby v~něm šel řešit \texttt{graf se dvěma a půl hráče} a hra \emph{Člověče, nezlob se}. Obě tyto funkčnosti budou obsahovat bílou scénu, na které bude grafika. Mezi těmito dvěma scénami a tedy hrami se bude moci přepínat pomocí záložek. Třída \texttt{MainWindow} bude představovat hlavní okno celé aplikace a zahrnovat všechny uživatelem vygenerované události (např. kliknutí na tlačítko). Zároveň se z~této třídy budou volat všechny důležité metody. Doménový model s~návrhem tříd můžete vidět na obrázku \ref{domenaProgram}. Všechny ostatní třídy z~modelu zmíníme v~další části textu.

\begin{figure}[ht] 
\begin{center}
\includegraphics{obr/domenaProgram.png} 
\caption{Doménový model pro program \texttt{GW2.5P}   } \label{domenaProgram}
\end{center}
\end{figure} 

\subsection{Návrh řešiče her se dvěma a půl hráče}
Základem bude bílá scéna, na které se bude kreslit graf. Nalevo od scény bude šest přepínacích tlačítek, které nám oznamují, jaké úkony s~grafem  můžeme právě dělat. Když bude aktivní tlačítko \texttt{Max}, tak se do scény po kliknutí vytvoří Max uzel. Stejným způsobem budou fungovat tlačítka \texttt{Min} a \texttt{Ave}. Aktivním tlačítkem \texttt{Sink} budeme kreslit Sink uzly. Ještě před jejich vytvořením však uživateli vyskočí okénko, kde zadá jeho hodnotu. Teprve poté se vytvoří uzel. Pokud bude zaškrtlé tlačítko \texttt{Edge}, tak můžeme kreslit hrany mezi uzly. Poslední bude tlačítko \texttt{Select}. S~tímto tlačítkem můžeme označovat, posunovat a mazat uzly v~našem grafu. 

Na pravé straně od scény bude přepínač, kterým si zvolíme algoritmus pro výpočet optimální strategie. Pod ním pak bude tlačítko, kterým se zmíněná optimální strategie spočítá.

Scénu pro graf implementuje třída \texttt{SceneGraph}. Uzly v~grafu představuje třída \texttt{GNode} a hrany třída \texttt{GEdge}.

\subsection{Návrh hry Člověče, nezlob se} 
Základem hry bude opět bílá scéna. Pomocí měničů si navolíme počet hráčů, počet figurek a počet prostředních políček. Na scéně se po kliknutí  na tlačítko vytvoří herní plán s~figurkami. Figurky můžeme tažením posouvat na libovolná políčka na herním plánu. Hra bude obsahovat měnící box pro číslo udávající, kolik padlo na kostce a také box pro hráče na tahu. Pro hráče na tahu se bude zároveň počítat vítězná strategie. Kliknutím na tlačítko se začne počítat optimální strategie a vítězná pravděpodobnost. 

Hru Člověče, nezlob se implementuje třída \texttt{Ludo}. V~této třídě probíhá transformace hry na graf a následné zavolání metody knihovny \texttt{SSG} pro výpočet optimální strategie. Grafickou scénu hry představuje třída \texttt{SceneLudo}. Na scéně se vytváří políčka, které jsou objekty třídy \texttt{Field}, a také figurky, které jsou objekty třídy \texttt{Figurine}.

\subsection{Převod hry Člověče, nezlob se na graf} \label{prevodd}

V~této podkapitole popíšeme jednu z~nejdůležitějších částí programu, kterou je transformace hry \emph{Člověče, nezlob se} na \emph{graf se dvěma a půl hráče}. 

Uzly v~grafu budou představovat stav, ve kterém se právě hra nachází. I~když hru mohou hrát až čtyři hráči, tak nám stačí dva hráči v~grafu -- jeden maximální a jeden minimální. Hráč, za kterého hrajeme my, je maximální a ostatní hráči, obrazně řečeno, hrají  za minimálního. Půl hráč pak představuje hození kostky -- kdy nám padne náhodné číslo od 1 do 6. Stav hry je zaznamenán pomocí rozložení figurek. V~každém uzlu grafu bude uloženo umístění všech figurek ve hře pomocí pole čísel. Např. pokud máme dva hráče, kteří mají dvě figurky, tak v~uzlu bude  čtveřice čísel -- první číslo udává polohu figurky 1, druhé udává polohu figurky 2 atd. Poloha figurky je určena pomocí ID políčka, na kterém se nachází. Na startu jsou políčka s~ID $0$. Prostřední políčká mají ID od $1$ do $N$, kde $N$ je počet prostředních políček. Cílová políčka pak mají ID od $N$ do ($N + kolik je figurek$). 

Z~každého MAX nebo MIN uzlu bude vycházek tolik hran, kolik má hráč figurek. Tato hrana bude představovat figurku, se kterou se táhne. Uzly Max a Min obsahují také číslo sdělující, kolik padlo na kostce. Na začátku každého grafu je tedy počáteční uzel Max. Tento uzel má v~sobě čísla udávající rozložení figurek a také číslo, které padlo na kostce. Z~něho vystupuje tolik hran, kolik má hráč figurek. Hrany vedou do Ave (pravděpodobnostního) uzlu. Tento uzel představuje hození kostky. Má tedy šest možných vystupujících hran, z~nichž každá představuje padlé číslo na kostce. Ave uzel obsahuje také rozložení figurek a informaci o~tom, který hráč je na tahu. Nyní hraje hráč Min (pokud tedy v~předchozím pokusu nepadla šestka), takže Ave uzel má šest následníků uzlů Min. Z~každého Min uzlu poté vedou opět dva Ave uzly, jakožto možné dvě figurky. Celý proces se takto opakuje, dokud nějaký hráč nemá všechny figurky v~domečku. V~tomto případě je poslední uzel Sink. Pokud má figurky v~cíli hráč Max, tak se jedná o~1--Sink (výhra), pokud má v~cíli hráč Min, tak se jedná o~0--Sink (prohra). Graf končí vždy některým ze Sink uzlů.

Při hře je možné se dostat do stavu, ve kterém uz jsme někdy byli. Např. když máme všechny figurky na startu a několik kol se nám nepodaří  hodit šestku, tak se stav hry, ve kterém se nachází hráč Max, nemění. Z~tohoto důvodu, když budeme vytvářet Ave uzel, tak se vždy podíváme jestli už neexistuje totožný Ave uzel (se stejným rozložením figurek a hráčem na tahu). V~případě že ano, tak nasměrujeme hranu do tohoto Ave uzlu a nevytváříme nový.

Na obrázku \ref{prevod} můžeme vidět začátek grafu, na který se transformovala hra se dvěma hráči se dvěma figurkami a 16 prostředními políčky. První hráč má figurky na pozicích 1 a 2, druhý hráč má figurky na pozicích 3 a 4 (na obrázku je rozložení figurek v~závorce). Prvnímu hráči padlo číslo 2. Figurkou 1 se tedy dostaneme do stavu (3,2,3,4) -- popojeli jsme figurkou o~dvě políčka.  Na stejném obrázku v~pravém dolním rohu je ukázka závěru hry, kdy hráč hodí číslo 1 a figurkou 1 se dostane do domečku. Protože už druhou figurku v~domečku má, tak vyhrává a je zde 1--Sink uzel.

\begin{figure}[H] 
\begin{center}
\includegraphics{obr/{prevod}.png} 
\caption{Ukázka transformace hry Člověče, nezlob se na graf} \label{prevod}
\end{center}
\end{figure} 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Implementace}
 V~této části popíšeme programovou realizaci aplikace a použité nástroje. Při implementaci
aplikace se vycházelo z~návrhu aplikace.
 \subsection{Vývojové prostředí \texttt{QT} }
 Jako vývojové prostředí pro naší aplikaci jsem zvolil knihovnu \texttt{QT}\footnote{Viz \texttt{https://www.qt.io/}}  vyvíjenou firmou Digia. \texttt{QT} je multiplatformní nástroj pro vyvíjení softwarových projektů s~grafickým uživatelským rozhraním. 
Aplikace jsou vyvíjeny s~nativním vzhledem, takže se vždy přizpůsobí operačnímu systému. \texttt{QT}
obsahuje knihovny pro více jazyků (\texttt{C++}, \texttt{Python}, \texttt{Ruby}, \texttt{Pascal}). Já jsem si vybral objektově
orientovaný jazyk C++. Tuto vývojovou knihovnu jsem zvolil z~důvodu velmi přívětivého prostředí,
zejména pak kvůli velké a přehledné dokumentaci. Knihovna \texttt{QT} obsahuje důležitou funkčnost,
kterou jsou signály a sloty. Tyto zvláštní metody slouží ke komunikaci mezi objekty. Používají se
například při kliknutí na tlačítko – vyšle se signál. Slot je pak metoda, která se provede v~reakci
na signál – obsluha po stisknutí tlačítka.

Knihovnu jsem použil v~nejnovější verzi 5.6.0. Provedl jsem také statickou kompilaci zdrojových kódů \texttt{QT}, takže výsledkem implementace je pouze jediný spustilený soubor, který má okolo 20 MB. Kdybych nepoužil statickou kompilaci, tak by ke spuštění programu byly vyžadovány knihovny  \texttt{QT}, a program by tak zabral o~hodně více místa na disku. 

Nástroj je dostupný pod \texttt{LGPL} veřejnou licencí. 

 \subsection{Struktura aplikace}
 
 Hlavní třídou je \texttt{MainWindow}. V~této třídě se obsluhují kliknutí na veškerá tlačítka v~aplikaci. 
 
 Scénu \texttt{řešiče grafu se dvěma a půl hráče} implementuje třída \texttt{SceneGraph}. Tato třída dědí z~\texttt{QGraphicsScene}, což je speciální třída knihovny  \texttt{QT} pro kreslení různých objektů. Do scény se přídávají uzly -- objekty třídy \texttt{GNode}, které dědí z~\texttt{QGraphicsEllipseItem}, která představuje grafickou elipsu (kruh). Uzly v~uvnitř sebe obsahují seznam všech vstupujících a vycházejících hran. Hrana mezi uzly je objekt třídy  \texttt{GEdge}, jenž dědí z~\texttt{QGraphicsLineItem}, která implementuje grafickou přímku ve scéně. Všechny uzly se přidávají do pole. Když se klikne na tlačítko k~vypočtení strategie, tak se přes všechny uzly vytvoří matice přechodů a ta se pošle třídě \texttt{SSG}, která výsledek vypočte. 
 
 Pro hru \emph{Člověče, nezlob se} je vytvořena speciální třída \texttt{Ludo}. V~této třídě probíhají veškeré úkony týkající se hry, zejména pak převod hry na \emph{graf se dvěma a půl hráče} popsaný v~kapitole \ref{prevodd}.  Scénu představuje třída \texttt{SceneLudo} dědící z~třídy \texttt{QGraphicsScene}. Na scénu se přidávají políčka, což jsou objekty třídy \texttt{TFields}, které jakožto kruhy dědí opět z~\texttt{QGraphicsEllipseItem}. Kromě políček jsou na scéně ještě figurky -- objekty třídy  \texttt{TFigurines}, které dědí z~třídy \texttt{QGraphicsPixmapItem}. \texttt{QGraphicsPixmapItem} představuje libovolný obrázek, který můžeme vložit do scény.
 
 Když probíhá výpočet strategie u~hry \emph{Člověče, nezlob se}, tak se zobrazuje okno informující o~stavu výpočtu. Výpočet proto musí probíhat ve speciálním vlákně. Knihovna \texttt{QT} má pro vlákna speciální třídu \texttt{QThreads}. Vlákno pak může pomocí zpráv informovat okno o~stavu -- např. že se dokončil převod na graf.
 
 \bigskip
 Všechny třídy a metody programu můžete shlédnout v~dokumentaci, která je v~příloze.
 
 \subsection{Testování}
 
 Testování probíhalo již při implementaci, kdy byla každá nově přidaná část řádně otestována. V~\texttt{řešiči grafu se dvěma a půl hráče} jsem testoval desítky grafů. Od obou algoritmů byly vždy stejné výsledky, což značí, že je výsledek správný. 
 
 Při testování hry \emph{Člověče, nezlob se} jsem zjistil, že transformace hry na graf trvá příliš dlouho. Při vytváření grafu se totiž každý nově přidáváný Ave uzel porovnává se všemi již vytvořenými, jestli už některý z~nich nemá stejnou polohu figurek. Časová náročnost tedy exponenciálně stoupá. Z~tohoto důvodu jsem vytvořil hashovací tabulku pro první tři figurky. Když např. budeme mít polohu figurek (1, 2, 3, 4), tak uzel budeme hledat v~hashovací tabulce na pozici [1][2][3]. Hashovací tabulka pouze pro tři figurky je z~důvodu, že při spuštění programu není jisté, kolik figurek přesně bude (může jich být až 16 -- při 4 hráčích a 4 figurkách). Implementace $k$ rozměrného pole o~$n$ prvcích by totiž byla velice složitá, ne--li nemožná. Po této úpravě je převod hry na graf několikanásobně rychlejší. 

 
 
 \chapter{Experimentování}
 Program \texttt{GW2.5P}, který jsme vytvořili, je potřeba otestovat a spustit na různých datech. V~této kapitole uvedeme, jak program ovládat a také několik příkladů použítí jak hry \emph{Člověče, nezlob se}, tak \texttt{řešiče grafu se dvěma a půl hráče}. 
 
 \section{Graf se dvěma a půl hráče}
 \subsection{Ovládání}
 Po spuštění programu můžeme na horní liště vybírat ze dvou módů:
 
 \begin {itemize}
 \item mód pro řešení grafu hry se dvěma a půl hráče --  lišta s~nápisem \texttt{Graph solver of game with two players}.
  \item mód \emph{Člověče, nezlob se} --  lišta s~nápisem \texttt{Ludo}. 
 \end{itemize}
 
 Pro vytvoření grafu použijeme šest tlačítek na levé straně. Mezi tlačítky se lze přepínat po kliknutí na libovolné z~nich. To tlačítko, které je aktivní, nám říká ve kterém stavu se nacházíme. Graf se kreslí do bílého prostoru -- scény. 
 
 \bigskip
 
 Tlačítka, a tedy i stavy, jsou následující:
 \begin {itemize}
  \item[>>] s~obrázkem šipky: V~tomto stavu můžeme hýbat s~uzly grafu a také kliknutím označit libovolný uzel či hranu. Při prodržení tlačítka \texttt{CTRL} můžeme označit více částí grafu najednou. Označit je můžeme i po tažení myši, kdy se nám tvoří výběrový obdélník. Pokud máme označený uzel nebo hranu, můžeme je smazat kliknutím klávesy \texttt{DELETE}. Samozřejmě se smažou i hrany vedoucí z~těchto a do těchto uzlů. 
   \item[>>] s~popisem \texttt{MAX}: Po kliknutí do scény se vytvoří \emph{MAX} uzel, který má zelenou barvu.
   \item[>>] s~popisem \texttt{MIN}: Po kliknutí do scény se vytvoří \emph{MIN} uzel, který má bílou barvu.
   \item[>>] s~popisem \texttt{AVE}: Po kliknutí do scény se vytvoří \emph{AVE} uzel, který má červenou barvu.
   \item[>>] s~popisem \texttt{SINK}: Po kliknutí do scény se vytvoří \emph{SINK} uzel, který má žlutou barvu. Zde jsme také vyzvání pro zadání hodnoty uzlu. \emph{SINK} uzel může nabývat hodnot od 0 do 1 (1 = výhra, 0 = prohra). 
   \item[>>] s~popisem \texttt{EDGE}: V~tomto stavu se kreslí hrana z~jednoho uzlu do druhého. Hranu kreslíme z~počátečního uzlu táhnutím s~přidrženým levým tlačítkem myši do cílového uzlu. 
   
  \end{itemize}
  
   \bigskip
   
   Pokud máme vytvořený graf, tak můžeme vypočítat strategii a hodnoty uzlů. To provedeme kliknutím na tlačítko \texttt{COUNT Strategy}. Ještě předtím si ale můžeme zvolit jednoduchým přepínačem jeden ze dvou algoritmů, pomocí něhož bude probíhat výpočet.
   
   Výpočtený výsledek se zobrazí následovně. Hodnota uzlu se zobrazí uvnitř, stejně jako tomu je u~SINK uzlu. Všechny hrany, které jsou obsaženy v~optimální strategii, se zvýrazní červenou barvou. Čas, jak dlouho trval výpočet, je obsažen v~kolonce s~popisem \texttt{Time}. 
   Vypočtené hodnoty a strategie lze smazat pomocí tlačítka \texttt{Clean Strategy}. 
   
   V~menu programu \texttt{File} pak můžeme grafy ukládat a znovu je načítat. Grafy se ukládají ve formátu \texttt{XML}.
   
   \subsection{Příklad grafu}
   Tento příklad zároveň otestuje správnost našeho programu. Proto jsem vytvořil graf totožný jako v~\cite[s.~8]{con93}, abychom mohli porovnat výsledky. Graf s~vypočtenou strategií vidíte na obrázku \ref{ssg1}. Pomocí  \emph{Shapleyho} algoritmu výpočet trval 2 000 000 ns, tedy cca. 2 ms. S~algoritmem  \emph{Hoffman--Karp} to proběhlo o~něco déle -- cca. 53 ms. Výsledky od obou algoritmů jsou totožné a zároveň se také shodují s~výsledky z~\cite[s.~8]{con93}. Správné hodnoty uzlů můžeme rozpoznat i pouhým pohledem. Každý \texttt{MAX} uzel obsahuje maximum ze svých synů. \texttt{MIN} uzel obsahuje naopak minimum. \texttt{AVE} uzel pak obsahuje součet hodnot synů podělený jejich počtem. Také zde můžeme vidět, že optimální strategie vede do uzlu, který má stejnou hodnotu.
  
  \begin{figure}[H] 
\begin{center}
\includegraphics{obr/ssg1.png} 
\caption{Vytvořený graf v~programu \texttt{GW2.5P}} \label{ssg1}
\end{center}
\end{figure}
 
  \section{Člověče, nezlob se} 
   \subsection{Ovládání}
   Ke hře \emph{Člověče, nezlob se} se dostaneme, pokud po spuštění programu na horní liště zvolíme \texttt{Ludo}.
   
   Hru musíme nejdříve nastavit pomocí měničů po levé straně:
    \begin {itemize}
  \item[>>] \texttt{Players} -- zde nastavíme počet hráčů ve hře, je možné nastavit 2 -- 4 hráče.
  \item[>>] \texttt{Figurines} -- zde nastavíme počet figurek, které mají hráči k~dispozici, je možné nastavit 2 -- 4 figurky.
  \item[>>] \texttt{Fields} -- tímto nastavíme počet políček na hlavním hracím poli, je možné nastavit 4 -- 52 políček.
   \end{itemize}   
  \medskip
   Po nastavení hry klikneme na tlačítko \texttt{SET NEW GAME PLAN}, čímž se nám nastaví hrací plán s~figurkami. Tažením s~přidrženým levým tlačítkem myši můžeme přesunovat figurky na libovolná místa na hracím plánu, kromě daných omezení, kdy např. nepůjde přesunout modrá figurka do zeleného domečku.
   
   Na pravé straně nastavíme, který hráč je na tahu\footnote{Pro tohoto hráče se počítá i pravděpodobnost výhry} a jaké číslo padlo na kostce. Nejprve zde byla možnost také zvolit i algoritmus výpočtu, ale po důkladném otestování jsem zjistil, že algoritmus \emph{Hoffman--Karp} je nepoužitelný. Používá totiž maticové násobení, které je velice časově i paměťově náročné a již při nejmenší možné hře -- tedy dvě figurky a dva hráči, by výpočet trval několik hodin. Proto se v~této hře používá pouze \emph{Shapleyho} algoritmus.
   
   Kliknutím na tlačítko \texttt{COUNT Strategy} se začně počítat pravděpodobnost výhry hráče, který je na tahu a také optimální strategie - tedy kterou figurkou je nejvýhodnější táhnout. 
   
   Při výpočtu nás informační okno informuje o~jeho průběhu, jak můžete vidět na obrázku \ref{ludoCalc}. Výpočet můžeme kdykoli zrušit kliknutím na tlačítko  \texttt{Abort}.

 Odhadovaný počet uzlů (\texttt{Estimated num. of nodes in Graph}) bere v~úvahu i to, na kterém místě se figurky nachází. V~závorce za odhadovaným počtem uzlů je číslo, které nám říká, kolik kombinací figurek může nastat. Více v~\ref{capComb}. Pokud odhadovaný počet přesáhne 5 000 000 uzlů, zobrazí se varování. Při tomto počtu uzlů totiž program zabírá již téměř 1,5 GB fyzické paměti a mohl by tedy spadnout kvůli jejímu nedostatku. 
 
  \begin{figure}[H] 
\begin{center}
\includegraphics{obr/ludoCalc.png} 
\caption{Okno v~průběhu výpočtu hry Človeče, nezlob se.} \label{ludoCalc}
\end{center}
\end{figure}
 
 Když se výpočet dokončí, tak se nám zobrazí ještě jedno okénko s~výsledky (viz obr. \ref{ludoCalc2}  ). Nemohu--li figurkou v~aktuálním tahu táhnout, jsou u~ní pomlčky. Figurka, která má největší pravděpodobnost výhry, se zvýrazní. Po pravé straně programu se nám také zobrazí výsledná pravděpodobnost výhry a celkový čas výpočtu. 
 
   \begin{figure}[H] 
\begin{center}
\includegraphics{obr/ludoCalc2.png} 
\caption{Okno po ukončení výpočtu hry Človeče, nezlob se.} \label{ludoCalc2}
\end{center}
\end{figure} 
 
 \subsection{Možné kombinace figurek} \label{capComb}
 
 Délka výpočtu optimální strategie je přímoúměrná počtu uzlů v~grafu, na který se hra transformuje. Graf zahrnuje všechny možné případy, do kterých se hra může dostat. Aby jsme shruba věděli, jak dlouho bude výpočet trvat a zda počítač obsahuje dostatečné množství fyzické paměti, tak program spočítá, kolik kombinací figurek může nastat. 
 
 Pokud je některá figurka v~cílovém domečku, tak již nemůže být vyhozena, proto se nám mnohonásobně zmenší počet možných kombinací. 
 
 Pro lepší vysvětlení uvedeme příklad: mějme dva hráče, každý se dvěma figurkami a 8 prostředních políček. Jedna figurka je v~cílovém domečku, ostatní 3 jsou někde v~poli. Figurky, ktere nejsou v~cíli, mohou být v~domečku, dále na 8 prostředních políčkách a nakonec na 2 políčkách v~cíli. Celkem se tedy jedna figurka může v~průběhu hry objevit na 11 políčkách. V~našem případě je tedy kombinace následující\footnote{První číslo je 1, protože je figurka v~cíli}: $1\cdot 11 \cdot 11 \cdot 11=1331$  možností rozestavení figurek v~průběhu hry. Výsledek není úplně přesný, protože dvě figurky nemohou být na stejném políčku, ale nám to k~hrubému odhadu stačí.    
 
 \subsection{Příklad 1}
  V~naší práci si ukážeme celkem tři příklady použití hry Člověče, nezlob se. Bohužel neexistuje možnost zjistit, jestli jsou naše vypočtené pravděpodobnosti správné. Hra se transformuje na \emph{Graf se dvěma a půl hráči}, který může obsahovat několik tisíc, někdy i miliónů uzlů.  Musíme se tedy spoléhat na svou logickou úvahu. Např. na začátku hry se dvěma hráči by asi každý očekával, že pravěděpodobnost výhry je kolem 50\%.
  
  V~našem prvním příkladě zkusíme tedy zjistit pravděpodobnost výhry na záčátku hry, kdy jsou všechny figurky ještě v~domečku. Budeme mít tři hráče se dvěma figurkami a čtyři prostřední políčka. Počet možných kombinací je tedy $7^6=117649$. 
  
  Rozložení figurek a výsledek můžete vidět na obr. \ref{ludo1}. Pravděpodobnost výhry 32.97\% je očekáváná. Máme totiž zhruba třetinovou šanci na výhru. Počet uzlů v~\emph{Grafu se dvěma a půl hráči} je 378668. Výpočet trval 29 sekund. Více v~tabulce \ref{tabShrnuti}.
  
  \begin{figure}[H] 
\begin{center}
\includegraphics{obr/ludo11.png} 
\caption{Příklad 1 použití hry Človeče, nezlob se.} \label{ludo1}
\end{center}
\end{figure} 
 
 \subsection{Příklad 2}
 V~tomto příkladu vyzkoušíme, zda je lepší vyhodit soupeřovu figurku, nebo raději s~druhou svojí figurkou zajet do domečku. Máme dva hráče a každý z~nich má tři figurky. Dvě figurky jsou ale v~domečku, přičemž jedna je v~domečku na prvním místě, takže se může ještě posunout dopředu (má tedy tři možnosti). Prostředních políček je dvanáct. Počet možných kombinací je tedy $3 \cdot 16 \cdot 16 \cdot 1\cdot 16 \cdot 16=196 608$. Výsledek vidíte na obr. \ref{ludo2}. Výhodnější je vyhodit soupeřovu figurku -- to máme pravděpodobnost výhry 67.32\%. Kdybychom táhli druhou figurkou, tak máme pravděpodobnost výhry pouze 53\%.

Celkový počet uzlů v~grafu je 1 436 431. Takto velké množství uzlu se projevilo i na spotřebované fyzické paměti. Program během výpočtu potřeboval 740 MB. To už je opravdu velké číslo. Zvláště pokud víme, že běžný OS Windows povoluje maximálně okolo 1900 MB paměti pro jeden program.  
 
   \begin{figure}[ht] 
\begin{center}
\includegraphics{obr/ludo22.png} 
\caption{Příklad 2 použití hry Človeče, nezlob se.} \label{ludo2}
\end{center}
\end{figure} 
 
 
 \subsection{Příklad 3}
 V~posledním příkladě zkusíme nastavit všechny čtyři hráče a čtyři figurky. Rozestavení volíme tak, aby program nespadl kvůli nedostatku paměti. Proto u~každého hráče dáme tři figurky do cílového domečku. Jednu figurku v~cíli ale necháme pohnutelnou, u~černého hráče pak dvě pohnutelné. Rozestavení figurek vidíte na obr \ref{ludo3}. Počet možných kombinací, když vynecháme sedm nepohnutelných figurek v~domečku, je:  $11 \cdot 2 \cdot 11 \cdot 2\cdot 11 \cdot 2\cdot 11 \cdot 3 \cdot 2=702768$.
 
 Pravděpodobnost výhry je 21.9\%. Pravděpodobnost druhé figurky, kterou můžeme popojet v~cíli, je pouze nepatrně menší -- 21.6\%. Tento výsledek je také očekávaný, protože při čtyřech hráčích je na začátku hry pravděpodobnost asi 25\%. Nyní jsou ovšem na řadě ale další hráči, kteří mi mohou figurku vyhodit, proto je pravděpodobnost nižší. 

 
   \begin{figure}[ht] 
\begin{center}
\includegraphics{obr/ludo33.png} 
\caption{Příklad 3 použití hry Človeče, nezlob se.} \label{ludo3}
\end{center}
\end{figure} 
 
 \subsection{Shrnutí příkladů} 
 
 Uvedené příklady nelze nijak přesněji ověřit, ale všechny dopadly podle původních očekávání. Rychlost výpočtu při tolika uzlech dopadla naopak nad očekávání dobře. Bohužel ale musíme dávat pozor, jak volíme figurky, jelikož již při třech hráčích je počet možných kombinací tak velký, že počet uzlů přesáhne milión. Program může mít nedostatek fyzické paměti a spadnout. 
 
 V~tabulce \ref{tabShrnuti} jsou shrnuty výsledky a měření všech tří příkladů.
 
 
  \begin{table}[ht]
\begin{center}
        \catcode`\-=12
	\begin{tabular}{| c | c | c | c | c |} \hline		
            
 	  		 	   & \textbf{Výhra}\tablefootnote{Pravděpodobnost výhry pro hráče na tahu} & \textbf{Počet uzlů}\tablefootnote{Počet uzlů po transformaci v~\emph{Grafu se dvěma a půl hráči}}& \textbf{Délka výpočtu} & \textbf{RAM} \tablefootnote{Kolik zabíral program fyzické paměti v~době výpočtu. Měřeno programem \texttt{Process Explorer}}   \\ \hline
          \textbf{Příklad 1}  & 32.97\% & 117 649 & 29 sek. & 170 MB  \\ \hline
          \textbf{Příklad 2}  & 67.33\% & 1 436 431 & 58 sek. & 740 MB  \\ \hline
          \textbf{Příklad 3}  & 21.9\% & 2 542 725 & 1097 sek. & 1266 MB  \\ \hline

       
	\end{tabular}
	\caption{Shrnutí příkladů hry Člověče, nezlob se } \label{tabShrnuti}
\end{center}
\end{table}
 
 \chapter{Závěr}
 
 Cílem práce bylo nastudovat algoritmy pro řešení \emph{her se dvěma a půl hráče}. Na základě nastudovaných algoritmů bylo úkolem vytvořit framework pro řešení těchto her. Součástí práce bylo také vytvořit funkční prototyp se hrou \emph{Člověče, nezlob se} využívající vytvořenou knihovnu.
 
 Při studiu jsem zjistil, že řešením \emph{her se dvěma a půl hráči} se zabývají tzv. \emph{SSG} (\emph{simple stochastic games}). U~těchto her je známo velké množství algoritmů pro jejich řešení. Vybral jsem dva algoritmy -- \emph{Randomizovaný Hoffman--Karp} a \emph{Shapleyho}. Tyto algoritmy jsem naimplementoval do frameworku nazvaného \texttt{SSG}.
 
 Navrhl jsem a naimplementoval také funkční program s~názvem \texttt{GW2.5P}, který využívá vytvořený framework. Program má dvě hlavní funkčnosti. První je grafické řešení grafu \emph{her se dvěma a půl hráče}, kde si uživatel může vytvořit graf a program mu vypočte optimální strategii. Druhou funkčností je hra \emph{Člověče, nezlob se}. Hra se na základě navoleného hracího pole a figurek transformuje na \emph{SSG} graf a dokáže tak spočítat pravděpodobnost výhry u~vybraného hráče. Již při nejmenším počtu hráčů a figurek však graf obsahuje několik tisíc uzlů. Při větším počtu figurek, kdy uzlů bude několik milionů, může nastat problém s~nedostatečnou fyzickou pamětí. Program ale dokáže odhadnout počet uzlů v~grafu a uživatele před tímto možným scénářem varovat.
 
 Knihovna \texttt{SSG} je plně funkční a je k dispozici pro různé projekty psané v jazyce C++ vyžadující spočítat optimální strategii ve \emph{hrách se dvěma a půl hráče}.
 
    
    % Bibliography goes here
    \printbibliography
    
    \appendix %% Start the appendices.
\chapter{Obsah přiloženého CD}
\begin{itemize}
\item thesis.zip -- PDF a zdrojové texty diplomové práce
\item src.zip -- zdrojové soubory k~programu \texttt{GW2.5P}
\item bin.zip -- spustitelný program \texttt{GW2.5P}
\item doc.zip -- dokumentace k~programu \texttt{GW2.5P}
\end{itemize}
 
    


    
    
    
    % Index goes here (optional)
\end{document}
