A primeira parte (análise de código) está aqui: https://habr.com/post/420725/ .

Algoritmo

Descrição do produto

O algoritmo executa continuamente as seguintes etapas:

1. Ele espera até que um novo tetrimino seja criado.
2. Verifica o tipo do tetrimino recém-criado, o tipo do próximo tetrimino (figura no campo de visualização) e o conteúdo do campo de jogo.
3. Explora todas as maneiras possíveis de adicionar dois tetriminos ao campo de jogo e avalia cada probabilidade.
4. Move o tetrimino recém-criado para que ele corresponda à localização da melhor probabilidade detectada.

Cada uma dessas etapas é descrita em detalhes abaixo.

Bloquear pesquisa

Considere uma versão simplificada do Tetris, na qual as formas não caem automaticamente. A única maneira de reduzir a figura é baixá-la suavemente. Depois de remover os tempos do jogo, podemos descrever completamente o estado do tetrimino ativo por sua posição e orientação. A figura possui um local conhecido de criação inicial e as seguintes operações são usadas para converter de um estado para outro:

• Um passo para baixo
• Um passo à esquerda
• Mova um passo para a direita
• Gire um passo no sentido anti-horário
• Rotação no sentido horário

Essas operações são aplicáveis ​​apenas quando os quadrados do tetrimino resultante correspondem a células vazias do campo de jogo. Quando é impossível descer um passo, o estado é considerado bloqueado. No entanto, como simplificamos o Tetris e a espera pelo bloqueio é essencialmente infinita, o estado bloqueado pode ser transformado ainda mais por outras operações, deslizando e rolando.

Muitos estados bloqueados com uma sequência mínima de operações que os criam podem ser encontrados usando a BFS (largura da primeira pesquisa). Conforme indicado abaixo, ele usa uma fila para armazenar resultados intermediários.

1. Enfileiramos o estado na criação.
2. Deduzimos o estado da fila.
3. Obtemos os seguintes estados usando a operação de conversão.
4. Se não houver movimento descendente entre eles, o estado removido da fila será bloqueado.
5. Enfileiramos estados subsequentes que ainda não foram visitados.
6. Se a fila não estiver vazia, repita da etapa 2.

O programa representa cada estado como um objeto com os seguintes campos:

{ x, y, rotation, visited, predecessor }

No processo de preparação, o programa cria uma matriz tridimensional de objetos de estado (20 linhas × 10 colunas × 4 voltas), inicializando x , y rotation acordo.

O campo visited é marcado quando o estado está na fila. No BFS, isso é válido porque cada estado subsequente aumenta o comprimento total do caminho em 1. Ou seja, aumentando o comprimento do caminho, é impossível criar um estado subsequente que precisa ser inserido em outro lugar que não seja o final da fila para manter a ordem.

O campo predecessor indica o objeto de estado do qual o estado atual é derivado. É definido quando o estado está na fila. O estado de criação não possui estados anteriores.

O conjunto de estados bloqueados detectados durante a pesquisa é determinado pelo tipo de tetrimino e pelos blocos preenchidos no campo de jogo. A sequência dos movimentos que os gerou pode ser esclarecida (na ordem inversa) seguindo os links predecessor ao estado de criação. Quando a constante PLAY_FAST é configurada como true no início do programa, ela ignora completamente os estados anteriores colocando diretamente o tetrimino no campo e bloqueando-o.

Uma matriz tridimensional de objetos de estado, uma fila e BFS são compactados em uma classe. Ele tem um método de busca que recebe o campo de jogo (matriz bidimensional), o tipo de tetrimino e o ouvinte. Cada vez que um estado bloqueado é detectado, o campo de jogo é atualizado adicionando tetrimino ao local apropriado. Em seguida, o campo de jogo alterado, juntamente com as informações sobre as alterações, são transmitidos ao ouvinte para processamento. Depois que o ouvinte completa o retorno, o campo de jogo é restaurado.

O ouvinte é usado para combinar várias operações de pesquisa em uma cadeia, o que possibilita encontrar todas as maneiras possíveis de adicionar dois (ou mais) tetriminos ao campo de jogo. O primeiro mecanismo de pesquisa da cadeia executa o BFS apenas uma vez. No entanto, o segundo mecanismo de pesquisa executa o BFS toda vez que a primeira pesquisa detecta um estado bloqueado. E assim por diante, se houver outros mecanismos de pesquisa na cadeia.

O ouvinte do último mecanismo de pesquisa avalia o campo de jogo alterado. Quando ele encontra o campo de jogo melhor do que o que foi investigado anteriormente, ele anota o objeto usado do estado bloqueado, que atualmente usa o primeiro mecanismo de pesquisa da cadeia. Como o primeiro mecanismo de pesquisa executa o BFS apenas uma vez, os campos predecessor de seus objetos de estado permanecem válidos até a conclusão de todo o processo de pesquisa. Ou seja, o último ouvinte registra essencialmente o caminho ao longo do qual o primeiro tetrimino deve seguir para obter a melhor configuração do campo de jogo como resultado.

Função de avaliação

A função de pontuação atribui um valor ao campo de jogo alterado - uma soma ponderada de vários parâmetros de influência. A função de avaliação usada neste caso é baseada na função desenvolvida por Islam Al-Ashi . Ele usa os seguintes parâmetros:

• Número total de linhas limpas : este é o número total de linhas que serão limpas pela adição de dois tetriminos.
• Altura total de bloqueio : a altura de bloqueio é a altura acima do piso do campo de jogo em que a figura está bloqueada. Esta é a distância vertical que uma figura bloqueada cairia se você remover todos os outros quadrados ocupados do campo de jogo e manter a orientação da figura. A altura total de bloqueio é a soma das alturas de bloqueio dos dois tetriminos.
• O número total de células "boas" : uma célula de poço é uma célula vazia localizada acima de todas as células ocupadas em uma coluna, de modo que seus vizinhos esquerdo e direito sejam células ocupadas; ao determinar os poços, as paredes do campo de jogo são consideradas células ocupadas. A ideia é que um poço seja uma estrutura aberta no topo, fechada no fundo e cercada por paredes de ambos os lados. A probabilidade de lacunas intermitentes nas paredes do poço significa que as células do poço não ocorrem necessariamente em uma pilha contínua dentro de uma coluna.
• Número total de orifícios nas colunas : o orifício na coluna é uma célula vazia localizada imediatamente abaixo da célula ocupada. O gênero do campo de jogo não é comparado com a célula acima dele. Não há furos nas colunas vazias.
• Número total de transições em colunas : uma transição em colunas é uma célula vazia adjacente a uma célula ocupada (ou vice-versa) em uma única coluna. A combinação do bloco de colunas ocupado mais acima com o espaço vazio acima dele não é considerada uma transição. Da mesma forma, o piso do campo de jogo também não é comparado com a célula acima dele. Portanto, não há transições em uma coluna completamente vazia.
• Número total de transições em linhas : uma transição em linhas é uma célula vazia adjacente a uma célula ocupada (ou vice-versa) na mesma linha. Células vazias perto das paredes do campo de jogo são consideradas transições. O valor total é calculado para todas as linhas do campo de jogo. No entanto, linhas completamente vazias não são levadas em consideração no número total de transições.

