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:
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.
A cada passo, é feito um pedido de jogada (função playChoose
, com um quê e um onde (what
e where
):
center
), canto (corner
), parede (wall
), uma combinação destes, ou indefenido, que é interpretado como qualquer coisa;what
) e um ou mais de eu, tu ou nenhum (me
, you
, none
):
anything
, rowOrCol
, rowAndCol
) – outros podiam ser implementados, mas não são necessários, logo...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:
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.
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!