Aprenda a aplicar a inteligencia artificial em seus jogos: Teoria dos Jogos Minimax

Olá a todos,

Eu estava escrevendo um pequeno tutorial de desenvolvimento de aplicativos móveis, e um dos aplicativos que utilizei como exemplo foi a construção de um simples jogo da velha, conhecido também como Tic Tac Toe. O jogo foi desenvolvido para ser jogado entre um jogador humano e um jogador controlado pelo computador. No exemplo que desenvolvi , os movimentos jogados pelo jogador controlado pelo computador são aleatórios, ou seja, não há uma lógica por trás das jogadas do PC e nem uma análise prévia das jogadas do adversário. A fim de tornar o algoritmo do jogo mais simples, tomei a decisão de fazer um algoritmo com movimentações aleatórias. Mas, pensei: "Eu poderia dificultar mais as coisas, e poderia aplicar conceitos básicos de inteligência artificial neste jogo, a fim de deixar o jogador controlado pelo computador mais desafiador!" .

E este é o foco deste artigo, irei utilizar o jogo da velha como base para aplicação de conceitos de inteligência artificial, especificamente, introduzir um dos clássicos teoremas de jogos: A Teoria de decisão ou Minimax.

"Quanta coisa pode-se aprender com um simples jogo da velha."

O jogo da velha é um jogo composto por um tabuleiro de matriz de três linhas por três colunas onde dois jogadores se enfrentam. Ganha o o jogador que conseguir três círculos ou três xis 'X' em linha, seja vertical, horizontal ou diagonal.

Aproveitei o jogo que foi desenvolvido na linguagem de programação Python portado para celulares Symbian S60 que pode ser executado no aparelho ou através de um emulador. Mais informações ver estes dois artigos explicando sobre a plataforma PyS60.

Quem joga?

A partida será disputada entre o jogador humano contra programas ou agente inteligentes desenvolvidos por outro jogador ou fornecidos pela própria empresa desenvolvedora do game. Mas o que seria agentes inteligentes ?

A Inteligência Artificial

O jogo da velha pode ser dividido e tratado em agente e ambiente. O agente seria o jogador, que percebe o seu ambiente por meio de sensores (os parâmetros) e age sobre o ambiente por intermédio de atuadores, isto é, o valor retornado com as coordenadas da jogada.

Fiz uma busca mais refinada, e encontrei mais informações sobre a definição de ambiente, e o mesmo pode ser definido como:

Completamente observável

Os agentes tem acesso ao estado completo do ambiente. Os sensores detectam todos os aspectos que são relevantes para a escolha da ação. A cada jogada o jogador recebe a matriz do tabuleiro atualizada.

Estratégico

O próximo estado do ambiente é completamente determinado pelo estado atual e pela ação executada pelos agentes.

Seqüencial

A decisão afeta todas as ações futuras. Ações em curto prazo podem ter conseqüências a longo prazo. O jogador faz uma jogada, o próximo jogador pode dar continuidade a sua jogada anterior, como também se defender ou iniciar uma nova jogada.

Estático

O ambiente não se altera enquanto o agente está decidindo sobre a realização de uma ação, nem precisa se preocupar com a passagem do tempo.

Discreto

O ambiente tem um número finito de estados distintos, também tem um número discreto de percepções e ações.

Multiagente

O agente está em um ambiente de dois agentes, o jogo precisa de dois jogadores pra disputar a partida.

Existem 2 tipos de agentes inteligentes para o jogo da velha: o agente que faz a melhor jogada analisando a situação atual, o que significa que para sua próxima jogada o seu movimento atual vai ser realmente útil; e o agente que planeja as suas jogadas, este que age com estratégia. O agente que faz a melhor jogada olha para o tabuleiro e se pergunta: "O que pode me fazer ganhar ou perder ?" . Já o agente estratégico pode fazer jogadas que aparentemente não tem sentido, mas que futuramente vão decidir a partida.

Teoria da decisão, Minimax ou Minmax

Minimax lida com jogos como jogo da velha, no qual cada jogador pode ganhar, perder ou empatar. No nosso exemplo específico que é o jogo da Velha, você pode considerar que após a sua jogada, o adversário vai escolher a melhor jogada possível e então você a partir dessa melhor jogada já pensa na melhor que você pode fazer e assim sucessivamente. Por exemplo, vamos chamar um jogador de MIN e outro de MAX (daí veio nome: MINIMAX). O jogador MAX sempre considera que MIN vai escolher a jogada que o deixa na pior situação (pior caso para MAX) e que ele (o MAX) vai escolher a melhor jogada para si. O algoritmo minimax ajuda a encontrar a melhor jogada ao caminha pelas opções válidas a partir do fim do jogo. A cada passo assume-e que o jogador MAX está tentando maximizar as chances de MAX ganhar, enquanto na próxima rodada o jogador MIN está tentando minimizar as chances de isso acontecer (ao maximizar as chances de que ele próprio ganhe).

