Otelo

MAC323 - Estruturas de Dados - Exerc�cio Programa Otelo

Otelo, tamb�m conhecido por Riversi, � um jogo que usa um tabuleiros, com dois jogadores. Um jogador (vou chamar de Branco) joga com pedras brancas (denotadas aqui por ``o'') e outro chamado Preto joga com pedras pretas (denotadas por ``x'').

(Uma maneira pr�tica � usar pedras coloridas brancas num lado e pretas noutro. Virando a pedra muda a sua cor.)

               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .

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

               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . o x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .

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.

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 cercantes deve ser a recentemente colocada atrav�s da jogada.

Por exemplo, Preto pode jogar na posi��o abaixo, pois cerca uma pedra branca entre duas pedras pretas.

               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . x o x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .

               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . x x x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .

               . . . . . . . .
               . . . . . . . .
               . . o . . . . .
               . . x x x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .

               . . . . . . . .
               . . . . . . . .
               . . o . . . . .
               . . x o x . . .
               . . . x o . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .

O trabalho � escrever um programa para ser um dos jogadores do Otelo, digamos o Branco.

Para simplicar, dado o pouco tempo que sobra at� o final do semestre, podem simplificar bem a parte visual, usando a mesma nota��o como neste enunciado.

Suponha que o advers�rio inicia a primeira jogada. O programa basicamente repete o seguinte at� terminar o jogo:

(O m�todo mais sofisticado � o alfa-beta, que dou uma breve explica��o mas a sua implementa��o necessitaria mais estudos. Um artigo est� referenciado abaixo.)

Uma sugest�o � decompor o programa escrevendo v�rios procedimentos, alguns dos quais podem ser:

Dada uma configura��o do tabuleiro, vamos discutir como o programa pode decidir qual a jogada a fazer. Na figura abaixo ``minha jogada'' significa a jogada do computador.

$\begin{figure} \centerline{ \epsfxsize 17cm \epsfbox{minimax.eps}} \end{figure}$

(Nota: essa figura n�o � vis�vel para quem est� usando html, tem que usar postscript para ver a figura, sorry...)

A raiz (primeiro n�vel da figura) da �rvore de jogo acima representa uma dada configura��o do tabuleiro. As ra�zes de suas sub�rvores (segunda n�vel) representam todas as novas configura��es que podem ser alcan�adas com a minha jogada. Por sua vez, com a jogada do advers�rio, podem ser geradas as configura��es representadas pelas n�s do terceiro n�vel, e assim sucessivamente. O arco que une as ramifica��es representa jogada do advers�rio. � preciso entender, como � �bvio, que eu tenho controle sobre a minha jogada, mas n�o sobre como o advers�rio vai jogar. As jogadas do advers�rio s�o portanto marcadas com o arco para distinguir das minhas jogadas.

No m�todo mini-max, dada uma configura��o do tabuleiro (a raiz), geram-se as poss�veis jogadas at� uma certa profundidade, parando sempre com as configura��es geradas pelo advers�rio. A gera��o dos n�s (configura��es do tabuleiro) segue a ordem por largura, ou seja n�vel por n�vel da esquerda para a direita (breadth-first).

Para cada n� terminal (isto �, os n�s do �ltimo n�vel) da �rvore assim gerada, procuro atribuir um valor ou uma nota atrav�s de uma fun��o de avalia��o f.

Tanto maior a nota, mais favor�vel � a configura��o para mim; ao passo que tanto menor � a nota melhor � para o meu advers�rio. Em outras palavras, eu procuro maximizar a nota, enquanto que o meu advers�rio procura minimizar a nota.

� muito importante saber como definir essa fun��o de avalia��o. Ela tem a ver com a estrat�gia do jogo. A escolha da fun��o pode muitas vezes acabar determinando se o programa vai jogar bem ou mal.

No caso do Otelo, uma fun��o simples � ditada pela estrat�gia gulosa, como se segue:

f ( configura��o ) = n�mero das minhas pe�as - n�mero das pe�as do advers�rio.

