MIH SWAT

Eu adoro jogos de computador e videogames, especialmente jogos online. No entanto, algo que me incomoda é que sempre tem gente com muito tempo livre e que acaba ganhando vantagens por causa disso. Como compensar isso?

A resposta é usar programação. Já fiz isso algumas vezes. Ao jogar Hattrick tinha dificuldades para negociar jogadores, pois era feito através de um sistema de leilão. Estar online próximo ao fim do leilão era fundamental para obter jogadores a um preço baixo. Ficar acordado até a madrugada seria impossível. Tinha gente que colocava despertador pra acordar na hora, mas eu nunca fui adepto de tais exageros. Então eu criei um programa que fazia parser na pagina do leilão e dava os lances de acordo com alguns parâmetros pré-definidos. Ele acabou ganhando outras funções e vários dos meus amigos usaram por bastante tempo, mesmo depois de eu ter parado de jogar Hattrick.
Agora jogo World of Warcraft e continuo sem muito tempo livre. Como ter alguma vantagem. Usar os itens corretos (armaduras, armas etc.) pode ajudar. O WOW é um jogo muito complexo e seria impossível fazer isso manualmente. Então o Tadeu, aqui da SWAT Brasil que também joga WOW, sugeriu que fizéssemos um programa para achar as melhores opções. Calcular todas as opções iria demorar muito tempo. A solução é usar alguma heurística. A primeira opção que vem na mente é usar algoritmos genéticos. Acabei me lembrando de um algoritmo que usei há muito tempo atrás chamado “Simulated Annealing“.
“O algoritmo Simulated Annealing baseia-se no fato de que quando um material é fundido e resfriado lentamente, este material atinge um estado de cristalização onde as moléculas estão perfeitamente ordenadas. O algoritmo especifica uma temperatura inicial, uma função de decremento da temperatura, uma condição de equilíbrio para cada temperatura e uma condição de convergência”.
Em termos computacionais, o Simulated Annealing é usado para achar a melhor configuração de um sistema minimizando (ou maximizando) o valor de uma função de custo associada. No caso do WOW podemos utilizar os valores de Attack Power (AP) e o Armor combinados para gerar uma função de custo. Variando os itens escolhidos, teremos diferentes valores de AP e Armor e conseqüentemente um custo diferente. O objetivo final é obter a melhor configuração de itens que resulte no maior valor de ambos os parâmetros dentro de uma certa proporção.
O primeiro passo é escolher uma configuração inicial. Isso pode ser obtido por uma escolha aleatória ou por alguma heurística simples. A partir daí começa o algoritmo propriamente dito. Ele faz uma troca aleatória de alguns dos itens. Usualmente para os diferentes tipos de classes de personagens (Warrior, Priest, Paladin, etc), temos uma infinidade de itens disponíveis. Com isto gera-se um novo estado para o sistema e calcula-se um novo custo. A variação do custo Δc = c1 – c2, também é calculada. Se Δc < 0, essa nova configuração passa a ser a configuração atual do sistema. Se Δc ≥ 0, a nova configuração é aceita com probabilidade , onde t é a temperatura atual do sistema. Caso contrário é rejeitada e volta-se ao estado anterior. A probabilidade de se aceitar uma configuração que gere Δc ≥ 0, serve para evitar que a função de custo fique confinada a um máximo local. Aceitando trocas ruins, o algoritmo espera que em passos futuros, as trocas subseqüentes originem uma configuração mais favorável. Deve-se lembrar que este método é heurístico. No início do algoritmo de Annealing, quando a temperatura é mais alta, a probabilidade de aceitar trocas ruins é maior. Conforme decresce a temperatura, o sistema tende a buscar um maior equilíbrio. Essa situação é uma analogia com o processo físico de fundição de materiais, pois quando submetidas a altas temperaturas, as moléculas ficam em um estado de completa desordem.
O algoritmo possui uma condição de equilíbrio para cada temperatura. Para o sistema passar para uma temperatura mais baixa, deve ocorrer um número fixo de iterações sem que a configuração atual tenha mudado, ou seja, sem que tenha sido encontrada um configuração melhor. Isto faz com que o algoritmo encontre uma melhor solução entre uma vizinhança de soluções (um máximo local). Os parâmetros do algoritmo, como temperatura inicial, numero de iterações até o equilíbrio etc., geralmente são estabelecidos empiricamente e devem ser ajustados com o uso do algoritmo.
Por incrível que pareça (eu não acreditei até ver os resultados) o algoritmo converge para uma solução próxima ao ótimo. Estamos pensando em implementar em Python e acho que vai ser bem divertido.

English version

Related posts:

1. Game Theory: Maximizing your chances