Resumindo, o jogador usando o algoritmo miniMax constrói uma árvore de jogadas achando que ambos (ele mesmo e o adversário) sempre escolherão soluções ótimas para si mesmos. Veja um exemplo de uma possível parte de uma árvore de jogo da velha. Atente apenas para o detalhe que nessa árvore temos a impressão que começou no MIN, quando na verdade começa no MAX. Eu escolhi essa parte do meio da árvore.

Árvore de busca de uma partida de Jogo da velha

Os números que você vê ao fundo representam o VALOR MINIMAX(n). Esse valor é apenas um “indicativo” de utilidade para o jogador MAX, ou seja, quanto MAIOR O VALOR da jogada do jogador MIN, melhor para o MAX e quanto MENOR O VALOR da jogada do jogador MAX, melhor para o MIN. No caso acima os números indicam as chances de se ganhar com a jogada correspondente. Caso você faça a jogada no centro do tabuleiro, o computador irá, com certeza, fazer a jogada no canto superior esquerdo. Repare que o MIN escolhe o mínimo valor e o MAX escolhe o máximo valor.

É a sua vez de jogar, o que você escolheria? Fazer um movimento de defesa impedindo que oponente vença na próxima jogada, iniciar um nova estratégia, continuar com a sua estratégia de jogadas anteriores ou fazer o movimento para a vitória? Separe os tipos de jogadas e estabeleça prioridades. É preferível vencer que impedir que o adversário vença na próxima jogada.

O Jogo

Tictactoe é responsável pelas regras e execução do jogo. Os jogadores são inseridos no tabuleiro e o jogo é iniciado.

As regras do jogo são bem simples:

• O tabuleiro é uma matriz quadrada de três linhas por três colunas (3x3). O valor mínimo e máximo para a coordenada é respectivamente 0 e 2.
• Em cada jogada o jogador recebe por parâmetro a matriz atualizada do tabuleiro e a sua marcação, caractere "x" (xis) ou "o" (círculo).
• O jogador vence quando conseguir três "o" (círculos) ou três "x" (xis) em linha, seja vertical, horizontal ou diagonal. Caso contrário, a partida se dá como empate.

O código-fonte do jogo é composto por várias classes: Keyboard (responsável pelo tratamento de eventos), Game (responsável pela lógica principal do jogo) e GameBoard(responsável pelas jogadas e pintura e desenho na tela dos elementos do jogo). O foco deste tutorial não é detalhar as implementações de todas estas classes, e sim na implementação das jogadas, em especial, as jogadas feitas pelo jogador adversário controlado pelo programa. Detalhes sobre as implementações e particularidades da linguagem PyS60, visitem estes links: link1 e link2. São artigos publicados de minha autoria introduzindo o leitor ao desenvolvimento de aplicativos móveis em Python para celulares Symbian S60, que contêm, inclusive, todo os procedimentos de desenvolvimento deste jogo.

Código-Fonte (Classe Game):

class Game: 
 
 def quit(self):
  self.running = False
  self.trava.signal()
 
 def newGame(self):
  global canvas, gameboard, keyboard, buf
  
  #Obtem o objeto "lock" da aplicação (trava).
  self.trava = e32.Ao_lock()
 
  #Seta a função quit() como callback do evento ExitKey.
  appuifw.app.exit_key_handler=self.quit
  
  #Instancia a classe Keyboard (tratamento de eventos de teclado)
  keyboard = KeyBoard()
  
  #Seta a aplicação para ocupar toda a tela.
  appuifw.app.screen="full"
 
  #Cria um novo objeto canvas e seta os respectivos callbacks (pintura e eventos)
  canvas=appuifw.Canvas(event_callback=keyboard.handle_event, redraw_callback=handle_redraw)
  
  #Cria uma nova imagem (buffer)
  buf=graphics.Image.new((240,320))
  
  #Instancia a classe GameBoard (Pintura do tabuleiro e elementos do jogo)
  gameboard = GameBoard()

  #Seta corpo da aplicação para o objeto canvas.
  appuifw.app.body=canvas
  
  #Para manter o registro de qual jogador irá jogar na rodada,
  #utilizamos a variavel turn (1 para o telefone, 2 para o jogador)
  #O jogador começa o jogo
  self.turn=2
  
  #Variável para verificar se a partida foi encerrada.
  self.gameover=False
  
  #Variavel que verifica se a aplicação está em execução (True para Em Execução , False para Finalizado)
  self.running = True
  
  #Loop de controle que move o cursor vermelho na tela de acordo com os eventos de teclado
  while self.running:
   #Inicializa o menu
   appuifw.app.menu=[(u"Novo jogo", self.newGame), (u"Sair", self.quit)]
   
   #SoftKey Direito for pressionado, sair do aplicativo.
   if(keyboard.pressed(key_codes.EScancodeRightSoftkey)):
    self.quit()
    
   #Quando for a vez do jogador jogar
   if(self.turn==2):
    self.turn = gameboard.playerTurn()
   
   
   #Checamos se o jogo foi finalizado. Isto acontece se um dos jogadores completou a
   #sequência contínua de 3 símbolos ou se a matriz está cheia.
   self.gameover = gameboard.hasWinner()
   if self.gameover == True:
    if(appuifw.query(u"Fim de jogo. Jogar de novo?", "query")):
     self.newGame()
    else:
     self.quit()
     
   #Se for o turno do jogador 'Telefone'  e se o jogo ainda não estiver ainda finalizado...
   while((self.turn==1) and (self.gameover==False)):
    self.turn = gameboard.phoneTurn()
  
   e32.ao_yield()    