El-Ashi sugeriu que pesos úteis podem ser encontrados usando o algoritmo de otimização de enxame de partículas (PSO), que melhora iterativamente o conjunto de soluções, simulando o comportamento do enxame observado na natureza. No nosso caso, cada solução é um vetor de peso e a adequação da opção é determinada pelo jogo no Tetris; este é o número total de tetriminos durante os quais ele sobreviveu até o final do jogo.

Essas idéias são aplicadas na versão Java descrita abaixo; ele roda fora do FCEUX e pode ser configurado para um jogo na memória não gráfico, rodando a uma velocidade muito maior. Depois de preparar o PSO, fiquei surpreso ao ver que o algoritmo não se move mais após a iteração inicial. Após essa iteração, várias variantes de solução geradas aleatoriamente já eram muito boas. Por vários dias, o tamanho desse conjunto diminuiu até restar apenas uma opção. Aqui estão os valores para esta solução:

Parâmetro	Peso
Número total de linhas limpas	1.000000000000000
Altura total de bloqueio	12.885008263218383
Número total de células de poço	15.842707182438396
O número total de furos nas colunas	26.894496507795950
O número total de transições nas colunas	27.616914062397015
Total de saltos de linha	30.185110719279040

O campo de jogo foi estimado multiplicando os parâmetros pelos respectivos pesos e somando os resultados. Quanto menor o valor, melhor a solução. Como todos os parâmetros e pesos têm valores positivos, todos os parâmetros prejudicam a avaliação geral; cada um deles deve ser minimizado. Isso também significa que a melhor pontuação é 0.

Como esses pesos foram selecionados aleatoriamente, a faixa de valores adequados pode ser muito ampla. Esse conjunto específico de números e a importância relativa estimada de cada parâmetro podem não ser relevantes. No entanto, será interessante observá-los de perto.

O parâmetro menos prejudicial é o número total de linhas limpas. O fato de esta opção ser prejudicial é contra-intuitivo. Mas o principal objetivo da IA ​​é a sobrevivência. Ele não se esforça para obter mais pontos. Em vez disso, ele joga de maneira conservadora, geralmente limpando as fileiras uma de cada vez. Para obter Double, Triple ou Tetris, você precisa cultivar um monte que vai contra o objetivo de longo prazo.

O próximo na lista é a altura total do bloqueio. Pode ser minimizado abaixando o tetrimino o mais próximo possível do chão. Essa é uma estratégia simples que contribui a longo prazo para a sobrevivência e, a curto prazo, para embalagens de qualidade de peças.

O peso atribuído ao número total de células de poços parece um pouco surpreendente, porque jogadores experientes geralmente constroem poços profundos intencionalmente para coletar vários Tetris (combinações de quatro linhas) seguidas. Mas, como mencionado acima, este é um jogo arriscado, ao contrário do objetivo principal - a sobrevivência. Além disso, o número de poços é um indicador da "rugosidade" da pilha. Um certo nível de irregularidade é benéfico ao colocar determinadas figuras ou combinações de figuras. Mas a alta rugosidade causa danos à embalagem apertada.

O número total de furos nas colunas é aproximadamente metade do número total de transições nas colunas. Esses parâmetros podem ser combinados e recolhidos em um parâmetro relacionado comum, obtendo um parâmetro mais extenso e mais prejudicial: o número total de transições.

As áreas densamente compactadas têm um pequeno número de transições em todas as direções. Portanto, a principal estratégia, impulsionada pela inteligência artificial, pode ser brevemente descrita da seguinte forma: empacote as peças o mais próximo possível uma da outra.

Outras opções

Aqui está uma lista de mais alguns parâmetros que experimentei durante o desenvolvimento da IA:

• Altura da pilha : blocos movimentados podem pairar sobre células vazias, criando saliências e buracos; no entanto, não é possível bloquear blocos ocupados em linhas completamente vazias. Portanto, altura da pilha é o número de linhas que contêm pelo menos um bloco ocupado.
• Número total de colunas ocupadas : este é o número de colunas que contêm pelo menos uma célula ocupada.
• Número total de células ocupadas : o número de células ocupadas no campo de jogo.
• Número total de áreas conectadas : o algoritmo de preenchimento é usado aqui para calcular o número de áreas conectadas continuamente. Além de encontrar "ilhas" ocupadas, ele descobre buracos que se estendem ao longo dos dois eixos.
• Dispersão da altura da coluna : é uma medida estatística da variação nas alturas da coluna. É um indicador de rugosidade da superfície.
• Valor total de adaptação : calcula o valor de adaptação do heap para a próxima figura desconhecida. Ele conta o número total de maneiras pelas quais 7 tipos de formas podem ser adicionados ao campo de jogo sem a aparência de novos furos. Para uma contagem precisa, será necessário o uso repetido de BFS. Mas, para um cálculo aproximado, a árvore de pesquisa pode ser muito truncada.
• Classificação média para a próxima figura : esse parâmetro aprofunda a pesquisa analisando todas as possibilidades para a próxima figura desconhecida. Ele usa outros parâmetros para separar a localização de cada tipo de figura e, em seguida, retorna a média para 7 classificações. Para cada posicionamento da figura, é necessário o BFS.
• Jogo simulado médio : o parâmetro simula uma série de jogos no Tetris, selecionando peças usando seu próprio gerador de números pseudo-aleatórios e usando a IA para trabalhar com elas. No final de cada jogo, o campo de jogo é avaliado usando outros parâmetros. O valor médio para todos os lotes é retornado.

Todos os parâmetros podem ser personalizados adicionando fatores personalizados. Por exemplo, em vez de simplesmente calcular as linhas limpas, você pode atribuir seus próprios pesos para Single, Double, Triple e Tetris, simulando um sistema de pontos. Se a limpeza simultânea de várias linhas prejudicar o objetivo de sobrevivência a longo prazo, então linhas únicas podem receber peso negativo, enquanto outras podem ficar positivas.

Outro fator útil é o valor de compensação. Por exemplo, uma superfície perfeitamente plana de uma pilha tem uma dispersão de alturas de coluna de 0. Mas uma superfície perfeitamente plana não se adapta a S e Z, assim como a outras combinações de formas. Portanto, subtraindo a constante, a variação deve ser centrada em torno da rugosidade ideal.

Os parâmetros ajustados e tendenciosos podem ser aumentados até certo ponto, para que antes do cálculo da soma ponderada eles possam escalar logaritmicamente ou exponencialmente. Todas essas probabilidades podem ser consideradas como pesos adicionais que podem ser potencialmente otimizados por métodos como PSO.

Muitos dos parâmetros permitem entender como a pilha pode lidar com peças adicionais, por exemplo, aquelas que lidam com a rugosidade da superfície, mas a "quantidade total de adaptação", "classificação média da próxima figura" e "jogo simulado médio" avaliam o campo de jogo alterado inserir figuras que não estão incluídas nos dois conhecidos. No estudo das figuras subseqüentes, devido à rápida eliminação das séries, a quantidade de conhecimento adicional obtido diminui com a profundidade. Isso significa que o longo percurso do partido não é tão importante, e o curso do partido no futuro distante também não é muito importante. De fato, se uma curta sequência de figuras é aleatoriamente configurada incorretamente, a IA restaura rapidamente o jogo, usando as seguintes figuras para limpar as linhas afetadas. Determinar o valor ideal para a análise de figuras subsequentes requer mais pesquisas.

