Aprendizagem de Tic-Tac-Toe e Reforço

Segue · 13 min ler

Tic-tac-toe (ou zeros e cruzes) é um jogo simples. Dado que dois jogadores ('X' e 'O') estão alternando turnos em uma grade de 3×3, qual jogador pode ser o primeiro a reivindicar três quadrados em uma única linha, coluna ou diagonal?

Quanto aos jogos, o tic-tac-toe não é muito interessante. Com jogo perfeito, sempre termina em empate. Além disso, existem apenas 26.830 jogos únicos, então o espaço de busca é pequeno o suficiente para que possa ser resolvido sem recorrer a técnicas de aprendizagem profunda.

Ao mesmo tempo, os jogos simples costumam ser a melhor maneira de aprender como a aprendizagem profunda funciona. Você não precisa de um modelo complexo para obter bons resultados, e você não ficará atolado na complexidade do jogo em si. Vamos ver como alguém pode ensinar uma rede neural profunda (DNN) a jogar tic-tac-toe.

O Notebook Jupyter está aqui se você quiser o código completo para os exemplos a seguir.

Redes Neurais Profundas

excelentes introduções para redes neurais profundas, então não vou entrar em muitos detalhes. Mas aqui está uma atualização.

Fundamentalmente, uma rede neural profunda é sobre correspondência de padrões. Ele consiste em várias camadas de nós empilhadas umas sobre as outras. Cada nó recebe entrada de um ou mais nós na camada anterior. Depois de aplicar uma função, ela envia sua saída para um ou mais nós na próxima camada. Seus dados de treinamento são passados como entrada para a camada superior e sua classificação é medida em relação à saída da camada inferior.

Usando uma técnica chamada de propagação reversa, as pilhas de nós atualizam seus pesos até que as saídas da camada inferior estejam muito próximas da classificação desejada para cada parte dos dados de treinamento. Para evitar o overfitting, é necessário treinar com muitos dados e também reservar um conjunto de dados de teste que o modelo não tenha visto durante o treinamento.

Em nosso modelo DNN para jogar tic-tac-toe, os dados de treinamento são estados de tabuleiro individuais, e a classificação é a probabilidade de ganhar 'X', 'O' ou um empate. Uma vez treinados, podemos passar ao nosso modelo uma série de movimentos possíveis, depois escolher o movimento que provavelmente resultará no resultado desejado.

Por exemplo, se "X" estiver em movimento, queremos escolher um lance que resulte em uma vitória "X". No entanto, também queremos ser sensíveis sobre se uma vitória para 'X' parece improvável, caso em que devemos jogar por um empate. Um empate é preferível a um adversário vencedor.

O ambiente do jogo

Uma maneira de adquirir dados de treinamento é simulá-lo. Antes de podermos criar um simulador de jogos, temos que construir um ambiente no qual o nosso simulador possa rodar. Felizmente, para o tic-tac-toe isso é relativamente simples.

Precisamos de uma função para inicializar uma nova placa:

 def initBoard (): 
board = [
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
]
placa de retorno

E uma função para obter uma lista de movimentos válidos para uma determinada prancha:

 def getMoves (quadro): 
move = []
para eu na faixa (len (placa)):
para j na faixa (len (placa [i])):
se placa [i] [j] == 0:
move.append ((i, j))
movimentos de retorno

E uma função um pouco mais complicada para nos dizer se alguém ganhou:

 def getWinner (quadro): 
candidato = 0
won = 0

# Verifique as linhas
para eu na faixa (len (placa)):
candidato = 0
para j na faixa (len (placa [i])):

# Certifique-se de que não há lacunas
se placa [i] [j] == 0:
pausa

# Identifique o favorito
se candidato == 0:
candidato = placa [i] [j]

# Determine se o favorito tem todos os slots
se candidato! = placa [i] [j]:
pausa
elif j == len (placa [i]) - 1:
won = candidate

se ganhou> 0:
retorno ganho

# Verifique as colunas
para j na faixa (len (placa [0])):
candidato = 0
para eu na faixa (len (placa)):

