\documentclass[12pt]{beamer}

\usetheme{Oxygen2}
\usepackage{thumbpdf}
\usepackage{wasysym}
%\usepackage{ucs}
\usepackage[T1]{polski}
\usepackage[utf8]{inputenc}
\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
\usepackage{verbatim}


%\logo{\includegraphics[height=5mm]{logopwrpl}}

\pdfinfo
{
  /Title       (Sztuczna Inteligencja - GRY)
  /Creator     (TeX)
  /Author      (Karol Kozłowski, Piotr Komoniewski)
}


\title{Sztuczna Inteligencja}
\subtitle{GRY}
\author{Karol Kozłowski, Piotr Komoniewski}
\date{\today}

\begin{document}

\frame{\titlepage}

\section*{}
\begin{frame}
  \frametitle{Konspekt}
  \tableofcontents[section=1,hidesubsections]
\end{frame}

\AtBeginSection[]
{
  \frame<handout:0>
  {
    \frametitle{Konspekt}
    \tableofcontents[currentsection,hideallsubsections]
  }
}

\AtBeginSubsection[]
{
  \frame<handout:0>
  {
    \frametitle{Konspekt}
    \tableofcontents[sectionstyle=show/hide,subsectionstyle=show/shaded/hide]
  }
}

\newcommand<>{\highlighton}[1]{%
  \alt#2{\structure{#1}}{{#1}}
}

\newcommand{\icon}[1]{\pgfimage[height=1em]{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Algorytmy przeszukiwania grafów}

\begin{frame}
	\frametitle{Algorytmy}
		Algorytmy przeszukiwania grafów:
		\begin{itemize}
		\item tworzenie grafów
		\item wyszukiwanie $min - max$
		\item wyzszukiwanie z odcięciami $\alpha - \beta$
		%\item usprawnione algorytmy $\alpha - \beta$
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{tworzenie grafów}
	\framesubtitle{Algorytm $min - max$}
	\begin{itemize}
    \item przepisy gry charakteryzują pewien skierowany graf (dalej nazywany grafem gry) 
    \item węzły grafu gry utożsamiamy ze stanami gry
    \item następnikami każdego węzła (stanu) są węzły (stany) osiągalne z niego poprzez wykonanie jednego ruchu
    \item gracze wykonują ruchy na przemian (następnikami węzła są sany w których ruch należy do przeciwnika)
    \item stany końcowe (dla których przepisy definiują wypłatę) charakterysuje brak następników
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Algorytmy przeszukiwania grafów}
	\framesubtitle{Algorytm $min - max$}
    \only<1>{
		\begin{center}
      		\pgfimage[width=10cm]{minmax_1}
  		\end{center}	
    }
    \only<2>{
		\begin{center}
      		\pgfimage[width=10cm]{minmax_2}
  		\end{center}	
    }
\end{frame}




\begin{frame}
	\frametitle{Algorytmy przeszukiwania grafów}
	\framesubtitle{Algorytm $\alpha - \beta$}
  \begin{center}
		\pgfimage[width=11	cm]{pruning}
	\end{center}
	
\end{frame}


\section{Algorytmy strategii szachowych}

\begin{frame}
	\frametitle{Strategia gry}

	System oceny pozycji:

	\begin{itemize}
		\item Przewaga materialna-zależna od posiadania figur.
		\begin{itemize}
			\item pionek=1pkt
			\item goniec i skoczek=3pkt
			\item wieża=5pkt
			\item hetman=9pkt
			% zaawansowane współczynniki wagi figur
		\end{itemize}
		\item Przewaga pozycyjna-zależna od układu figur na planszy
		\begin{itemize}
			\item zablokowana figura jest warta mniej niż wolna
			\item można też oszacować bezpieczeństwo króla
			\item panowanie nad centrum planszy
		\end{itemize}
	\end{itemize}
\end{frame}


