Qual é o algoritmo ideal para o jogo 2048?

1920

Recentemente, deparei com o jogo 2048 . Você mescla blocos semelhantes movendo-os em qualquer uma das quatro direções para criar blocos "maiores". Após cada movimento, um novo bloco aparece na posição vazia aleatória com um valor de 2ou 4. O jogo termina quando todas as caixas estão preenchidas e não há movimentos que possam mesclar peças ou você cria uma peça com um valor de 2048.

Primeiro, preciso seguir uma estratégia bem definida para alcançar a meta. Então, pensei em escrever um programa para ele.

Meu algoritmo atual:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

O que estou fazendo é que, a qualquer momento, tentarei mesclar os ladrilhos com valores 2e 4, ou seja, tento ter 2e 4ladrilhos, o mínimo possível. Se eu tentar dessa maneira, todos os outros blocos serão mesclados automaticamente e a estratégia parecerá boa.

Mas, quando eu realmente uso esse algoritmo, recebo apenas 4000 pontos antes do jogo terminar. Máximo de pontos O AFAIK é um pouco mais de 20.000 pontos, muito maior do que a minha pontuação atual. Existe um algoritmo melhor que o acima?

nitish712
fonte
84
Isso pode ajudar! ov3y.github.io/2048-AI
cegprakash
5
@ nitish712 por sinal, seu algoritmo é ganancioso, pois você tem choose the move with large number of mergesque levar rapidamente a ótimos locais
Khaled.K
21
@ 500-InternalServerError: Se eu fosse implementar uma IA com poda de árvore de jogos alfa-beta, seria assumido que os novos blocos sejam colocados de forma adversa. É uma suposição do pior caso, mas pode ser útil.
Charles
6
Uma distração divertida quando você não tem tempo para obter uma pontuação alta: tente obter a menor pontuação possível. Em teoria, alterna 2s e 4s.
Mark Hurd
7
Discussão sobre a legitimidade desta pergunta pode ser encontrada em meta: meta.stackexchange.com/questions/227266/...
Jeroen Vannevel

Respostas:

1266

Desenvolvi uma IA 2048 usando a otimização expectimax , em vez da pesquisa minimax usada pelo algoritmo do @ ovolve. A IA simplesmente realiza maximização em todos os movimentos possíveis, seguida de expectativa em todos os spawns possíveis (ponderada pela probabilidade dos blocos, ou seja, 10% para um 4 e 90% para um 2). Tanto quanto sei, não é possível remover a otimização do expectimax (exceto para remover ramificações que são extremamente improváveis) e, portanto, o algoritmo usado é uma pesquisa de força bruta cuidadosamente otimizada.

atuação

O AI em sua configuração padrão (profundidade máxima de pesquisa de 8) leva de 10ms a 200ms para executar um movimento, dependendo da complexidade da posição da placa. Nos testes, a IA atinge uma taxa média de movimentos de 5 a 10 movimentos por segundo ao longo de um jogo inteiro. Se a profundidade da pesquisa for limitada a 6 movimentos, a IA pode executar facilmente mais de 20 movimentos por segundo, o que contribui para uma observação interessante .

Para avaliar o desempenho da pontuação da IA, executei a AI 100 vezes (conectada ao jogo do navegador via controle remoto). Para cada bloco, aqui estão as proporções de jogos em que esse bloco foi alcançado pelo menos uma vez:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

A pontuação mínima em todas as corridas foi 124024; a pontuação máxima alcançada foi 794076. A pontuação média é 387222. A IA nunca conseguiu obter o bloco 2048 (portanto, nunca perdeu o jogo nem uma vez em 100 jogos); de fato, alcançou o bloco 8192 pelo menos uma vez em cada execução!

Aqui está a captura de tela da melhor execução:

32768 lado a lado, pontuação 794076

Este jogo levou 27830 jogadas em 96 minutos, ou uma média de 4,8 jogadas por segundo.

Implementação

Minha abordagem codifica todo o quadro (16 entradas) como um único número inteiro de 64 bits (onde os blocos são os nybbles, isto é, pedaços de 4 bits). Em uma máquina de 64 bits, isso permite que toda a placa seja distribuída em um único registro de máquina.

As operações de deslocamento de bits são usadas para extrair linhas e colunas individuais. Uma única linha ou coluna é uma quantidade de 16 bits; portanto, uma tabela de tamanho 65536 pode codificar transformações que operam em uma única linha ou coluna. Por exemplo, os movimentos são implementados como 4 pesquisas em uma "tabela de efeitos de movimento" pré-computada que descreve como cada movimento afeta uma única linha ou coluna (por exemplo, a tabela "mover para a direita" contém a entrada "1122 -> 0023", descrevendo como o linha [2,2,4,4] se torna a linha [0,0,4,8] quando movida para a direita).

A pontuação também é feita usando a pesquisa de tabela. As tabelas contêm pontuações heurísticas calculadas em todas as linhas / colunas possíveis, e a pontuação resultante para um quadro é simplesmente a soma dos valores da tabela em cada linha e coluna.

