Fluxograma de estratégiaDurante o desenvolvimento do LikeFriends, fui fortemente coagido a desenvolver um passatempo pela beta-tester, que, incidentalmente, é também minha esposa. A escolha recaiu sobre o jogo do galo, e o código foi colocado no GitHub. Este post é uma tradução do README que acompanha o meu repositório TicTacToeJS, no GitHub.

Existem três maneiras de fazer uma AI de jogo imbatível:

  1. Processar cada jogada possível adiantadamente e jogar pela linha de maior sucesso a cada passo – isto é um método de força bruta;
  2. Implementar uma rede neuronal – isto vai começar bastante palerma, mas depois de alguns milhares de jogos deverá ser imbatível;
  3. Implementar uma solução heurística, fazendo-a jogar como um especialista humano.

O jogo do galo é um fortíssimo candidato a uma solução de força bruta: o número total de jogadas é de apenas 9!, ou 362.880; de facto, seriam muito menos, visto que a maioria das jogadas poderia ser obtida por rotação do tabuleiro de jogo. No entanto, não existe grande "I" nesta AI...

A solução por rede neuronal é bastante divertida, e é usada frequentemente em cenários complexos, desde que alguém tenha o tempo (ou os jogos automatizados) para treinar a rede. Aparte o código da rede neuronal em si (que poderia ser usada para paletes de outros problemas), esta solução seria a mais pequena ao nível do código.

A solução heurística é a mais difícil de implementar para a maioria dos jogos. Implica criar um conjunto de regras a seguir, para cada situação possível, da forma mais compacta possível. De novo, o jogo do galo é propício a este tipo de solução, porquanto apenas três jogadas, no máximo, podem ser problemáticas; a quarta e a eventual quinta jogada são feitas para ganhar ou para empatar.

Esta foi a solução que implementei.

Rápido resumo de partes importantes do código

A cada passo, é feito um pedido de jogada (função playChoose, com um quê e um onde (what e where):

  • O quê pode ser centro (center), canto (corner), parede (wall), uma combinação destes, ou indefenido, que é interpretado como qualquer coisa;
  • O onde é um objecto com um quê (what) e um ou mais de eu, tu ou nenhum (me, you, none):
    • O quê é o que procurar no tabuleiro: os valores válidos são qualquer coisa, fila ou coluna e fila e coluna (anythingrowOrColrowAndCol) – outros podiam ser implementados, mas não são necessários, logo...
    • eu, tu e nenhum são as quantidades de jogadas no quê: 0, 1 ou 2.

Portanto, eu posso pedir qualquer coisa como playChoose(undefined, {what: "anything", me: 2}), que procurará uma posição livre onde já exista uma fila, coluna ou diagonal com duas jogadas minhas. Isto é efectivamente usado no jogo, e é uma busca por uma jogada para ganhar. Pode ser vista na função play. Sempre que há uma jogada para fazer, são colocadas ao motor de jogo as seguintes questões:

  • Posso ganhar já?
  • Se não posso, tenho que bloquear uma posição de vitória do adversário?

Se tudo correu da forma normal (isto é, nem posso ganhar já, nem o adversário tem uma posição de vitória iminente), é preciso fazer uma jogada estratégica (por oposição a uma jogada reactiva, que é o caso das outras). Eu não vou explicar as opções estratégicas do jogo do galo, mas o fluxograma que acompanha este post contém toda a estratégia, tal como é implementada na função strategicPlay.

Um último aviso em relação ao código: cuidado com a rotação do tabuleiro que faço na função playChoose. Podia ter obtido os mesmos resultados de dezenas de outras maneiras, mas esta foi a que me pareceu mais elegante, embora admita que não seja a mais fácil de compreender.

Como usar em qualquer lado

O código usa intensivamente jQuery. Isto foi feito para o LikeFriends, que já o tinha, mais valia usá-lo. Não é uma extensão para o jQuery, pelo que é relativamente fácil de dissociar.

Antes de mais nada, é necessário incluir o ficheiro .js do repositório (ou uma versão minificada e gzipada) na página. Depois, criar um elemento para servir de contentor (um simples div chega) e formatar os estilos dos componentes do jogo via CSS. Incluí no repositório um ficheiro SCSS com tudo o que é necessário (já falei sobre SASS anteriormente, mas cá fica novamente a ligação para a documentação).

Finalmente, onde quer que dê jeito, é só chamar a inicialização (o primeiro parâmetro é o id do contentor):

tictactoe.init('ticTacToeHolder');

Se for necessário, como segundo parâmetro, pode ser passado um objecto com as traduções necessárias ao jogo –  as inglesas estão integradas, mas o jogo pode ser inicializado em português da seguinte forma:

tictactoe.init(
    'ticTacToeHolder',
    {
        me: "Eu",
        you: "Tu",
        ties: "Empates",
        iwon: "Ganhei!",
        youwon: "Ganhaste!",
        tie: "É um empate!"
    }
);

Basicamente, é isto. Divirtam-se!

Partilhar no Sapo Links Partilhar no del.icio.us Partilhar no Digg Partilhar no Twitter Partilhar no StumbleUpon Partilhar no MySpace Partilhar no Facebook

Comentários Deixar um comentário

 Categorias
 Arquivo
 Projectos em Destaque
 Últimas Postas no Blog
 Últimos Comentários do Blog