Primeiramente, vejamos o código-fonte da Classe Game. Existem 2 funções particulares que são chamadas durante a ação do jogo: phoneTurn() e playerTurn() (Em negrito no código acima). Estas funções contêm as implementações necessárias para a tomada de decisão e movimentação das jogadas pelos jogadores. Vamos focar, especificamente, na função phoneTurn() que está encapsulada na classe GameBoard. Ela é responsável pelas jogadas controladas pelo telefone (programa) e é o alvo deste artigo.

Código-Fonte (Classe GameBoard):

class GameBoard:
 def __init__(self):
  global game_state
  #A fim de manter na memória o estado do jogo, utilizamos uma matriz preenchida de:
  #0 se o quadrado estiver vazio, 1 se o quadrado for ocupado por uma jogada do Fone
  #e 2 se o quadrado for ocupado por uma jogada do jogador. (3 x 3)
  game_state=[[0,0,0],[0,0,0],[0,0,0]]

  #Escrever X ou O requer as coordenadas pré-definidas.
  self.xcoord=[32,112,192]
  self.ycoord=[65,172,279]
  
  #Para mostrar onde o cursor do jogador se posiciona,
  #Colocamos um ponto vermelho (No início do jogo, ele é inicializado no meio da matriz)
  self.dotx=self.doty=1
  
  #Pinta o tabuleiro do Jogo
  self.drawgrid()
 
 (...)
  
 def phoneTurn(self):
  global game_state
  turn = 1
  px=random.choice([0,1,2])
  py=random.choice([0,1,2])
  if(game_state[px][py]==0):
   buf.text((self.xcoord[px],self.ycoord[py]), u"O", font="title")
   game_state[px][py]=1
   handle_redraw(())
   self.drawgrid()
   turn=2
  return turn

Jogador RandomPlayer

RandomPlayer é um jogador randômico, aposta na sorte e foi utilizado neste primeiro exemplo do jogo da velha. Como podemos visualizar na definição da função phoneTurn(), ele simplesmente lê o estado atual do tabuleiro, sorteia uma jogada (função random.choice())e depois verifica se tal posição está livre para ser jogada. Caso contrário, sorteia novamente até encontrar uma posição livre. A chance do RandomPlayer ganhar uma partida contra um jogador humano é muito baixa, especialmente por não analisar ou prever jogadas baseado no estado atual do tabuleiro do jogo.

Jogador MiniMax

MiniMax é um jogador inteligente. Estou implementando algoritmos de aprendizado nele, este aqui demonstrado implementa decisão por heurística (MINMAX), apresentado anteriormente. Ele é capaz de examinar várias sequências de movimenotos a fim tomar a decisão de jgada que o leve à vitória. Ele tenta maximizar a probabilidade de vitória, e ao mesmo tempo assume que o oponente tentará minimizar esta probabilidade. A idéia do algoritmo é iniciar na posição corrente e usar um gerador de movimentos plausíveis (uma árvore de jogadas) para gerar o conjunto de possíveis jogadas sucessoras. Então, aplica-se a função de avaliação estática (notas) à essas jogadas e simplesmente escolhe-se a melhor.

Vamos ao código do mesmo:

