\section{Optimizations}

\begin{frame}
    \frametitle{Optimizations}

    \begin{itemize}
        \setlength\itemsep{1.5em}
        \item Alpha-Beta Search
        \item Oware Micro Optimizations
        \item Profiling
        \item OpenMP
        \item Transposition table
    \end{itemize}
\end{frame}

% Frames for all Optimizations

\begin{frame}
    \frametitle{Alpha-Beta Search}

    \begin{itemize}
        \setlength\itemsep{1.5em}
        \item Extends min-max search with pruning
        \item Finds optimal move for the specified depth
        \item Skips subtrees which can not yield better results
        \item Disadvantage: harder to parallelize
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Oware Micro Optimizations}
    
    \begin{itemize}
        \setlength\itemsep{1.5em}
        \item Seeding done via loop from 0 to houses
        \item Increase of seeds per house is calculated once
        \item Manual loop unrolling
        \item Capturing is done in subsequent loop
        \item + Constant amount of loops
        \item - Divisions, Modulo operations
        \item - Branches
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Profiling}
    
    \begin{itemize}
        \setlength\itemsep{1.5em}
        \item GCC Profiling \footnote{https://gcc.gnu.org/onlinedocs/gcc/Cross-profiling.html}
        \item Profile program to gather information
        \item Compile the program with optimization according to the information
        \item + Optimized compiler optimizations
        \item - Needs to be run before it can be recompiled
        \item - Cannot deal well with parallelization
        \item - Optimized for the benchmark program 
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{OpenMP}

    \begin{itemize}
        \setlength\itemsep{1.5em}
        \item Parallelize loops in the search implementation
        \item - No pruning at top level
        \item + All searches are parallel
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Transposition table}
    
    \begin{itemize}
        \setlength\itemsep{1.5em}
        \item Array of fixed size
        \item Saves best move per board layout (+ depth)
        \item Using zobrist\footnote{https://en.wikipedia.org/wiki/Zobrist\_hashing} hash of the board
        \item Update entry on deeper depth
        \item Good reusability in one turn
        \item Hard to reuse over multiple turns
    \end{itemize}
\end{frame}