Usando inteligência artificial para resolver o jogo 2048 (código JAVA)

• 7 de abril de 2014
• Vasilis Vryniotis
• . 6 Comentários

Até agora, a maioria de vocês já ouviu/tocou o 2048 jogo por Gabriele Cirulli. É um jogo de tabuleiro simples, mas altamente viciante, que exige que você combine os números das células para chegar ao número 2048. Como esperado, a dificuldade do jogo aumenta à medida que mais células são preenchidas com valores altos. Pessoalmente, apesar de ter passado um bom tempo jogando o jogo, nunca consegui chegar a 2048. Então, a coisa natural a fazer é tentar desenvolver um solucionador de IA em JAVA para vencer o jogo de 2048. 🙂

Neste artigo vou discutir brevemente minha abordagem para construir o Artificial Intelligence Solver do Game 2048, descreverei as heurísticas que usei e fornecerei o código completo que está escrito em JAVA. O código é de código aberto sob licença GPL v3 e você pode baixá-lo em Github.

Desenvolvendo o jogo 2048 em JAVA

O jogo original é escrito em JavaScript, então tive que reescrevê-lo em JAVA do zero. A ideia principal do jogo é que você tenha uma grade 4×4 com valores Integer, todos potências de 2. As células de valor zero são consideradas vazias. Em todos os pontos durante o jogo, você pode mover os valores para 4 direções para cima, para baixo, para a direita ou para a esquerda. Quando você executa um movimento, todos os valores da grade se movem nessa direção e param quando atingem as bordas da grade ou quando atingem outra célula com valor diferente de zero. Se essa célula anterior tiver o mesmo valor, as duas células serão mescladas em uma célula com valor duplo. No final de cada movimento, um valor aleatório é adicionado ao tabuleiro em uma das células vazias e seu valor é 2 com probabilidade de 0.9 ou 4 com probabilidade de 0.1. O jogo termina quando o jogador consegue criar uma célula com valor 2048 (ganha) ou quando não há outras jogadas a fazer (perde).

Na implementação original do jogo, o algoritmo de mesclagem de movimento é um pouco complicado porque leva em consideração todas as direções. Uma boa simplificação do algoritmo pode ser realizada se fixarmos a direção para a qual podemos combinar as peças e girar o tabuleiro de acordo para realizar o movimento. Maurits van der Schee recentemente escreveu um artigo sobre isso que eu acredito que vale a pena conferir.

Todas as classes são documentadas com comentários Javadoc. Abaixo, fornecemos uma descrição de alto nível da arquitetura da implementação:

1. Classe do Conselho

A classe tabuleiro contém o código principal do jogo, que é responsável por movimentar as peças, calcular a pontuação, validar se o jogo foi encerrado etc.

2. ActionStatus e Direction Enum

O ActionStatus e o Direction são 2 enums essenciais que armazenam o resultado de um movimento e sua direção de acordo.

3. Classe de jogo de console

O ConsoleGame é a classe principal que nos permite jogar e testar a precisão do AI Solver.

4. Classe de Solver

O AIsolver é a classe primária do módulo de Inteligência Artificial que é responsável por avaliar o próximo melhor movimento dado um determinado Board.

Técnicas de Inteligência Artificial: Poda Minimax vs Alpha-beta

Várias abordagens foram publicadas para resolver automaticamente este jogo. O mais notável é o desenvolvido por Matt Overlan. Para resolver o problema, tentei duas abordagens diferentes, usando o algoritmo Minimax e usando a poda Alpha-beta.

Algoritmo Minimax

A Minimax é um algoritmo recursivo que pode ser usado para resolver jogos de soma zero de dois jogadores. Em cada estado do jogo associamos um valor. O algoritmo Minimax busca através do espaço de possíveis estados de jogo criando uma árvore que é expandida até atingir uma determinada profundidade predefinida. Uma vez atingidos esses estados folha, seus valores são usados ​​para estimar os dos nós intermediários.

A ideia interessante deste algoritmo é que cada nível representa a vez de um dos dois jogadores. Para vencer, cada jogador deve selecionar o movimento que minimize o pagamento máximo do oponente. Aqui está uma boa apresentação em vídeo do algoritmo minimax:

[Conteúdo incorporado]

Abaixo você pode ver o pseudocódigo do Algoritmo Minimax:

função minimax(nó, profundidade, maximizandoJogador)
    if profundidade = 0 or nó é um nó terminal
        retorno o valor heurístico do nó
    if maximizandoPlayer bestValue := -∞
        para cada filho do nó val := minimax(filho, profundidade - 1, FALSE)) bestValue := max(bestValue, val);
        retorno Melhor valor
    outro
        melhorValor := +∞
        para cada filho do nó val := minimax(filho, profundidade - 1, TRUE)) bestValue := min(bestValue, val);
        retorno Melhor valor