Outro aspecto da utilidade de um parâmetro é o custo computacional. Os custos aumentam bastante porque a função de avaliação é chamada para cada colocação possível de dois números. Como a IA deve poder reproduzir o Tetris em tempo real, os fatores de custo que fornecem informações valiosas podem ser trocados por técnicas mais aproximadas, que são executadas mais rapidamente.

Treinamento de IA

Existem sequências patológicas que podem levar ao Game Over, independentemente da estratégia. O exemplo mais simples é a sequência interminável de tetrimino S e Z, que, como mostrado na animação, leva rapidamente a IA a perder.


Como leva dias para executar a variante AI antes da conclusão de vários lotes e calcular a média, é completamente impraticável usar a duração média do lote como uma métrica de controle PSO. Em vez disso, você pode aumentar a complexidade do jogo com uma velocidade controlada, aumentando a frequência de S e Z, o que com o tempo levará à criação alternativa apenas desse par de figuras.

Tentei usar esse método de ensino, mas descobri que ensinar IA a trabalhar com S e Z freqüentes prejudica a capacidade de lidar com formas aleatórias distribuídas uniformemente.

Em um método alternativo inspirado no jogo do tipo B, a métrica PSO controla a frequência da limpeza das linhas. O campo de jogo é um diagrama de 10 linhas de blocos de lixo aleatórios e, cada vez que a linha é limpa, uma nova linha de lixo aparece abaixo, restaurando a altura da pilha. Como o campo de jogo tem uma largura de 10 colunas e cada tetrimino consiste em 4 quadrados, em média, a IA deve limpar uma linha a cada 2,5 tetrimino. E para se livrar do lixo, ele deve fazê-lo ainda mais rápido.

Infelizmente, essa técnica também não melhorou o desempenho. Uma razão provável é que os buracos de lixo aleatórios não correspondem exatamente às strings com as quais a IA lida no jogo real. Além disso, limpar a linha é uma meta de curto prazo; limpeza de linha gananciosa não melhora necessariamente a sobrevivência a longo prazo. De tempos em tempos, as linhas não devem ser tocadas para processar certas combinações de figuras subseqüentes.

Colin Fei sugeriu uma abordagem diferente em sua página da web. Ele criou histogramas que mostram a porcentagem de formas bloqueadas em cada linha durante os lotes de teste. Curiosamente, todos os histogramas parecem quase idênticos, independentemente do número de figuras criadas. Com base nisso, ele sugeriu que você possa usar uma imagem aproximada da função para qualquer lote de avaliação ao avaliar a expectativa estatística de bloquear uma figura na linha de criação, obtendo assim o tempo durante o qual a IA será reproduzida até o final do jogo. Eu decidi explorar essa possibilidade.

Abaixo está um mapa de calor de muitos lotes de teste, no total contendo 2.039.900.000 de tetrimino. Cada célula é colorida com base na porcentagem de formas bloqueadas nela. Para aprimorar o contraste visual, uma paleta não linear é selecionada. O mapa foi criado normalizando os valores das células, dividindo pela porcentagem máxima de células e anunciando a potência de 0,19 (consulte "correção gama" ).

Cor Percentagem ■ 0.00000000 ■ 0.00000315 ■ 0.00024227 ■ 0.00307038 ■ 0.01860818 ■ 0.07527774 ■ 0.23582574 ■ 0.61928352 ■ 1.42923040 ■ 2.98867416 ■ 5.78182519

As listras laranja escuro e vermelho nas linhas 17 e 18 significam que a grande maioria das figuras termina ali. A tonalidade verde pálida de baixo é uma conseqüência da geometria das figuras: apenas 4 dos 7 tipos de tetrimino podem aparecer na linha inferior. Os cantos inferiores são pretos porque é impossível chegar lá.

A cor ao longo de cada linha é quase uniforme, e isso sugere que as formas são distribuídas horizontalmente uniformemente. Pequenas lacunas podem ser explicadas observando os histogramas de tipos individuais de formas:

T

J

Z

O

S

L

Eu

T é o tipo mais universal: seu histograma é mais uniforme que todos os outros. Anomalias no histograma J - o resultado da influência das paredes; apenas Jr e Jl podem estar nas colunas laterais, o que faz com que a IA use as colunas 1 e 9. com mais freqüência para compensar.O mesmo se aplica a L. Os histogramas Z e S parecem aproximadamente os mesmos, o que enfatiza o desequilíbrio devido ao fato de Zv e Sv não são imagens espelhadas perfeitas uma da outra. O tipo O é limitado a um campo de jogo de 19 × 9 e parece que a IA tem maior probabilidade de usar O nas laterais do que no centro. Tetrimino I é deslocado para a direita, porque seu ponto de partida está localizado lá; portanto, o bloqueio na coluna 1 é raro.

A tabela mostra a porcentagem de números bloqueados em cada linha.

String	Percentagem
0 0	0,0000000000
1	0,0000000000
2	0.0000004902
3	0.0000026472
4	0.0000066180
5	0.0000172557
6	0.0000512280
7	0.0001759400
8	0.0006681210
9	0.0023187901
10	0.0077928820
11	0.0259672043
12	0.0866187068
13	0.2901315751
14	0.9771663807
15	3.3000408353
16	10.6989059268
17	28.5687976371
18	50.0335706162
19	6.0077671454

Aqui está um gráfico dos valores:


Se a linha 19 não for levada em consideração, o gráfico mostra um crescimento exponencial.

A seguir, é apresentada uma lista das proporções do número de formas bloqueadas nas linhas adjacentes.

String A / String B	Relação (%)
1/2	0,00
2/3	18,52
3/4	40,00
4/5	38,35
5/6	33,68
6/7	29/12
8/7	26,33
9/8	28,81
9/10	29,76
10/11	30/01
11/12	29,98
13/12	29,85
13/14	29,69
14/15	29,61
15/16	30,84
16/17	37,45
17/18	57,10
18/19	832,81

As linhas 16–19levam em consideração as figuras que interagem com o chão do campo de jogo, para que possam ser descartadas. Nas linhas, a 0–5seleção é pequena demais para ser significativa. As taxas restantes, pares 6 / 7–14 / 15, são quase idênticas; seu valor médio é de 29,24%. Isso significa que a probabilidade de o heap crescer uma linha é aproximadamente a mesma, independentemente da altura do heap. Isso é lógico, porque as regras do Tetris limitam a interação na parte superior da pilha quando ela está compactada.

O gráfico a seguir mostra o log de ₁₀ % das figuras nas linhas 6–15.


É próximo a uma linha perfeitamente reta com um coeficiente de determinação próximo a 1 . A fórmula derivada da regressão linear mostrada acima nos dá a interseção com o eixo Y, assumindo que a porcentagem de formas na linha 0 seja aproximadamente 10 ^−7,459 %. O inverso desse valor nos dá uma expectativa estatística de 2.877.688.349 tetrimino ou 1.151.175.340 linhas até o final do jogo.