Suponha que j� atribu�mos notas a todos os n�s terminais atrav�s da fun��o de avalia��o. Vamos agora proceder de baixo para cima em dire��o � raiz da �rvore. Repare os 3 n�s terminais mais a esquera, com notas 5, 10 e 20. Para escolher uma jogada entre as 3 que geram essas notas, o advers�rio naturalmente iria escolher a mais esquerda, isto �, aquela jogada que d� a menor nota (5). Com isso obtenho as notas do n�vel acima dos n�s terminais, usando sempre o m�nimo das notas. Subindo mais um n�vel, como a� � a minha jogada, posso escolher sempre aquela que maximiza a nota. Assim sucessivamente, usando alternadamente m�nimo e m�ximo, chego finalmente ao n�vel das n�s gerados pela raiz. A� � a minha vez de jogar, ent�o escolho aquela jogada que d� a maior nota (no caso 5). Essa jogada est� indicada pela seta da figura. A decis�o da jogada est� assim feita.

A estrat�gia gulosa (onde a fun��o de avalia��o � simplesmente a diferen�a entre as quantidades de pedras de cada lado) n�o � uma boa estrat�gia. Ou pelo menos ela sozinha n�o � suficiente para obter um bom programa.

               C . . . . . . C
               . X . . . . X .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . . . . . . . .
               . X . . . . X .
               C . . . . . . C

Um outra estrat�gia comum � de ponderar as posi��es. Os quatro cantos do tabuleiro (C) s�o as posi��es mais est�veis e devem receber um peso alto. As demais posi��es da borda do tabuleiro tamb�m s�o boas em termos de estabilidade. Por outro lado a posi��o marcada com X na figura anterior � altamente n�o desej�vel, pois pode permitir o advers�rio conseguir o canto.

Outras estrat�gias mais sofisticadas existem. Uma id�ia pouco intuitiva � a chamada mobilidade. Mobilidade tem a ver com o n�mero de poss�veis jogadas de cada jogador. Tanto maior � o n�mero de possibilidades, melhor para este jogador pois ele tem mais escolha (o que � obvio) e portanto ele n�o se sujeita a situa��o em fica for�ado a fazer uma jogada numa posi��o desfavor�vel.

Sejam C = n�mero de poss�veis jogadas minhas (do computador) e A = n�mero de poss�veis jogadas do advers�rio.

A mobilidade pode ser expressa por alguma fun��o envolvendo a diferen�a C - A.

A fun��o de avali��o pode ser uma combina��o das diversas estrat�gias.

No m�todo mini-max, todos os n�s terminais at� uma certa profundidade s�o primeiro gerados. Depois todos esses n�s terminais s�o avaliados e os valores obtidos retornados at� a raiz da �rvore pelo mini-max.

No m�todo alfa-beta, vamos usar a ordem por profundidade (depth-first) para gerar os n�s da �rvore. Uma grande diferen�a � que, assim que um n� terminal � gerado, o seu valor � obtido atrav�s da fun��o de avalia��o. Um valor ``tempor�rio'' � retornado � raiz. Desse modo � poss�vel n�o ter que gerar todos os n�s como no m�todo mini-max, pois aquelas sub�rvore desnecess�rias s�o podadas. Para a mesma profundidade dos n�s terminais, o m�todo alfa-beta pode levar bem menos tempo que o m�todo mini-max, devido a essa poda��o. Em ingl�s, esse m�todo � conhecido pelo nome de alpha-beta pruning. A redu��o no n�mero de n�s gerados permite muitas vezes aumentar a profundidade da �rvore para decidir a melhor jogada.

Considere a seguinte figura, onde os n�s s�o gerados por depth-first. A profundiade adotada � apenas 2, para simplificar a ilustra��o. N� A j� gerou todos os seus n�s terminais que s�o avaliados retornando o valor 5 ao n� A.

$\begin{figure} \centerline{ \epsfxsize 15cm \epsfbox{alfa-beta.eps}} \end{figure}$

(Nota: essa figura n�o � vis�vel para quem est� usando html, tem que usar postscript para ver a figura, sorry...)

O n� raiz pode receber o valor provis�rio VP de 5. Dependendo de valores retornados pelos outros sucessores da raiz, o valor final da raiz pode ser $\geq$ ao valor VP que � 5 mas n�o pode ser menor.

Agora suponha a gera��o do primeiro sucessor de B, n� Cque tem valor 5. B pode receber o valor provis�rio 5. De novo, dependendo dos valores dos outros sucessores de B, o valor final de B pode ser $\leq$ o valor VP que � 5 mas n�o pode ser maior.

Podemos ent�o observar que o valor final de B n�o pode exceder o valor VP da raiz e assim podemos descontinuar a gera��o de n�s abaixo de B. Dizemos que podamos a sub�rvore abaixo de B. Isso � poss�vel pois garantimos que B n�o � melhor que A.