class GameBoard:
 def __init__(self):
  global game_state
  #A fim de manter na memória o estado do jogo, utilizamos uma matriz preenchida de:
  #0 se o quadrado estiver vazio, 1 se o quadrado for ocupado por uma jogada do Fone 
  #e 2 se o quadrado for ocupado por uma jogada do jogador. (3 x 3)
  game_state=[[0,0,0],[0,0,0],[0,0,0]]
  
  #Variável que armazena todas as possíveis sequências de posições que levam à vitória do jogo.
  self.end_game_state = [[(0,0),(0,1),(0,2)],[(1,0),(1,1),(1,2)],[(2,0),(2,1),(2,2)],
          [(0,0),(1,0),(2,0)],[(0,1),(1,1),(2,1)],[(0,2),(1,2),(2,2)],
          [(0,0),(1,1),(2,2)],[(0,2),(1,1),(2,0)]]
 
  (...)
 
 (...)
 
 def getValidMoves(self,board):
  #Analisa o tabuleiro e retorna as posições que ainda estão vazias.
  possible_moves = list()
  for i in range(3):
   for j in range(3):
    if board[i][j] == 0:
     possible_moves.append((i,j))
  return possible_moves
 
 def judge(self,board):
  #Verifica o estado final do tabuleiro:
  # (+1 Vitoria do fone, -1 Vitoria do Humano, 0 Empate)
  winning_rows = list(self.end_game_state)
  winner = None
  for row in winning_rows:
   row_win = [board[x][y] for x,y in row]
   if row_win == [1,1,1]:
    winner = 1
    break
   elif row_win == [2,2,2]:
    winner = 2
    break  
  if winner == 1:
   return 1
  if winner == None:
   return 0 
  return -1
 
 
 def hasEnded(self,board):
  #Checa se o jogo foi finalizado. Isto acontece se um dos jogadores completou a 
  #sequência contínua de 3 símbolos ou se a matriz está cheia.
  winning_rows = list(self.end_game_state)
  gameover=True
  for i in range(3):
   for j in range(3):
    if(board[i-1][j-1]==0):
     gameover=False
  for row in winning_rows:
   row_winner = [board[x][y] for x,y in row]
   if row_winner == [1,1,1] or row_winner == [2,2,2]:
    gameover = True
    break
  return gameover  
 
 def maxValue(self,board):
  #Checa se o jogo foi finalizado (Vitória ou empate).
  if self.hasEnded(board):
   #Retorna o estado final do jogo 
   #(+1 Vitoria do fone, -1 Vitoria do Humano, 0 Empate)
   return self.judge(board)
   
  #Obtem todas as possiveis jogadas.
  possible_moves = self.getValidMoves(board)
  #Armazena a jogada que tem o melhor score.
  bestScore  = -100
  for possible_move in possible_moves:
   new_game_state = eval(repr(board))
   #Telefone joga.
   px,py = possible_move
   new_game_state[px][py] = 1
   #Obtem o minimo do proximo nivel (MIN).
   score = self.minValue(new_game_state)
   #Pega o maior score dos piores analisados.
   if score >= bestScore:
    bestScore = score
    
  return bestScore
  
 
 def minValue(self,board):
  #Checa se o jogo foi finalizado (Vitória ou empate).
  if self.hasEnded(board):
   #Retorna o estado final do jogo 
   #(+1 Vitoria do fone, -1 Vitoria do Humano, 0 Empate)
   return self.judge(board)
  
  #Obtem todas as possiveis jogadas.
  possible_moves = self.getValidMoves(board)
  #Armazena a jogada que tem o pior score.
  bestScore = 100
  for possible_move in possible_moves:
   new_game_state = eval(repr(board))
   #Jogador joga.
   px,py = possible_move
   new_game_state[px][py] = 2
   #Obtem o maximo do proximo nivel (MAX).
   score = self.maxValue(new_game_state)
   #Pega o menor score dos melhores analisados.
   if score <= bestScore:
    bestScore = score
    
  return bestScore

 def phoneDecision(self):
  #Testa todas jogadas possiveis.
  possible_moves = self.getValidMoves(game_state)
  #Armazena a jogada que tem o melhor score.
  bestScore = -100
  #Se possui mais de uma jogada disponivel.
  if len(possible_moves) > 1:
   for possible_move in possible_moves:
    new_game_state = eval(repr(game_state))
    #Inicia com a jogada do telefone.
    px,py = possible_move
    new_game_state[px][py] = 1
    #Obtem o minimo do proximo nivel (MIN).
    score = self.minValue(new_game_state)
    #Pega o maior score dos piores analisados.
    if score >= bestScore:
     move = possible_move
     bestScore = score
  else:
   #Apenas uma única jogada, esta será a jogada do telefone.
   move = possible_moves[0]
   
  return move

     
 def phoneTurn(self):
  global game_state
  turn = 1
  px,py = self.phoneDecision()
  if(game_state[px][py]==0):
   buf.text((self.xcoord[px],self.ycoord[py]), u"O", font="title")
   game_state[px][py]=1
   handle_redraw(())
   self.drawgrid()
   turn=2
  return turn

