\documentclass[12pt]{article}


\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\setlength{\textheight}{21cm}
\newcommand{\p}{\vspace{1.44ex}}

\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 323 -- Estruturas de Dados}
\end{center}

\begin{center}
{\bf Primeiro semestre de 1999}
\end{center}

\begin{center}
{\large  EP Substitutivo -- Entrega: {\bf 30 de junho de 1999}}

\vspace{0.3cm}
Otelo
\end{center}


Otelo, também conhecido por Riversi, é um jogo que usa um
tabuleiro, em que dois jogadores jogam.
Um jogador (chamado \textit{branco}) joga com pedras brancas (denotadas
aqui por ``o'') e
outro, chamado \textit{preto} joga com pedras pretas (denotadas por ``x''). 


(Uma maneira prática é usar pedras coloridas brancas em um lado e pretas
no outro.  Virando a pedra mudamos a sua cor.)


O tabuleiro é composto por 8 linhas e 8 colunas,
totalizando 64 casas:

\begin{center}
\begin{verbatim}
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
\end{verbatim}
\end{center}


O jogo inicia-se com a seguinte disposição, com duas pedras
de cada cor no centro:

\begin{center}
\begin{verbatim}
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . o x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
\end{verbatim}
\end{center}

Preto começa primeiro e depois os dois adversários alternam
suas jogadas, até que nenhum lado tenha uma jogada válida,
ou  até  o tabuleiro estar totalmente preenchido.
Então o jogador com mais pedras de sua cor ganha o jogo,
podendo haver empate.

O que é uma jogada válida?

É colocar uma pedra no tabuleiro em uma posição 
\begin{enumerate}
\item que deve estar vazia antes da jogada, 
\item ao colocar a pedra deve
   cercar uma ou mais pedras consecutivas do adversário,
    em linha horizontal, vertical ou diagonal.
\end{enumerate}

{\it Cercar} significa ter no meio de duas pedras de mesma
cor uma ou mais pedras consecutivas de outra cor.
Note-se que uma das duas pedras {\it cercantes}
deve ser a recentemente colocada através da jogada.

O resultado da jogada é mudar a cor das pedras cercadas 
para a sua cor.


Por exemplo, preto pode jogar na posição abaixo, pois cerca uma pedra
branca entre duas pedras pretas.


\begin{center}
\begin{verbatim}
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . x o x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
\end{verbatim}
\end{center}


\noindent
resultando no seguinte:


\begin{center}
\begin{verbatim}
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . x x x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
\end{verbatim}
\end{center}

\pagebreak

Branco pode jogar agora, por exemplo, da seguinte forma:

\begin{center}
\begin{verbatim}
               . . . . . . . .
               . . . . . . . .
               . . o . . . . .
               . . x x x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
\end{verbatim}
\end{center}

\noindent
e com isso resulta em:

\begin{center}
\begin{verbatim}
               . . . . . . . .
               . . . . . . . .
               . . o . . . . .
               . . x o x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
\end{verbatim}
\end{center}

Quando um jogador não consegue fazer uma jogada
válida, então perde a vez e passa ao adversário.

Neste exercício-programa você deve escrever um programa para ser um 
dos jogadores do Otelo, digamos o Branco. As jogadas do preto serão obtidas do
teclado (ou do mouse, ou de um outro programa -- veja bônus a seguir). 

Há vários métodos para este tipo de jogo:
método mini-max e método alfa-beta. Faça uma boa busca em nossa biblioteca e
na internet a
respeito de estratégias para jogar. Estas estratégias envolvem, em geral, 
uma função de avaliação de cada
configuração do tabuleiro. Pense que tipo de situações seu programa deve
tentar detectar. 


\noindent
\textbf{Bônus:} Escreva a classe que define a jogada de forma que seja
possível fazer dois programas jogarem um contra o outro. Para isso, combine
com seus colegas uma interface comum para este método, de forma que possamos 
organizar um pequeno campeonato de otelo. 

\end{document}