Gráficos com R e ggplot2

Olá pessoal, tudo certo? No post de hoje vamos fugir um pouco dos algoritmos e dar uma olhada em algo bastante importante para quem lida com análise de dados e estatística: como criar gráficos complexos e bonitos, de maneira rápida e fácil? A resposta: usando Linguagem R e o pacote ggplot2!

Como comentado no post sobre Tetris e algoritmos genéticos, R é uma linguagem de programação open source voltada para análise estatística e gráfica, sendo hoje em dia bastante utilizada por diversas empresas, incluindo Google, Pfizer, Merck, Bank of America, Shell, entre outras.

Computer art - parte 2

No post anterior implementamos o framework básico que nos permite aplicar o algoritmo a qualquer problema. O desafio agora é encontrar uma maneira de 'traduzir' um vetor de polígonos (nossa aproximação da imagem) em um cromossomo, e implementar um método getFitness que nos diga a qualidade de nossa aproximação. Antes disso vamos definir algumas classes utilitárias para nos auxiliar com as imagens e com a configuração de parâmetros.

Computer art - parte 1

Olá pessoal, tudo certo? No post de hoje temos um desafio interessante para um algoritmo evolucionário: dado uma determinada imagem e um número fixo de polígonos semi-transparentes, será que conseguimos aproximar a imagem de maneira satisfatória, em um tempo razoável? Como você deve ter adivinhado, a resposta é sim, podemos! Observe as imagens abaixo:

Após 2386 gerações:

Após 17451 gerações:

Após 121076 gerações:

Imagem original:

Nas imagens acima vemos que mesmo com poucas gerações, obtemos bons resultados. Por exemplo, a imagem do centro (linha 2, coluna 2) foi formada em 8094 gerações, tomando pouco mais de 5 minutos de execução no meu MacBook Pro (2.4 GHz, 4 GB). Neste post vou mostrar como fazer isso da maneira mais simples possível, então mãos a obra!

Othello e Minimax com poda alpha beta - parte 2

No post anterior criamos o framework básico do game e vimos (de forma bem simplificada) alguns conceitos sobre o Minimax. Neste post vamos colocar esses conceitos em prática, além de utilizar poda alfa - beta e ordenação de lances para melhorar o desempenho da engine, fundamental caso você esteja desenvolvendo para alguma plataforma mobile.

Othello e Minimax com poda alpha beta - parte 1

Olá pesssoal, tudo bem? Nesse post vamos aplicar o famoso Minimax com poda alfa-beta, um dos meus algoritmos preferidos. Como aplicação, não queria escolher algo tão simples como Tic-Tac-Toe, nem tão complexo como xadrez. Foi aí que eu descobri o jogo Othello, também conhecido como Reversi.

Nosso objetivo é criar uma engine simples, mas que jogue de maneira convincente. O interessante no Othello é que o jogo ainda não foi 'resolvido' computacionalmente, pelo menos no tabuleiro padrão 8 x 8. Além disso é extremamente simples de aprender, e as estratégias básicas são fáceis de codificar. Caso não conheça o jogo, visite o link acima e tente algumas applets, depois volte aqui!

Tetris e algoritmos genéticos em Java - parte 3

Finalmente, chegamos a parte mais interessante da série: implementar a GA. Partindo de uma população randômica de k agentes, cada um será testado em uma série de n games aleatórios, conforme discutido no post anterior. A cada geração, os agentes de maior desempenho terão uma probabilidade maior de serem selecionados para reprodução, o que dará origem aos membros da próxima geração, e assim sucessivamente.

Usaremos uma GA contínua, com operações de mutação e crossover relativamente simples, mas que parecem funcionar bem em diversos casos. O encode/decode de um cromossomo binário requer um pouco mais de código e provavelmente o desempenho seria inferior, por isso o evitamos.

O algoritmo nos retornará uma lista com o histórico de todas as gerações, assim podemos visualizar claramente a evolução dos agentes ao longo do tempo. Há uma infinidade de dados e estatísticas interessantes que podem ser modelados, por exemplo: qual a distribuição de probabilidade do número de linhas removidas por um determinado agente? Dado um determinado agente, qual a distribuição de probabilidade da altura da grade? Estamos interessados na evolução dos agentes, por enquanto.

Lembrando que os agentes não sabem qual a próxima peça, o que levante outra questão interessante: qual efeito isso causa no desempenho do agente? As distribuições de probabilidade comentadas acima serão as mesmas? Hora de sujar as mãos...

Tetris e algoritmos genéticos em Java - parte 2

No post anterior implementamos o cliente Tetris e testamos sua funcionalidade. Na segunda parte da série, daremos início a parte realmente interessante: AI. Para começar, a classe TetrisAgent será discutida em detalhes, já que os agentes serão a população alvo do algoritmo. Além disso iremos implementar duas classes que definem habilidades importantes: listar os lances possíveis e avaliar as posições resultantes.