\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{Gry planszowe}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Warcaby}
  \begin{block}{Gry planszowe}
  \begin{itemize}
			\item<1-> Go
			\item<2-> Othello
			\item<3-> TrykTrak
			\item<4-> Warcaby
			\item<5-> Szachy
  \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{GO}
	\begin{center}
  	\pgfimage[center,height=6cm,interpolate=false]{game_go}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Go - większe wyzwanie}
		\begin{itemize}
		\item Liczba ruchów w Go to średnio 260 (szachy tylko 35).
		\item Liczba partii: $10^{260}$(szachy $10^{123}$).
		\item Liczba różnych pozycji na planszy\: $10^{172}$ (szachy $10^{46}$).
		%Techniki szukania są mało przydatne: obecne programy są kiepskie na standardowej planszy 19x19, ale na poziomie mistrzowskim na planszach 9x9.
		%Pierwszy program w 1968 roku, najlepszy obecnie Go4++ napisał M. Reiss, program jest znacznie lepszy od swojego twórcy.
		\item Konieczne do dobrego grania w Go jest\: 
		\begin{itemize}
			\item rozpoznawanie struktur (typ lokalnych konfiguracji), 
			\item uczenie maszynowe, 
			\item strategie i planowanie, 
			\item metody reprezentacje wiedzy.
		\end{itemize}
		\item Nagroda 1 mln \$ dla programu, który pokona mistrza z Taiwanu\!
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Othello}
	\begin{center}
  	\pgfimage[center,height=6cm,interpolate=false]{game_othello}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Othello}
	\begin{itemize}
		\item 1995, Logistello zwycięża mistrza świata Takeshi Murakami 6 do 0!
		%  http://www.cs.ualberta.ca/~mburo/log.html
		\item Program grał parę tygodni sam z sobą poprawiając swoje funkcje oceny heurystycznej.
		\item Funkcje ewaluacji bazują na ponad milionie parametrów.
		\item Obecne programy sa o wiele lepsze od nalepszych ludzkich graczy.	
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Warcaby}
	\begin{center}
  	\pgfimage[center,height=6cm,interpolate=false]{game_checkers}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Warcaby}
	\begin{itemize}
		\item 1952, Samuel, pierwszy program uczący się gry w warcaby.
		\item 1992, Chinook (J. Schaeffer, UoA) wygrywa US. Open. Program używa szukania $ \alpha - \beta $
		\item Mistrzostwa człowiek-maszyna, Londyn 1992.
		\item Dr. Marion Tinsley, wygrał z Chinookiem 4-2, 33 remisy.	
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Warcaby}
	\begin{itemize}
		\item Użyto 8-proc. stacji Silicon Graphics 4D/480, 256 MB RAM, baza danych wszystkich końcówek z 1-7 figurami + 	prawie połowa wszystkich partii z 8 figurami. 
		\item 1994, remis 1-1 i 18 remisów. 
		\item 1995, wygrana Chinooka 1-0 i 31 remisów.	Użyto komputera SGI z 512 MB RAM. 
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Backgammon, Tryktrak}
	\begin{center}
  	\pgfimage[center,height=6cm,interpolate=false]{game_backgammon}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Backgammon, Tryktrak}
	\begin{itemize}
		\item Tryktrak (backgammon), popularny w Japonii. 
		\item Zawiera element niepewności (rzut kostką).
		\item 1979, program BKG 9.8 wygrał z mistrzem świata 7-1. %Luigi Villa, pierwszy program który wygrał,logika rozmyta
		\item Koniec lat '80 powstaje TD-Gammon oparty o sieć neuronową %TD od temporal difference lerning=monte carlo + programowanie dynamiczne(bootstraping). 
		\item 1992, program TD-Gammon 2.1, techniki jak dla warcabów + nauka lepszych ocen.
		\item 1995, wersja 3.0 nie pokonana o powiększonej warstwie ukrytej (160).
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy}
	\begin{center}
  	\pgfimage[center,height=6cm,interpolate=false]{game_chess}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy}
	\begin{itemize}
		\item 1958, pierwszy program szachowy, Alex Bernstein. 
		\item Szkocki międzynarodowy mistrz szachowy funduje nagrodę dla programu, który ogra go chociaż raz na cztery partie.
		\item W 1985 roku przegrał wszystkie cztery partie. 
		\item 1985, HiTech wśród najlepszych 800 graczy, oceniał ok. 10 mln pozycji, w 1988 roku wygrał z arcymistrzem. 
		\item Intel+IBM\: szachy to dobra reklama. 
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy}
	\begin{itemize}
		\item 1890, Leonardo Torre`s y Qeuvedo - maszyna poprawnie rozwiązująca problemy szachowe typu król - wieża - król.
		\item 1958, pierwszy program szachowy, Alex Bernstein.
		\item 1983, Belle - pierwszy program który osiągnał poziom mistrza 
		\item Szkocki międzynarodowy mistrz szachowy funduje nagrodę dla programu, który ogra go chociaż raz na cztery partie.
		\item W 1985 roku przegrał wszystkie cztery partie. 
		\item 1985, HiTech wśród najlepszych 800 graczy, oceniał ok. 10 mln pozycji, w 1988 roku wygrał z arcymistrzem. 
	\end{itemize}	
\end{frame}


\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy}
	\begin{itemize}
		\item 1994 Chess Genius na PC Pentium, kilka razy zwyciężył Gary Kasparova; czas grania ograniczono do 25 minut na zawodnika.
		\item 1996 – Deep Blue przegrał z Kasparowem 2:4
		\item 1997 – Deep Blue wygrał 3.5:2.5 
		\item 2002 – program Deep Fritz na PC remisuje z Vladimirem Kramnikiem 
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-strategia}
	\begin{itemize}
		\item Zastosowanie algorytmu min-max - analiza 6 półruchów. %nie stosuje sie brute force z braku czasu-tworzy drzewo ruchów do pewnej głębokoci-okrela wartoć tych ruchów
		\begin{itemize}
			\item Metody ograniczania obszaru - przeszukiwanie alfa-beta.
		\end{itemize}	
		\item Iteracyjne pogłębianie-wybór najlepszych galęzi drzewa.
		\item System oceny pozycji:
		\begin{itemize}
			\item Przewaga materialna-zależna od posiadania figur. %pionek-1pkt; goniec=skoczek=3pkt; wieza=5pkt; hetman=9pkt; zaawansowane majš współczynniki wagi figur
			\item Przewaga pozycyjna-zależna od układu figur na planszy. %zablokowana figura jest warta mniej niż wolna, można też oszacować bezpieczeństwo króla, panowanie nad centrum planszy,
		\end{itemize}	
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-strategia}
	\begin{itemize}
		\item Książka otwarć - typowe zagrania i pierwsze ruchy.
		\item Baza końcówek - gdy zostaje 5 figur.
		\item Ważne pojęcia:
		\begin{itemize}
			\item Stan wyciszony i horyzont zdarzeń - walka pozycyjna.
			\item Stan niewyciszony
		\end{itemize}	
		\item Iteracyjne pogłębianie - wybór najlepszych galęzi drzewa.
	\end{itemize}	
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-Thinking Machine 4}
	\begin{center}
  	\pgfimage[center,width=6cm,interpolate=false]{a}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-Thinking Machine 4}
	\begin{center}
		\pgfimage[center,width=6cm,interpolate=false]{b}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-Thinking Machine 4}
	\begin{center}
		\pgfimage[center,width=6cm,interpolate=false]{c}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-Thinking Machine 4}
	\begin{center}
		\pgfimage[center,width=6cm,interpolate=false]{d}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-Thinking Machine 4}
	\begin{center}
		\pgfimage[center,width=6cm,interpolate=false]{e}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Szachy-Thinking Machine 4}
	\begin{center}
		\pgfimage[center,width=6cm,interpolate=false]{f}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Deep Thougt i Deep Blue (1)}
	\begin{itemize}
		\item Deep Thought, od 1985 roku, 4 studentów z USA  (T. Hsu, T. Anantharaman, M. Campbell, A. Nowatzyk).
		\item Program Deep Blue (nowsze Deep Thought) + hardware do gry w szachy: 32 procesory IBM RS6000/SP2 + 256 ASIC.
		\item Ocenia 200-1000 milionów pozycji/sek! 
		\item Duża biblioteka otwarć i końcówek.
		\item Deep Thought – szukanie alfa-beta, ok. 10 ruchów w skomplikowanych sytuacjach. 
		\item Deep Blue - ok. 14 ruchów, 3000 punktów, pobił Kasparova. 
		%\item Reakcja prasy – potworna szybkość i pamięć zwyciężyły. 
		%\item Mózg: 10.000 razy większa pamięć/szybkość więc to uwagi bez sensu!
		%\item Moc już nadchodzi i będzie z nami …
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Gry planszowe}
	\framesubtitle{Deep Thougt i Deep Blue (2)}
		\begin{columns}
			\column{0.45\textwidth}
				Nowy Jork, listopad 2003
				\centerline{Kasporov}
				\centerline{vs.}
				\centerline{X3D Deep Fritz junior.}
				%Mecz zakończył się remisem; główną atrakcją była gra w wirtualnej rzeczywistości. 
				%Komputer, na którym zainstalowany był program Fritz był około 100 razy wolniejszy niż Deep Blue i do tego zajęty generowaniem obrazu w 3 wymiarach, nic więc dziwnego, że mecz zakończył się remisem. 
				%PC stoi w kącie ... następny taki mecz odbędzie się z programem działającym w telefonie ?  
			\column{0.55\textwidth}
				\pgfimage[width=6cm,interpolate=false]{kasparov}
		\end{columns}
\end{frame}

\section{Rozwiązanie problemu}

\begin{frame}
	\frametitle{Rozwiązanie problemu}
  \begin{block}{Rozwiązanie problemu}
  \begin{enumerate}
	 \item Budowanie drzewa ruchów
	 \item Wyznaczenie wag rozwiązań
	 \item Znalezienie optymalnej ścieżki
  \end{enumerate}
  \end{block}
	\begin{center}
		\pgfimage[width=4cm,interpolate=false]{binary_tree}	
	\end{center}
\end{frame}


\begin{frame}
	\frametitle{Rozwiązanie problemu}
	\framesubtitle{Budowanie drzewa}
	\begin{center}
    \only<1>{
      \pgfimage[width=9.5cm,interpolate=false]{ttt0}
    }
    \only<2>{
      \pgfimage[width=9.5cm,interpolate=false]{ttt1}
    }
    \only<3>{
      \pgfimage[width=9.5cm,interpolate=false]{ttt2}
    }
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Rozwiązanie problemu}
	\framesubtitle{Ewaluacja rozwiązań}
	\begin{block}{Ewaluacja rozwiązań}
		\begin{itemize}
		 \item kółko i krzyżyk
		 \item szachy
		 \item warcaby (chinook)
		\end{itemize}
	\end{block}
\end{frame}

\section{Algorytmy}

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

\begin{frame}
	\frametitle{Algorytmy przeszukiwania grafów}
	\framesubtitle{Algorytm $min - max$}
    \only<1>{
			\begin{center}
      \pgfimage[height=6cm]{minmax0}
  		\end{center}	
    }
    \only<2>{
			\begin{center}
      \pgfimage[height=6cm]{minmax1}
  		\end{center}	
    }
    \only<3>{
			\begin{center}
      \pgfimage[height=6cm]{minmax2}
  		\end{center}	
    }
    \only<4>{
			\begin{center}
      \pgfimage[height=6cm]{minmax3}
  		\end{center}	
    }
    \only<5>{
			\begin{center}
      \pgfimage[height=6cm]{minmax4}
  		\end{center}	
    }
    \only<6>{
			\begin{center}
      \pgfimage[height=6cm]{minmax5}
  		\end{center}	
    }
    \only<7>{
			\begin{center}
      \pgfimage[height=6cm]{minmax6}
  		\end{center}	
    }
    \only<8>{
			\begin{center}
      \pgfimage[height=6cm]{minmax7}
  		\end{center}	
    }
    \only<9>{
			\begin{center}
      \pgfimage[height=6cm]{minmax8}
  		\end{center}	
    }
	
\end{frame}

\begin{frame}
	\frametitle{Algorytmy przeszukiwania grafów}
	\framesubtitle{Algorytm $min - max$}
  \begin{center}
		\pgfimage[width=11	cm]{pruning}
	\end{center}
	
\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}
