Qual é o algoritmo ideal para o jogo 2048?

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?

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:

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 .

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.

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 .

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.

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

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:

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.

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.

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:

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:

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:

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:

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

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.

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: onde 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:

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.

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

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

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.

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) ⁴ . 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>

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.

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);
}

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.

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.

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:

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:

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:

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

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")
  }

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.