# Certifique-se de que não há lacunas
se placa [i] [j] == 0:
pausa

# Identifique o favorito
se candidato == 0:
candidato = placa [i] [j]

# Determine se o favorito tem todos os slots
se candidato! = placa [i] [j]:
pausa
elif i == len (placa) - 1:
won = candidate

se ganhou> 0:
retorno ganho

# Verifique as diagonais
candidato = 0
para eu na faixa (len (placa)):
se board [i] [i] == 0:
pausa
se candidato == 0:
candidato = diretoria [i] [i]
se candidato! = diretoria [i] [i]:
pausa
elif i == len (placa) - 1:
won = candidate

se ganhou> 0:
retorno ganho

candidato = 0
para eu na faixa (len (placa)):
se placa [2 - i] [2 - i] == 0:
pausa
se candidato == 0:
candidato = quadro [2 - i] [2 - i]
se candidato! = placa [2 - i] [2 - i]:
pausa
elif i == len (placa) - 1:
won = candidate

se ganhou> 0:
retorno ganho

# Ainda não é vencedor?
if (len (getMoves (board)) == 0):
# É um empate
return 0
else :
# Ainda mais movimentos para fazer
return -1

Os valores de retorno possíveis desta função são:

  • -1 (o jogo ainda não acabou)
  • 0 (o jogo é um empate)
  • 1 ('X' vence)
  • 2 ('O' ganha)

E, finalmente, precisamos de uma função que possa imprimir uma placa na tela:

 printBoard def (placa): 
para eu na faixa (len (placa)):
para j na faixa (len (placa [i])):
mark = ''
se placa [i] [j] == 1:
marca = 'X'
elif board [i] [j] == 2:
mark = 'O'
if (j == len (placa [i]) - 1):
imprimir (marca)
else :
print (str (mark) + "|", end = '')
if (i <len (placa) - 1):
impressão("-----")

Você notará que a representação interna de uma placa usa números, não letras. Isso é importante porque os DNNs funcionam melhor com números.

Testando o Meio Ambiente

Agora que temos um ambiente básico, vamos ver como funciona. Primeiro, vamos inicializar e imprimir uma nova placa.

 b = initBoard () 
printBoard (b)
# OUTPUT
#
# | |
# -----
# | |
# -----
# | |

E vamos ver o que acontece quando pedimos uma lista de movimentos.

 print (getMoves (b)) # SAÍDA 
#
# [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

Vemos que qualquer coordenada no tabuleiro é um jogo justo.

Finalmente, vamos ver se alguém ganhou o jogo ainda.

 print (getWinner (b)) # SAÍDA 
#
# -1

Lembre-se, -1 significa que o jogo não terminou, o que está correto!

Para testar os casos restantes, vamos simular algumas outras placas e ver em que estado elas estão.

 b [0] [0] = 1 
b [1] [1] = 1
b [2] [2] = 1
printBoard (b)
print (getWinner (b))
# SAÍDA
#
# X | |
# -----
# | X |
# -----
# | X
# 1

1 significa que 'X' ganhou, obtendo três 'X's em uma única linha, coluna ou diagonal.

 b [0] [2] = 2 
b [1] [2] = 2
b [2] [2] = 2
printBoard (b)
print (getWinner (b))
# SAÍDA
#
# X | | O
# -----
# | X | O
# -----
# | | O
# 2

2 significa que 'O' ganhou.

 b [0] [1] = 1 
b [1] [0] = 2
b [2] [0] = 1
b [2] [1] = 2
b [2] [2] = 1
b [0] [0] = 2
printBoard (b)
print (getWinner (b))
# SAÍDA
#
# O | X | O
# -----
# O | X | O
# -----
# X | O | X
# 0

0 significa que houve um empate.

O simulador de jogo

Agora que criamos o nosso ambiente de jogo da velha, precisamos de uma maneira de simular jogos reais. Embora existam várias maneiras de fazer isso, vamos usar um simulador aleatório. Há algumas razões pelas quais esta é uma boa ideia.