(* Chamada inicial para maximizar o jogador *)
minimax(origem, profundidade, VERDADEIRO)

Poda alfa-beta

A Algoritmo de poda alfa-beta é uma expansão de minimax, que diminui fortemente (poda) o número de nós que devemos avaliar/expandir. Para conseguir isso, o algoritmo estima dois valores, o alfa e o beta. Se em um determinado nó o beta for menor que alfa, o restante das subárvores poderá ser podado. Aqui está uma boa apresentação em vídeo do algoritmo alpha:

[Conteúdo incorporado]

Abaixo você pode ver o pseudocódigo do Algoritmo de poda Alfa-beta:

função alfabetoa(nó, profundidade, α, β, maximizandoJogador)
    if profundidade = 0 or nó é um nó terminal
        retorno o valor heurístico do nó
    if maximizandoJogador
        para cada filho do nó α := max(α, alpha(filho, profundidade - 1, α, β, FALSE))
            if β ≤ α
                quebrar (* corte β *)
        retorno α
    outro
        para cada filho do nó β := min(β, alpha(filho, profundidade - 1, α, β, TRUE))
            if β ≤ α
                quebrar (* corte α *)
        retorno β
(*Chamada inicial*)
alpha(origem, profundidade, -∞, +∞, TRUE)

Como a IA é usada para resolver o jogo 2048?

Para usar os algoritmos acima, devemos primeiro identificar os dois jogadores. O primeiro jogador é a pessoa que joga o jogo. O segundo jogador é o computador que insere valores aleatoriamente nas células do tabuleiro. Obviamente, o primeiro jogador tenta maximizar sua pontuação e alcançar a fusão de 2048. Por outro lado, o computador no jogo original não está especificamente programado para bloquear o usuário selecionando o pior movimento possível para ele, mas insere valores aleatoriamente nas células vazias.

Então, por que usamos técnicas de IA que resolvem jogos de soma zero e que assumem especificamente que ambos os jogadores selecionam o melhor movimento possível para eles? A resposta é simples; apesar de ser apenas o primeiro jogador que tenta maximizar sua pontuação, as escolhas do computador podem bloquear o progresso e impedir o usuário de completar o jogo. Ao modelar o comportamento do computador como um jogador ortológico não aleatório, garantimos que nossa escolha será sólida, independentemente do que o computador joga.

A segunda parte importante é atribuir valores aos estados do jogo. Este problema é relativamente simples porque o próprio jogo nos dá uma pontuação. Infelizmente, tentar maximizar a pontuação por conta própria não é uma boa abordagem. Uma razão para isso é que a posição dos valores e o número de células com valores vazios são muito importantes para ganhar o jogo. Por exemplo, se espalharmos os valores grandes em células remotas, seria muito difícil para nós combiná-los. Além disso, se não tivermos células vazias disponíveis, corremos o risco de perder o jogo a qualquer minuto.

Por todas as razões acima, várias heurísticas foram sugeridos como a Monoticidade, a suavidade e os Free Tiles do tabuleiro. A ideia principal não é usar apenas a pontuação para avaliar cada estado do jogo, mas sim construir uma pontuação composta heurística que inclua as pontuações mencionadas.

Por fim, devemos observar que, embora eu tenha desenvolvido uma implementação do algoritmo Minimax, o grande número de estados possíveis torna o algoritmo muito lento e, portanto, a poda é necessária. Como resultado na implementação JAVA eu uso a expansão do algoritmo de poda Alpha-beta. Além disso, ao contrário de outras implementações, não aparo agressivamente as escolhas do computador usando regras arbitrárias, mas levo todas elas em consideração para encontrar a melhor jogada possível do jogador.

Desenvolvendo uma função de pontuação heurística

Para vencer o jogo, tentei várias funções heurísticas diferentes. O que achei mais útil é o seguinte:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

A função acima combina a pontuação real do quadro, o número de células/telhas vazias e uma métrica chamada pontuação de agrupamento, que discutiremos mais adiante. Vamos ver cada componente com mais detalhes:

1. Pontuação real: Por razões óbvias, quando calculamos o valor de uma prancha temos que levar em conta sua pontuação. Placas com pontuações mais altas são geralmente preferidas em comparação com placas com pontuações mais baixas.
2. Número de células vazias: Como mencionamos anteriormente, manter poucas células vazias é importante para garantir que não perderemos o jogo nas próximas jogadas. Estados de placa com mais células vazias são geralmente preferidos em comparação com outros com menos. Surge uma pergunta sobre como avaliaríamos essas células vazias? Na minha solução, eu os peso pelo logaritmo da pontuação real. Isso tem o seguinte efeito: quanto menor a pontuação, menos importante é ter muitas células vazias (isso ocorre porque no início do jogo combinar as células é bastante fácil). Quanto maior a pontuação, mais importante é garantir que tenhamos células vazias em nosso jogo (isso porque no final do jogo é mais provável perder devido à falta de células vazias.
3. Pontuação de agrupamento: Usamos a pontuação de agrupamento que mede o quão dispersos são os valores do nosso conselho. Quando células com valores semelhantes estão próximas, elas são mais fáceis de combinar, o que significa que é mais difícil perder o jogo. Nesse caso, a pontuação de agrupamento tem um valor baixo. Se os valores do tabuleiro estiverem dispersos, essa pontuação recebe um valor muito grande. Essa pontuação é subtraída das duas pontuações anteriores e funciona como uma penalidade que garante que as placas agrupadas sejam preferidas.

Na última linha da função, garantimos que a pontuação não seja negativa. A pontuação deve ser estritamente positiva se a pontuação da prancha for positiva e zero somente quando a prancha da pontuação for zero. As funções max e min são construídas para que tenhamos esse efeito.

Finalmente, devemos observar que quando o jogador atinge um estado de jogo terminal e não são permitidos mais movimentos, não usamos a pontuação acima para estimar o valor do estado. Se o jogo for ganho, atribuímos o maior valor inteiro possível, enquanto se o jogo for perdido, atribuímos o menor valor não negativo (0 ou 1 com lógica semelhante ao parágrafo anterior).

Mais sobre a pontuação de clustering

Como dissemos anteriormente, a pontuação de agrupamento mede o quanto dispersos estão os valores do tabuleiro e funciona como uma penalidade. Construí essa partitura de forma a incorporar dicas/regras de usuários que “dominaram” o jogo. A primeira regra sugerida é que você tente manter as células com valores semelhantes próximas para combiná-las mais facilmente. A segunda regra é que as células de alto valor devem estar próximas umas das outras e não aparecer no meio do tabuleiro, mas sim nas laterais ou cantos.

Vamos ver como a pontuação de agrupamento é estimada. Para cada célula do tabuleiro estimamos a soma das diferenças absolutas de suas vizinhas (excluindo as células vazias) e tiramos a diferença média. A razão pela qual tomamos as médias é evitar contar mais de uma vez o efeito de duas células vizinhas. A pontuação total de agrupamento é a soma de todas essas médias.

A pontuação de clustering tem os seguintes atributos:

1. Obtém valor alto quando os valores do tabuleiro estão dispersos e valor baixo quando células com valores semelhantes estão próximas umas das outras.
2. Não supera o efeito de duas células vizinhas.
3. As células nas margens ou cantos têm menos vizinhos e, portanto, pontuações mais baixas. Como resultado, quando os valores altos são colocados perto das margens ou cantos, eles têm pontuações menores e, portanto, a penalidade é menor.

A precisão do algoritmo

Como esperado, a precisão (também conhecida como a porcentagem de jogos ganhos) do algoritmo depende muito da profundidade de pesquisa que usamos. Quanto maior a profundidade da busca, maior a precisão e mais tempo de execução. Nos meus testes, uma busca com profundidade 3 dura menos de 0.05 segundos, mas dá 20% de chance de ganhar, uma profundidade de 5 dura cerca de 1 segundo, mas dá 40% de chance de ganhar e, finalmente, uma profundidade de 7 dura 27-28 segundos e dá cerca de 70-80% de chance de ganhar.

Expansões futuras

Para aqueles que estão interessados ​​em melhorar o código, aqui estão algumas coisas que você pode analisar:

1. Melhore a velocidade: Melhorar a velocidade do algoritmo permitirá que você use maior profundidade e, assim, obtenha melhor precisão.
2. Criar gráficos: Há uma boa razão pela qual a implementação de Gabriele Cirulli se tornou tão famosa. É bonito olhar! Eu não me incomodei em desenvolver uma GUI, mas sim imprimir os resultados no console, o que torna o jogo mais difícil de seguir e jogar. Criar uma boa GUI é uma obrigação.
3. Sintonize Heurísticas: Como mencionei anteriormente, vários usuários sugeriram heurísticas diferentes. Pode-se experimentar a forma como as pontuações são calculadas, os pesos e as características do tabuleiro que são levados em consideração. Minha abordagem de medir a pontuação do cluster deve combinar outras sugestões, como Monotonicidade e Suavidade, mas ainda há espaço para melhorias.
4. Ajustando a profundidade: Pode-se também tentar ajustar/ajustar a profundidade da busca dependendo do estado do jogo. Você também pode usar o Pesquisa em profundidade de aprofundamento iterativo algoritmo que é conhecido por melhorar o algoritmo de poda alfa-beta.

Não se esqueça de baixar o código JAVA de Github e experimentar. Espero que você goste desse post! Se você fez, por favor, tome um momento para compartilhar o artigo no Facebook e Twitter. 🙂