Criando o bot (quatro) de conexão (quase) perfeito com tempo de movimento e tamanho de arquivo limitados

Em operações de bits, os estados iniciais de edição de alfa-beta e codificação rígida do jogo criam um agente AI muito forte para conectar quatro.

Gilles Vandewiele Blocked Unblock Seguir Seguindo 28 de novembro de 2017

No contexto do curso de 'Informática', onde os engenheiros do primeiro ano da Universidade de Ghent aprendem a codificar em Python, montamos uma plataforma de competição de bot de IA . O objetivo era criar um bot que jogasse o jogo connect-four implementando a seguinte função:

 def generate_move (placa, jogador, saved_state): 
"" "Contém todo o código necessário para gerar um movimento,
dado um estado de jogo atual (tabuleiro e jogador)
 Args: 
 board (2D np.array): tabuleiro de jogo (elemento é 0, 1 ou 2) 
jogador (int): seu número de placador (float)
saved_state (object): valor retornado da chamada anterior
 Retorna: 
 ação (int): number in [0, 6] 
saved_state (opcional, objeto): será retornado na próxima vez
a função é chamada
 "" " 
return 0

Depois de enviar o código para a plataforma, você desafia automaticamente todos os jogadores classificados acima de você na tabela de classificação. Os jogos são simulados entre seu bot e seus oponentes. Cada jogo consiste em cinco rodadas nas quais 5 pontos são concedidos ao jogador que pode conectar primeiro quatro fichas ou 1 ponto ao jogador que conectou a maior cadeia (provavelmente 3 fichas) primeiro, no caso de um empate. Isso para garantir que sempre haja um vencedor. O jogador inicial da primeira rodada é escolhido aleatoriamente, após o qual os jogadores alternam em quem começa. Sua classificação continua aumentando até você perder (jogo da escada).

Uma simulação de um jogo entre bots. O jogador 1 está definitivamente na mão vencedora.

Um colega, Jeroen van der Hooft , e eu decidimos que seria um exercício divertido tentar imitar um solucionador perfeito ( que ganha o jogo se ele puder começar ), com base no post do blog seguinte, tanto quanto possível. Alguns requisitos importantes que nosso código tinha que cumprir (o que levou ao fato de nosso solucionador não ser completamente ideal) eram:
* tamanho máximo de arquivo de 1 MB
* generate_move não pode ser executado por mais de 1s
* use apenas a biblioteca padrão e o NumPy

Representando o tabuleiro de jogo com bitstrings

Vamos primeiro introduzir uma estrutura de dados eficiente para armazenar o tabuleiro de jogo: bitstrings . Vou resumir as operações mais importantes (como verificar se quatro tokens estão conectados e atualizar a placa após um movimento). Para uma explicação muito completa sobre os bitstrings (ou bitboards), e todas as operações possíveis, por favor, verifique este readme (embora feito um pouco diferente).

Podemos representar cada estado de jogo possível (ou configuração do tabuleiro de jogo) exclusivamente na forma de dois bitstrings, que podem ser facilmente convertidos em um inteiro:
* um bitstring representando as posições dos tokens de um jogador ( posição )
* um bitstring representando as posições de ambos os jogadores ( máscara )
A posição bitstring do oponente pode ser calculada aplicando um operador XOR entre a máscara e a posição . É claro que armazenar dois bitstrings para os tokens de ambos os jogadores também é uma abordagem viável (podemos calcular a máscara aplicando o operador OR em ambos os bitstrings).

O bitstring é composto de 49 bits que inclui uma linha sentinela (todos os 0's) de 7 bits (o uso disto será explicado em breve). Os bits são ordenados da seguinte maneira:

A ordenação dos bits no bitstring (0 é o bit menos significativo, ou mais à direita). Observe como os bits 6, 13, 20, 27, 34, 41 e 48 formam uma linha sentinela, que é sempre preenchida com 0s.

Por exemplo, verifique a seguinte configuração do tabuleiro de jogo:

Um exemplo de uma possível configuração de estado / placa do jogo

Agora vamos formar os bitstrings, com a bitstring de posição para o jogador amarelo:

 posição 
0000000
0000000
0000000
0011000 = b'0000000000000000000110001101000100000000000000000 '
0001000
0000100
0001100 = 832700416
 mascarar 
0000000
0000000
0001000
0011000 = b'0000000000000100000110011111000111100000000000000 '
0011000
0011100
0011110 = 35230302208
 (posição do adversário) 
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0001000 0001000
0011000 XOR 0011000 = 0000000
0001000 0011000 0010000
0000100 0011100 0011000
0001100 0011110 0010010

Como o parâmetro de entrada da placa é uma matriz numpy de matrizes numpy, primeiro precisamos converter essa placa nos bitmaps correspondentes. Abaixo está o código (bastante direto) para fazer isso:

 def get_position_mask_bitmap (placa, jogador): 
posição, máscara = '', ''
# Comece com a coluna mais à direita
para j no intervalo (6, -1, -1):
# Adicione 0 bits ao sentinela
mascarar + = '0'
posição + = '0'
# Comece com a fila de baixo
para i no intervalo (0, 6):
mask + = ['0', '1'] [tabuleiro [i, j]! = 0]
posição + = ['0', '1'] [tabuleiro [i, j] == jogador]
retornar int (posição, 2), int (máscara, 2)

Agora podemos usar a posição bitstring para verificar se quatro tokens estão conectados, com as seguintes operações bit a bit :

 def connected_four (posição): 
# Checagem horizontal
m = posição & (posição >> 7)
se m & (m >> 14):
return True
 # Diagonal 
m = posição & (posição >> 6)
se m & (m >> 12):
return True
 # Diagonal / 
m = posição & (posição >> 8)
se m & (m >> 16):
return True
 # Vertical 
m = posição & (posição >> 1)
se m & (m >> 2):
return True
 # Nada encontrado 
retorna falso

Agora vamos dividir a parte onde verificamos se quatro tokens estão conectados horizontalmente:

 1. m = posição & (posição >> 7) 
2. se m & (m >> 14):
return True

O primeiro passo (1.) está mudando as 7 posições da string de bits para a direita e tomando uma máscara AND, isso se resume a mover cada bit para a esquerda em nossa placa de bits (diminuímos o índice na bitstring, onde o índice 0 corresponde ao bit mais adequado ou menos significativo). Vamos pegar o seguinte bitboard como exemplo (versão simplificada que não pode ocorrer em um jogo real):

 0000000 
0000000
0011110
0000000
0000000
0000000
0000000
 = b'0000000001000000100000010000001000000000000000000 ' 
>> 7: b'0000000000000000100000010000001000000100000000000 '
 0000000 
0000000
0111100
0000000
0000000
0000000
0000000
 &: b'0000000000000000000000010000001000000100000000000 ' 
 0000000 
0000000
0011100
0000000
0000000
0000000
0000000

Podemos ver o novo bitboard da seguinte forma: um bit é igual a 1 se houver um token à esquerda dele e se for o mesmo (ou em outras palavras: os bits iguais a 1 indicam que podemos conectar dois tokens horizontalmente a a esquerda dessa posição ). Agora, para a próxima operação (2.), deslocamos nosso resultado 14 posições para a direita e aplicamos novamente uma máscara AND.

 0000000 
0000000
0011100
0000000
0000000
0000000
0000000
 = b'0000000000000000100000010000001000000000000000000 ' 
>> 14: b'0000000000000000000000000000001000000100000000000 '
-------------------------------------------------
&: b'0000000000000000000000000000001000000000000000000 '
 > 0 : True # quatro tokens encontrados encontrados 

Deslocando as nossas 14 posições de bitstring resultantes para a direita, estamos verificando se podemos combinar dois tokens consecutivos horizontalmente com dois outros tokens consecutivos horizontalmente 2 posições deixadas no tabuleiro. Essas etapas combinadas são equivalentes a verificar se quatro tokens estão conectados horizontalmente. As operações para as outras direções (diagonal e vertical) são as mesmas, apenas mudamos nosso bitmap para mais ou menos posições (1 para vertical, 8 para diagonal para o sudoeste / () e 6 para diagonal para sudeste ()).

A razão para a linha sentinela (os sete bits extras) é fazer uma distinção entre a linha superior e a linha de engarrafamento da grade. Sem isso, essa abordagem produziria falsos positivos, abaixo estão dois bitstrings de posição , um em uma grade de 6×7, o outro em uma grade de 7×7. Verificamos se podemos encontrar quatro tokens consecutivos verticalmente (o que é, neste caso, falso)

 verificação vertical na grade 6x7 
--------------------------
0010000
0010000
0010000
0000000
0000000
0001000
 = b'000000000000000000000001111000000000000000 ' 
>> 1: b'000000000000000000000000111100000000000000 '
&: b'000000000000000000000000111000000000000000 '
>> 2: b'000000000000000000000000001110000000000000 '
&: b'000000000000000000000000001000000000000000 '
> 0 ?: Verdadeiro (ERRADO)
 verificação vertical na grade 7x7 
--------------------------
0000000
0010000
0010000
0010000
0000000
0000000
0001000
 = b'0000000000000000000000000001011100000000000000000 ' 
>> 1: b'0000000000000000000000000000101110000000000000000 '
&: b'0000000000000000000000000000001100000000000000000 '
>> 2: b'0000000000000000000000000000000011000000000000000 '
&: b'0000000000000000000000000000000000000000000000000 '
> 0 ?: Falso (CORRETO)

Agora vamos dar uma olhada melhor na operação de movimento, onde alteramos os bitmaps de acordo com um movimento feito por um jogador:

 def make_move (posição, máscara, col): 
new_position = position ^ mask
new_mask = mask | (máscara + (1 << (col * 7)))
return new_position, new_mask

A primeira coisa que fazemos é aplicar uma máscara XOR entre a posição e a máscara de bitstring para obter a posição de bitstring para o oponente (já que será sua vez após fazer este movimento). Em seguida, atualizamos nossa máscara de bitstring aplicando uma máscara OR entre a máscara atual e uma adição da máscara com um bit na coluna correspondente (onde queremos descartar nosso token). Vamos dar uma olhada em um exemplo:

 posição 
0000000
0000000
0000000
0011000
0001000
0000100
0001100
 mascarar 
0000000
0000000
0001000
0011000
0011000
0011100
0011110
 # Soltar um token na quarta coluna 
-> make_move (posição, máscara, 4)
 new_position = position ^ mask 
nova posição
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0001000 0001000
0011000 XOR 0011000 = 0000000
0001000 0011000 0010000
0000100 0011100 0011000
0001100 0011110 0010010
 1 << (col * 7) 
0000000
0000000
0000000
0000000 = 268435456
0000000
0000000
0000100
 máscara + (1 << (col * 7)) = 35230302208 + 268435456 = 35498737664 
0000000
0000000
0001000
0011000
0011 1 00
0011000
0011010
 máscara | (máscara + (1 << (col * 7))) 
0000000
0000000
0001000
0011000
0011 1 00
0011100
0011110

Árvores de jogo, minimax e poda alfa-beta

Ao ler a seção anterior, você pode estar pensando: "por que você adicionaria tanta complexidade ao seu código?". A razão pela qual estamos otimizando demais as operações básicas do jogo de quatro conectas é por causa do conceito que vou introduzir agora: árvores de jogos .

Para cada jogo que tenha um espaço de ação discreto (ou um número finito de ações possíveis em cada movimento), podemos construir uma árvore de jogo na qual cada nó representa um possível estado de jogo. Os nós internos com profundidade igual representam o estado inicial do jogo (a raiz) ou um estado de jogo que resultou de um movimento feito pelo oponente. Os nós internos a uma profundidade ímpar representam estados de jogo resultantes de movimentos feitos por nós. Se um estado for final de jogo (quatro tokens conectados ou placa cheia), é um nó de folha. Cada nó da folha recebe uma determinada pontuação e não é mais expandido. Abaixo está um exemplo de uma subárvore de jogo para o jogo conectar-quatro.

Um exemplo de um caminho para um estado final de jogo em uma subárvore de jogo

No total, existem 4531985219092 possíveis nós de folhas e, portanto, um número muito maior de nós totais na árvore. Mesmo com as operações otimizadas de bitboard, é computacionalmente inviável percorrer toda a árvore de jogos. Vamos precisar de técnicas para encontrar com eficiência um caminho vencedor nesta árvore.

Agora, enquanto o caminho 1–1–2 na árvore de jogos da figura acima leva a um estado final do jogo onde o jogador amarelo vence (é um caminho vencedor), ele repousa no pressuposto de que o vermelho é um bot estúpido e estraga seu movimento (ele não bloqueia você).

Como não sabemos o quão bom é o bot que vamos jogar, temos que assumir o pior caso: e se o nosso oponente for o melhor possível e, assim, fizer o melhor movimento possível todas as vezes? Se conseguirmos encontrar um caminho vencedor contra um bot tão pessimista, então podemos definitivamente seguir esse caminho e ter certeza de que ganharemos o jogo (o bot real só pode piorar, fazendo com que o jogo acabe mais cedo). Para o jogo conectar-quatro, esse caminho existe se você for o jogador inicial. Aqui é onde o algoritmo minimax entra em jogo.

Antes de podermos aplicar este algoritmo às árvores de jogos, precisamos definir uma função de pontuação para cada nó na árvore. Vamos apenas pegar a mesma função de pontuação que a postagem no blog em que esta escrita está baseada. A pontuação de uma configuração de tabuleiro de jogo é igual a:
* 0 se o jogo terminar em empate
* 22 – o número de pedras usadas se pudermos ganhar o jogo
* – (22 – o número de pedras) se vai perder.
Na figura abaixo, se assumirmos que somos o jogador amarelo, podemos atribuir uma pontuação de -18 ao tabuleiro de jogo, já que o jogador vermelho pode ganhar com sua quarta pedra.

Este tabuleiro é atribuído uma pontuação de -18 desde que o adversário pode terminar com 4 pedras

Na prática, é difícil atribuir uma pontuação quando o jogo ainda não terminou. É por isso que exploramos nossa árvore até chegarmos a um nó da folha, calculamos a pontuação e propagamos essa pontuação de volta para a raiz. Agora, quando estamos propagando esses valores para cima, os nós internos dentro da nossa árvore de jogos receberão múltiplos valores (um valor para cada um de seus filhos). A questão é qual valor devemos atribuir aos nós internos. Agora podemos dar a definição para o valor de um nó interno:
* Se o nó interno estiver em uma profundidade ímpar, tomamos o valor mínimo dos valores para os filhos (como um oponente, queremos tornar a pontuação final o mais negativa possível, já que queremos vencer)
* Se o nó interno estiver em uma profundidade uniforme, nós tomamos o valor máximo das crianças por seus valores (queremos que nossa pontuação seja a mais positiva possível)

Aqui está um exemplo, tirado diretamente da wikipedia :

A pontuação ótima que podemos alcançar é -7, tomando a ação que corresponde à borda que vai para o filho direito da raiz.

Então, agora temos uma maneira de encontrar o caminho ideal dentro de uma árvore de jogos. O problema com essa abordagem é que, especialmente no início do jogo, leva muito tempo para percorrer a árvore inteira. Nós só temos 1 segundo para fazer um movimento! Portanto, introduzimos uma técnica que nos permite remover partes (grandes) da árvore do jogo, de tal forma que não precisamos procurá-la completamente. O algoritmo é chamado de poda alfa-beta .

Vou resumir os conceitos mais importantes. Um bom vídeo passo a passo, pelo prof. Pieter Abbeel, pode ser encontrado aqui . Nós definimos as seguintes variáveis:
* alpha : a melhor pontuação atual no caminho para a raiz pelo maximizer (us)
* beta : a melhor pontuação atual no caminho para a raiz pelo minimizador (oponente)

O que fazemos é atualizar nossos valores alfa e beta toda vez que vemos um novo valor de nossos filhos (dependendo se estamos em uma profundidade par ou ímpar). Nós passamos esses alfa e beta junto aos nossos outros filhos, agora quando encontramos um valor que é mais alto do que o nosso beta atual, ou inferior ao nosso alfa atual, podemos descartar toda a subárvore (já que temos certeza de que o caminho ideal será não passe por isso). Vamos dar uma olhada em outro exemplo, retirado da wikipedia :

  • Atravessamos a profundidade da árvore de jogo primeiro, da esquerda para a direita. A primeira folha que encontramos é a folha mais à esquerda (com valor 5). A folha propaga esse valor para seu pai, onde o valor beta é atualizado e alterado para 5. Ele também verifica a segunda folha mais à esquerda (que tem um valor de 6), mas isso não atualiza nenhum dos valores (desde 6 não é melhor que 5 se estivermos na perspectiva do minimizador).
  • O melhor valor encontrado neste nó (novamente, 5) é propagado para seu pai, onde o valor alfa é atualizado. Agora, estamos no filho certo desse pai e primeiro verificamos seu filho esquerdo com o valor 7 e atualizamos o valor beta (agora temos alfa = 5 e beta = 7). Verificamos o seguinte filho: com o valor 4, esse é um valor melhor para o minimizador, então agora temos beta = 4 e alfa = 5.
  • Desde agora beta ? alfa, podemos podar todas as crianças restantes. Isso ocorre porque sempre teremos um valor ? 4 nesse nó interno (somos um minimizador e apenas atualizamos nosso valor quando encontramos um valor menor que o atual), MAS o nó pai só atualizará os valores quando eles estiverem ? 5 (já que somos um maximizador nesse nó). Portanto, qualquer que seja o valor que teremos depois de percorrer todos os nós, ele nunca será escolhido pelo nó maximizador, pois ele deve ser maior que 5 para que isso aconteça.
  • Este processo continua para todos os nós restantes…

Uma boa implementação em python deste algoritmo, pelos autores de um dos livros de referência mais proeminentes da IA , pode ser encontrada aqui .

Na seção seguinte, otimizações adicionais para este algoritmo alfa-beta, das quais a maioria é adaptada especificamente para o jogo conectar-quatro, serão discutidas. Para avaliar o ganho no desempenho de cada uma das otimizações, vamos configurar uma linha de base. Vamos expressar a taxa de sucesso em função do número ou movimentos já realizados. Uma execução foi bem sucedida se a solução foi encontrada dentro de um segundo. Aqui está o nosso plano de base.

As taxas de sucesso em função do comprimento da sequência. Quanto mais longa a sequência, menores os movimentos até um estado final do jogo e, portanto, quão grande é a probabilidade de um sucesso. Podemos ver que nosso algoritmo pode encontrar os movimentos ótimos uma vez que 27 movimentos já tenham sido feitos (o que significa que teríamos que encontrar uma solução intermediária para os primeiros 26 movimentos).

Outras otimizações

No que segue agora, as otimizações implementadas mais significativas serão listadas com um gráfico correspondente das taxas de sucesso, em comparação com a linha de base.

1. Uso de cache (tabelas de transposição e cache LRU do Python)
Podemos adicionar a posição e mascarar o bitmap para formar uma chave exclusiva. Essa chave pode ser armazenada em um dicionário com o limite superior ou inferior correspondente. Agora, antes de começar a iterar sobre todos os nossos filhos, já podemos inicializar nosso valor atual, obtendo o limite correspondente do cache primeiro. Outra otimização muito simples é adicionar lru_cache decorators a todas as funções auxiliares.

Podemos ver bastante uma melhoria de nossas taxas de sucesso em comparação com a linha de base. Infelizmente, temos um patamar de aproximadamente o mesmo valor de x da nossa linha de base, o que significa que ainda precisamos de uma solução intermediária para nossos (aproximadamente) primeiros 26 movimentos.

2. Determinação anterior do estado vencedor
Inicialmente, um estado final (nó de folha) foi atingido quando quatro tokens foram conectados ou 42 movimentos foram feitos. Já podemos determinar um movimento antes se o jogo terminar ou não (ou seja, se houver três tokens conectados e o usuário puder fazer um movimento que introduza o quarto token na conexão). Esta é uma verificação muito eficiente e torna nossas árvores mais rasas.

Nós vemos uma melhora significativa tornando nossas árvores mais rasas… Além disso, nós alcançamos um valor x menor (por volta de 23), o que significa que precisaremos apenas de uma solução intermediária para os primeiros 22 movimentos.

3. Ir para qualquer caminho vencedor, não o caminho vencedor com menor número de movimentos
Em vez de procurar um valor máximo ou mínimo, podemos apenas seguir o caminho do primeiro valor estritamente positivo ou negativo (respectivamente). Esses caminhos não são os melhores (não vamos ganhar com um número mínimo de jogadas ou perder com um número máximo de jogadas), mas ficamos mais do que felizes com uma vitória regular (não precisa ser a melhor).

Um aumento nas taxas de sucesso, mas não nos estabilizamos em um valor x menor.

4. Outras otimizações
Muitas outras otimizações foram tentadas: multiprocessamento (não funcionou, provavelmente devido ao overhead em Python), ordenando a ordem da travessia da folha com base na heurística (trabalhada apenas em baixas profundidades da árvore do jogo), podando subárvores mais cedo que levar a uma perda de jogo (ganho pequeno), etc. Aqui estão as taxas de sucesso da nossa solução final:

As melhorias finais listadas não resultaram em ganhos significativos. Nosso solucionador pode resolver todas as seqüências assim que o comprimento for maior ou igual a 23. Isso significa que precisamos encontrar uma solução para unir os 22 primeiros movimentos, onde o nosso solucionador geralmente leva mais de 1 segundo.

Armazenando os primeiros 22 movimentos ótimos

Agora ainda há muitas otimizações possíveis, mas parece um trabalho quase impossível encontrar a melhor jogada para cada configuração de jogo possível dentro de um segundo, especialmente em uma linguagem como Python. Mas como o jogo é determinístico, há apenas um número limitado de movimentos ideais para cada configuração de jogo. Por exemplo, a jogada ideal para o jogador que está iniciando o jogo é SEMPRE descartar um token na coluna do meio.

Portanto, decidimos armazenar todos os movimentos ideais para sequências mais curtas (ou estados de jogo com uma pequena quantidade de movimentos já feitos) de forma codificada. Novamente, isso provou ser um desafio, já que o tamanho do arquivo só poderia ser de 1 MegaByte.

Para cada sequência possível (um exemplo de uma sequência poderia ser 3330, o que significa que 4 movimentos já foram feitos: 3 fichas na coluna do meio e 1 na coluna mais à esquerda), armazenamos seu movimento ideal ( que seria 4 para esta sequência ). Um dicionário simples, onde as diferentes seqüências representam as chaves e os movimentos ideais, os valores correspondentes explodem muito rapidamente em termos de tamanho de arquivo. Isso se deve a muitas informações redundantes armazenadas. Uma compactação muito eficiente é não usar um dicionário, mas use 7 conjuntos. Armazene todas as seqüências pertencentes a um movimento ideal (mesmo valor no dicionário) no mesmo conjunto (nossa sequência 3330 seria armazenada com outras sequências, como 2220 no mesmo conjunto). Em seguida, consulte todos os conjuntos para encontrar uma determinada sequência e exiba o movimento correspondente quando uma correspondência for encontrada. Um dos sete conjuntos também pode ser descartado para mais alguma compactação (se não conseguirmos encontrar uma correspondência em todos os 6 conjuntos, o conjunto final deverá conter essa sequência).

Esses conjuntos com sequências ainda tendiam a crescer quando queríamos armazenar sequências mais longas também, então decidimos procurar uma maneira ainda mais eficiente de armazenar as seqüências. Nós tentamos achar uma função f tal que f(x) = y onde x é a sequência (consistindo de números 1–7, preenchidos com 0's na frente de tal forma que todas as seqüências tivessem o mesmo comprimento) e y é o movimento ótimo correspondente . Essa é uma configuração típica de aprendizado de máquina, na qual tentamos construir um modelo que prevê com precisão um determinado valor ou classe, dado um vetor de entrada. Além disso, nós tivemos muitos dados (nosso solucionador pode ser visto como um oráculo, você apenas dá a seqüência e espera pela solução ótima correspondente). Tentamos encaixar uma rede neural, mas não conseguimos obter um erro de 0 (o que significa que, para algumas sequências, foi dada uma solução sub-ótima). Em seguida, tentamos uma árvore de decisão, conhecida por suas capacidades de ajuste excessivo (especialmente se você não especificar uma profundidade máxima ou podar a árvore posteriormente). E, de fato, um erro de 0 nos dados poderia ser alcançado (na verdade: desde que não tenhamos dois vetores de entrada idênticos com rótulos conflitantes, uma técnica de indução de árvore de decisão pode sempre descobrir uma hipótese que se encaixa completamente no treinamento). dados). Encontramos, portanto, uma função que gera o movimento ideal para uma determinada sequência de um determinado comprimento. Essa árvore de decisão pode ser desserializada de maneira muito eficiente, percorrendo a largura da árvore primeiro e armazenando as informações dos nós. Abaixo está um exemplo de uma árvore de decisão (para seqüências de até 2). Infelizmente, não conseguimos que a solução de árvore de decisão funcionasse nos contêineres dockerizados e tivemos que recorrer aos 6 conjuntos para armazenar nossas seqüências.

Uma árvore de decisão para sequências de comprimento máximo 2. O nó raiz pode ser interpretado da seguinte forma: se o tabuleiro estiver vazio ou o primeiro movimento do adversário estiver na coluna mais à esquerda (sequência vazia ou '1'), coloque um token no meio. Como esperado, vemos muitos nós de folhas com 4 (já que mover um token na coluna do meio geralmente é o movimento mais ideal no início do jogo). O nó raiz e seus dois filhos podem ser serializados como: '0 <2 4 1 <2', que é muito eficiente em termos de espaço.

Uma vez que o jogo connect-four é simétrico, nunca armazenamos uma sequência maior que todos os 4's. Assim, se fôssemos armazenar sequências até o comprimento 4, armazenaríamos apenas as seqüências menores que 4444. Se alguma vez encontramos uma sequência maior que essa, podemos espelhá-la aplicando 8 — k para cada k em nossa sequência. Além disso, dado que existe uma solução ótima para cada estado, é possível dividir conjuntos de movimentos em dois conjuntos distintos: um para movimentos ímpares e para movimentos pares. Usando esta abordagem permite reduzir significativamente a representação do estado. Como exemplo, considere a seguinte sequência de movimentos:

 1. 3 
2 3
1. 3
2 3
1. 3
2. 0
1. 2
2. 1

Uma representação possível seria 33333021. No entanto, sabemos que nosso bot terá a solução ideal em cada estado possível. Como tal, é suficiente extrair os movimentos feitos apenas pelo adversário. Isso resulta em uma representação de estado de 3301 ou 3332, se o bot for o primeiro ou o segundo jogador, respectivamente. O uso dessas representações de estado resulta em caminhos menores na árvore e, portanto, em uma tabela de pesquisa de ação mais compactada.

Notas conclusivas

Jeroen e eu nos divertimos muito enquanto competíamos e foi um bom exercício para nós dois. Esperávamos que uma submissão fosse suficiente para chegar ao primeiro lugar, mas tivemos alguns problemas para fazer nosso código funcionar no lado do servidor dos contêineres dockerized.

Gostaria de agradecer a todos os alunos que competiram e gostariam de parabenizar o TomVDM, o pythonneke e o Ledlamp pelos seus três primeiros lugares. Além disso, fiquei impressionado com a diversidade e a complexidade das submissões feitas pelos estudantes de engenharia do primeiro ano. As submissões variaram de poda alfa-beta (embora pesquisas menos profundas do que as nossas), abordagens heurísticas muito inteligentes para redes neurais.

Se alguma coisa nesta postagem do blog não estiver clara, se você souber de possíveis melhorias ou se quiser mais esclarecimentos sobre algumas das partes escritas, deixe um comentário. Além disso, estou disposto a compartilhar o código python (de nível de pesquisa) com outros, mediante solicitação.

Até o próximo ano para outra competição de IA;),
Gilles e Jeroen