Observem a implementação da função phoneTurn(). Decidimos substituir as chamadas das funções de sorteio aleatória de jogadas pela função phoneDecision(). A idéia é que quando for o turno do jogador 1 (telefone) realizar a sua jogada, uma árvore seja criada com o nó raiz sendo seu nível atual (ply1), ou seja o estado do tabuleiro antes de realizar a sua jogada. Todos os possíveis movimentos que o jogador 1 (fone) a partir daquele estado são mapeados no próximo nível (ply2). O próximo nível (ply3) abriga todas as contra-jogadas possíveis pelo jogador2 (humano) após os movimentos realizados no nível ply2. Esse padrão continua alternadamente entre movimentos possíveis do jogador1 e jogador2 até chegar em uma configuração do tabuleiro que há uma vitória de um dos jogadores ou há um empate (não é mais possível realizar jogadas no tabuleiro). A árvore de jogadas para um simples jogo da velha é geralmente composto por 4 a 6 níveis de altura. Isto significa que até este jogo pode construir uma árvore de jogadas um pouco grande para ser armazenada na memória ou para ser totalmente percorrida em um tempo razoável, especialmente quando estamos tentando implementar um jogo para um aparelho móvel que não possui o mesmo poder de processamento e memória que um PC. Irei em breve discutir sobre como reduzir o tamanho da árvore em breve. Temporariamente, vamos assumir que os nós finais (folhas) da árvore representem o estado final (fim do jogo), o qual se pode obter um valor. Este valor em cada folha da árvore representa uma nota de avaliação do jogo pela perspectiva do jogador 1 (fone). Um alto valor representa uma vantagem para o jogador1 enquanto um valor baixo representa uma desvantagem. Veja a implementação da função judge(). Ela é responsável por obter a nota de avaliação no fim do jogo. Para este jogo da velha, especificamos que +1 seria o valor retornado para caso fosse a vitória do jogador1, -1 para derrota e 0 para caso de empate.

Faria sentido se no ponto de vista do jogador1 (fone) pegasse o nó da árvore que tivesse o maior valor. Porém, não faria sentido para o jogador2 (humano), já que para os seus interesses em vencer o jogo não selecionaria os maiores valores para o jogador 1. Isto acarreta num sistema alternado de avaliações, no qual os valores são propagados até o topo da árvore. O jogador1 está interessado em maximizar os valores, já o jogador2 está interessado em minimizar tais valores. Isto vem da premissa que cada jogador irá fazer a melhor jogada para eles.

Exemplo de árvore de jogadas

Uma vez que árvore foi gerada, uma busca por profundidade é realizada na árvore com o objetivo de propagar os valores das folhas da árvore (ply3) até o topo da árvore. Entretanto cada nível (ply) tem um conjunto diferente de regras de como cada valor é enviado até o nó raiz. Os níveis representando as jogadas do jogador1 (fone), os níveis pares, são considerados os níveis MAX. Os níveis ímpares (excluindo a raiz) são considerados os níveis MIN. Os níveis MAX irão enviar os melhores valores (scores) dos piores analisados vindos do nível mais abaixo, enquanto os níveis MIN irão enviar os piores valores dos melhores analisados do nível mais abaixo.

Observem a implementação das funções minValue() e maxValue(). Eles são funções bastante similares, com a diferença que em maxValue ele recebe um nó (estado atual do tabuleiro após feita as jogadas) e caminha sobre os nós- filho em busca dos melhores valores. Já o minValue faz o mesmo exceto que ele procura pelos piores valores. Vejam a figura neste link que ilustra bem o algoritmo minimax em ação.

Otimização por cortes Alpha-Beta

Imagine uma árvore de todas as jogadas possíveis de um jogo da velha. Mesmo com um tabuleiro com apenas nove posições, isto dá uma árvore com mais de 9! (362.880) nós. Em jogos como xadrez, onde as peças podem se movimentar em diversas direções, as árvores geradas nesses jogos com apenas alguns níveis podem levar a tamanhos gigantescos. Só para ter uma idéia, uma jogada de abertura de uma partida de xadrez tem mais 20 diferentes opções!

Pelo algoritmo descrito acima, a busca por profundidade pelo qual visitamos todos os nós da árvore é extremamente lenta, quando implementamos o mesmo em um jogo portado para um aparelho móvel. Algumas otimizações podem ser feitas a fim de tornar a busca mais eficiente e rápida. Uma delas bastante utilizadas na literatura, é o Alpha-beta shortcutting. Vamos incrementar o nosso código acima apresentado incluindo a técnica de cortes Alpha-beta e explicar como o mesmo funciona.

Vejamos o código abaixo:

