\documentclass[12pt, a4paper]{article}
 
\newcounter{conta}
\newcounter{conta2}

\hyphenation{ha-bi-li-da-de es-pe-cia-li-za-das e-xem-plo pro-je-to
com-ple-xi-da-de de-sa-pa-re-ce a-bor-da-gem to-ma-da su-ces-so
in-te-li-gen-tes a-gen-te co-nhe-ci-men-to ra-i-nhas e-fei-tos
al-go-rit-mo o-pe-ra-do-res ta-bu-lei-ro co-mo ne-nhu-ma co-lu-na
cons-tan-te}

\begin{document}

\vspace*{9cm}
\begin{center} \LARGE\bf
 Cap\'{\i}tulo 5: Jogos
\end{center}

\vfill
\ 

\pagebreak
\noindent{\Huge\bf Jogos como Problemas de Busca}

\vspace*{1.5cm}
\begin{itemize} \LARGE
 \item Oponente {\em imprevis\'{\i}vel\/}: a solu\c c\~ao \'e um plano dependente
       do comportamento do advers\'ario.

 \item Limite de {\em tempo\/}: necessidade de fazer lance sem certeza de que \'e o
       melhor.

       Exemplo: \'arvore de busca para xadrez tem em torno de $35^{100}$ nodos.
\end{itemize}


\vspace*{1cm}
\noindent{\LARGE\bf Nosso plano de ataque:}

\begin{itemize}\LARGE
 \item Algoritmo para um jogo perfeito (Vom Neumann, 1944).
 \item Avalia\c c\~ao aproximada (Zuze, 1945; Shannon, 1950; Samuel, 1952--57).
 \item Poda da \'arvore de busca (McCarthy, 1956).
\end{itemize}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf Um jogo \'e um problema de busca com:}

\begin{itemize}\LARGE
 \item {\bf Estado inicial:} configura\c c\~ao inicial do jogo e quem inicia.

 \item {\bf Operadores:} lances permitidos.

 \item {\bf Condi\c c\~ao de t\'ermino:} situa\c c\~ao em que o jogo termina.

 \item {\bf Fun\c c\~ao utilit\'aria:} d\'a o valor para cada configura\c c\~ao
       terminal. Exemplo: em xadrez {\em vit\'oria\/}(+1), {\em empate\/}(0) ou
       {\em derrota\/}(-1).
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE Algumas suposi\c c\~oes:}

\begin{itemize}\LARGE
 \item Dois jogadores: MAX e MIN.
 \item MAX come\c ca jogando.
 \item MAX deve fazer lance que lhe garanta o {\em m\'aximo\/}.
 \item MIN sempre faz lance que d\^e o {\em m\'{\i}nimo\/} para MAX.
\end{itemize}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf Exemplo: jogo da velha}

\vspace*{5cm}
\begin{center}
Figura 5.1
\end{center}

\vspace*{5cm}
\noindent {\LARGE\bf Exemplo de \'arvore minimax com dois lances:}

\vspace*{2.5cm}
\begin{center}
Figura 5.2
\end{center}


\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf O algoritmo Minimax}

\vspace*{4cm}
\begin{center}
Figura 5.3
\end{center}

\vspace*{4cm}
\noindent {\LARGE\bf Propriedades do Minimax:}

\begin{itemize}\LARGE
 \item {\bf Completo:} Sim, se \'arvore finita.
 \item {\bf \'Otimo:} Sim, contra um oponente \'otimo.
 \item {\bf Complexidade de tempo:} $O(b^m)$.

       (xadrez: $b\approx 35$, $m\approx 100$ $\Rightarrow$ invi\'avel)
 \item {\bf Complexidade de espa\c co:} $O(mb)$.

       (explora\c c\~ao em profundidade)
\end{itemize}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf Abordagem para limita\c c\~ao de tempo:}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item {\em Teste de corte\/}: profundidade m\'axima.
 \item {\em Fun\c c\~ao de avalia\c c\~ao\/}: estimativa do valor da configura\c c\~ao.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE\bf Fun\c c\~ao de avalia\c c\~ao para Xadrez:}

\vspace*{1cm}
{\Large
\[\mbox{EVAL}(s)=w_1f_1(s)+w_2f_2(s)+\cdots+w_nf_n(s)\]
}

\vspace*{1cm}
\noindent {\LARGE por ex., $w_1=9$, $f_1(s)=\mbox{(n\'umero de rainhas brancas)}-
\mbox{(n\'umero de rainhas pretas)}$}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf Corte $\alpha-\beta$}

\vspace*{3.5cm}
\begin{center}
Figura 5.6
\end{center}

\vspace*{3.5cm}
\noindent {\Large\bf O caso geral:}


\vspace*{3.5cm}
\begin{center}
Figura 5.7
\end{center}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf O algoritmo $\alpha-\beta$:}

\vspace*{5cm}
\begin{center}
 Figura 5.8
\end{center}

\vspace*{5cm}
\noindent {\LARGE\bf Propriedades de $\alpha-\beta$:}

\begin{itemize} \LARGE
 \item A poda \underline{n\~ao} afeta o resultado final.
 \item A efetividade da poda depende da ordem.
 \item Com ``ordem perfeita'', complexidade de tempo  \'e $O(b^{m/2})$.
       \begin{enumerate}
        \item[$\Rightarrow$] {\em Dobra\/} profundidade da busca.
        \item[$\Rightarrow$] Um bom jogador de xadrez chegando \`a profundidade 8.
       \end{enumerate}
\end{itemize}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf Jogos determin\'{\i}sticos na pr\'atica:}

\vspace*{.5cm}
\begin{itemize} \LARGE
 \item {\bf Damas:} Chinook acabou com um reinado de 40 anos do campe\~ao mundial
       Marion Tinsley em 1994. (Usou banco de dados para finais de 8  pe\c cas ou
       menos: 443.748.401.247 configura\c c\~oes.)
 \item {\bf Xadrez:} Deep Blue venceu o campe\~ao mun\-dial Gary Kasparov em 1997 em
       uma partida de 6. Analisa 200 milh\~oes de configura\-\c c\~oes por segundo, usa
       avalia\c c\~ao sofisticada, e m\'etodos para estender algumas linhas de busca at\'e
       40 lances \`a frente.
 \item {\bf Otelo:} campe\~oes humanos se recusam a competir com computadores, que s\~ao
       muito bons.
 \item {\bf Go:} campe\~oes humanos se recusam a competir com computadores, que s\~ao
       muito ruins. Em go, $b>300$...
\end{itemize}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf Jogos com elementos rand\^omicos}

\vspace*{1cm}
\noindent {\LARGE $\Rightarrow$ Introdu\c c\~ao de {\em nodos de possibilidades.}}

\vspace*{.5cm}
\noindent {\LARGE\bf Exemplo: gam\~ao}

\vspace*{8cm}
\begin{center}
 Figura 5.10
\end{center}

\vfill
\hfill Jogos

\pagebreak
\noindent {\LARGE\bf Algoritmo para jogos n\~ao determin\'{\i}sticos}

\vspace*{1cm}
\noindent {\LARGE $\Rightarrow$ Como Minimax, mas levando em conta os nodos
 de possibilidades.}

\vspace*{1cm} {\Large
\[\mbox{expectimax}(C)=\sum_iP(d_i)\mbox{max}_{s\in S(C,d_i)}\mbox{utility}(s)\]
}

\vspace*{1cm}
\noindent {\LARGE Expectiminimax \'e como Minimax, s\'o que lida com nodos de posssibilidades:}

\vspace*{1cm}
$\vdots$

\noindent {\large
{\bf if} {\em state\/} is a chance node {\bf then} \\
\hspace*{.5cm} {\bf return} average of Expectiminimax-Value of Successors({\em state})

$\vdots$
}

\vspace*{1cm}
\noindent {\LARGE Poda $\alpha-\beta$ \'e poss\'{\i}vel...}


\end{document}