Primeiro, um simulador aleatório criará a maior coleção possível de dados de treinamento. Isso significa que quando um humano joga contra o nosso modelo treinado em IA, a IA não será facilmente desconcertada por movimentos não intuitivos que não foram treinados. Em um jogo mais complicado, podemos precisar de algum tipo de heurística para restringir o espaço de busca e apontar as simulações de treinamento na direção certa, mas no tic-tac-toe o espaço de busca é pequeno, então isso não é um problema.

Em segundo lugar, um simulador aleatório nos dará uma boa base para medir o desempenho do nosso modelo. No tic-tac-toe, 'X' tem uma vantagem inerente porque vai primeiro, mas não sabemos o quanto de uma vantagem isso dá 'X' sem simulá-lo.

A primeira coisa que precisamos fazer é criar uma função que simule um jogo de jogo-da-velha.

 def simulateGame (p1 = Nenhum , p2 = Nenhum , rnd = 0): 
history = []
board = initBoard ()
playerToMove = 1

enquanto getWinner (board) == -1:

# Escolha um movimento (aleatório ou use um modelo de jogador, se fornecido)
move = None
if playerToMove == 1 e p1! = None :
move = bestMove (board, p1, playerToMove, rnd)
elif playerToMove == 2 e p2! = Nenhum :
move = bestMove (placa, p2, playerToMove, rnd)
else :
move = getMoves (placa)
move = move [random.randint (0, len (movimentos) - 1)]

# Faça o movimento
tabuleiro [move [0]] [move [1]] = playerToMove

# Adicione a mudança para o histórico
history.append ((playerToMove, move))

# Mudar o jogador ativo
playerToMove = 1 se playerToMove == 2 else 2

histórico de retorno

Há um monte de coisas extras nessa função que não vamos usar agora! O simulador pode passar modelos treinados para jogar 'X' e / ou 'O'. Quando um modelo não é passado, ele escolhe movimentos aleatoriamente, que é o que queremos agora.

Vamos testar essa função simulando um jogo e vendo o que ele retorna.

 history = simulateGame () 
imprimir (história)
# OUTPUT
#
# [(1, (2, 1)), (2, (0, 1)), (1, (1, 0)), (2, (2, 2)), (1, (2, 0) ), (2, (1, 2)), (1, (0, 2)), (2, (1, 1)), (1, (0, 0)]]

Vemos que a "história" de um jogo consiste em um conjunto de tuplas. O primeiro elemento em cada uma dessas tuplas é o jogador que moveu (1 para 'X', 2 para 'O'), e o segundo elemento é a coordenada onde o jogador se moveu.

Qualquer estado de tabuleiro deste jogo pode ser facilmente reconstruído a partir deste array. Vamos criar uma função para fazer exatamente isso.

 def movesToBoard (movimentos): 
board = initBoard ()
para mover em movimentos:
jogador = movimento [0]
coords = movimento [1]
tábua [coords [0]] [coords [1]] = jogador
placa de retorno

Agora, quando passamos esta função a história de qualquer jogo, podemos ver o tabuleiro resultante.

 board = movesToBoard (histórico) 
printBoard (quadro)
print (getWinner (placa))
# SAÍDA
#
# X | O | X
# -----
# X | O | O
# -----
# O | X | X
# 0

Nós vemos que o jogo resultou em um empate!

Simulando Jogos Aleatórios

Agora que estamos em um ponto em que podemos simular jogos aleatórios, vamos gerar algumas estatísticas agregadas para 10.000 jogos de uma só vez. Nós podemos fazer isso em uma única linha.

 games = [simulateGame () para _ no intervalo (10000)] 

Agora, precisamos de uma função para gerar estatísticas dessa lista de jogos.

 def gameStats (jogos, jogador = 1): 
stats = {"win": 0, "loss": 0, "draw": 0}
para jogo em jogos:
result = getWinner (moveToBoard (jogo))
se resultar == -1:
continuar
resultado elif == jogador:
stats ["ganhar"] + = 1
resultado elif == 0:
stats ["desenhar"] + = 1
else :
stats ["perda"] + = 1

winPct = stats ["win"] / len (jogos) * 100
lossPct = stats ["perda"] / len (jogos) * 100
drawPct = stats ["desenhar"] / len (jogos) * 100