\begin{frame}
	\frametitle{Strategia gry}
	\begin{itemize}
	\item Stan wyciszony
	\begin{itemize}
		\item powolna walka pozycyjna
		\item rozległy horyzont zdarzeń
	\end{itemize}
	\item Stan niewyciszony
	\begin{itemize}
		\item wąski horyzont zdarzeń
	\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Stan wyciszony}
	\begin{itemize}
	\item indywidualne wartości pozycji dla danej figury
	\item dodatkowe wartości dla strategii figury
	\item bezpieczeństwo króla
	\item panowanie nad centrum
	\item zbite pionki
	\item szacowanie końca gry
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Szacowanie pozycji-obrona}

\begin{center}
	\pgfimage[center,width=5cm]{s1}
	\pgfimage[center,width=5cm]{s2} %zeby znalazl sie obok
\end{center}

\end{frame}

\begin{frame}
	\frametitle{Szacowanie pozycji-obrona}

\begin{center}
	\pgfimage[center,width=5cm]{s3}
	\pgfimage[center,width=5cm]{s4} %zeby znalazl sie obok
\end{center}

\end{frame}

\begin{frame}
	\frametitle{Quiescent search}
Algorytm cichego wyszukiwania (quiescent search)
	\begin{itemize}
	\item określa pozycje aby uniknąć oczywistych warunków taktyk
	\item używa do obliczeń dynamicznych możliwości
	\item podstawowy algorytm poszukuje tylko zdobyczy
	\item mniejszy wpływ na chwilowe rozegranie lub początkowy ruch
	\item waży dwie zmienne odpowiadające za:
	\begin{itemize}
		\item zachowanie wysokiej pozycji na szachownicy ($\beta$)
		\item uzyskania przewagi figur ($\alpha$)
	\end{itemize}
	\end{itemize}
\end{frame}


\begin{frame}
	\frametitle{Stan wyciszony}
Możliwe sytuacje wyjścia z algorytmu:
	\begin{itemize}
	\item gdy funkcja ocen zwróci wystarczająco wysoką wartość (wyjście z odcięciem $\beta$)
	\item zbicie figury (pozwoli odciąć $\beta$)
	\item gdy funkcja ocen jak i zbicie figury nie da pożądanego rezultatu
	\item gdy żadne zbicie nie będzie poprawiało parametru ale ocena pozycji spowoduje poprawę parametru $\alpha$
	\end{itemize}
\end{frame}

\section*{}

%  \begin{block}{Standard block}
%  \end{block}
%  \begin{alertblock}{Alert block}
%  \end{alertblock}
%  \begin{example}
%  \end{example}

%\frame{ 
%	\vspace{2cm} {\huge Pytania ?} 
%	\vspace{3cm} 
%	\begin{flushright}
%    Karol Kozłowski, Piotr Komoniewski
%    \structure{\footnotesize{konqi@kde.org}}
%  \end{flushright}
%}

\begin{frame}
	\frametitle{Bibliografia}
	\begin{thebibliography}{10}

		\beamertemplatearticlebibitems

		\bibitem{duch}
			Sztuczna Inteligencja
			\newblock {Włodzisław Duch (prezentacja)}
		\bibitem{kujaw}
			 Programowanie gry w szachy
			\newblock {Adam Kujawski (1994, mgr)}
		\bibitem{clauset} 
			Game Tree Searching and pruning
			\newblock {Aaron Clauset}
		\bibitem{solved} 
			Checkers Is Solved
			\newblock {praca zb., Science  317, 2007}
		\bibitem{louisvictor} 
			Searching for Solutions in Games and Arti cial Intelligence
			\newblock {Louis Victor Allis }

  \end{thebibliography}
\end{frame}

\frame{
  \vfill
  \centering
  \highlighton{
  	\usebeamerfont*{frametitle}KONIEC
  }
  
  \centering
  \highlighton{
		\usebeamerfont*{framesubtitle}Dziękujemy za uwagę.
  }
  \vfill
}

\end{document}
