Durante 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 (anything, rowOrCol, rowAndCol) – 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!