print ("Resultados para o player % d :"% (player))
print ("Vitórias: % d ( % .1f %% )"% (estatísticas ["win"], winPct))
print ("Perda: % d ( % .1f %% )"% (stats ["perda"], lossPct))
print ("Draw: % d ( % .1f %% )"% (estatísticas ["desenhar"], drawPct))

Vamos aplicar essa função nos jogos que geramos e ver o que acontece no jogo completamente aleatório.

 gameStats (jogos) 
impressão()
gameStats (jogos, jogador = 2)
# OUTPUT
#
# Resultados para o jogador 1:
# Vitórias: 51934 (51,9%)
# Perda: 24212 (24,2%)
# Empate: 23854 (23,9%)
#
# Resultados para o jogador 2:
# Vitórias: 24212 (24,2%)
# Perda: 51934 (51,9%)
# Empate: 23854 (23,9%)

Vemos que o jogador 1 ('X') ganha cerca de metade do tempo, enquanto o jogador 2 ('O') ganha apenas cerca de um quarto do tempo. Os jogadores também desenham cerca de um quarto do tempo. Esta é a linha de base para vencer nosso modelo.

O modelo DNN

Agora é hora de construir uma rede neural profunda! Lembre-se de que nossos dados de entrada são estados individuais da placa e nossos dados de saída usados para classificação são o resultado resultante para cada jogo associado ao estado da placa.

Os dados de entrada são, portanto, uma matriz de nove elementos, se achatarmos o estado da placa. Os dados de saída são um array de três elementos, se codificarmos um dos possíveis resultados de um jogo ('X' vence, 'O' vence, desenha).

Aqui está a função que usaremos para gerar nosso modelo. Nós usamos Keras neste exemplo.

 importar keras 
de keras.models import Sequential
de keras.layers importam denso
de keras.layers import Dropout
de keras.backend import reshape
de keras.utils.np_utils import to_categorical
def getModel ():
numCells = 9
resultados = 3
model = Sequential ()
model.add (denso (200, ativação = 'relu', input_shape = (9,)))
model.add (Rejeição (0.2))
model.add (denso (125, ativação = 'relu'))
model.add (denso (75, ativação = 'relu'))
model.add (Dropout (0,1))
model.add (denso (25, ativação = 'relu'))
model.add (denso (resultados, ativação = 'softmax'))
model.compile (loss = 'categorical_crossentropy', optimizer = 'rmsprop', métricas = ['acc'])
modelo de retorno

Apesar de não entrar na tentativa e erro usado para criar este modelo, observe como a função loss é crossentropy categórica. É assim que dizemos ao modelo que queremos que ele produza uma série de probabilidades. Essas probabilidades projetam a confiança do modelo em cada um dos três resultados do jogo para uma determinada diretoria.

Lembre-se dos jogos aleatórios que simulamos? Estes são os nossos dados de treinamento. Mas precisamos formatar os dados de tal forma que nosso modelo possa consumi-los. Isso significa fazer o seguinte:

  • Dividindo cada jogo em estados de tabuleiro separados, rotulando cada tabuleiro com o resultado final de seu jogo associado.
  • Achatando cada placa em uma matriz 1D.

Também queremos reservar um conjunto de dados de teste para fins de validação. Aqui está a função que usamos para fazer todos os itens acima.

 def gamesToWinLossData (jogos): 
X = []
y = []
para jogo em jogos:
vencedor = getWinner (moveToBoard (jogo))
para mover no intervalo (len (jogo)):
X.append (moveToBoard (jogo [:( move + 1)]))
y.append (vencedor)

X = np.array (X) .reshape ((- 1, 9))
y = to_categorical (y)

# Retornar uma divisão de trem / teste apropriada
trainNum = int (len (X) * 0,8)
retorno (X [: trainNum], X [trainNum:], e [: trainNum], y [trainNum:])

Agora, podemos instanciar nosso modelo, reformular nossos dados e treinar o modelo.

 model = getModel () 