Isso nos faz entender que o log ₁₀a porcentagem de figuras em cada linha permanece linear até a linha 0. No entanto, quando a pilha quase atinge o teto do campo de jogo, a liberdade de movimento é limitada a tal ponto que essa propriedade é violada. Além disso, bloquear uma peça na linha 0 não significa necessariamente game over; você ainda pode ser salvo se houver um lugar para criar novas figuras.

Outra maneira de avaliar a força da IA ​​é medir o número médio de formas criadas entre a limpeza completa do campo de jogo. A limpeza completa pode ser obtida com apenas 5 tetriminos. Por exemplo, entre outras possibilidades, isso pode ser alcançado por cinco figuras O dispostas no chão do campo de jogo.Em geral, como cada tetrimino consiste em 4 quadrados e a largura do campo de jogo é 10 quadrados, o número de figuras criadas entre a limpeza completa deve ser um múltiplo de 5 ( desde4 × 5n = 2 × 10n ).

Minha IA tem um número médio de formas criadas entre as limpezas de campo completo de 1.181 - um número bastante pequeno. Como uma limpeza completa é como reiniciar um jogo, um lote inteiro pode ser visto como uma série extremamente longa de reinicializações do jogo, seguida por um rápido avanço no fim do jogo. Como a sequência de alternativas descrita acima SZ, as seqüências patológicas que levam ao final do jogo são geralmente muito curtas.

O histograma abaixo mostra a probabilidade (em porcentagem) de que a IA alcance uma limpeza completa do campo após o número especificado de figuras criadas.


A ordem dos graus na fórmula acima determina a taxa de diminuição e, presumivelmente, a força da IA. De acordo com esta fórmula, cerca de 0,4%, ou cerca de 1 de 253 jogos começando com um campo vazio, termina com uma limpeza completa após apenas 5 tetriminos.

Em contraste com o que Faye sugeriu, as constantes nas aproximações linear e exponencial requerem um tamanho de amostra muito grande para que R ²abordado 1, portanto esse método não é aplicável ao PSO. No entanto, as constantes obtidas com lotes longos podem ser usadas para otimizar a função de aproximação que cria possíveis valores constantes para lotes curtos. Em um tipo de loop de feedback de desenvolvimento, a função de aproximação otimizada pode ser usada no PSO, o que melhora a IA, que por sua vez pode ser usada para calcular novas constantes, servindo como critério de referência para a função de aproximação.

Versão Java

Sobre o programa

Para desenvolvedores não familiarizados com Lua, adicionei uma porta Java AI ao arquivo zip de origem . Classes são quase tradução linha por linha de objetos Lua com base em fechamentos .

Pacotes

O código é dividido em dois pacotes:

• tetris.ai contém classes e interfaces de IA.
• tetris.gui cria um modelo gráfico do campo de jogo.

Classes e interfaces de IA

Uma classe com o nome apropriado Tetriminosdescreve o tetrimino. É usado de forma semelhante enume contém constantes para todos os tipos de tetrimino:

 public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6; 

NONEsignifica valor não atribuído. É usado para células vazias do campo de jogo.

Também Tetriminoscontém dois modelos da tabela de orientação. PATTERNS- esta é uma matriz inteira quadridimensional (tipo × rotação × quadrado × coordenadas) contendo as coordenadas relativas dos quadrados; as linhas são organizadas de modo que em cada tipo a orientação de criação da forma seja a primeira. ORIENTATIONSÉ outro modelo, uma matriz bidimensional (tipo × rotação) de objetos Orientation. Cada um Orientationcontém as coordenadas do quadrado como uma matriz de objetos Point. Também possui campos que descrevem o intervalo de posições permitidas para a orientação correspondente.

 public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... } 

 public class Point { public int x; public int y; ... } 

A rotação do Tetrimino (o segundo índice nas duas tabelas de orientação) é usada em objetos Stateque o BFS manipula.

 public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... } 

xye , rotationjuntos, descrevem a posição e a orientação da figura. Como o tipo Tetrimino permanece constante desde o momento da criação até o bloqueio, um campo para ele é opcional.

A classe Searcherque contém o algoritmo BFS cria um conjunto completo de todos os objetos possíveis Statequando criados:

 private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } } 

Embora o Java tenha uma API de coleções rica, ele Searchercontém sua própria implementação da fila. A classe Queueusa State.nextpara associar objetos Statea uma lista vinculada. Como todos os objetos Statesão predefinidos e cada um Statepode ser adicionado à fila mais de uma vez, a fila pode funcionar no local, o que elimina a necessidade de objetos de contêiner temporário desnecessários usados ​​em implementações de fila comuns.

O "coração" do BFS é o método mostrado abaixo search.

 public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; } 

Ele gera uma fila com o estado do tetrimino criado e, em seguida, recupera sequencialmente os elementos filhos dos estados removidos da fila, adicionando-os novamente à fila quando aparecem no campo de jogo.

Um searchcampo de jogo que contém uma combinação de células ocupadas e vazias, o tipo de Tetrimino criado e um identificador arbitrário é passado para o método . Durante a execução do BFS, um ouvinte é chamado sempre que uma posição de bloqueio é detectada.

 public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); } 

O ouvinte recebe um campo de jogo alterado contendo um tetrimino bloqueado no local. O tipo de Tetrimino criado e um identificador arbitrário também são transmitidos. O último parâmetro está Stateno qual o tetrimino está bloqueado. Seguindo a cadeia de links State.predecessor, você pode restaurar todo o caminho de volta para Statecriar uma forma.

State.visitedpoderia ser implementado como boolean; mas com todas as comodidades necessárias para resolver antes de pesquisar Statepara alívio visitedno false. Em vez disso, criei um visitedvalor intcomparado a um contador, incrementando a cada chamada.

MétodoaddChildpré-enfileira estados subseqüentes. O estado subsequente deve estar dentro do campo e estar localizado em 4 células vazias do campo de jogo. Além disso, o estado subsequente deve ser não visitado State. Se a posição for válida, addChildretornará truemesmo se o estado subsequente não puder ser colocado na fila porque já foi visitado.

O método searchusa o addChildvalor de retorno para determinar se uma forma pode ser criada. Se a figura não puder ser criada, o heap alcançou o topo e a pesquisa não poderá mais ser realizada; portanto, ele retorna false.

RetornáveladdChildO significado também está sendo estudado para a possibilidade de descer mais um passo. Se isso não puder ser feito, o estado atual é a posição de bloqueio e a chamada é iniciada lockTetrimino. O método lockTetriminoaltera o campo de jogo, chama o ouvinte e depois restaura o campo de jogo.

Cada linha da matriz playfieldcontém 1 elemento adicional, que armazena o número de células ocupadas na linha. Incrementar um elemento é realizado pelo método lockTetriminoporque marca as células como ocupadas.

Quando o ouvinte recebe um campo de jogo modificado, ele chamaPlayfieldUtil.clearRowsPara excluir linhas preenchidas o método os reconhece verificando o valor no elemento adicional da matriz. Para remover uma string, o código tira vantagem do fato de que em Java, matrizes bidimensionais são essencialmente matrizes de matrizes; apenas pressiona os links para as strings. PlayfieldUtilcontém linhas livres; ele conclui o processo de limpeza inserindo um link em um deles. Antes de executar o turno, o índice da linha que está sendo limpa é armazenado em um elemento de linha adicional. Em seguida, o link para a linha é empurrado para a pilha.

