A ver posts de Agosto de 2012

LikeFriendsPronto, mais um projecto lançado, mais um making of para podermos partir para outra. Não vou voltar a passar pelas coisas do costume (sim, voltei a usar a Yii, voltei a usar SASS e Compass) e também não vou voltar a falar do jogo do galo, nem da racionalização matemática por trás do LikeFriends.

Vamos lá.

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.

LikeFriendsLancei (finalmente) esta semana o LikeFriends, o meu pequeno projecto de Verão. É um brinquedo social, engraçado como conceito, que apresenta dois rankings baseados nos likes e amigos do Facebook, um de amigos, outro de likes.

Eu podia dar motivações perfeitamente válidas como uma melhoria do ranking de amigos que o próprio Facebook faz (e mesmo esse está absurdamente escondido aqui, à direita – para se chegar lá, é preciso ir aos nossos likes e depois clicar em Sugestões, no topo) ou até como negócio; mas não: só encontrei o ranking (errado) do Facebook quando estava na fase de investigação deste projecto e o site do projecto não está, nem vai estar, monetizado.

Na verdade, fi-lo porque podia. Só isso. Há muito que queria experimentar umas coisas com métricas sociais, mas que fosse algo útil; ao mesmo tempo, andava a brincar com a API do Facebook e resolvi juntar as duas coisas. Ora, a única coisa que contém um espaço métrico no Facebook é a relação entre os likes e os utilizadores.

Afinal, que raio de ranking é aquele?

Versão TL;DR

Um ranking feito unicamente a partir dos likes que dois utilizadores partilham não é preciso.

Se eu tenho 50 likes e tenho 10 em comum com dois dos meus amigos, qual deles é o mais parecido comigo, o que tem 100 likes ou o que têm 500? Com um amigo que tem uma quantidade enorme de likes até seria de estranhar se não tivesse alguns em comum; por outro lado, se outro amigo tem tão poucos likes e mesmo assim tem alguns em comum comigo, quer dizer que, efectivamente, temos gostos muito mais semelhantes.

Aviso: a próxima secção inclui matemática!

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