class GameBoard:
 
 (...)
 
 def maxValue(self,board,alpha,beta):
  #Checa se o jogo foi finalizado (Vitória ou empate).
  if self.hasEnded(board):
   #Retorna o estado final do jogo (+1 Vitoria do fone, -1 Vitoria do Humano, 0 Empate)
   return self.judge(board)
   
  #Obtem todas as possiveis jogadas.
  possible_moves = self.getValidMoves(board)
  #Armazena a jogada que tem o melhor score.
  bestScore  = -100
  for possible_move in possible_moves:
   new_game_state = eval(repr(board))
   #Telefone joga.
   px,py = possible_move
   new_game_state[px][py] = 1
   #Obtem o minimo do proximo nivel (MIN).
   score = self.minValue(new_game_state,alpha,beta)
   #Pega o maior score dos piores analisados.
   if score >= bestScore:
    bestScore = score
    alpha = bestScore
   if alpha >= beta:
    return alpha
    
  return bestScore
  
 
 def minValue(self,board,alpha,beta):
  #Checa se o jogo foi finalizado (Vitória ou empate).
  if self.hasEnded(board):
   #Retorna o estado final do jogo (+1 Vitoria do fone, -1 Vitoria do Humano, 0 Empate)
   return self.judge(board)
  
  #Obtem todas as possiveis jogadas.
  possible_moves = self.getValidMoves(board)
  #Armazena a jogada que tem o pior score.
  bestScore = 100
  
  for possible_move in possible_moves:
   new_game_state = eval(repr(board))
   #Jogador joga.
   px,py = possible_move
   new_game_state[px][py] = 2
   #Obtem o maximo do proximo nivel (MAX).
   score = self.maxValue(new_game_state,alpha,beta)
   #Pega o menor score dos melhores analisados.
   if score <= bestScore:
    bestScore = score
    beta = score
   if beta <= alpha:
    return beta
  
  return bestScore
  
    
 def phoneDecision(self):
  #Testa todas jogadas possiveis.
  possible_moves = self.getValidMoves(game_state)
  #Armazena a jogada que tem o melhor score.
  bestScore = -100
  #Melhor score encontrado por MAX ate este nivel.
  alpha = -100
  #Melhor score encontrado por MIN ate este nivel.
  beta = 100
  #Se possui mais de uma jogada disponivel.
  if len(possible_moves) > 1:
   for possible_move in possible_moves:
    new_game_state = eval(repr(game_state))
    #Inicia com a jogada do telefone.
    px,py = possible_move
    new_game_state[px][py] = 1
    #Obtem o minimo do proximo nivel (MIN).
    score = self.minValue(new_game_state,alpha,beta)
    #Pega o maior score dos piores analisados.
    if score >= bestScore:
     move = possible_move
     bestScore = score
     alpha = score
    if alpha >= beta:
     break
  else:
   #Como so existe uma única jogada, esta será a jogada do telefone.
   move = possible_moves[0]
   
  return move
 
 (...)

Com apenas algumas linhas de código adicionais, nós aumentamos a eficiência do algoritmo minimax com a inclusão da variação de cortes alpha-beta. Esta técnica permite a omissão de alguns "ramos" da árvore de jogadas possíveis na busca da melhor jogada. Para isso, são introduzidos os limites Alpha e Beta, sendo Alpha o valor mínimo que se garante que o MAX obtenha, e o Beta o valor máximo que o MAX pode esperar obter. Logo, o valor final obtido encontrar-se-á entre este dois limites, considerada uma jogada que seja suficientemente boa (não necessariamente a melhor) para conduzir à decisão correta. No pior caso, o algoritmo alpha-beta visitará exatamente as mesmas posições que visita o algoritmo minimax simples, não havendo nesse caso vantagem deste algoritmo em relação ao minimax exaustivo. No entanto, está provado que no melhor caso (quando a jogada mais forte é considerada primeiro), o algoritmo alpha-beta terá apenas que avaliar o nó-pai do ramo de folhas das jogadas terminais, poupando assim tempo de processamento e memória.

Para ilustrar a explicação acima, dê uma olhada na figura abaixo. O valor para o nó A é 3, e na primeira rodada o valor para sub-árvore começando pelo nó B é 2. Basta observar que já que o nó B está no nível MIN, então o valor final para o nó B deve ser menor ou igual a 2. E nós já sabemos que o nó A abriga o valor 3, e ambos nós A e B possuem o mesmo nó-pai no nível MAX. Isto significa que o ramo da sub-árvore começando pelo nó B não precisaria ser visitado, porque 3 é melhor que 2 para o nó MAX. Então não vale o esforço de continuar a busca por nós filhos de B, e podemos seguradamente ignorar todo este ramo.

Algoritmo Minimax com variação de cortes alpha-beta

Podemos considerar a otimização acima realizada da seguinte maneira:

1. Adicionamos mais 2 valores (alpha e beta) na chamada das funções MinValue e MaxValueHave :
   • o valor alpha que contem o melhor valor MAX encontrado a partir daquele nível.
   • o valor beta que abriga o melhor valor MIN encontrado a partir daquele nível.
     
2. No nível MAX, antes de avaliar a próxima possível jogada e suas respectivas contra-jogadas (sub-árvore), o melhor valor (alpha) encontrado é comparado com o valor beta. Se o alpha for maior, então aborte a busca naquele nó.
   