X_train, X_test, y_train, y_test = gamesToWinLossData (jogos)
history = model.fit (X_train, y_train, validation_data = (X_test, y_test), épocas = 100, batch_size = 100)

Isso leva cerca de 200 segundos em um Core i7 com 4 núcleos.

Desempenho do Modelo

Uma vez que o treinamento é feito, podemos ver o desempenho do nosso modelo! Vamos passar nosso modelo recém-treinado para o simulador como 'X' e jogá-lo contra um aleatório 'O' para 1.000 jogos.

 games2 = [simulateGame (p1 = model) para _ in range (1000)] 

Isso leva alguns segundos, mas quando terminar, podemos usar a mesma função estatística de antes para ver qual foi o resultado.

 gameStats (games2) # OUTPUT 
#
# Resultados para o jogador 1:
# Vitórias: 950 (95,0%)
# Perda: 16 (1,6%)
# Empate: 34 (3,4%)

Uau! Passamos de perder 24,2% dos jogos para perder apenas 1,6% do tempo!

Vamos ver como nosso modelo se comporta como 'O', jogando contra um 'X' aleatório.

 games3 = [simulateGame (p2 = model) para _ no intervalo (1000)] 
gameStats (games3, player = 2)
# OUTPUT
#
# Resultados para o jogador 2:
# Vitórias: 427 (42.7%)
# Perda: 43 (4,3%)
# Empate: 530 (53,0%)

Isso é igualmente impressionante! "O" passou de 51,9% dos jogos para apenas 4,3% do tempo perdido.

O que acontece quando o modelo é usado para jogar dos dois lados? Para evitar o determinismo completo, aplicamos um fator aleatório para forçar o modelo a escolher movimentos diferentes em cada jogo.

 games4 = [simulateGame (p1 = modelo, p2 = modelo, rnd = 0.6) para _ no intervalo (1000)] 
gameStats (games4, player = 1)
impressão()
gameStats (games4, player = 2)
# OUTPUT
#
# Resultados para o jogador 1:
# Vitórias: 483 (48,3%)
# Perda: 44 (4,4%)
# Empate: 473 (47,3%)
#
# Resultados para o jogador 2:
# Vitórias: 44 (4.4%)
# Perda: 483 (48,3%)
# Empate: 473 (47,3%)

Vemos que o jogo tende a um empate, que é o que poderíamos esperar de um par de jogadores humanos. Ainda assim, nenhum dos jogadores é particularmente bom. Lembre-se que no jogo perfeito, os jogos sempre terminam em empate.

Como uma medida final de habilidade, vamos ver como o comprimento do jogo médio mudou. Esperamos que isso diminua com um aumento do desequilíbrio nos níveis de habilidade.

 print ("Tamanho médio do jogo totalmente aleatório é % f moves"% (np.mean ([float (len (jogo)) para jogo nos jogos]))) 
print ("Duração média do jogo em que P1 usa NN é % f move"% (np.mean ([float (len (game)) para jogo em games2])))
print ("Duração média do jogo em que P2 usa NN é % f move"% (np.mean ([float (len (game)) para jogo em games3])))
print ("Duração média do jogo em que ambos usam NN é % f move"% (np.mean ([float (len (game)) para jogo em games4])))
# OUTPUT
#
# Duração média do jogo totalmente aleatório é 7.788300 movimentos
# Duração média do jogo em que P1 usa NN é 6.762000 movimentos
# Duração média do jogo em que P2 usa NN é 7.711000 movimentos
# Duração média do jogo em que ambos usam NN é 8.036.000 movimentos

Como mostrado acima, os jogos são mais curtos para 'X' e os mesmos para 'O'. Quando o modelo está jogando dos dois lados, os jogos tendem a ser um pouco mais longos do que quando são totalmente aleatórios.

AI v. Humano

Agora, jogamos um jogo contra o nosso modelo e vemos o quão bem ele funciona. Nós deixamos o modelo jogar como 'X'.

Mover 1 (modelo):

 board = initBoard () move = bestMove (placa, modelo, 1) 
placa [move [0]] [move [1]] = 1
printBoard (quadro) # OUTPUT
#
# | |
# -----
# | |
# -----
# | X

