Em operações de bit, poda alpha-beta e estados iniciais de jogo de codificação dura para criar um agente de IA muito forte para ligar quatro.
No contexto do curso ‘Informática’, onde os engenheiros do primeiro ano na Universidade de Gand aprendem a codificar em Python, criámos uma plataforma de competição de bot de IA. O objectivo era criar um bot que jogasse o jogo de ligação – quatro, implementando a seguinte função:
def generate_move(board, player, saved_state):
"""Contains all code required to generate a move,
given a current game state (board & player) Args: board (2D np.array): game board (element is 0, 1 or 2)
player (int): your plabyer number (float)
saved_state (object): returned value from previous call Returns: action (int): number in
saved_state (optional, object): will be returned next time
the function is called """
return 0
Depois de submeter o código à plataforma, desafia-se automaticamente todos os jogadores classificados acima de si no quadro de líderes. Os jogos são simulados entre o seu bot e os adversários. Cada jogo consiste em cinco rondas nas quais são atribuídos 5 pontos ao jogador que pode primeiro ligar quatro fichas ou 1 ponto ao jogador que ligou primeiro a cadeia mais longa (muito provavelmente 3 fichas), em caso de empate. Isto para garantir que há sempre um vencedor. O jogador inicial da primeira volta é escolhido aleatoriamente, após o que os jogadores se alternam em quem começa. A sua classificação continua a aumentar até perder (jogo de escada).
Um colega, Jeroen van der Hooft, e eu decidi que seria um exercício divertido tentar imitar um solucionador perfeito (que ganha o jogo se ele puder começar), baseado no seguinte post no blogue, tanto quanto possível. Alguns requisitos importantes que o nosso código tinha de cumprir (o que levou ao facto de o nosso solucionador não ser completamente óptimo) eram:
* tamanho máximo de ficheiro de 1 MB
* generate_move não podia correr mais do que 1s
* apenas fazer uso da biblioteca padrão e NumPy
P>Vamos primeiro introduzir uma estrutura de dados eficiente para armazenar o tabuleiro do jogo: bitstrings. Vou resumir as operações mais importantes (tais como verificar se quatro fichas estão ligadas, e actualizar o tabuleiro após uma jogada). 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 de forma um pouco diferente).
Podemos representar cada possível estado de jogo (ou configuração do tabuleiro de jogo) unicamente sob a forma de duas bitstrings, que podem ser facilmente convertidas num número inteiro:
* uma bitstring representando as posições das fichas de um jogador (posição)
* uma bitstring representando as posições de ambos os jogadores (máscara)
A posição da bitstring do adversário pode ser calculada aplicando um XOR-operador entre a máscara e a posição. Claro que armazenar duas bitstrings para as fichas de ambos os jogadores é também uma abordagem viável (podemos então calcular a máscara aplicando o operador OR em ambas as bitstrings).
A bitstring é composta de 49 bits que inclui uma fila de sentinela (todos os 0’s) de 7 bits (o uso disto será explicado em breve). Os bits são ordenados da seguinte forma:
Como exemplo, verifique a seguinte configuração do tabuleiro de jogo:
position
0000000
0000000
0000000
0011000 = b'0000000000000000000110001101000100000000000000000'
0001000
0000100
0001100 = 832700416mask
0000000
0000000
0001000
0011000 = b'0000000000000100000110011111000111100000000000000'
0011000
0011100
0011110 = 35230302208(opponent position)
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0001000 0001000
0011000 XOR 0011000 = 0000000
0001000 0011000 0010000
0000100 0011100 0011000
0001100 0011110 0010010
Desde que o parâmetro de entrada do tabuleiro é uma matriz numérica de matrizes numéricas, precisamos primeiro de converter este tabuleiro para os bitmaps correspondentes. Abaixo está o código (bastante simples) para o fazer:
def get_position_mask_bitmap(board, player):
position, mask = '', ''
# Start with right-most column
for j in range(6, -1, -1):
# Add 0-bits to sentinel
mask += '0'
position += '0'
# Start with bottom row
for i in range(0, 6):
mask += != 0]
position += == player]
return int(position, 2), int(mask, 2)
p>Podemos agora usar a posição bitstring para verificar se quatro fichas estão ligadas, com as seguintes operações bitwise:
def connected_four(position):
# Horizontal check
m = position & (position >> 7)
if m & (m >> 14):
return True # Diagonal \
m = position & (position >> 6)
if m & (m >> 12):
return True # Diagonal /
m = position & (position >> 8)
if m & (m >> 16):
return True # Vertical
m = position & (position >> 1)
if m & (m >> 2):
return True # Nothing found
return False
Agora vamos decompor a parte onde verificamos se quatro fichas estão ligadas horizontalmente:
1. m = position & (position >> 7)
2. if m & (m >> 14):
return True
O primeiro passo (1.) está a deslocar as nossas 7 posições do fio de bits para a direita e, tomando uma máscara AND, isto resume-se a mover cada bit para a esquerda no nosso fio de bits (diminuímos o índice no fio de bits, onde o índice 0 corresponde ao bit mais à direita ou ao bit menos significativo). Tomemos como exemplo o seguinte bitboard (versão simplificada que não pode ocorrer num 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 uma ficha à esquerda dele e se for o mesmo (ou seja: as fichas iguais a 1 indicam que podemos ligar duas fichas horizontalmente à esquerda a partir dessa posição). Agora para a próxima operação (2.), deslocamos o nosso resultado 14 posições para a direita e aplicamos uma máscara AND novamente.
0000000
0000000
0011100
0000000
0000000
0000000
0000000= b'0000000000000000100000010000001000000000000000000'
>> 14: b'0000000000000000000000000000001000000100000000000'
-------------------------------------------------
& : b'0000000000000000000000000000001000000000000000000'> 0? : True # four connected tokens found
Ao deslocar as nossas 14 posições de bitstring resultantes para a direita, estamos a verificar se podemos combinar duas fichas na horizontal consecutiva com duas outras fichas 2 posições horizontais consecutivas que lhe restam no tabuleiro. Estes passos combinados são equivalentes a verificar se quatro fichas estão ligadas horizontalmente. As operações para as outras direcções (diagonal e vertical) são as mesmas, apenas deslocamos o nosso bitmap para mais ou menos posições (1 para vertical, 8 para diagonal para sudoeste (/) e 6 para diagonal para sudeste (\)).
A razão para a fila de sentinela (os sete bits extra) é para fazer uma distinção entre a fila superior e a fila inferior da grelha. Sem ela esta abordagem produziria falsos positivos, abaixo estão dois bitstrings de posição, um numa grelha 6×7, o outro numa grelha 7×7. Verificamos se conseguimos encontrar quatro fichas verticalmente consecutivas (o que é, neste caso, falso)
vertical check on 6x7 grid
--------------------------
0010000
0010000
0010000
0000000
0000000
0001000= b'000000000000000000000001111000000000000000'
>> 1: b'000000000000000000000000111100000000000000'
& : b'000000000000000000000000111000000000000000'
>> 2: b'000000000000000000000000001110000000000000'
& : b'000000000000000000000000001000000000000000'
> 0?: True (WRONG)vertical check on 7x7 grid
--------------------------
0000000
0010000
0010000
0010000
0000000
0000000
0001000= b'0000000000000000000000000001011100000000000000000'
>> 1: b'0000000000000000000000000000101110000000000000000'
& : b'0000000000000000000000000000001100000000000000000'
>> 2: b'0000000000000000000000000000000011000000000000000'
& : b'0000000000000000000000000000000000000000000000000'
> 0?: False (CORRECT)
Agora vamos ver melhor a operação de movimentação, onde alteramos os bitmaps de acordo com uma movimentação feita por um jogador:
def make_move(position, mask, col):
new_position = position ^ mask
new_mask = mask | (mask + (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 bitstring para obter a posição bitstring para o adversário (já que vai ser a sua vez depois de fazer este movimento). Depois actualizamos a nossa máscara bitstring aplicando uma máscara OR-máscara entre a máscara actual e uma adição da máscara com um bit na coluna correspondente (onde queremos deixar cair a nossa ficha). Vejamos um exemplo:
position
0000000
0000000
0000000
0011000
0001000
0000100
0001100mask
0000000
0000000
0001000
0011000
0011000
0011100
0011110# Drop a token in the fourth column
--> make_move(position, mask, 4)new_position = position ^ mask
new_position
0000000 0000000 0000000
0000000 0000000 0000000
0000000 0001000 0001000
0011000 XOR 0011000 = 0000000
0001000 0011000 0010000
0000100 0011100 0011000
0001100 0011110 00100101 << (col*7)
0000000
0000000
0000000
0000000 = 268435456
0000000
0000000
0000100mask + (1 << (col*7)) = 35230302208 + 268435456 = 35498737664
0000000
0000000
0001000
0011000
0011100
0011000
0011010mask | (mask + (1 << (col*7)))
0000000
0000000
0001000
0011000
0011100
0011100
0011110
Árvores do jogo, poda de minimax e alpha-beta
Enquanto lia a secção anterior, talvez estivesse a pensar para si próprio: ‘porque é que acrescentaria tanta complexidade ao seu código? A razão pela qual estamos a optimizar em demasia as operações básicas do jogo de ligação-quatro é devido ao conceito que vou agora introduzir: árvores de jogo.
Para cada jogo que tem um espaço de acção discreto (ou um número finito de acções possíveis em cada jogada), podemos construir uma árvore de jogo em que cada nó representa um possível estado de jogo. Os nós internos a uma profundidade uniforme representam ou o estado inicial do jogo (a raiz) ou um estado de jogo que resultou de um movimento feito pelo adversário. Os nós internos a uma profundidade ímpar representam estados de jogo resultantes de jogadas feitas por nós. Se um estado é de fim de jogo (quatro fichas ligadas ou o tabuleiro está cheio), é um nó de folha. Cada nó de folha recebe uma determinada pontuação e não é mais expandido. Abaixo está um exemplo de uma sub-árvore de jogo para o jogo de ligação-quatro.
No total, há 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 optimizadas de bitboard, é computacionalmente inviável atravessar toda a árvore de jogo. Vamos precisar de técnicas para encontrar eficientemente um caminho vencedor nesta árvore.
Agora, enquanto o caminho 1-1-2 na árvore de jogo da figura acima leva a um estado de fim de jogo em que o jogador amarelo ganha (é um caminho vencedor), assenta na suposição de que o vermelho é um robot estúpido e lixa o seu movimento (ele não o bloqueia).
Desde que não sabemos o quão ‘bom’ é o bot contra o qual vamos jogar, temos de assumir o pior caso: e se o nosso adversário for o melhor bot possível e assim fizer sempre a melhor jogada possível? Se conseguirmos encontrar um caminho vencedor contra um bot tão pessimista, então podemos definitivamente tomar este caminho e ter a certeza de que ganhamos o jogo (o verdadeiro bot só pode fazer pior, fazendo com que o jogo acabe mais cedo). Para o jogo de ligação-quatro, tal caminho existe se for o jogador inicial. Aqui é onde o algoritmo do minimax vem no jogo.
Antes de podermos aplicar este algoritmo às árvores do jogo, precisamos de definir uma função de pontuação para cada nó da árvore. Tomaremos apenas a mesma função de pontuação em que o blogue publica esta escrita. A pontuação para uma configuração do tabuleiro de jogo é igual a:
* 0 se o jogo terminar num empate
* 22 – o número de pedras utilizadas se conseguirmos ganhar o jogo
* -(22 – o número de pedras) se perdermos.
Na figura abaixo, se assumirmos que somos o jogador amarelo, podemos atribuir uma pontuação de -18 ao tabuleiro de jogo, uma vez que o jogador vermelho pode ganhar com a sua quarta pedra.
Na prática, é difícil atribuir uma pontuação quando o jogo ainda não terminou. É por isso que exploramos a nossa árvore até alcançarmos um nó de folha, calculamos a pontuação e propagamos esta pontuação de volta para cima até à raiz. Agora, quando estamos a propagar estes valores para cima, os nós internos dentro da nossa árvore de jogo receberão múltiplos valores (um valor para cada um dos seus filhos). A questão é qual o valor que devemos atribuir aos nós internos. Agora podemos dar a definição para o valor de um nó interno:
* Se o nó interno estiver numa profundidade ímpar, tomamos o valor mínimo das crianças os seus valores (como adversário, queremos tornar a pontuação final o mais negativa possível, uma vez que queremos ganhar)
* Se o nó interno estiver numa profundidade par, tomamos o valor máximo das crianças os seus valores (queremos que a nossa pontuação seja o mais positiva possível)
Aqui está um exemplo, retirado directamente da wikipedia:
Então agora temos uma maneira de encontrar o caminho óptimo dentro de uma árvore de jogo. O problema com esta abordagem é que, especialmente no início do jogo, demora muito tempo a atravessar toda a árvore. Temos apenas 1 segundo para fazer uma jogada! Portanto, introduzimos uma técnica que nos permite podar (grandes) partes da árvore de jogo, de tal forma que não precisamos de a procurar completamente. O algoritmo chama-se poda alpha-beta.
I resumirei os conceitos mais importantes. Um belo vídeo passo-a-passo, por prof. Pieter Abbeel, pode ser encontrado aqui. Definimos as seguintes variáveis:
* alfa: a melhor pontuação actual no caminho para a raiz pelo maximizador (us)
* beta: a melhor pontuação actual no caminho para a raiz pelo minimizador (adversário)
O que fazemos é actualizar os nossos valores alfa e beta sempre que vemos um novo valor dos nossos filhos (dependendo se estamos numa profundidade par ou ímpar). Passamos estes alfa e beta aos nossos outros filhos, agora quando encontramos um valor ou superior ao nosso beta actual, ou inferior ao nosso alfa actual, podemos descartar toda a sub-árvore (uma vez que temos a certeza de que o caminho óptimo não passará por isto). Vejamos outro exemplo, mais uma vez retirado da wikipedia:
- Passamos primeiro a profundidade da árvore de jogo, da esquerda para a direita. A primeira folha que encontramos é a folha mais à esquerda (com valor 5). A folha propaga este valor ao seu pai, onde o valor beta é actualizado e transformado em 5. Também verifica a segunda folha mais à esquerda (que tem um valor de 6) mas isto não actualiza nenhum dos valores (visto que 6 não é melhor que 5 se estivermos na perspectiva do minimizador).
- O melhor valor encontrado neste nó (novamente, 5) é propagado ao seu pai, onde o valor alfa é actualizado. Agora, estamos no filho direito deste pai, e primeiro verifica o seu filho esquerdo com valor 7, e actualiza o valor beta (agora temos alfa=5 e beta=7). Verificamos o seguinte filho: com o valor 4, este é um valor melhor para o minimizador, por isso agora temos beta=4 e alfa=5.
- desde agora beta ≤ alfa, podemos podar todas as crianças restantes. Isto é porque SEMPRE teremos um valor ≤ 4 agora nesse nó interno (somos um minimizador e só actualizamos o nosso valor quando encontramos um valor menor que o actual), MAS o nó pai só actualizará valores quando estiverem ≥ 5 (uma vez que somos um maximizador nesse nó). Por isso, qualquer que seja o valor que iremos ter depois de atravessar todos os nós, nunca será escolhido pelo nó maximizador, uma vez que terá de ser maior do que 5 para que isso aconteça.
- Este processo continua para todos os nós restantes…
Uma boa implementação python deste algoritmo, pelos autores de um dos livros de referência mais proeminentes da IA, pode ser encontrada aqui.
Na secção subsequente, serão discutidas mais optimizações para este algoritmo alfa-beta, das quais a maioria é adaptada especificamente para o jogo de ligação-quatro. Para avaliar o ganho em desempenho de cada uma das optimizações, estabeleceremos uma linha de base. Iremos expressar a taxa de sucesso em função do número ou dos movimentos já efectuados. Uma execução foi bem sucedida se a solução foi encontrada dentro de um segundo. Aqui está a nossa trama de base.