3. No nível MIN, antes de avaliar a próxima jogada e suas respectivas contra-jogadas (sub-árvore), o melhor valor (beta) encontrado é comparado com o valor alpha. Se o beta for menor, então aborte a busca naquele nó.
   

Reduzindo o tamanho da árvore

A próxima otimização é limitar a profundidade da busca na árvore e definir alguma maneira de avaliar um nó se o mesmo não for o último da árvore (folha) que representa o estado do fim do jogo. Por exemplo, em uma partida de xadrez , o tempo necessário para percorrer toda a árvore de jogadas, devido à quantidade gigantesca de opções é enorme e não seria válido. Uma solução para isso é limitar a buscar em até 3 níveis de profundidade e avaliar o estado do tabuleiro a fim de verificar se na perspectiva do jogador é vantajosa ou não. Alguns fatores como peças capturadas, posições ocupadas, ou até número de peças em posição de ataque ou capturadas podem ser utilizadas como regras de avaliação.

Esta otimização é bastante simples de ser feita em linhas de código. Consiste apenas de incluir um mecanismo que mantenha na memória o valor do nível (ply) em que se está na busca na árvore e que possa ser comparado com um valor armazenado em uma variável global (maxDepth) que define o quão profundo você pode descer pela árvore. Adicionei algumas linhas de código ao código do algoritmo minimax com variações de corte Alpha-beta para incluir a verificação de profundidade. Vejam o código abaixo:

(...)
class GameBoard:
 def __init__(self):
  global game_state
  
  (...)
  
  #Especifica a máxima profundidade da árvore de busca.
  self.maxDepth = 3
 
  (...)
 
 
 def calculateChances(self,board,turn):
  #Dado o tabuleiro suposto (new_game_state), calcula quantas chances 
        #o jogador selecionado ainda tem para ganhar e retorna seu valor.
  winning_rows = eval(repr(self.end_game_state))
  for i in range(3):
   for j in range(3):
    if board[i][j] != 0 and board[i][j] != turn:
     forbidden_play = (i,j)
     list_remove = list()
     for row in winning_rows:
      if forbidden_play in row:
       list_remove.append(row)
     for chance in list_remove:
      winning_rows.remove(chance)
      
  return len(winning_rows)
 
 def judge(self,board):
  #Verifica o estado final do tabuleiro.
  #(Vitoria: +10,Derrota: -10,Empate: 0
  # Nao finalizada: [Número de 3-sequencias abertas para Vitoria] - [Numero de 3-sequencias abertas para derrota])
  winning_rows = list(self.end_game_state)
  winner = None
  for row in winning_rows:
   row_win = [board[x][y] for x,y in row]
   if row_win == [1,1,1]:
    winner = 1
    break
   elif row_win == [2,2,2]:
    winner = 2
    break  
  if winner == 1:
   return 10
  if winner == None:
   #Sem mais jogadas disponiveis, significa que o jogo empatou.
   if self.hasEnded(board):
    return 0
   else:
    #calcula quantas chances o jogador selecionado ainda tem para ganhar e retorna seu valor.
    return self.calculateChances(board,1) - self.calculateChances(board,2)  
  return -10
 
 
 def maxValue(self,board,alpha,beta,depth):
  depth+=1
  #Checa se o jogo foi finalizado (Vitória ou empate) ou se está na profundidade máxima de busca.
  if self.hasEnded(board) or depth == self.maxDepth:
   #Retorna o estado final do jogo (+1 Vitoria do fone, -1 Vitoria do Humano, 0 Empate)
   return self.judge(board)
   
  #Obtem todas as possiveis jogadas.
  possible_moves = self.getValidMoves(board)
  #Armazena a jogada que tem o melhor score.
  bestScore  = -100
  for possible_move in possible_moves:
   new_game_state = eval(repr(board))
   #Telefone joga.
   px,py = possible_move
   new_game_state[px][py] = 1
   #Obtem o minimo do proximo nivel (MIN).
   score = self.minValue(new_game_state,alpha,beta,depth)
   #Pega o maior score dos piores analisados.
   if score >= bestScore:
    bestScore = score
    alpha = bestScore
   if alpha >= beta:
    return alpha
    
  return bestScore
   
 def minValue(self,board,alpha,beta,depth):
  depth +=1
  #Checa se o jogo foi finalizado (Vitória ou empate) ou se está na profundidade máxima de busca.
  if self.hasEnded(board) or depth == self.maxDepth: 
   #Retorna o número de pontos acumulados pelo jogador - número de pontos acumulados pelo outro jogador
   return self.judge(board)
  
  #Obtem todas as possiveis jogadas.
  possible_moves = self.getValidMoves(board)
  #Armazena a jogada que tem o pior score.
  bestScore = 100
  for possible_move in possible_moves:
   new_game_state = eval(repr(board))
   #Jogador joga.
   px,py = possible_move
   new_game_state[px][py] = 2
   #Obtem o maximo do proximo nivel (MAX).
   score = self.maxValue(new_game_state,alpha,beta,depth)
   #Pega o menor score dos melhores analisados.
   if score <= bestScore:
    bestScore = score
    beta = score
   if beta <= alpha:
    return beta
  
  return bestScore
     
 def phoneDecision(self):
  #Testa todas jogadas possiveis.
  possible_moves = self.getValidMoves(game_state)
  #Armazena a jogada que tem o melhor score.
  bestScore = -100
  #Melhor score encontrado por MAX ate este nivel.
  alpha = -100
  #Melhor score encontrado por MIN ate este nivel.
  beta = 100
  #profundidade atual
  depth = -1
  #Se possui mais de uma jogada disponivel.
  if len(possible_moves) > 1:
   depth += 1
   for possible_move in possible_moves:    
    new_game_state = eval(repr(game_state))
    #Inicia com a jogada do telefone.
    px,py = possible_move
    new_game_state[px][py] = 1
    #Obtem o minimo do proximo nivel (MIN).
    score = self.minValue(new_game_state,alpha,beta,depth)
    #Pega o maior score dos piores analisados.
    if score >= bestScore:
     move = possible_move
     bestScore = score
     alpha = score
    if alpha >= beta:
     break
  else:
   #Como so existe uma única jogada, esta será a jogada do telefone.
   move = possible_moves[0]
   
  return move

 (...)

