What is the Optimal Algorithm for the Game 2048?
introdução
2048 é um emocionante jogo de mudança de azulejos, onde movemos as peças para combiná-las, visando valores de azulejos cada vez maiores.
neste tutorial, vamos investigar um algoritmo para tocar 2048, que irá ajudar a decidir os melhores movimentos a fazer em cada passo para obter a melhor pontuação.
como jogar 2048
um jogo de 2048 é jogado em uma placa de 4×4., Cada posição na placa pode estar vazia ou conter uma peça, e cada peça terá um número nela.
quando começarmos, a placa terá duas peças em locais aleatórios, cada uma das quais tem um “2” ou um “4” nela – cada uma tem uma chance independente de 10% de ser um “4”, ou de outra forma a é um “2”.os movimentos de
são realizados deslocando todas as peças para uma aresta para cima, para baixo, para a esquerda ou para a direita., Ao fazer isto, todas as peças com o mesmo valor que são adjacentes umas às outras e que se movem juntas irão juntar-se e acabar com uma nova peça igual à soma das duas anteriores:
Depois de termos feito um movimento, será colocada uma nova peça no tabuleiro. Isto é colocado em um local Aleatório, e será um “2” ou um “4” da mesma forma que os azulejos iniciais – “2” 90% do tempo e “4” 10% do tempo.
o jogo então continua até que não haja Mais jogadas possíveis.
em geral, o objetivo do jogo é alcançar uma única peça com um valor de “2048”., No entanto, o jogo não pára aqui, e podemos continuar a jogar o mais longe possível, visando a maior telha possível. Em teoria, esta é uma peça com o valor “131,072”.
explicação do problema
resolver este jogo é um problema interessante porque tem um componente Aleatório. É impossível prever corretamente não só onde cada nova peça será colocada, mas se será um “2” ou um “4”.
Como tal, é impossível ter um algoritmo que resolva corretamente o quebra-cabeça de cada vez., O melhor que podemos fazer é determinar o que é provável ser o melhor movimento em cada etapa e jogar o jogo de probabilidade.
em qualquer ponto, há apenas quatro movimentos possíveis que podemos fazer. Algumas vezes, alguns desses movimentos não têm impacto no tabuleiro e, portanto, não valem a pena fazer – por exemplo, no quadro acima um movimento de “para baixo” não terá impacto, uma vez que todas as peças já estão na borda inferior.
O desafio é então determinar qual destes quatro movimentos vai ser o que tem o melhor resultado a longo prazo.,
nosso algoritmo é baseado no algoritmo de Expectimax, que é uma variação do algoritmo de Minimax, mas onde as possíveis rotas através de nossa árvore são ponderadas pela probabilidade de que elas aconteçam.
Essencialmente, tratar o jogo como um jogo de dois jogadores:
- Um Jogador – o jogador humano – pode mudar a placa em uma das quatro direções
- o Jogador Dois – o jogador do computador – pode colocar um bloco em um local vazio na placa
com Base nisso, pode-se gerar uma árvore de resultados de cada movimento, ponderado pela probabilidade de cada movimento acontecendo., Isto pode, então, dar-nos os detalhes necessários para determinar qual o movimento humano é susceptível de dar o melhor resultado.
3.1. Fluxograma de jogo
O fluxo geral de como a jogabilidade funciona:
Nós podemos ver imediatamente o aspecto aleatório do jogo em “Adicionar Aleatório Telha” processo – tanto no fato de que estamos encontrando uma aleatórios praça para adicionar o bloco, e estamos a selecionar um valor aleatório para o bloco.
nosso desafio é então decidir o que fazer no passo “determinar o próximo movimento”. Este é o nosso algoritmo para jogar o jogo.,
O excesso geral disto parece enganosamente simples:
tudo o que precisamos fazer é simular cada um dos movimentos possíveis, determinar qual deles dá o melhor resultado, e então usar isso.
portanto, reduzimos agora o nosso algoritmo para simular qualquer movimento dado e gerar alguma pontuação para o resultado.
Este é um processo de duas partes. A primeira passagem é para ver se o movimento é mesmo possível, e se não, então abortar cedo com uma pontuação de “0”., Se o movimento é possível, então vamos passar para o algoritmo real onde determinamos quão bom é esse movimento:
3.2. Determinar o próximo movimento
a parte chave do nosso algoritmo até agora é simular um movimento, e a parte chave disso é como geramos uma pontuação para cada movimento possível. É aqui que entra o nosso algoritmo de Expectimax.
vamos simular todos os movimentos possíveis de ambos os jogadores para vários passos, e ver qual desses dá o melhor resultado. Para o jogador humano, isso significa cada um dos movimentos” para cima”, “para baixo”, “esquerda” e “direita”.,
Para o jogador do computador, isso significa colocar um “2” ou “4” telha para qualquer local vazio:
Este algoritmo é recursivo, com cada passo recursivo parando apenas se uma determinada profundidade do real mover no jogo real.,ulating uma pontuação para o atualmente simulado de layout de placa
- Simular todos humana possível mover
- Para cada um desses
- Recurse de volta para o algoritmo
- Retorno calculada a pontuação a partir desta humanos mover
- Adicionar a pontuação calculada a partir deste computador, mover, ponderada pela probabilidade de esse movimento acontecendo
Quando acabamos, então somar todas as calculadas as pontuações, e este é o resultado final para o movimento que deseja fazer no atual jogo de tabuleiro., Porque nós fazemos isso quatro vezes – um para cada movimento possível a partir do atual tabuleiro de jogo-nós acabamos com quatro pontuações, e o mais alto desses é o movimento a fazer.
3, 3. Marcando uma posição de tabuleiro
neste ponto, a única coisa a fazer é calcular uma pontuação para uma placa. Esta não é a mesma pontuação que o jogo usa, mas ele precisa levar em conta o quão boa é uma posição que esta é para continuar a jogar.
Há um grande número de maneiras que isso pode ser alcançado através da adição de vários fatores, juntamente com ponderações adequadas., Por exemplo:
- Número de locais vazios
- Número de possíveis mescla – por exemplo, o número de vezes que o mesmo número em dois lugares adjacentes
- O maior valor em qualquer local
- Soma de todos os locais
- Monotonicity do conselho de administração – esta é a forma como o conselho de administração está estruturado, de tal forma que valores de local de aumentar em uma única direção.
Pseudocode
Agora que sabemos como o algoritmo vai funcionar, como é que isto se parece? Vamos explorar um pseudocode que descreva o algoritmo com mais detalhes.,
Nós não estamos interessados no jogo real do jogo, apenas no algoritmo para determinar se move, então vamos começar por aí:
Como antes, isto leva-nos ao ponto onde estamos a simulação de cada um dos movimentos possíveis a partir do conselho e, voltando aquele que marcar o melhor. Isso nos deixa com a necessidade de gerar pontuações para as placas recém-simuladas.
adicionamos em um limite de profundidade para que possamos parar o processamento depois de um tempo., Porque estamos trabalhando com uma recursiva do algoritmo, precisamos de uma maneira de pará-lo caso contrário, ele irá executar potencialmente para sempre:
Este dá-nos a recursividade, a simulação de todos os possíveis humano e o computador mover para um determinado número de passos e decidir qual o humano se move dar o melhor resultado possível.
a única coisa que resta é trabalhar para fora uma pontuação final para qualquer posição dada da placa. Não há algoritmo perfeito para isso, e diferentes fatores darão resultados diferentes.,
Otimização de Desempenho
Então, agora nós temos um algoritmo que irá tentar resolver o jogo, mas não é tão eficiente quanto poderia ser. Devido à natureza aleatória do jogo, é impossível ter um perfeitamente otimizado solver – há sempre algum nível de repetição, simplesmente por causa da natureza do processo.podemos pelo menos fazer o nosso melhor para reduzir o trabalho que não precisamos de fazer.,
já estamos fazendo um pouco de otimização no algoritmo acima, não processando quaisquer movimentos que não tenham qualquer impacto no jogo. Existem outras maneiras que podemos reduzir o trabalho a fazer, porém, tais como rastrear a probabilidade cumulativa de movimentos, e parar quando isso fica muito baixo. Isso tem o risco de remover a solução perfeita, mas se a probabilidade é tão baixa, então quase certamente não vai acontecer de qualquer maneira.
também podemos determinar dinamicamente o limite de profundidade com o qual trabalhar., Nosso pseudocode acima tem um limite de 3, mas podemos calcular dinamicamente com base na forma da placa no início de nossos cálculos – por exemplo, configurando-o para o número de quadrados vazios ou o número de telhas distintas na placa. Isso significaria que percorremos menos movimentos de placas que têm menos espaço para expansão.
adicionalmente, porque é possível revisitar as mesmas posições de tabuleiro várias vezes, podemos lembrar estes e armazenar a pontuação para essas posições em vez de voltar a computá-las todas as vezes., Potencialmente podemos gerar todas as posições possíveis da placa antes do tempo, mas há um grande número destas – 281.474,976,710,656 diferentes posições possíveis da placa usando telhas até 2048 – então isso provavelmente não é viável.
no entanto, a otimização mais importante que podemos fazer é ajustar o algoritmo para gerar pontuações de placa. Isto funciona para decidir o quão bom tabuleiro é para continuar a jogar e os fatores e ponderações que usamos para isso estão diretamente ligados ao quão bem o nosso algoritmo se desenrola.,
conclusão
2048 é um jogo extremamente interessante para tentar resolver. Não há uma maneira perfeita de resolvê-lo, mas podemos escrever heurísticas que irão procurar as melhores rotas possíveis através do jogo.
os mesmos princípios gerais funcionam para qualquer jogo de dois jogadores – por exemplo, xadrez-onde você não pode prever o que o outro jogador fará com qualquer grau de certeza.por que não tentar escrever uma implementação disto e ver como funciona?