Mova 2 (humano):

 tabuleiro [1] [1] = 2 
printBoard (quadro)
# OUTPUT
#
# | |
# -----
# | O |
# -----
# | X

Mova 3 (modelo):

 move = bestMove (placa, modelo, 1) 
board [move [0]] [move [1]] = 1
printBoard (quadro)
# OUTPUT
#
# X | |
# -----
# | O |
# -----
# | X

Mover 4 (humano):

 placa [0] [2] = 2 
printBoard (quadro)
# OUTPUT
#
# X | | O
# -----
# | O |
# -----
# | X

Mova 5 (modelo):

 move = bestMove (placa, modelo, 1) 
board [move [0]] [move [1]] = 1
printBoard (quadro)
# OUTPUT
#
# X | | O
# -----
# | O |
# -----
# X | X

Mova 6 (humano):

 placa [2] [1] = 2 
printBoard (quadro)
# OUTPUT
#
# X | | O
# -----
# | O |
# -----
# X | O | X

Mova 7 (modelo):

 move = bestMove (placa, modelo, 1) 
board [move [0]] [move [1]] = 1
printBoard (quadro)
# OUTPUT
#
# X | | O
# -----
# X | O |
# -----
# X | O | X

E o modelo vence! Isso não augura nada de bom para a humanidade. Bem, esse humano pelo menos. 🙂

Uma observação interessante é o quanto o modelo é ofensivo ou defensivo se ele é tocado como 'X' ou 'O'. O modelo se moverá "para vencer" se perceber que está à frente de seu oponente e "para atrair" se perceber que seu oponente está à frente. Como o jogador 'X' está geralmente à frente estatisticamente, o modelo tende a jogar 'para vencer' nessa situação, enquanto que o jogador 'O' geralmente está estatisticamente atrasado, o modelo tende a jogar 'desenhar' nessa situação.

Isso poderia ser corrigido no simulador com um mecanismo de pontuação melhor. A função bestMove conforme usada neste exemplo é mostrada abaixo:

 def bestMove (tabuleiro, modelo, jogador, rnd = 0): 
pontuações = []
move = getMoves (placa)

# Faça previsões para cada movimento possível
para eu no intervalo (len (movimentos)):
future = np.array (placa)
future [move [i] [0]] [move [i] [1]] = jogador
prediction = model.predict (future.reshape ((- 1, 9)))) [0]
se jogador == 1:
winPrediction = previsão [1]
perdaPredição = previsão [2]
else :
winPrediction = previsão [2]
perdaPredição = previsão [1]
drawPrediction = previsão [0]
if winPrediction - lossPrediction> 0:
scores.append (winPrediction - lossPrediction)
else :
scores.append (drawPrediction - lossPrediction)

# Escolha o melhor movimento com um fator aleatório
bestMoves = np.flip (np.argsort (pontuações))
para eu no intervalo (len (bestMoves)):
if random.random () * rnd <0,5:
movimentos de retorno [bestMoves [i]]

# Escolha um movimento completamente ao acaso
movimentos de retorno [random.randint (0, len (moves) - 1)]

Como mostrado, o simulador usa o modelo para prever as chances de ganhar e as chances de se perder. Se é mais provável ganhar do que perder, joga para ganhar, caso contrário joga para empatar. Isso poderia ser melhorado pela ponderação do algoritmo com um fator de "otimismo". Um modelo otimista jogará para ganhar mesmo que esteja um pouco atrasado.

Resumo

Espero que tenham gostado desta rápida jornada para o aprendizado por reforço e redes neurais profundas. Mostramos como construir um ambiente de jogo básico para o jogo-da-velha, um simulador de jogos e um DNN que pode treinar em dados gerados a partir do simulador.

Embora nosso modelo seja extremamente simples e, portanto, não tenha jogado tão bem quanto dois proficientes humanos teriam jogado, ele ainda mostrou uma melhora significativa em relação ao jogo aleatório. Além disso, parecia tomar decisões sensatas quando jogado contra um humano.

Continue aprendendo!