Então o ouvinte chamaPlayfieldUtil.restoreRowspara descartar as alterações feitas no campo de jogo. As etapas são canceladas na ordem inversa. Primeiro, temos uma linha livre a partir do topo. Em seguida, a linha preenchida é recuperada da pilha e o índice do elemento adicional é restaurado. É usado para mudar as referências de linha e retornar ao local da linha excluída. Finalmente, um elemento adicional é restaurado, é atribuído o valor da largura do campo de jogo - o número de células ocupadas na linha preenchida.

Também existe PlayfieldUtilum método evaluatePlayfieldque calcula e grava 4 parâmetros de avaliação na classe de contêiner mostrada abaixo.

 public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; } 

A classe gerencia tudo isso AI. Ele contém dois objetos Searcherconectados pelo ouvinte mostrado abaixo.

 public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); } 

Uma classe AIpode lidar com qualquer número de objetos Searcher, mas o Nintendo Tetris mostra apenas uma forma com antecedência. Os objetos Searchersão armazenados em uma matriz e o código mostrado acima serve como seu ouvinte comum. O identificador aleatório passado para o método Searcher.searché realmente o índice da matriz, que também é a profundidade da pesquisa. Quando o ouvinte é chamado, o identificador direciona a chamada para o próximo Searcherna cadeia. Se ele chegar ao final da matriz, avalia o campo de jogo. E quando ele encontra um campo de jogo com uma pontuação mais alta de condicionamento físico, ele anota o bloqueado Statedo primeiro Searcherda cadeia.

AIcontém um método searchque recebe o campo de jogo e uma matriz que contém os tipos do tetrimino criado e do próximo. Ele voltaStatecontendo a posição e rotação em que o primeiro tetrimino deve ser bloqueado. Ele não se concentra no segundo tetrimino; da próxima vez que for chamado, recalcula a pontuação. Se a pilha for muito alta e a cadeia Searcherfalhar em colocar os dois tetriminos, ela AI.searchretornará null.

 public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; } 

Desafio de IA

Como a versão Java não está vinculada ao FCEUX, ela pode potencialmente ser usada para outros projetos. Para aqueles que estão interessados ​​em integrar a IA em outro lugar, esta seção descreve tudo o que você precisa.

Primeiro, crie uma instância AI, instância PlayfieldUtile matriz para armazenar todos os tipos conhecidos de tetrimino. Além disso, crie uma PlayfieldUtil.createPlayfieldinstância do campo de jogo chamando ; ele retorna uma matriz bidimensional com uma coluna adicional, que examinamos acima. Você provavelmente também precisará de um gerador de números aleatórios.

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); 

Inicialmente, o campo de jogo está vazio e todas as células são relevantes Tetriminos.NONE. Se você preencher as células programaticamente, não esqueça de anotar o playfield[rowIndex][AI.PLAYFIELD_WIDTH]número de células ocupadas em cada linha.

Preencha a matriz de tipos de tetrimino com os tipos da forma criada inicialmente e a próxima forma, que geralmente são selecionadas manualmente.

 tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); 

Em seguida, dar o campo de jogo e tipos de matriz no método AI.search. Ele retornará Stateno qual você precisará bloquear o primeiro tetrimino. Se ele voltar null, o jogo acabará inevitável.

 State state = ai.search(playfield, tetriminos); 

Se você precisar de uma maneira de criar peças para bloquear, passar Statemétodo AI.buildStateList.

 State[] states = ai.buildStatesList(state); 

Para atualizar o campo de jogo, nós o transmitiremos PlayfieldUtil.lockTetriminojunto com seu tipo e objeto State. Este método limpa automaticamente as linhas preenchidas.

 playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); 

Antes de ligar novamente, AI.searchvocê precisa selecionar aleatoriamente o próximo tetrimino.

 tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); 

Juntos, fica assim:

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) { // ... print playfield ... State state = ai.search(playfield, tetriminos); if (state == null) { break; // game over } playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); } 

Em vez de exibir o campo de jogo em forma de texto, você pode usar uma maneira mais interessante de exibir o que está acontecendo ...

Exibição do campo de jogo

A classe TetrisFrameimita os gráficos do Nintendo Tetris, incluindo recursos comportamentais descritos na parte anterior do artigo.


Para vê-lo em ação, execute-o tetris.gui.Main. Assim como na versão Lua, podemos ajustar a velocidade do jogo alterando o valor constante no início do arquivo.

 public static final boolean PLAY_FAST = true; 

TetrisFramepossui 4 métodos para manipular a tela. O método displayTetriminoprocessa o tetrimino ativo nas coordenadas especificadas. Ele recebe um parâmetro de atraso, que faz com que o método aguarde antes de retornar o número especificado de quadros de animação.

 public void displayTetrimino(int type, int rotation, int x, int y, int delay) 

O método lockTetriminobloqueia a figura no lugar. As cores do contador de linhas, pontos, nível e tetrimino são atualizadas de acordo, demonstrando o comportamento curioso esperado quando os valores excedem os valores permitidos. A atribuição de um animatevalor a um parâmetro trueinclui animações de limpeza de linha e tremulação da tela ao receber o Tetris. O método é bloqueado até a animação terminar.

 public void lockTetrimino(int type, int rotation, int x, int y, boolean animate) 

updateStatisticsAndNext executa um incremento do contador de estatísticas para o tetrimino recém-criado e atualiza a exibição da próxima figura.

 public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino) 

O método dropTetriminocria uma forma e permite que ela desça sob a influência da "gravidade", sem fazer nenhuma tentativa de girá-la ou movê-la. Mainusa-o para as duas últimas figuras quando AI.searchretorna null. Se o parâmetro for animateimportante true, se for impossível criar uma figura, a cortina do final do jogo cairá. Como em todos os outros métodos, esse método é bloqueado até a animação terminar. Ele retorna trueapenas quando pode criar uma figura em um campo de jogo ocupado.

 public boolean dropTetrimino(int type, boolean animate) 

Esses 4 métodos devem ser chamados pelo fluxo de trabalho, mas TetrisFramedevem ser criados no próprio thread de distribuição de eventos. Para ver como isso é feito, veja a turma Main.

Por uma questão de interesse, ele Mainusa uma classe Randomizerque simula um gerador de números pseudo-aleatórios da Nintendo Tetris.

O pacote tetris.gui.imagescontém arquivos relacionados à exibição. tiles.png- Esta é uma tabela de padrões que contém todos os gráficos de blocos. background.datarmazena os identificadores dos blocos que compõem o plano de fundo; dados extraídos de $BF3F. E colors.datcontém bytes que geram cores quadradas incomuns que aparecem no nível 138.

ImageLoaderContém uma tabela de paletas do NES e o ImagePaneconjunto completo de valores de nível exibidos é armazenado.

Outros projetos