Essa representação do quadro, juntamente com a abordagem de pesquisa de tabela para movimentação e pontuação, permite que a IA pesquise um grande número de estados de jogos em um curto período de tempo (mais de 10.000.000 de estados de jogos por segundo em um núcleo do meu laptop de meados de 2011).

A própria pesquisa expectimax é codificada como uma pesquisa recursiva que alterna entre as etapas de "expectativa" (testando todos os locais e valores possíveis de geração de blocos e ponderando suas pontuações otimizadas pela probabilidade de cada possibilidade) e as etapas de "maximização" (testando todos os movimentos possíveis) e selecionando aquele com a melhor pontuação). A pesquisa em árvore termina quando vê uma posição vista anteriormente (usando uma tabela de transposição ), quando atinge um limite de profundidade predefinido ou quando atinge um estado de quadro que é altamente improvável (por exemplo, foi alcançado obtendo 6 peças "4") a partir da posição inicial). A profundidade típica da pesquisa é de 4-8 movimentos.

Heurística

Diversas heurísticas são usadas para direcionar o algoritmo de otimização para posições favoráveis. A escolha precisa da heurística tem um enorme efeito no desempenho do algoritmo. As várias heurísticas são ponderadas e combinadas em uma pontuação posicional, que determina o quão "boa" é uma determinada posição do conselho. A pesquisa de otimização terá como objetivo maximizar a pontuação média de todas as posições possíveis no quadro. A pontuação real, como mostra o jogo, não é usada para calcular a pontuação do tabuleiro, pois é muito pesada em favor da mesclagem de peças (quando a mesclagem atrasada pode produzir um grande benefício).

Inicialmente, usei duas heurísticas muito simples, concedendo "bônus" para quadrados abertos e por ter grandes valores no limite. Essas heurísticas tiveram um desempenho muito bom, frequentemente atingindo 16384, mas nunca chegando a 32768.

Petr Morávek (@xificurk) pegou minha IA e adicionou duas novas heurísticas. A primeira heurística foi uma penalidade por ter linhas e colunas não monotônicas que aumentavam à medida que as fileiras aumentavam, garantindo que linhas não monotônicas de pequenos números não afetassem fortemente a pontuação, mas linhas não monotônicas de grandes números prejudicavam substancialmente a pontuação. A segunda heurística contou o número de possíveis fusões (valores iguais adjacentes), além de espaços abertos. Essas duas heurísticas serviram para empurrar o algoritmo para placas monotônicas (que são mais fáceis de mesclar) e para posições da placa com muitas mesclagens (incentivando-a a alinhar mesclagens sempre que possível para obter um efeito maior).

Além disso, Petr também otimizou os pesos heurísticos usando uma estratégia de "meta-otimização" (usando um algoritmo chamado CMA-ES ), onde os pesos foram ajustados para obter a maior pontuação média possível.

O efeito dessas mudanças é extremamente significativo. O algoritmo passou de alcançar o bloco 16384 em cerca de 13% do tempo para atingi-lo em mais de 90% do tempo, e o algoritmo começou a atingir 32768 em 1/3 do tempo (enquanto as antigas heurísticas nunca produziram um bloco 32768) .

Acredito que ainda há espaço para melhorias nas heurísticas. Esse algoritmo definitivamente ainda não é "ideal", mas eu sinto que está chegando bem perto.


O fato de a IA atingir a marca 32768 em mais de um terço de seus jogos é um grande marco; Ficarei surpreso ao saber se algum jogador humano alcançou 32768 no jogo oficial (ou seja, sem usar ferramentas como savestates ou desfazer). Eu acho que o ladrilho 65536 está ao nosso alcance!

Você pode experimentar a IA por si mesmo. O código está disponível em https://github.com/nneonneo/2048-ai .

nneonneo
fonte
12
@RobL: 2 aparecem 90% das vezes; 4 aparecem 10% do tempo. Está no código fonte : var value = Math.random() < 0.9 ? 2 : 4;.
N
35
Atualmente portando para Cuda, para que a GPU faça o trabalho para velocidades ainda melhores!
Nssonson
25
@nneonneo Portei seu código com emscripten para javascript, e ele funciona muito bem no navegador agora! Arrefecer para assistir, sem a necessidade de compilar e tudo ... No Firefox, o desempenho é muito bom ...
reverse_engineer
7
Na verdade, o limite teórico em uma grade 4x4 é 131072 e não 65536. No entanto, isso exige um 4 no momento certo (ou seja, toda a placa é preenchida com 4 .. 65536 cada uma vez - 15 campos ocupados) e a placa deve ser configurada nesse momento. momento para que você possa realmente combinar.
Bodo Thiesen
5
@nneonneo Você pode conferir nossa IA, que parece ainda melhor, chegando a 32k em 60% dos jogos: github.com/aszczepanski/2048
cauchy
1253

Eu sou o autor do programa de IA que outros mencionaram neste tópico. Você pode visualizar o AI em ação ou ler a fonte .

Atualmente, o programa alcança uma taxa de ganho de 90% em javascript no navegador do meu laptop, com cerca de 100 milissegundos de tempo de raciocínio por jogada, portanto, embora não seja perfeito (ainda!), Ele funciona muito bem.

