I.A Jogo 2048

Thiago,

Como esse problema envolve incerteza no ambiente (os números aleatórios que surgem), acredito que duas abordagens que poderiam funcionar são:

1. Utility Agent simplificado: Toda vez que chega o turno do agente (a hora de apertar a setinha pra fazer algo no tabuleiro), ele vai simplesmente avaliar as possibilidades (apertar esquerda, cima, direita ou baixo, quando possível) e decidir qual gera o melhor outcome para ele. Um outcome seria uma espécie de nota, ou valor para um estado tabuleiro. Imagine que existe uma função mágica chamada calcularValorDoEstado(tabuleiro), que retorna um número. O algoritmo seria mais ou menos assim (pseudo-código, meio python, meio qualquer coisa hehe):

   funcao tomarDecisao(jogo):
       tabuleiro = jogo.getTabuleiro()
       acoesPossiveis = tabuleiro.getAcoesPossiveis()
       melhorValor = null;
       melhorAcao = null;
       for acao in acoesPossiveis:
           valor = calcularValorDoEstado(tabuleiro)
           if valor melhor que melhorValor:
               melhorValor = valor
               melhorAcao = acao
       return melhorAcao // retorna a acao que gera o melhor tabuleiro, de acordo com a funcao calcularValorDoEstado
   

   O problema é implementar essa função, calculaValorDoEstado. Você precisa converter o estado em um número, de forma que o algoritmo consiga diferenciar dois tabuleiros e decidir qual deles é melhor, para que possa tomar a melhor ação. Você pode pontuar várias características do tabuleiro, como:

   • Beneficiar pela quantidade de peças que vai ficar no tabuleiro após o movimento (quanto menos peças melhor)
   • Beneficiar pela quantidade de peças que pode ser juntada na próxima jogada, depois dessa que está sendo analisada (mais peças para juntar = melhor)
   • Penalizar (retorna um número negativo) se aquele movimento acaba com o jogo e é uma derrota
   • Beneficiar absurdamente se aquele movimento ganha o jogo (monta o 2048)

   Enfim, modelar uma função dessa é uma arte. Recomendo a leitura do livro Artificial Intelligence: A modern approach, do Stuart Russell/Peter Norvig. Tem tudo lá!

2. Busca com a árvore E/Ou (And/Or Tree): também tem no livro do Russell. Resumindo, você vai criar um plano de contenção (uma árvore e/ou), que prevê todas as possibilidades de aparecimento de números no tabuleiro e possui uma solução para todas elas. Eu não sei se tem como fazer isso, porque a árvore de busca desse jogo parece ser gigantesca. Essa solução com certeza iria resolver o problema, porque ia prever tudo (resolver não significa ganhar sempre, porque existe a aleatoriedade. O jogo pode simplesmente te dar uma rasteira colocando um bloco 2 no meio dos teus dois blocos 1024). Vale a pena tentar pra ver no que dá.

Entre as várias outras possíveis abordagens, tem uma que pode ser bem interessante:

Existem algoritmos para tentar prever o modelo probabilístico do ambiente. Você pode tentar fazer um agente capaz de tentar prever quais são os próximos números que vão aparecer, e onde. O agente aprende errado, e fica cada vez melhor no jogo. Porém, isso tudo cai por água a baixo se o algoritmo do jogo for completamente aleatório. De novo, tem muito material sobre isso no livro do Russell (tem dois capítulos extremamente fodas sobre isso lá, Probabilistic Reasoning e Learning Probabilistic Models).

Mais uma vez, mencionando o livro do Russell, existem outras várias possíveis soluções para lidar com a incerteza do ambiente. Vale a leitura, com certeza!

Boa sorte