\documentclass[12pt]{beamer}
\usepackage[T1]{polski}
\usepackage[utf8]{inputenc}
%\usepackage{multimedia}
%\usepackage[a4paper]{geometry}
%\usepackage{graphicx}
%\usepackage[]{hyperref}


\author{Karol Kozłowski, Piotr Komoniewski}
\title{Sztuczna Inteligencja}
 \subtitle{GRY}
 \date{\today}
 \institute{Seminarium Specjalistyczne}
 \subject{}
 \keywords{} 
 \titlegraphic{}

%\setbeamersize{text margin left=0mm,text margin right=2.5mm}
\setbeamersize{sidebar width left=0mm,sidebar width right=0cm}
%\usetheme{pwr}
%\usetheme{Antibes} %taki gabrysiowaty
%\usetheme{Boadilla} % prosty taki
%\usetheme{boxes}		% jeszcze prostszy
%\usetheme{Dresden}
%\usetheme{Oxygen}


%\transdissolve[duration=0.2]
%\logo{\includegraphics[height=7mm]{poziom-pl-pantone}}
\logo{\includegraphics[height=7.05mm]{logopwrpl}}

\begin{document}
\transdissolve
\begin{frame}[plain,t]
 \maketitle
\end{frame}

\begin{frame}

	\frametitle{Konspekt}
	\begin{itemize}
		\item Gry planszowe.
		\begin{itemize}
			\item Warcaby
			\item Trik-Trak
			\item Szachy
			\item Go
		\end{itemize}	
		\item Rozwiązanie problemu
		\item Algorytmy
	\end{itemize}	
\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{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{Backgammon, Tryktrak}
	\begin{itemize}
		\item Trik-trak (backgammon), popularny w Japonii. 
		\item Zawiera element niepewności (rzut kostką).
		\item 1980, program BKG wygrał raz z mistrzem świata. 
		\item 1992, program Tesauro, techniki jak dla warcabów + nauka lepszych ocen, ranking wśród 3 najlepszych graczy.
		\item Mistrzowskie rezultaty w wielu grach osiągnięto dopiero w latach 1990.
		\item Moc obliczeniowa
	\end{itemize}	
\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 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:3
		\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{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}

\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
	{Rozwiązanie problemu}
	\begin{center}
		\pgfimage[width=9.5cm,interpolate=false]{Tic-tac-toe-game-tree}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{Algorytmy}
		Alborytmy przeszukiwania grafów:
		\begin{itemize}
		\item min-max
		\item $\alpha\beta$
		\item usprawnione algorytmy $\alpha\beta$
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Bibliografia}
	\begin{small}
	\begin{itemize}
		\item Włodzisław Duch - \textit{Sztuczna Inteligencja} (prezentacja)
		\item Adam Kujawski - \textit{Programowanie gry w szachy} (1994, mgr)
		\item Aaron Clauset - \textit{Game Tree Searching and pruning}
		\item praca zb. - \textit{Checkers Is Solved} (Science  317, 2007)
		\item Louis Victor Allis \textit{Searching for Solutions in Games and Arti cial Intelligence}
	\end{itemize}
	\end{small}
\end{frame}

\begin{frame}
	\frametitle{Koniec}
	Dziękujemy za uwagę.
\end{frame}

%\begin{frame}
%\frametitle{Kolumny}
%	\begin{columns}[t]
%		\column{0.4\textwidth}
%			\begin{block}{Ala ma kota}
%				Ala ma kota Ala ma kota Ala ma kota
%			\end{block}
%			
%		\column{0.5\textwidth}
%			\begin{block}{Ola ma psa}
%				Ola ma psa Ola ma psa Ola ma psa
%			\end{block}
%		\end{columns}
%\end{frame}




\end{document}

%  \pgfimage[width=7mm,interpolate=false]{Tic-tac-toe-game-tree}

%	\begin{itemize}
%		\item<1>
%		\item<2->
%	\end{itemize}	

%\alert{lepiej} 

%\url{http://www.immt.pwr.wroc.pl/}

%$$g=\sin(x)\sum_{i=1}^{100}g_i$$