Potencialmente, o código pode ser usado em vez de gravar no modo de demonstração. De fato, essa demonstração pode ser renderizada para sempre, aproveitando a rapidez com que a IA é capaz de limpar todo o campo. Para conseguir isso, no gerador de números pseudo-aleatórios, você precisa usar alguma constante arbitrária como semente, o que nos dará uma sequência tetrimino determinística. As duas primeiras seqüências de tetrimino serão gravadas. Quando a IA atingir a limpeza de campo total, os próximos dois tetriminos serão comparados com os dois primeiros da sequência. Se eles corresponderem (esse evento é esperado a cada 49 limpezas de campo completo), o gerador de números pseudo-aleatórios pode passar a mesma constante que a semente, o que criará um loop de demonstração infinito. A duração do ciclo pode ser muito longa para ocultar o fato de que é um ciclo. Tambéma demonstração pode começar em um ponto aleatório no loop, criando uma nova demonstração a cada vez.

Outra possibilidade de usar a IA é criar um modo "player versus computer". No Tetris para vários jogadores, enquanto limpa várias linhas ao mesmo tempo, linhas de lixo aparecem na parte inferior do campo do oponente, aumentando o campo de jogo. A IA deve poder se proteger de detritos pelo mesmo motivo que pode jogar jogos do tipo B. No entanto, como afirmado anteriormente, a IA é executada de maneira conservadora, geralmente tentando limpar uma linha de cada vez. Ou seja, ele será capaz de se defender de ataques, mas ele não é capaz de atacar. Para poder mudar seu comportamento, criei uma interface chamada IChildFilter.

 public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); } 

AIpossui um construtor alternativo que obtém uma implementação IChildFilter. Se disponível, IChildFilter.validateserve como uma verificação adicional para a permissão do estado filho; se retornar false, o estado filho não está na fila.

WellFilterÉ uma implementaçãoIChildFilterdestinado a pegar quatro linhas (Tetris). Como jogadores vivos, ela gradualmente constrói um poço na coluna mais à direita do campo de jogo, subindo linha por linha de baixo para cima. Como funciona linha por linha, rejeita os estados filhos que adicionam um quadrado à coluna mais à direita. Quando a linha inteira, com exceção da coluna do poço, está completamente cheia, o AI prossegue para a próxima linha. Quando 4 ou mais dessas linhas estão prontas, permite que o "bastão" caia no poço e obtenha Tetris. Além disso, a altura da pilha é rastreada; se ficar muito grande, WellFilterdeixa de afetar a IA.


Para testá-lo em operação, faça as Mainseguintes alterações:

 AI ai = new AI(new WellFilter()); 

WellFilterfunciona, mas não é particularmente eficaz. Ele contém uma heurística simples projetada para demonstrar o conceito. Para obter o Tetris com mais frequência, você precisa usar uma estratégia mais sofisticada, talvez uma que possa ser otimizada usando o PSO.

Além disso, você pode usar a filtragem de estado filho para gerar padrões. Abaixo está um exemplo do que ele é capaz PatternFilter.


PatternFilterCria imagens linha por linha de baixo para cima, semelhante à forma como funciona WellFilter; no entanto, em vez de preservar a coluna mais à direita, ele PatternFilteraprova apenas os estados filhos que correspondem a um padrão específico.

O construtor PatternFilterobtém o nome de uma das imagens no pacote tetris.gui.patterns, que ele usa como modelo. Cada imagem 20 × 10 contém pixels em preto e branco correspondentes às células no campo de jogo.

 AI ai = new AI(new PatternFilter("tetriminos")); 

A linha de código mostrada acima cria as silhuetas de sete tipos de tetrimino.


Outro exemplo com um grande tetrimino T girado em ângulo.


Outro exemplo Se você olhar de perto, verá o nome do jogo.


Como WellFilter, PatternFilternada mais é do que uma prova de conceito. Os padrões que ele processa são limitados ao fundo do campo devido ao fato de que as tentativas de obtê-los geralmente terminam com o fim do jogo. No entanto, essa é uma ideia interessante que vale a pena estudar mais.

Versão do Gamepad

O script Lua e o programa Java ignoram a gravidade; para eles, a velocidade de descida não é importante, pois, dependendo da configuração, eles teleportam as figuras imediatamente para o local desejado ou arrastam ao longo de qualquer caminho escolhido. De certa forma, eles apenas imitam Tetris, não o reproduzem. No entanto, no arquivo zip com as fontes, há outro script Lua que é gerado ao gerar os sinais dos botões do gamepad, o que permite ao jogo controlar o movimento de figuras, gravidade e tudo mais.

A adição de gravidade expande bastante o espaço de pesquisa, forçando a IA a levar em conta as regras astutas de manipulação de formas. Os detalhes dessas regras são descritos na primeira parte do artigo e podem ser totalmente apreciados por um estudo direto do código. Aqui estão os mais importantes:

• : , .
• «» .
• «» «» .
• .
• .
• .
• .
• , .
• A B .
• «» «» 6 16 . «» «» , .
• «» 3 .
• 96 . , — .

Para acomodar todas essas regras, as informações históricas devem ser incorporadas nos estados de pesquisa. Eles precisam de campos nos quais o número de quadros de espera para cada botão e o número de quadros após a última liberação automática serão armazenados. Cada conjunto exclusivo de valores, incluindo coordenadas x, ye a rotação do tetrimino caracterizam um estado separado e único. Infelizmente, o número de possibilidades é tão vasto que uma pesquisa completa desse espaço é impraticável. A versão AI do gamepad explora apenas um subconjunto dele.

O AI usa um objeto Statecom os seguintes campos:

 { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor } 

Em vez de usar o deslocamento automático da IA ​​em quadros alternativos, pressione e solte o botão shift. Portanto, ele precisa monitorar apenas se o botão está pressionado e não por quanto tempo ele é pressionado. Uma vez que nenhuma rotação automática, a mesma ideia se aplica aos botões A e B. Portanto, o campo Left, Right, Ae Bpode ser interpretado como a listagem contendo um dos seguintes valores:

 { RELEASED, PRESSED } 

Por outro lado, para descida suave, você deve inicialmente manter pressionado o botão "Para baixo" por três quadros, o que requer a existência de 4 estados:

 { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES } 

Downaumenta incrementalmente do valor RELEASEDpara o PRESSED_FOR_3_FRAMESqual ocorre uma descida suave. Depois disso, ele pode receber um valor RELEASEDou retornar a PRESSED_FOR_2_FRAMES, causando uma descida suave a cada segundo quadro após o atraso inicial. Não pode ser RELEASEDde PRESSED_FOR_1_FRAMEou de PRESSED_FOR_2_FRAMES.

Na verdade, o código Lua usa uma constante inteira, mas o princípio é o mesmo.

Da mesma forma, visitede predecessor, fallTimerele é atribuído o valor obtido quando se escreve no estado fila subsidiária; ele fallTimerserá um a mais que o valor do estado pai. Condição que contémfallTimer, igual à velocidade de descida, implica que a descida automática ocorra nesse quadro e, para estados subsequentes desse estado, o valor fallTimerserá 0.

Cada Searcherpré-define uma 8-matriz que contém todos os estados possíveis ( 20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B) e o BFS é executado de maneira semelhante ao método mostrado para a matriz. O pseudo-código mostrado abaixo descreve como os estados subsequentes são obtidos a partir dos estados inativos.

 Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end 