Como se pode observar com a inclusão deste novo mecanismo de limite de profundidade, a busca é interrompida antes de chegar ao estado final do jogo. Para solucionar este problema, assumimos agora a existência de uma função heurística (chamada de função de avaliação estática) - nova implementação da função judge(). A função de avaliação estática estima valores altos para indicar situações boas para a máquina e valores baixos para indicar situações desfavoráveis para a máquina. Ela avalia o estado do tabuleiro de acordo com o nó não terminal investigado. A função aplicada neste jogo da velha retorna valores de -10 a 10, sendo que +10 significa vitória do telefone, - 10 derrota do telefone e 0 em caso de empate para as condições em que a jogada resultar no fim do jogo. Para os outros casos, em que não se finalizou o jogo, a função calcula quantas chances o jogador1 (fone) tem de completar a sequência de símbolos para a vencer e quantas chances o jogador2 (humano) tem de completar a sua sequência. O valor retornado será a diferença entre esses dois valores calculados (score_fone - score_humano). Esse valor servirá como orientador da busca, e informará o quão vantajoso é para o jogador2 se ele decidir tomar a posição no ínicio da busca como sua jogada. A outra modificação foi nas funções de maxValue e minValue para suportar o limite de busca de profundidade. Para este caso, inicializamos a máxima profundidade (maxDepth) com o valor 3, este considerado um valor razoável para um aplicativo portado para plataformas móveis. Claro, que há um custo em comparação ao algoritmo Minimax padrão, já que o novo algoritmo "estima" a vantagem de a máquina vencer a partida, acarretando na perda de "inteligência" em tomar decisões mais precisas.

Conclusão

Estamos chegando ao fim deste artigo, onde apresentamos o algoritmo Minimax que pode ser aplicado em jogos a fim de determinar qual a melhor jogada através de uma árvore de decisão com todas as jogadas possíveis. Com um simples jogo da velha desenvolvido em Python para celulares Symbian S60, demonstramos o poder desse algoritmo e seu uso para construção de jogadores inteligentes. Algumas otimizações foram realizadas a fim de tornar o algoritmo mais eficiente, especialmente por se tratar de uma plataforma móvel (celulares) caracterizadas por poder de processamento limitado e pouca quantidade de memória. Demonstramos o algoritmo com cortes Alpha-beta, que realiza os mesmos cálculos que o algoritmo MiniMax, mas é mais eficiente pois corta ramificações que são irrelevantes para o resultado final. Na maioria dos casos é impossível considerar toda a árvore de jogadas, logo é necessário também cortar a árvore ou limitar a sua construção. Criamos mecanismos de controle de busca de profundidade e também a criaçãod e funções de avaliação, que estime o valor dos nós terminais.

Outras variações do minimax existem a fim de otimizá-lo ou deixá-lo mais inteligente. Posteriormente, novos artigos podem abordar essas variações do Minimax.

Espero que tenham gostado!

O código-fonte do jogo da velha com minimax está disponível para download aqui.

Até a próxima!

Marcel Pinheiro Caraciolo

Referências

[1] AI Depot article - MiniMax Explained
[2] Generation5 - MiniMax Trees
[3] Caltech - Minimax and Alpha Beta Template
[4] AlphaBeta cuttoff discussion
[5] MiniMax and Alpha-Beta Cutoff