Como o jogo é um espaço de estado discreto, informações perfeitas, jogos baseados em turnos, como xadrez e damas, usei os mesmos métodos que comprovadamente funcionam nesses jogos, ou seja, pesquisa minimax com poda alfa-beta . Como já existem muitas informações sobre esse algoritmo, falarei sobre as duas heurísticas principais que eu uso na função de avaliação estática e que formalizam muitas das intuições que outras pessoas expressaram aqui.

Monotonicidade

Essa heurística tenta garantir que os valores dos blocos estejam aumentando ou diminuindo nas direções esquerda / direita e para cima / para baixo. Somente essa heurística captura a intuição que muitos outros mencionaram, de que blocos de maior valor devem ser agrupados em um canto. Normalmente, impede que peças menores com valor se tornem órfãs e mantém o tabuleiro muito organizado, com peças menores em cascata e preenchendo as peças maiores.

Aqui está uma captura de tela de uma grade perfeitamente monotônica. Obtive isso executando o algoritmo com a função eval configurada para desconsiderar as outras heurísticas e considerar apenas a monotonicidade.

Uma placa 2048 perfeitamente monotônica

Suavidade

Somente a heurística acima tende a criar estruturas nas quais os blocos adjacentes estão diminuindo em valor, mas é claro que, para mesclar, os blocos adjacentes precisam ter o mesmo valor. Portanto, a heurística de suavidade apenas mede a diferença de valor entre os blocos vizinhos, tentando minimizar essa contagem.

Um comentarista do Hacker News deu uma interessante formalização dessa idéia em termos de teoria dos grafos.

Aqui está uma captura de tela de uma grade perfeitamente suave, cortesia deste excelente garfo de paródia .

Uma placa 2048 perfeitamente lisa

Free Tiles

E, finalmente, há uma penalidade por ter poucas peças gratuitas, pois as opções podem acabar rapidamente quando o tabuleiro do jogo fica muito apertado.

E é isso! Pesquisando no espaço do jogo e otimizando esses critérios, obtém um desempenho notavelmente bom. Uma vantagem de usar uma abordagem generalizada como essa, em vez de uma estratégia de movimentação explicitamente codificada, é que o algoritmo pode frequentemente encontrar soluções interessantes e inesperadas. Se você assisti-lo correr, muitas vezes fará movimentos surpreendentes, mas eficazes, como alternar repentinamente contra qual parede ou canto ele está se erguendo.

Editar:

Aqui está uma demonstração do poder dessa abordagem. Limitei os valores dos blocos (por isso continuou depois de chegar a 2048) e aqui está o melhor resultado após oito tentativas.

4096

Sim, isso é um 4096 ao lado de um 2048. =) Isso significa que alcançou o esquivo 2048 três vezes no mesmo tabuleiro.

ovolar
fonte
89
Você pode tratar o computador colocando os blocos '2' e '4' como o 'oponente'.
Wei Yen
29
@ WeiYen Claro, mas considerá-lo um problema minmax não é fiel à lógica do jogo, porque o computador está colocando blocos aleatoriamente com certas probabilidades, em vez de minimizar intencionalmente a pontuação.
koo
57
Mesmo que a IA esteja colocando as peças aleatoriamente, o objetivo não é perder. Ficar sem sorte é a mesma coisa que o oponente que escolhe a pior jogada para você. A parte "min" significa que você tenta jogar de forma conservadora, para que não haja jogadas terríveis que possam ter azar.
FryGuy
196
Tive uma ideia de criar uma bifurcação de 2048, onde o computador, em vez de colocar os 2s e 4s, usa aleatoriamente sua IA para determinar onde colocar os valores. O resultado: pura impossibilidade. Pode ser experimentado aqui: sztupy.github.io/2048-Hard
SztupY
30
@SztupY Uau, isso é mau. Me lembra o qntm.org/hatetris Hatetris, que também tenta colocar a peça que melhorará a sua situação.
Patashu 17/03/14
145

Fiquei interessado na ideia de uma IA para este jogo que não contém inteligência codificada (ou seja, nenhuma heurística, funções de pontuação etc.). A IA deve "conhecer" apenas as regras do jogo e "descobrir" o jogo. Isso contrasta com a maioria das IAs (como as deste tópico), nas quais o jogo é essencialmente uma força bruta orientada por uma função de pontuação que representa a compreensão humana do jogo.

Algoritmo AI

Encontrei um algoritmo de jogo simples, mas surpreendentemente bom: para determinar o próximo passo para um determinado tabuleiro, a IA joga o jogo na memória usando movimentos aleatórios até o jogo terminar. Isso é feito várias vezes, mantendo o controle da pontuação do jogo final. Então, a pontuação final média por jogada inicial é calculada. A jogada inicial com a pontuação final média mais alta é escolhida como a próxima jogada.

Com apenas 100 execuções (ou seja, em jogos de memória) por jogada, a IA atinge o bloco 2048 em 80% das vezes e o bloco 4096 em 50% das vezes. O uso de 10000 execuções obtém o bloco 2048 100%, 70% para o bloco 4096 e cerca de 1% para o bloco 8192.

Veja em ação

A melhor pontuação alcançada é mostrada aqui:

melhor pontuação