Conforme mostrado no pseudo-código abaixo, a função addChildleva em consideração a ordem dos eventos que ocorrem em cada quadro (por exemplo, deslocamento, rotação e descida).

 nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end 

Como na versão anterior, ele AI.searchretorna uma cadeia de objetos State. Mas, neste caso, cada um Statecontém muitos botões que precisam ser pressionados em cada quadro. Campo x, ye rotationnão são usados para manipular os números, mas pode ser usado para verificar a regularidade do movimento figuras.

Embora o espaço de pesquisa tenha sido significativamente reduzido devido às limitações descritas acima, leva 1-3 segundos para concluir a pesquisa. Se você executá-lo, notará uma pausa após criar cada tetrimino. Além disso, os movimentos parecem muito antinaturais; geralmente é feita uma curva um instante antes de travar. No entanto, essa IA funciona quase da mesma maneira que a versão que ignorou a gravidade, mesmo na velocidade máxima.

Para verificar, execute-o lua/NintendoTetrisAIGamepadVersion.lua, localizado no arquivo zip com as fontes .

Uma maneira mais simples de explicar a gravidade é limitar o movimento das figuras apenas girando, seguido de uma mudança e depois descendo para o fundo. A idéia é que, se você se livrar do deslizamento e da rolagem, a velocidade vertical das figuras terá pouco efeito na IA; tudo o que ele precisa fazer é entregar a figura na coluna desejada, e a gravidade fará o resto. Outra vantagem dessa técnica é que o espaço de pesquisa é muito pequeno, o que permite que você jogue em tempo real, sem demora para cálculos. No entanto, a desvantagem dessa abordagem é que, sem deslizar e rolar, a IA é muito pior. No entanto, o Tetris AI, incapaz de jogar em tempo real, é praticamente inútil.

Adição

Anteriormente, escrevi um plug-in que simulava processualmente um jogador no Tetris. No entanto, meu projeto teve algumas desvantagens:

1. O bot desligou a gravidade, permitindo executar deslizamentos e rolagem, excedendo as capacidades do jogador no nível mínimo do Nintendo Tetris. Ele nunca eleva os números, mas a única maneira de reduzi-los é uma descida suave controlada. Ou seja, ele joga em um mundo idealizado e teórico. Para ser franco, ele trapaceia.
2. . — , . Double, Triple Tetris, — , . 90. , , 29 - .
3. . . . , Tetris .

Nesta seção, falarei sobre um bot avançado que joga o Nintendo Tetris sem desativar a gravidade. Ele avalia o risco e o gerencia, esforçando-se agressivamente para obter o número máximo de pontos antes de atingir uma alta velocidade de descida.

---

Vídeo

Veja o bot ganhar o número máximo de pontos do Nintendo Tetris a partir do nível 19 em todos os vídeos mostrados abaixo.

---

Baixar

TetrisAI_2018-01-28.zip

O arquivo .zipcontém:

• src - árvore de código fonte.
• TetrisAI.jar - arquivo binário compilado.
• lgpl-2.1.txt - licença de software livre.

---

Lançamento

Pré-requisitos

• Nintaco é um emulador de NES / Famicom.
• Tetris (U) [!].nes - arquivo ROM Nintendo Tetris.

Lançamento do plug-in

1. Inicie o Nintaco e abra Tetris (U) [!].nes.
2. Extrair TetrisAI.jardo baixado .zip.
3. Abra a janela Executar Programa, escolhendo Ferramentas | Executar programa ...
4. JAR Find JAR… .
5. Load JAR, .
6. Run.
7. , GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), .
8. A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .

Vale a pena considerar que o bot foi projetado apenas para o nível 19 e acima. Em níveis mais baixos, ele não será capaz de controlar as peças.

Referência de velocidade

Para que o jogo acelere, selecione Máquina | Velocidade Máx.

---

Detalhes

Platô

Abaixo do nível 10, a velocidade de descida em cada nível é um pouco mais alta que na anterior. Mas no nível 10 e acima, existem vários planaltos nos quais a velocidade permanece constante por vários níveis. Isso é uma consequência da maneira como o mecanismo de gatilho funciona. A velocidade é apresentada como o número de quadros por descida, que é um valor inteiro. Ou seja, para níveis mais altos não existem muitas opções: 10–12, 13–15, 16–18, 19–28 e 29+ são 5, 4, 3, 2 e 1 quadro para descida.

O bot foi desenvolvido levando em consideração apenas o platô 19–28. Nos quadros pares, ele clica no gamepad "Esquerda", "Direita", A, B ou nada. E em quadros ímpares, permite a descida automática sem pressionar nenhum botão. Parece que o jogo não percebe o movimento horizontal coincidindo com a rotação; portanto, cada botão é pressionado independentemente em quadros pares.

Diferentemente dos mestres que tocam em níveis altos, o bot não tira proveito do DAS (Delayed Auto Shift), também conhecido como repetição automática, e técnicas relacionadas. Seu trabalho lembra mais a técnica do polegar vibratório de Thor Akerlund . No entanto, aumenta a frequência da vibração para o máximo teórico permitido pelo jogo.

Os jogadores são recompensados ​​com 40, 100, 300 e 1200 pontos por Single, Double, Triple e Tetris. E os pontos são multiplicados pelo número do nível mais 1. Em outras palavras, para obter a pontuação máxima, o jogador deve se esforçar para obter o número máximo de Tetris, jogando o maior tempo possível em níveis altos.

O nível 19 é o mais alto que pode ser selecionado como o inicial, o que permite que o bot salte diretamente para o platô 19–28. No entanto, devido a um erro no mecanismo de cálculo de nível que mencionei na parte anterior, o jogo passará para o nível 20 após limpar 140 linhas, em vez dos 200 esperados. Depois disso, o jogo mudará de nível a cada 10 linhas. No entanto, depois de atingir 230 linhas, o bot subirá do platô e desistirá rapidamente. Ou seja, ele precisa discar o máximo de Tetris possível antes de limpar 230 linhas.

Descida suave

A descida suave também pode aumentar o número de pontos. Para ganhar pontos, a figura deve ser suavemente abaixada para travar no campo de jogo. Qualquer descida suave de curto prazo que ocorra ao longo do caminho ao posicionar uma figura não afetará a pontuação. Se a descida for bem sucedida, o jogador receberá um ponto para cada linha cruzada durante a descida suave. E o valor resultante não é multiplicado pelo número do nível, mesmo que uma descida suave leve à limpeza das linhas.

A descida suave tem pouco efeito na pontuação geral. No entanto, se possível, o bot conclui o posicionamento da figura clicando em "Para baixo" para obter esses pontos. Em casos raros, pode calcular a diferença entre uma pontuação muito alta e exceder a pontuação máxima.

Algoritmo AI

Ao criar uma forma, o bot explora todos os posicionamentos possíveis das formas atuais e seguintes. Posicionamento permitido é a posição em que a figura repousa nas células ocupadas ou no chão do campo de jogo. A partir do local de criação da figura, essa posição pode ser alcançada através de uma sequência de movimentos horizontais, curvas e descidas. Locais válidos e seqüências de caminhos são encontrados usando o BSF.

