"2048" daqui a algumas semanas marca 5 anos, o que significa que é hora de escrever algo dedicado a este jogo maravilhoso.
O tópico de um jogo independente de inteligência artificial em um quebra-cabeça é especialmente informativo. Existem várias maneiras de implementá-lo e hoje analisaremos uma relativamente fácil. Nomeadamente, ensinaremos à mente do computador a coletar graus de dois usando o método de Monte Carlo.
Este artigo foi escrito com o apoio da EDISON Software, uma empresa que desenvolve aplicativos móveis e fornece serviços de teste de software .
A inspiração para este trabalho foi uma discussão sobre stackoverflow, em que
caras espertos sugeriram maneiras eficazes de um jogo de computador . Aparentemente, a melhor maneira é o método minimax com recorte alfa-beta e em alguns dias a próxima publicação será dedicada a ele.
Método de cassino sugerido pelo usuário stackoverflow
Ronenz como parte da discussão acima. A próxima seção inteira é uma tradução de sua publicação.
Método de Monte Carlo
Fiquei interessado na ideia de IA para este jogo, na qual
não há inteligência codificada (ou seja, não há heurísticas, pontuação, etc.). A IA deve "conhecer" apenas as regras do jogo e "entender" o jogo. Isso o distingue da maioria das IA (como neste tópico), porque a jogabilidade é, de fato, força bruta controlada pela função de pontuação, refletindo a compreensão humana do jogo.
Algoritmo AI
Eu encontrei um algoritmo de jogo simples, mas surpreendentemente bom: para determinar o próximo movimento para um determinado estado do campo, a IA joga o jogo na RAM, fazendo
movimentos aleatórios até o jogo terminar em derrota. Isso é feito várias vezes, com a pontuação final sendo rastreada. Então, a pontuação final média é calculada levando em consideração o curso inicial. O movimento inicial que apresentou o resultado médio mais alto é selecionado como o movimento já realmente escolhido.
Com 100 execuções para cada turno inicial, a IA passa para 2048 em 80% dos casos e 4096 para 50% dos casos. Ao usar 10.000 execuções, 2048 é obtido em 100% dos casos, 70% para 4096 e cerca de 1% para 8192.
Visualizar em açãoO melhor resultado alcançado é mostrado na captura de tela:
Um fato interessante para esse algoritmo é que, embora se espere que jogos com movimentos executados aleatoriamente sejam muito ruins, no entanto, escolher o melhor (ou pelo menos ruim, se você quiser) leva a uma jogabilidade muito boa: um jogo típico de Monte Carlo AI pode marcar 70.000 pontos por 3000 jogadas, mas jogos com um jogo arbitrário na memória de qualquer posição fornecem uma média de 340 pontos adicionais para cerca de 40 jogadas adicionais antes de perder. (Você pode verificar isso iniciando o AI e abrindo o console de depuração.)
Este gráfico ilustra esse conceito: a linha azul mostra a pontuação do jogo após cada jogada. A linha vermelha mostra o
melhor resultado do algoritmo, fazendo movimentos arbitrariamente dessa posição para o final do jogo. De fato, os valores vermelhos “puxam” os azuis, pois são as melhores frases do algoritmo. Curiosamente, a linha vermelha está ligeiramente acima da linha azul em cada ponto, mas a linha azul reduz a diferença cada vez mais.
Acho surpreendente que o algoritmo não preveja necessariamente uma boa jogabilidade e, no entanto, escolha os movimentos que a produzem (um bom processo).
Mais tarde, descobri que esse método pode ser classificado como
um algoritmo de busca em árvore de Monte Carlo .
Implementação e links
Primeiro, criei uma versão JavaScript que pode ser
vista em ação aqui . Esta versão é capaz de executar 100 execuções em um período de tempo razoável. Abra o console para mais informações. (
fonte )
Mais tarde, para brincar, usei a infraestrutura @nneonneo altamente otimizada e implementei minha versão em C ++. Esta versão permite até 100.000 execuções por turno e até 1.000.000 se você estiver pronto para esperar. Instruções de montagem incluídas. Tudo funciona no console e também possui um controle remoto para reprodução na versão web. (
fonte )
Resultados
Surpreendentemente, um aumento no número de corridas não melhora fundamentalmente a jogabilidade. Parece que essa estratégia tem um limite de 80.000 pontos com um bloco de 4096 e todos os resultados menores muito próximos de atingir o bloco 8192. Um aumento no número de execuções de 100 para 100.000 aumenta as chances de atingir esse limite (de 5% para 40%), mas não supera isso.
A realização de 10.000 corridas com um aumento temporário de até 1.000.000 de posições próximas da crítica tornou possível superar essa barreira em menos de 1% dos casos, com o número máximo de pontos marcados em 129892 e nos ladrilhos 8192.
Melhorias e otimizações
Após implementar esse algoritmo, tentei muitas melhorias, incluindo o uso de classificações mínimas ou máximas ou uma combinação de valores mínimos, máximos e médios. Também tentei usar a profundidade: em vez de tentar completar K corridas por turno, tentei K jogadas por lista de jogadas de um determinado comprimento (por exemplo, “cima, cima, esquerda”) e escolhi a primeira jogada da lista de jogadas com a melhor vitória.
Posteriormente, implementei uma árvore de pontuação que levava em conta a probabilidade condicional de que ele seria capaz de concluir um movimento após uma determinada lista de movimentos.
No entanto, nenhuma dessas idéias mostrou uma vantagem real sobre uma simples primeira idéia. Deixei um código comentado para essas idéias na fonte C ++.
Adicionei o mecanismo Deep Search, que aumentou temporariamente o número de execuções para 1.000.000 quando alguma delas acidentalmente conseguiu alcançar o próximo bloco mais alto. Isso levou a uma melhoria no desempenho do tempo.
Gostaria de saber se alguém tem outras idéias de melhoria que apóiam a independência da IA em relação à área de assunto?
Opções e clones 2048
Por diversão, também implementei a IA como um bookmarklet, conectando-a aos controles do jogo. Isso permite que você trabalhe com o jogo original e com muitas de suas variações.
Isso é possível devido à natureza independente de domínio da IA. Algumas das opções são bastante originais, como um clone hexagonal.
2048.xlsm
O próprio aplicativo Excel
pode ser baixado do Google .
A imagem é clicável - uma imagem em tamanho real será aberta.
Brevemente sobre a interface e a funcionalidade do aplicativo.
Para começar a jogar, você precisa clicar no botão "
Usuário: iniciar jogo ". Quando você pressiona esse botão novamente, a inscrição muda de "
Usuário: inicie o jogo " para "
Usuário: encerre o jogo " e vice-versa, ou seja, a qualquer momento você pode interromper o jogo e iniciá-lo novamente. Quando o jogo termina, você pode alterar manualmente o alinhamento em campo, melhorando ou piorando sua posição, a fim de testar ou verificar algumas idéias.
Durante o jogo em si, você pode fazer jogadas de duas maneiras:
- Teclado: simplesmente pressionando as teclas "cima", "baixo", "esquerda", "direita".
- Com o mouse: clique nas células com grandes setas indicando a direção desejada.
O botão "
Novo campo " limpa o campo de jogo e coloca aleatoriamente os "dois" e "quatro" nele.
O mais interessante é que o método Monte Carlo foi implementado, na forma em que foi proposto pelo cara com stackoverflow. Em cada posição, o computador na memória passa por ramificações aleatórias para cada primeiro movimento ("para cima", "para baixo", "esquerda", "direita") até levar a uma perda. Estatisticamente, a direção mais favorável é destacada em vermelho em uma tabela especial abaixo. Você pode usá-lo como uma dica se perceber que seu próprio jogo está parado e precisar se salvar de alguma forma. ;)
Acima da tabela, há caixas de seleção com opções de análise. No momento, apenas Monte Carlo foi decidido, o restante será adicionado nos próximos dias (como resultado, haverá mais problemas com a atualização do aplicativo do Excel e explicações da teoria).
Há também um botão
AI: game . Ao clicar nele, o assistente do computador fará um movimento de acordo com o método Monte Carlo ou outro selecionado no grupo de comutadores (o minimax e a rede neural trabalharão nessa lista um pouco mais tarde).
Todos os artigos das séries AI e 2048