Um fato interessante sobre esse algoritmo é que, embora os jogos aleatórios sejam surpreendentemente ruins, escolher a melhor jogada (ou menos ruim) leva a uma jogabilidade muito boa: um jogo típico de IA pode atingir 70000 pontos e os últimos 3000 movimentos; jogos aleatórios na memória de qualquer posição fornecem uma média de 340 pontos adicionais em cerca de 40 movimentos extras antes de morrer. (Você pode ver isso executando a AI e abrindo o console de depuração.)

Este gráfico ilustra este ponto: A linha azul mostra a pontuação do tabuleiro após cada jogada. A linha vermelha mostra a melhor pontuação do jogo final de corrida aleatória do algoritmo a partir dessa posição. Em essência, os valores vermelhos estão "puxando" os valores azuis para cima em direção a eles, pois são o melhor palpite do algoritmo. É interessante ver que a linha vermelha está apenas um pouquinho acima da linha azul em cada ponto, mas a linha azul continua a aumentar cada vez mais.

gráfico de pontuação

Acho bastante surpreendente que o algoritmo não precise realmente prever um bom jogo para escolher os movimentos que o produzem.

Pesquisando mais tarde, descobri que esse algoritmo pode ser classificado como um algoritmo Pure Monte Carlo Tree Search .

Implementação e Links

Primeiro, criei uma versão JavaScript que pode ser vista em ação aqui . Esta versão pode executar centenas de execuções em tempo decente. Abra o console para informações adicionais. ( fonte )

Mais tarde, para brincar um pouco mais, usei a infraestrutura altamente otimizada do @nneonneo e implementei minha versão em C ++. Esta versão permite até 100000 execuções por movimentação e até 1000000 se você tiver paciência. Instruções de construção fornecidas. Ele roda no console e também possui um controle remoto para reproduzir a versão da web. ( fonte )

Resultados

Surpreendentemente, aumentar o número de corridas não melhora drasticamente o jogo. Parece haver um limite para essa estratégia em cerca de 80000 pontos com o ladrilho 4096 e todos os menores, muito próximo do alcance do ladrilho 8192. Aumentar o número de execuções de 100 para 100000 aumenta as chances de atingir esse limite de pontuação (de 5% para 40%), mas não ultrapassá-lo.

A execução de 10000 execuções com um aumento temporário para 1000000 perto de posições críticas conseguiu quebrar essa barreira em menos de 1% das vezes, atingindo uma pontuação máxima de 129892 e o bloco 8192.

Melhorias

Depois de implementar esse algoritmo, tentei várias melhorias, incluindo o uso das pontuações mínimas e máximas, ou uma combinação de mín, máx e média. Também tentei usar a profundidade: em vez de tentar K corridas por movimento, tentei K movimentos por lista de movimentos de um determinado comprimento ("cima, cima, esquerda", por exemplo)) e selecionando o primeiro movimento da lista de movimentos com melhor pontuação.

Posteriormente, implementei uma árvore de pontuação que levava em conta a probabilidade condicional de poder executar uma jogada após uma determinada lista de movimentos.

No entanto, nenhuma dessas idéias mostrou qualquer vantagem real sobre a primeira idéia simples. Deixei o código para essas idéias comentadas no código C ++.

Eu adicionei um mecanismo de "Pesquisa profunda" que aumentou temporariamente o número da execução para 1000000 quando qualquer uma das execuções conseguiu alcançar acidentalmente o próximo bloco mais alto. Isso ofereceu uma melhora no tempo.

Eu ficaria interessado em saber se alguém tem outras idéias de melhoria que mantêm a independência de domínio da IA.

2048 Variantes e clones

Apenas por diversão, eu também implementei a IA como um bookmarklet , conectando-nos aos controles do jogo. Isso permite que a IA trabalhe com o jogo original e com muitas de suas variantes .

Isso é possível devido à natureza independente de domínio da IA. Algumas das variantes são bastante distintas, como o clone hexagonal.

Ronenz
fonte
7
+1. Como estudante de IA, achei isso realmente interessante. Analisará melhor isso no tempo livre.
Isaac
4
Isso é incrível! Passei horas otimizando pesos para uma boa função heurística do expectimax e implemento isso em 3 minutos, o que o destrói completamente.
Brendan Annable
8
Bom uso da simulação de Monte Carlo.
nneonneo
5
Assistir a esta peça está chamando para uma iluminação. Isso explode todas as heurísticas e, no entanto, funciona. Parabéns!
Stéphane Gourichon
4
De longe, a solução mais interessante aqui.
shebaw
126

EDIT: Este é um algoritmo ingênuo, que modela o processo de pensamento consciente do ser humano, e obtém resultados muito fracos em comparação com a IA que busca todas as possibilidades, uma vez que apenas olha um ladrilho à frente. Foi enviado no início da linha do tempo da resposta.

Eu refinei o algoritmo e venci o jogo! Pode falhar devido à simples má sorte no final (você é forçado a descer, o que nunca deve fazer, e um bloco aparece onde deve estar o mais alto. Apenas tente manter a linha superior preenchida, para que a esquerda não quebrar o padrão), mas basicamente você acaba tendo uma parte fixa e uma parte móvel para brincar. Este é o seu objetivo:

Pronto para terminar

Este é o modelo que eu escolhi por padrão.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

O canto escolhido é arbitrário, você basicamente nunca pressiona uma tecla (a jogada proibida) e, se o fizer, pressiona o contrário novamente e tenta corrigi-lo. Para blocos futuros, o modelo sempre espera que o próximo bloco aleatório seja um 2 e apareça no lado oposto ao modelo atual (enquanto a primeira linha estiver incompleta, no canto inferior direito, depois que a primeira linha for concluída, no canto inferior esquerdo canto).

Aqui está o algoritmo. Cerca de 80% das vitórias (parece que sempre é possível vencer com técnicas de IA mais "profissionais", no entanto, não tenho certeza disso.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Algumas dicas sobre os passos que faltam. Aqui:mudança de modelo

O modelo mudou devido à sorte de estar mais próximo do modelo esperado. O modelo que a IA está tentando alcançar é

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

E a cadeia para chegar lá se tornou:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

Os Oespaços proibidos representam ...

Então, ele pressiona para a direita, depois para a direita novamente e, em seguida (para a direita ou para cima, dependendo de onde os 4 foram criados), prossegue para concluir a cadeia até obter:

Cadeia concluída

Então agora o modelo e a cadeia estão de volta a:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

Segundo ponteiro, teve azar e seu ponto principal foi ocupado. É provável que falhe, mas ainda é possível:

Digite a descrição da imagem aqui

Aqui o modelo e a cadeia são:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Quando consegue alcançar os 128, ganha uma linha inteira novamente:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x
Daren
fonte
execute move with best scorecomo você pode avaliar a melhor pontuação dos próximos estados possíveis?
Khaled.K
a heurística é definida em evaluateResultvocê basicamente tenta se aproximar do melhor cenário possível.
Daren 12/03
@ Daren Estou esperando por seus detalhes detalhados
ashu
@ashu Estou trabalhando nisso, circunstâncias inesperadas me deixaram sem tempo para terminar. Enquanto isso, aprimorei o algoritmo e agora o soluciona 75% das vezes.
Daren
13
O que eu realmente gosto nessa estratégia é que sou capaz de usá-la ao jogar o jogo manualmente, isso me levou a 37k pontos.
Cefalópode
94

Copio aqui o conteúdo de uma postagem no meu blog


A solução que proponho é muito simples e fácil de implementar. Embora tenha atingido a pontuação de 131040. São apresentados vários parâmetros de desempenho do algoritmo.

Ponto

Algoritmo

Algoritmo de pontuação heurística

A suposição sobre a qual meu algoritmo se baseia é bastante simples: se você deseja obter uma pontuação mais alta, o quadro deve ser mantido o mais organizado possível. Em particular, a configuração ideal é dada por uma ordem decrescente linear e monotônica dos valores do bloco. Essa intuição também fornecerá o limite superior para um valor de bloco: sonde n é o número de blocos no tabuleiro.

(Existe a possibilidade de alcançar o bloco 131072 se o bloco 4 for gerado aleatoriamente em vez do bloco 2 quando necessário)

Duas maneiras possíveis de organizar o quadro são mostradas nas seguintes imagens:

insira a descrição da imagem aqui

Para impor a ordenação dos ladrilhos em uma ordem decrescente monotônica, a pontuação é calculada como a soma dos valores linearizados no tabuleiro multiplicados pelos valores de uma sequência geométrica com razão comum r <1.

s

s

Vários caminhos lineares podem ser avaliados de uma só vez, a pontuação final será a pontuação máxima de qualquer caminho.

Regra de decisão

A regra de decisão implementada não é muito inteligente, o código em Python é apresentado aqui:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Uma implementação do minmax ou do Expectiminimax certamente melhorará o algoritmo. Obviamente, uma regra de decisão mais sofisticada desacelerará o algoritmo e exigirá algum tempo para ser implementada. Tentarei uma implementação minimax em um futuro próximo. (Fique ligado)

Referência

  • T1 - 121 testes - 8 caminhos diferentes - r = 0,125
  • T2 - 122 testes - 8 caminhos diferentes - r = 0,25
  • T3 - 132 testes - 8 caminhos diferentes - r = 0,5
  • T4 - 211 testes - 2 caminhos diferentes - r = 0,125
  • T5 - 274 testes - 2 caminhos diferentes - r = 0,25
  • T6 - 211 testes - 2 caminhos diferentes - r = 0,5

insira a descrição da imagem aqui insira a descrição da imagem aqui insira a descrição da imagem aqui insira a descrição da imagem aqui

No caso de T2, quatro testes em dez geram o bloco 4096 com uma pontuação média de s42000

Código

O código pode ser encontrado no GiHub no seguinte link: https://github.com/Nicola17/term2048-AI É baseado no term2048 e está escrito em Python. Implementarei uma versão mais eficiente em C ++ o mais rápido possível.

Nicola Pezzotti
fonte
Não é ruim, sua ilustração deu-me uma ideia, de tomar os vetores se fundem em avaliação
Khaled.K
Olá. Você tem certeza de que as instruções fornecidas na página do github se aplicam ao seu projeto? Quero experimentá-lo, mas essas parecem ser as instruções para o jogo jogável original e não a execução automática da IA. Você poderia atualizar isso? Obrigado.
JD Gamboa #
41

Minha tentativa usa expectimax como outras soluções acima, mas sem placas de bit. A solução da Nneonneo pode verificar 10 milhões de movimentos, o que é aproximadamente uma profundidade de 4 com 6 peças restantes e 4 movimentos possíveis (2 * 6 * 4) 4 . No meu caso, essa profundidade leva muito tempo para explorar, eu ajusto a profundidade da pesquisa expectimax de acordo com o número de peças livres restantes:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

As pontuações das placas são calculadas com a soma ponderada do quadrado do número de peças livres e o produto escalar da grade 2D com isso:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

que obriga a organizar as peças descendente em uma espécie de cobra a partir da peça superior esquerda.

código abaixo ou no github :

var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}


updateUI(ai);
updateHint(predict(ai));

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai);
		updateUI(ai);
		updateHint(p);
		requestAnimationFrame(runAI);
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
		updateHint(predict(ai));
	}
}


function updateHint(dir) {
	hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(ai));
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}
<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

caub
fonte
3
Não sei por que isso não tem mais votos positivos. É realmente eficaz por sua simplicidade.
David Greydanus
Graças, resposta tardia e não executa muito bem (quase sempre em [1024, 8192]), o custo / stats funcionar precisa de mais trabalho
caub
Como você pesou os espaços vazios?
David Greydanus
1
É simplesmente cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid)e nós tentamos maximizar este custo
caub
graças @Robusto, eu deveria melhorar o código algum dia, ele pode ser simplificado
caub
38

Eu sou o autor de um controlador 2048 que tem uma pontuação melhor do que qualquer outro programa mencionado neste segmento. Uma implementação eficiente do controlador está disponível no github . Em um repositório separado , também há o código usado para treinar a função de avaliação de estado do controlador. O método de treinamento é descrito no artigo .

O controlador usa a pesquisa expectimax com uma função de avaliação de estado aprendida do zero (sem experiência humana em 2048) por uma variante do aprendizado da diferença temporal (uma técnica de aprendizado por reforço). A função de valor de estado usa uma rede de n-tupla , que é basicamente uma função linear ponderada de padrões observados no quadro. Envolveu mais de 1 bilhão de pesos no total.

atuação

Em 1 movimentos / s: 609104 (média de 100 jogos)

Com 10 movimentos / s: 589355 (média de 300 jogos)

Com 3 dobras (ca. 1500 movimentos / s): 511759 (média de 1000 jogos)

As estatísticas do bloco para 10 movimentos / s são as seguintes:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(A última linha significa ter as peças dadas ao mesmo tempo no tabuleiro).

Para 3 camadas:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

No entanto, nunca o observei obtendo o bloco 65536.

cauchy
fonte
4
Resultado bastante impressionante. No entanto, você poderia atualizar a resposta para explicar (a grosso modo, em termos simples ... Tenho certeza de que os detalhes completos seriam muito longos para serem postados aqui) como o seu programa consegue isso? Como em uma explicação grosseira de como o algoritmo de aprendizado funciona?
Cedric Mamo 27/01
27

Acho que encontrei um algoritmo que funciona muito bem, já que muitas vezes alcanço pontuações acima de 10000, sendo o meu melhor em torno de 16000. Minha solução não visa manter os maiores números em um canto, mas mantê-lo na linha superior.

Por favor veja o código abaixo:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}
Vincent Lecrubier
fonte
5
Eu corri 100.000 jogos testando isso em relação à estratégia cíclica trivial "para cima, para a direita, para cima, para a esquerda ..." (e para baixo, se necessário). A estratégia cíclica terminou com uma "pontuação média de bloco" 770.6, enquanto essa foi apenas 396.7. Você sabe por que isso pode ser? Eu estou pensando que faz muitos ups, mesmo quando a esquerda ou a direita se fundiriam muito mais.
Thomas Ahle
1
Os blocos tendem a empilhar de maneira incompatível se não forem deslocados em várias direções. Em geral, o uso de uma estratégia cíclica resultará em ladrilhos maiores no centro, o que torna as manobras muito mais limitadas.
bcdan
25

Já existe uma implementação de IA para este jogo aqui . Trecho de README:

O algoritmo é a profundidade de aprofundamento iterativo da primeira pesquisa alfa-beta. A função de avaliação tenta manter as linhas e colunas monotônicas (todas diminuindo ou aumentando) enquanto minimiza o número de blocos na grade.

Há também uma discussão sobre o Hacker News sobre esse algoritmo que você pode achar útil.

baltazar
fonte
4
Essa deve ser a resposta principal, mas seria interessante adicionar mais detalhes sobre a implementação: por exemplo, como o tabuleiro de jogo é modelado (como gráfico), a otimização empregada (mín-máx a diferença entre peças) etc.
Alceu Costa
1
Para futuros leitores: Este é o mesmo programa explicado por seu autor (ovolve) na segunda resposta mais importante aqui. Essa resposta e outras menções ao programa do ovolve nesta discussão fizeram com que o ovolve aparecesse e escrevesse como seu algoritmo funcionava; essa resposta agora tem uma pontuação de 1200.
MultiplyByZer0
23

Algoritmo

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Avaliação

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Detalhes da Avaliação

128 (Constant)

Esta é uma constante, usada como linha de base e para outros usos, como testes.

+ (Number of Spaces x 128)

Mais espaços tornam o estado mais flexível, multiplicamos por 128 (que é a mediana), pois uma grade preenchida com 128 faces é um estado impossível ideal.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Aqui, avaliamos as faces que têm a possibilidade de mesclar, avaliando-as para trás, o bloco 2 passa a ter o valor 2048, enquanto o bloco 2048 é avaliado 2.

+ Sum of other faces { log(face) x 4 }

Aqui ainda precisamos verificar os valores empilhados, mas de uma maneira menor que não interrompa os parâmetros de flexibilidade, portanto, temos a soma de {x in [4,44]}.

+ (Number of possible next moves x 256)

Um estado é mais flexível se tiver mais liberdade de transições possíveis.

+ (Number of aligned values x 2)

Esta é uma verificação simplificada da possibilidade de haver mesclagens nesse estado, sem dar uma olhada no futuro.

Nota: As constantes podem ser ajustadas.

Khaled.K
fonte
2
Vou editar isso mais tarde, para adicionar um código ativo @ nitish712
Khaled.K 12/14
9
Qual é a% de ganho deste algoritmo?
cegprakash
Por que você precisa de um constant? Se tudo o que você está fazendo é comparar pontuações, como isso afeta o resultado dessas comparações?
bcdan
@bcdan, a heurística (também conhecida como comparação-pontuação) depende da comparação do valor esperado do estado futuro, semelhante à maneira como as heurísticas do xadrez funcionam, exceto que é uma heurística linear, já que não construímos uma árvore para saber os melhores próximos movimentos N
Khaled.K
12

Esta não é uma resposta direta à pergunta do OP, este é mais um dos materiais (experimentos) que tentei até agora para resolver o mesmo problema e obtive alguns resultados e tenho algumas observações que quero compartilhar, estou curioso para saber se podemos ter algum mais informações sobre isso.

Eu apenas tentei minha implementação minimax com poda alfa-beta com corte de profundidade da árvore de pesquisa em 3 e 5. Eu estava tentando resolver o mesmo problema para uma grade 4x4 que uma atribuição de projeto para o curso edX ColumbiaX: CSMM.101x Artificial Intelligence ( AI) .

Apliquei a combinação convexa (tentei diferentes pesos heurísticos) de duas funções de avaliação heurística, principalmente por intuição e pelas discutidas acima:

  1. Monotonicidade
  2. Espaço livre disponível

No meu caso, o player do computador é completamente aleatório, mas ainda assim assumi configurações contraditórias e implementei o agente do AI player como o player máximo.

Eu tenho grade 4x4 para jogar o jogo.

Observação:

Se eu atribuir pesos demais à primeira função heurística ou à segunda função heurística, ambos os casos, as pontuações que o jogador de IA obtém são baixas. Joguei com muitas atribuições de peso possíveis para as funções heurísticas e tomo uma combinação convexa, mas muito raramente o jogador de IA consegue marcar 2048. Na maioria das vezes ele pára em 1024 ou 512.

Eu também tentei a heurística da esquina, mas por algum motivo isso piora os resultados, qualquer intuição por que?

Além disso, tentei aumentar o corte da profundidade de pesquisa de 3 para 5 (não posso aumentá-lo mais, pois a pesquisa de que o espaço excede o tempo permitido, mesmo com poda) e adicionei mais uma heurística que analisa os valores dos blocos adjacentes e fornece mais pontos se forem capazes de mesclar, mas ainda não consigo obter 2048.

Eu acho que será melhor usar o Expectimax em vez do minimax, mas ainda quero resolver esse problema apenas com o minimax e obter pontuações altas como 2048 ou 4096. Não tenho certeza se estou perdendo alguma coisa.

A animação abaixo mostra os últimos passos do jogo jogado pelo agente de IA com o player do computador:

insira a descrição da imagem aqui

Quaisquer informações serão realmente muito úteis, desde já, obrigado. (Este é o link do meu blog para o artigo: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve -2048-game-with-computer / e o vídeo do youtube: https://www.youtube.com/watch?v=VnVFilfZ0r4 )

A animação a seguir mostra os últimos passos do jogo em que o agente do jogador de IA pode obter pontuações em 2048, desta vez adicionando também a heurística de valor absoluto:

insira a descrição da imagem aqui

As figuras a seguir mostram a árvore do jogo explorada pelo agente de IA do jogador, assumindo o computador como adversário por apenas uma única etapa:

insira a descrição da imagem aqui insira a descrição da imagem aqui insira a descrição da imagem aqui insira a descrição da imagem aqui insira a descrição da imagem aqui insira a descrição da imagem aqui

Sandipan Dey
fonte
9

Eu escrevi um solucionador de 2048 em Haskell, principalmente porque estou aprendendo esse idioma no momento.

Minha implementação do jogo difere um pouco do jogo real, pois um novo bloco é sempre um '2' (em vez de 90% 2 e 10% 4). E que o novo bloco não é aleatório, mas sempre o primeiro disponível no canto superior esquerdo. Essa variante também é conhecida como Det 2048 .

Como conseqüência, esse solucionador é determinístico.

Eu usei um algoritmo exaustivo que favorece azulejos vazios. Ele executa muito rapidamente na profundidade de 1 a 4, mas na profundidade 5 fica mais lento a cerca de 1 segundo por movimento.

Abaixo está o código que implementa o algoritmo de solução. A grade é representada como uma matriz de 16 números inteiros. E a pontuação é feita simplesmente contando o número de quadrados vazios.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

Eu acho que é bem sucedido por sua simplicidade. O resultado alcançado ao iniciar com uma grade vazia e resolver na profundidade 5 é:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

O código-fonte pode ser encontrado aqui: https://github.com/popovitsj/2048-haskell

wvdz
fonte
Tente estendê-lo com as regras reais. É um bom desafio para aprender sobre o gerador aleatório de Haskell!
9788 Thomas Ahle #
Fiquei muito frustrado com Haskell tentando fazer isso, mas provavelmente vou tentar outra vez! Eu achei que o jogo fica consideravelmente mais fácil sem a randomização.
Wdc #
Sem randomização, tenho certeza que você pode encontrar uma maneira de obter sempre 16k ou 32k. No entanto, a randomização em Haskell não é tão ruim assim, você só precisa de uma maneira de contornar a `semente '. Faça isso explicitamente ou com a mônada aleatória.
9788 Thomas Ahle
Refinar o algoritmo para que ele sempre alcança 16k / 32k para um jogo não-aleatória pode ser outro desafio interessante ...
wvdz
Você está certo, é mais difícil do que eu pensava. Consegui encontrar esta sequência: [CIMA, ESQUERDA, ESQUERDA, CIMA, ESQUERDA, BAIXO, ESQUERDA], que sempre vence o jogo, mas não ultrapassa 2048. (No caso de nenhuma jogada legal, o algoritmo de ciclo apenas escolhe o próximo em sentido horário)
Thomas Ahle
6

Esse algoritmo não é ideal para ganhar o jogo, mas é bastante ideal em termos de desempenho e quantidade de código necessário:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }
API-Beast
fonte
10
funciona melhor se você diz random from (right, right, right, down, down, up) que nem todos os movimentos têm igual probabilidade. :)
Daren
3
Na verdade, se você é completamente novo no jogo, realmente ajuda a usar apenas 3 chaves, basicamente o que esse algoritmo faz. Portanto, não é tão ruim quanto parece à primeira vista.
Dígitos
5
Sim, é baseado em minha própria observação com o jogo. Até você ter que usar a quarta direção, o jogo praticamente se resolverá sem nenhum tipo de observação. Esse "AI" deve ser capaz de chegar a 512/1024 sem verificar o valor exato de qualquer bloco.
API-Beast
3
Uma IA adequada tentaria evitar chegar a um estado em que só pode se mover em uma direção a todo custo.
API-Beast
3
Usar apenas 3 direções é realmente uma estratégia muito decente! Isso me levou quase ao 2048 jogando o jogo manualmente. Se você combinar isso com outras estratégias para decidir entre os três movimentos restantes, pode ser muito poderoso. Sem mencionar que reduzir a opção para 3 tem um enorme impacto no desempenho.
Wdc #
4

Muitas das outras respostas usam IA com pesquisa computacionalmente cara de possíveis futuros, heurísticas, aprendizado e outros. Estes são impressionantes e provavelmente o caminho correto a seguir, mas desejo contribuir com outra idéia.

Modele o tipo de estratégia que os bons jogadores do jogo usam.

Por exemplo:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Leia os quadrados na ordem mostrada acima, até que o valor dos próximos quadrados seja maior que o atual. Isso apresenta o problema de tentar mesclar outro bloco do mesmo valor nesse quadrado.

Para resolver esse problema, existem duas maneiras de mudar que não são deixadas ou pioram e examinar as duas possibilidades pode revelar imediatamente mais problemas; isso forma uma lista de dependências, cada problema exigindo que outro problema seja resolvido primeiro. Eu acho que tenho essa cadeia ou, em alguns casos, uma árvore de dependências internamente ao decidir meu próximo passo, principalmente quando preso.


O bloco precisa ser mesclado com o vizinho, mas é muito pequeno: mesclar outro vizinho com esse.

Ladrilho maior no caminho: aumente o valor de um ladrilho menor ao redor.

etc ...


Toda a abordagem provavelmente será mais complicada do que isso, mas não muito mais complicada. Poderia ser tão mecânico em sentir falta de pontuações, pesos, neurônios e pesquisas profundas de possibilidades. A árvore de possibilidades precisa mesmo ser grande o suficiente para precisar de qualquer ramificação.

alan2here
fonte
5
Você está descrevendo uma pesquisa local com heurísticas. Isso o deixará preso, então você precisa planejar com antecedência os próximos movimentos. Isso, por sua vez, leva você a uma pesquisa e pontuação das soluções (para decidir). Portanto, isso realmente não é diferente de qualquer outra solução apresentada.
runDOSrun