A colocação de uma peça no campo de jogo tem consequências: 4 células vazias ficam ocupadas e todas as linhas preenchidas são limpas, deixando as linhas descerem. Para cada posicionamento permitido da figura atual e as consequências associadas a ela, o bot verifica cada posicionamento válido da figura seguinte, avaliando a combinação de consequências. Essa cadeia de pesquisa é apresentada SearchChain.

Cada uma das consequências combinadas é transferida para uma função de avaliação que calcula o conteúdo do campo de jogo. A combinação com a menor pontuação vence e a peça atual é colocada de acordo. Os resultados da cadeia de pesquisa afetam apenas a forma atual. Ao criar a próxima figura, ela é avaliada em combinação com a figura a seguir e assim por diante.

Função de avaliação

A função de avaliação é uma soma ponderada dos seguintes parâmetros:

• O número total de linhas limpas é o número de linhas limpas pela adição de ambos os tetriminos.
• – , . — , , .
• - – .
• – , -.
• – , . . .
• – . , 1. , , .
• – , . — , — .
• – . , (20).
• – . , 0.
• – , ( ) .
• : — , ( ) . . . .
• – . , 1 , 1, — 0.
• – .
• – .
• – .
• – . .
• – .

Aprendizado de máquina

Para encontrar os pesos da função de avaliação, usamos uma variante do método Particle Swarm Optimization (PSO) descrito na nota de rodapé [1]. Para obter um bom comportamento convergente, são aplicados os coeficientes de inércia e aceleração propostos. E os tamanhos máximos dos passos das partículas são determinados pela limitação de seus valores de velocidade.

Durante cada iteração, as partículas foram avaliadas em paralelo para fazer pleno uso dos recursos de computação disponíveis. Além disso, depois que a convergência foi detectada (nenhuma melhoria após um certo número de iterações), o PSO foi configurado para reiniciar automaticamente com pesos selecionados aleatoriamente, o que nos permitiu explorar ainda mais o espaço de pesquisa.

Cada vetor de posição das partículas foi avaliado simulando a conclusão de 100 lotes em um platô de níveis 19 a 28. Um lote completo envolve a limpeza de 230 linhas, mas muitos terminaram com um estouro de campo. As pontuações dos lotes foram classificadas e as pontuações das partículas foram determinadas como a média de 33 dos 100 lotes. A ideia era escolher com base na agressividade. As partículas no terço superior se acostumam apenas às seqüências desejadas de figuras, o que limita a necessidade de um jogo conservador. Como resultado, eles tendem a empurrar o jogo usual para o limiar, esperando o próximo "stick".

Sequências de padrões para 100 lotes foram geradas antes do PSO, e as mesmas sequências foram usadas repetidamente. Isso foi necessário para corrigir o espaço de pesquisa, para que as opções de solução pudessem ser comparadas. As seqüências foram criadas usando a lógica de um verdadeiro PRNG Nintendo Tetris, que é projetado para reduzir as chances de duplicatas se sucederem. Mas o PRNG também tem pontos fracos (consulte a seção “Escolhendo o Tetrimino” de um artigo anterior): ele não seleciona os números uniformemente.

As tentativas iniciais resultaram em bots agindo de forma muito agressiva. Se eles superaram o platô 19–28, geralmente atingiram a pontuação máxima. Infelizmente, porém, muitas vezes cedo demais, levavam a estouros de campo. Em resposta a isso, quatro medidas foram tomadas para "acalmar" os bots:

1. : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
2. . , , 7 . .
3. , , . , 7 .
4. , , . , . , .

Depois de aplicar todas essas regras para "acalmar" os bots, o método PSO forneceu os seguintes pesos:

Parâmetro	Peso
Número total de linhas limpas	0.286127095297893900
Altura total de bloqueio	1.701233676909959200
Número total de células de poço	0.1111304230768307700
Número total de poços profundos	0.910665415998680400
O número total de furos nas colunas	1.879338064244357000
Furos de coluna ponderados totais	2.168463848297177000
Número total de profundidades de furo em colunas	−0.265587111961757270
Profundidade mínima do furo da coluna	0.289886584949610500
Profundidade máxima do furo da coluna	0.362361055261181730
O número total de transições nas colunas	−0,028668795795469625
Total de saltos de linha	0.874179981113233100
Alturas totais da coluna	−0.507409683144361900
Altura da pilha	−2.148676202831281000
Dispersão das alturas da coluna	−1.187558540281141700
Número total de células ocupadas	−2.645656132241128000
Número total ponderado de células ocupadas	0.242043416268706620
Dispersão das alturas das colunas	0.287838126164431440

Como a cadeia busca uma combinação que minimize a função de avaliação, parâmetros com pesos positivos podem ser considerados bônus e o restante é multado. Mas os pesos não mostram necessariamente o significado dos parâmetros correspondentes; eles não são normalizados, portanto, não podem ser comparados.

Força da IA

Para avaliar a força da IA, foram coletados aproximadamente 1,7 milhão de resultados (em pontos) de jogos simulados em um platô de 19 a 28. A pontuação não reflete o jogo no nível 29 ou superior e não leva em consideração os pontos obtidos em descidas suaves. No entanto, inclui jogos concluídos prematuramente devido a estouros de campo. A lógica Nintendo Tetris PRNG foi usada para gerar as seqüências de Tetrimino.

Entre esses resultados, a maior pontuação é de 1.313.600. A mínima é 0. A

média é 816.379 e parece pequena. Mas, como mencionado abaixo, os dados são distorcidos, portanto, a pontuação média de 989.200 pontos dá uma idéia melhor do valor típico.

Como mencionado acima, o PSO otimizou os pesos com base na média do melhor terço dos lotes. Nesse caso, a pontuação média do melhor terço é de 1 108 860. Na verdade, a pontuação média dos melhores 75% é de 1.000.000. O

bot tem uma probabilidade de 47% de atingir o limite de pontos do nível 29. Ele tem uma probabilidade de 61% de obter 900.000 pontos ao nível 29. O gráfico abaixo mostra as probabilidades de pontuação até o nível 29.


Parece que a probabilidade diminui linearmente para cerca de 900.000 pontos. Então entra em uma curva sigmóide invertida.

Abaixo está um histograma suavizado com o número de participantes para cada um dos pontos marcados. Sua forma é determinada pela derivada do gráfico mostrado acima.


Se você ignorar as flutuações, até cerca de 900.000 são planas e depois entra em uma distribuição normal com o centro em torno de 1.050.000 pontos. As razões para as flutuações não são claras. Parece que o número de pontos prefere pular em incrementos de 20.000 pontos. Talvez isso se deva ao ciclo de construção da pilha e à obtenção do Tetris.

Alocação de RAM e ROM

Para manipular a memória da CPU, transmitir cliques no botão e receber eventos de renderização de quadro, o plug-in usa a API do Nintaco . Todos os endereços de memória foram descobertos usando as ferramentas de depuração do Nintaco e as informações foram adicionadas ao wiki do Data Crystal ROMhacking.net . No código fonte, eles se parecem com constantes na interface Addresses.

---

Referências

1. van den Bergh, F.; Engelbrecht, AP (2006)
   A study of particle swarm optimization particle trajectories
   In: Information Sciences 176 (2006) (pp. 937–971)
   Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf