Pular para o conteúdo principal

Implementando o algoritmo Minimax para IA em Python

Aprenda a programar uma IA imbatível de jogo da velha usando o algoritmo Minimax em Python. Este tutorial aborda teoria, implementação e otimização, ideal para entusiastas de IA de jogos.
Actualizado 31 de jan. de 2025  · 14 min de leitura

O algoritmo Mini-Max tem uma história rica em IA, que remonta à década de 1920. Embora o termo IA não fosse usado para algoritmos de computador naquela época, o algoritmo fundamental certamente forneceu alguns dos primeiros insights sobre como as máquinas poderiam tomar decisões ideais em cenários adversos. O algoritmo foi formalizado pela primeira vez por John von Neumann em seu artigo de 1928 "Zur Theorie der Gesellschaftsspiele" (Sobre a teoria dos jogos de estratégia), que estabeleceu as bases para a teoria moderna dos jogos e os algoritmos de tomada de decisão.

Em 1997, o Deep Blue da IBM derrotou o campeão mundial de xadrez Garry Kasparov usando as variantes avançadas do Mini-max. Desde então, o algoritmo tem sido a espinha dorsal de abordagens mais sofisticadas, como Busca em árvore de Monte Carlo (MCTS) e sistemas de aprendizado por reforço sistemas.

Neste artigo, não reconstruiremos o famoso Deep Blue para o xadrez, mas uma versão muito mais simples para o jogo da velha em Python. Ao longo do caminho, você adquirirá uma forte intuição sobre como o algoritmo funciona e como aplicá-lo a jogos mais complexos do mundo real.

O que é o algoritmo Minimax?

O Minimax é geralmente um algoritmo de tomada de decisão para jogos de dois jogadores (como xadrez, jogo da velha ou damas). Ele permite que os computadores planejem várias jogadas, presumindo que o adversário sempre fará a melhor jogada possível. Nesta seção, veremos uma visão geral do algoritmo por meio do exemplo do jogo da velha.

Visão geral do algoritmo Minimax

Em um jogo da velha do mundo real, toda vez que chega a sua vez, você tenta fazer a melhor jogada possível, presumindo que seu oponente também fará a melhor jogada. É exatamente isso que o algoritmo Minimax faz: ele ajuda o computador a fazer a melhor jogada possível, pensando antecipadamente em todas as jogadas possíveis.

O nome do algoritmo Minimax vem do modo como ele funciona:

  • "Mini" representa o adversário tentando minimizar sua pontuação
  • "Max" representa você tentando maximizar sua pontuação

Quando for a sua vez, você deve fazer jogadas que lhe proporcionem a melhor chance de ganhar (maximização). Quando é a vez do seu oponente, você presume que ele fará movimentos que lhe darão o pior resultado (minimização).

A importância do Minimax na IA

O Minimax é muito importante na inteligência artificial por vários motivos:

  1. Ele ajuda os computadores a tomar decisões inteligentes em jogos para dois jogadores
  2. É a base de muitos sistemas modernos de IA para jogos
  3. Ele ensina os computadores a pensar no futuro e a planejar movimentos

A parte mais legal? Essa mesma ideia é usada em muitos aplicativos do mundo real:

  • Oponentes de IA de videogame
  • Jogos de estratégia, como xadrez e damas
  • Até mesmo algumas ferramentas de tomada de decisões de negócios

Embora o Minimax possa parecer complicado, na verdade trata-se apenas de ensinar o computador a pensar como um jogador cuidadoso que considera suas jogadas e as jogadas do adversário antes de tomar uma decisão.

Entendendo o algoritmo Minimax

Vamos explicar como o Minimax funciona usando um exemplo simples de jogo da velha. Imagine que você está jogando com X, e o computador é O.

Como o computador pensa

Quando for a vez do computador, você seguirá estas etapas:

  1. Veja todos os movimentos possíveis que você pode fazer
  2. Para cada movimento, ele imagina o que você pode fazer em seguida
  3. Ele continua pensando no futuro até chegar a um ponto final (como a vitória de alguém ou um empate)
  4. Ele escolhe a jogada que lhe dá a melhor chance de vencer

Pontuação do jogo

O computador pode usar um sistema de pontuação simples:

  • +10 pontos se o computador vencer
  • -10 pontos se você vencer
  • 0 pontos se houver empate

Pense nisso como uma árvore de possibilidades:

  • Na parte superior está o tabuleiro de jogo atual
  • Cada ramo é um movimento possível
  • Na parte inferior, você encontrará todos os resultados possíveis

Revezamento

O computador alterna entre dois modos de pensar:

1. Modo de maximização (é a vez do computador):

  • Procura movimentos que obtêm a pontuação mais alta
  • Tentativas de vencer ou forçar um empate

2. Modo de minimização (vez do jogador):

  • Pressupõe que você fará movimentos que obtenham a pontuação mais baixa
  • Prepara você para as melhores jogadas possíveis

Um exemplo simples

Digamos que seja a vez do computador (X) neste jogo:

Um exemplo de estado em um jogo do galo a ser resolvido com o algoritmo mini-max

O computador irá:

  1. Você verá que há 3 lugares vazios para escolher
  2. Para cada ponto vazio, ele imagina todos os movimentos futuros possíveis
  3. Escolhe o movimento que leva ao melhor resultado
  4. Nesse caso, você deve selecionar o canto inferior médio para bloquear sua vitória

Essa maneira de pensar no futuro ajuda o computador a jogar uma partida perfeita de jogo da velha todas as vezes!

Pseudocódigo do algoritmo Minimax

Vamos explicar a você como escrever o algoritmo Minimax, passo a passo. Não se preocupe se você não conhece o pseudocódigo - pense nele como se estivesse escrevendo as etapas em inglês simples antes de transformá-lo em código real!

Explicação passo a passo

A função Minimax precisa de três coisas principais para funcionar:

  1. O tabuleiro de jogo atual
  2. A profundidade (quantos movimentos à frente você está procurando)
  3. Seja na vez do jogador maximizador (computador) ou na vez do jogador minimizador (humano)

Veja como é o pseudocódigo básico:

function minimax(board, depth, isMaximizingPlayer):
   # First, check if the game is over
   if game is won:
       return +10 if computer wins, -10 if human wins
   if game is tied:
       return 0

   # If it's the computer's turn (maximizing)
   if isMaximizingPlayer:
       bestScore = -infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, false)
           undo the move
           bestScore = max(score, bestScore)
       return bestScore

   # If it's the human's turn (minimizing)
   else:
       bestScore = +infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, true)
           undo the move
           bestScore = min(score, bestScore)
       return bestScore

Embora a maioria dos exemplos de pseudocódigo seja lida em inglês e seja perfeitamente compreensível, o exemplo acima é diferente, pois usa recursão. Recursão é quando uma função chama a si mesma várias vezes para resolver um problema maior. Pense nisso como olhar em um espelho que reflete outro espelho - você vê a mesma imagem repetida muitas vezes, ficando menor a cada vez.

Em nosso algoritmo Minimax, precisamos de recursão porque estamos tentando examinar todas as jogadas futuras possíveis no jogo. Cada vez que a função chama a si mesma, ela está analisando o próximo movimento que pode acontecer. 

Isso nos ajuda a descobrir a melhor jogada, verificando todas as maneiras possíveis de o jogo se desenrolar, como um jogador realmente inteligente que pensa: "Se eu fizer isso, eles podem fazer aquilo, então eu poderia fazer isso..." e assim por diante até o fim do jogo. Para saber mais sobre recursão, você pode ler nosso tutorial de recursão separado.

Exemplo ilustrativo

Vamos ver como isso funciona em uma situação simples de jogo:

1. Posição inicial:

Um exemplo de estado em um jogo do galo a ser resolvido com o algoritmo mini-max

2. O computador pensa:

  • "Se eu colocar X em qualquer lugar vazio..."
  • "O que o humano faria em seguida?"
  • "E o que eu poderia fazer depois disso?"
  • "Qual movimento me dá a melhor pontuação final?"

3. Para cada ponto vazio, o computador:

  • Faz um movimento
  • Verifica se o jogo terminou
  • Se não tiver terminado, você imagina a melhor jogada do humano
  • Continua até encontrar um final
  • Escolhe a jogada com a maior pontuação

Pense nisso como no xadrez - você está sempre pensando "Se eu me mover para cá, eles se moverão para lá, então eu posso me mover para cá...", mas o computador pode pensar em TODOS os movimentos possíveis ao mesmo tempo!

O interessante desse algoritmo é que ele sempre encontra a melhor jogada possível, supondo que ambos os jogadores joguem perfeitamente. É como ter uma bola de cristal que mostra a você todos os futuros possíveis do jogo!

Implementação passo a passo do Minimax para o jogo da velha

Nesta seção, criaremos uma IA de jogo da velha imbatível com o algoritmo Mini-max em Python puro. Vamos dividir a implementação em etapas simples e explicar a intuição por trás de cada uma delas e como ela se encaixa no panorama geral do jogo.

Etapa 1: Definição de uma classe TicTacToe

Primeiro, definimos uma classe que contém toda a lógica e os métodos necessários para jogar um jogo da velha com nossos computadores:

class TicTacToe:
   def __init__(self):
       # Initialize empty board (using ' ' for empty squares)
       self.board = [" " for _ in range(9)]
       self.human_player = "O"
       self.ai_player = "X"

   def print_board(self):
       """Print the current state of the board"""
       for i in range(0, 9, 3):
           print(f"{self.board[i]} | {self.board[i+1]} | {self.board[i+2]}")
           if i < 6:
               print("---------")

   def available_moves(self):
       """Returns list of available moves (indices of empty squares)"""
       return [i for i, spot in enumerate(self.board) if spot == " "]

Acima, o método __init__ inicializa um novo tabuleiro de jogo como uma lista de 9 espaços vazios (representados por espaços " "), com índices de 0 a 8 representando as posições do tabuleiro da esquerda para a direita, de cima para baixo. Ele também configura dois símbolos de jogador: "O" para o jogador humano e "X" para a IA.

O método print_board oferece uma maneira de visualizar o estado atual do quadro. Ele imprime a grade 3x3 com linhas divisórias entre as linhas, mostrando os movimentos de cada jogador em suas respectivas posições.

O métodoavailable_moves retorna uma lista de todas as jogadas válidas que ainda podem ser feitas. Ele faz isso verificando quais posições no tabuleiro ainda estão vazias (contêm um espaço " ") e retornando seus índices. Isso será fundamental para que o algoritmo minimax saiba quais movimentos ele pode considerar.

Esses métodos formam a base sobre a qual nos basearemos para criar nosso jogador de IA usando o algoritmo minimax.

Vamos testá-los rapidamente:

>>> game = TicTacToe()
>>> game.print_board()
  |   | 
---------
  |   | 
---------
  |   |

>>> game.available_moves()
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Como esperado, temos um tabuleiro vazio no momento e todas as jogadas estão disponíveis.

Etapa 2: Implementar métodos para fazer uma jogada e verificar os estados do quadro

Agora, vamos adicionar um método para fazer um movimento:

class TicTacToe:
   ...
  
   def make_move(self, position, player):
       """Make a move on the board"""
       if self.board[position] == " ":
           self.board[position] = player
           return True
       return False

Adicionamos o método make_move, que você pode usar para fazer o que quiser:

  • Recebe uma posição (0-8) e o símbolo do jogador ("X" ou "O") como entrada
  • Verifica se a posição selecionada está vazia (" ")
  • Se estiver vazio, coloca o símbolo do jogador e retorna True
  • Se a posição já estiver ocupada, você retornará False sem fazer nenhuma alteração

Vamos fazer algumas jogadas e verificar as jogadas restantes:

>>> game = TicTacToe()

>>> game.make_move(0, "X")
>>> game.make_move(1, "O")

>>> game.print_board()
 X | O | 
-----------
   |   | 
-----------
   |   |

>>> game.available_moves()
[2, 3, 4, 5, 6, 7, 8]

Funcionando bem. A próxima etapa é adicionar um método para verificar se o quadro está cheio:

class TicTacToe:
   ...

   def is_board_full(self):
       """Check if the board is full"""
       return " " not in self.board

is_board_full é um método booleano que verifica se ainda há espaços vazios no tabuleiro.

Em seguida, adicionamos um método para verificar se um estado vencedor foi alcançado:

class TicTacToe:
   ...

   def check_winner(self):
       """Check if there's a winner. Returns winner symbol or None"""
       # Check rows
       for i in range(0, 9, 3):
           if self.board[i] == self.board[i + 1] == self.board[i + 2] != " ":
               return self.board[i]

       # Check columns
       for i in range(3):
           if self.board[i] == self.board[i + 3] == self.board[i + 6] != " ":
               return self.board[i]

       # Check diagonals
       if self.board[0] == self.board[4] == self.board[8] != " ":
           return self.board[0]
       if self.board[2] == self.board[4] == self.board[6] != " ":
           return self.board[2]

       return None

O método check_winner avalia o estado atual do tabuleiro Tic-tac-toe para determinar se há um vencedor. Ele verifica todas as combinações vencedoras possíveis:

1. Fileiras (3 possibilidades):

  • Linha superior (índices 0,1,2)
  • Linha do meio (índices 3,4,5)
  • Linha inferior (índices 6,7,8)

2. Colunas (3 possibilidades):

  • Coluna esquerda (índices 0,3,6)
  • Coluna do meio (índices 1,4,7)
  • Coluna da direita (índices 2,5,8)

3. Diagonais (2 possibilidades):

  • Da parte superior esquerda para a parte inferior direita (índices 0,4,8)
  • De cima para baixo, da direita para a esquerda (índices 2,4,6)

Para cada combinação, ele verifica se todas as três posições contêm o mesmo símbolo de jogador (X ou O) e se não são espaços vazios. Se você encontrar uma combinação vencedora, ela retornará o símbolo do jogador vencedor. Se nenhum vencedor for encontrado após a verificação de todas as possibilidades, ele retornará None.

Vamos testar a função em estados vencedores e não vencedores:

game = TicTacToe()

# Winning state
game.make_move(0, "X")
game.make_move(1, "X")
game.make_move(2, "X")

>>> game.print_board()
 X | X | X
-----------
   |   | 
-----------
   |   |

>>> game.check_winner()
'X'

game = TicTacToe()

# Non-winning state
game.make_move(0, "X")
game.make_move(1, "O")
game.make_move(2, "O")
game.make_move(3, "X")

>>> game.print_board()
 X | O | O
-----------
 X |   | 
-----------
   |   |

>>> game.check_winner() is None
True

Por fim, adicionamos outro método booleano para especificar se o jogo terminou ou não:

class TicTacToe:
   ...

   def game_over(self):
       """Check if the game is over"""
       return self.check_winner() is not None or self.is_board_full()

O método retorna True se o vencedor for encontrado ou se o tabuleiro estiver cheio.

Até o momento, criamos toda a mecânica central do jogo:

  • O tabuleiro é representado como uma lista de 9 quadrados inicializados vazios
  • print_board() exibe visualmente o estado atual do jogo
  • available_moves() retorna índices de quadrados vazios
  • make_move() coloca o símbolo de um jogador no tabuleiro
  • check_winner() Examina linhas, colunas e diagonais para obter uma vitória em cada jogada
  • is_board_full() determina se não há movimentos restantes
  • game_over() combina a verificação do vencedor com a verificação do quadro completo

Esses métodos fornecem a base necessária para criar um jogo jogável, lidando com todas as operações básicas, como fazer movimentos e determinar o estado do jogo.

Agora vem a parte crítica: dar ao computador o "cérebro" para jogar o jogo com o Minimax.

Etapa 3: Implementação do Minimax para o jogo da velha

Agora, vamos implementar o algoritmo do jogo em um novo método:

class TicTacToe:
   ...

   def minimax(self, depth, is_maximizing):
       """
       Minimax algorithm implementation
       Returns the best score possible for the current board state
       """
       # Base cases
       winner = self.check_winner()
       if winner == self.ai_player:
           return 1
       if winner == self.human_player:
           return -1
       if self.is_board_full():
           return 0

A função recebe dois parâmetros:

  • depth - Rastreia quantos níveis de profundidade temos na recursão. Isso pode ser usado para limitar a profundidade da pesquisa em jogos muito complexos, embora para o jogo da velha não seja necessário limitá-la.
  • is_maximizing - Um sinalizador booleano que indica se estamos procurando a pontuação máxima (turno da IA) ou a pontuação mínima (turno do humano). Isso se alterna com cada chamada recursiva à medida que os jogadores se revezam.

No corpo da função, começamos definindo os casos básicos: Se o jogo for vencido pela IA (winner == ai_player), retornaremos 1, pois esse é o melhor resultado possível para a IA. Se o ser humano vencer (winner == human_player), retornaremos -1, pois esse é o pior resultado para a IA. Se o tabuleiro estiver cheio e não houver vencedor, retornaremos 0 para um empate.

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       best_score = float("-inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(depth + 1, False)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = max(score, best_score)
       return best_score

Quando is_maximizing é True, estamos simulando a vez da IA e queremos encontrar a jogada que leva à maior pontuação possível. Começamos definindo best_score como infinito negativo para que qualquer pontuação real seja melhor. Então, para cada movimento disponível, nós:

  1. Coloque o símbolo da IA no tabuleiro temporariamente
  2. Avalie recursivamente o que aconteceria se você fizesse essa jogada chamando o minimax com is_maximizing=False (já que seria a vez do humano em seguida)
  3. Desfaça a movimentação temporária para restaurar o estado do quadro
  4. Acompanhe a pontuação mais alta que vimos até agora usando max()

Isso nos permite verificar todos os movimentos possíveis que a IA poderia fazer. Para cada jogada, analisamos o que pode acontecer em seguida, até que alguém vença ou o jogo esteja empatado. Em seguida, trabalhamos de trás para frente para descobrir qual primeira jogada dá à IA a melhor chance de vencer.

Agora, vamos fazer a parte de minimização para o ser humano:

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       ...

   else:
       # if it is the minimizing player's turn (human), we want to minimize the score
       best_score = float("inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.human_player
           # Recursively call minimax with the next depth and the maximizing player
           score = self.minimax(depth + 1, True)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = min(score, best_score)
       return best_score

Quando is_maximizing é False, estamos simulando a vez do jogador humano e queremos encontrar o movimento que leva à menor pontuação possível (já que uma pontuação alta significa que a IA vence). Começamos com best_score como infinito positivo, portanto, qualquer pontuação real será menor. Para cada movimento disponível, nós:

  1. Coloque o símbolo do humano no quadro temporariamente
  2. Avalie recursivamente o que aconteceria chamando o minimax com is_maximizing=True (já que seria a vez da IA em seguida)
  3. Desfaça a movimentação temporária para restaurar o estado do quadro
  4. Acompanhe a pontuação mais baixa que já vimos usando min()

Isso simula o jogador humano tentando fazer as melhores jogadas para evitar que a IA vença. O ser humano quer minimizar a pontuação, pois as pontuações positivas representam vitórias da IA. Ao alternar entre turnos de maximização e minimização, o algoritmo pode determinar a sequência de movimentos ideal para ambos os jogadores.

Etapa 4: Encontrar a melhor jogada para IA usando o Minimax

Agora que temos o algoritmo pronto, precisamos de outro método que use o método minimax para determinar a melhor jogada para a IA após cada jogada humana:

class TicTacToe:
   ...

   def get_best_move(self):
       """Find the best move for AI using minimax"""
       best_score = float("-inf")
       best_move = None

       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(0, False)
           # Reset the move
           self.board[move] = " "

           # Update the best score
           if score > best_score:
               best_score = score
               best_move = move

       return best_move

O método get_best_move é responsável por determinar o movimento ideal para o jogador de IA usando o algoritmo minimax. Ele funciona da seguinte forma:

1. Começando com infinito negativo como a melhor pontuação e nenhuma jogada selecionada

2. Para cada jogada disponível no tabuleiro:

  • Colocar temporariamente o símbolo da IA nessa posição
  • Usar o minimax para avaliar a qualidade dessa jogada, simulando o restante do jogo
  • Desfazendo a mudança temporária
  • Se essa jogada levar a uma pontuação melhor do que a que vimos antes, você atualizará a melhor pontuação e a melhor jogada

3. Finalmente, você retornou a jogada que levou à maior pontuação

Essa abordagem garante que a IA escolherá a jogada que oferece a melhor chance de vitória, supondo que o jogador humano também jogue de forma otimizada. O método considera todos os possíveis estados futuros do jogo e escolhe o caminho que maximiza as chances da IA e minimiza as chances de vitória do ser humano.

Vamos testá-lo em um exemplo de estado de jogo:

game = TicTacToe()

# Make a couple of moves
game.make_move(0, "X")
game.make_move(1, "O")

# Print the board

>>> game.print_board()
X | O | 
---------
  |   | 
---------
  |   |

>>> game.get_best_move()
3

# AI moves
>>> game.make_move(3, "X")

# I move
>>> game.make_move(4, "O")
>>> game.print_board()
X | O | 
---------
X | O | 
---------
  |   |

# Get the best move for AI
>>> game.get_best_move()
6

Como você pode ver, a IA encontrou a combinação vencedora com base nas minhas jogadas (era um estado fictício, mas isso prova que nosso algoritmo está funcionando).

Etapa 5: Implementação de um loop de jogo

Agora que implementamos e testamos nosso algoritmo minimax, vamos criar um loop de jogo que nos permita jogar contra a IA.

class TicTacToe:

   ...

   def play_game(self):
       """Main game loop"""
       print("Welcome to Tic Tac Toe!")
       print("You are 'O' and the AI is 'X'")
       print("Enter positions (0-8) as shown below:")
       print("0 | 1 | 2")
       print("---------")
       print("3 | 4 | 5")
       print("---------")
       print("6 | 7 | 8")
       print("\n")

O método play_game começa com a exibição de uma mensagem de boas-vindas e instruções para o jogador. Isso mostra que o jogador humano usa "O" e a IA usa "X". Em seguida, ele imprime uma grade numerada (0-8) para mostrar ao jogador qual número corresponde a qual posição no tabuleiro. Isso facilita para os jogadores saberem exatamente qual número devem inserir para a jogada desejada.

# ... the rest of the class
def play_game(self):
   ...

   # Randomly decide who goes first
   import random

   ai_turn = random.choice([True, False])

   while not self.game_over():
       self.print_board()

       if ai_turn:
           print("\nAI's turn...")
           move = self.get_best_move()
           self.make_move(move, self.ai_player)
       else:
           while True:
               try:
                   move = int(input("\nYour turn (0-8): "))
                   if 0 <= move <= 8 and self.make_move(move, self.human_player):
                       break
                   else:
                       print("Invalid move! Try again.")
               except ValueError:
                   print("Please enter a number between 0 and 8!")

       ai_turn = not ai_turn

Depois de exibir as instruções iniciais, o jogo entra em seu loop principal. O jogo decide aleatoriamente quem vai primeiro - a IA ou o jogador humano - usando o site random.choice([True, False]). Isso cria um elemento de justiça e imprevisibilidade no início de cada jogo.

O loop principal do jogo continua até que game_over() retorne True (ou alguém ganhou ou o tabuleiro está cheio). Durante cada turno, o estado atual do tabuleiro é exibido usando print_board().

Se for a vez da IA (ai_turn é True), o programa:

  1. Imprime uma mensagem indicando que a IA está pensando
  2. Chama get_best_move() para determinar o movimento ideal usando o algoritmo minimax
  3. Você faz a jogada colocando o símbolo da IA ("X") na posição escolhida

Se for a vez do ser humano (ai_turn é False), o programa:

1. Entra em um loop para obter entradas válidas do jogador2. Solicita um número de movimento entre 0-83. Valida que a entrada é:

  • Um número inteiro válido (usando try/except)
  • Dentro do intervalo válido de 0 a 8
  • Aponta para uma posição vazia no quadro

4. Continua perguntando até que uma entrada válida seja recebida. Você faz a jogada colocando o símbolo do jogador ("O") na posição escolhida

Após cada turno, o site ai_turn é virado usando not para alternar entre os jogadores. Isso cria o fluxo de ida e volta do jogo, com cada jogador se revezando até que alguém vença ou o jogo termine empatado.

A validação de entrada garante que o jogo não trave devido a entradas inválidas do usuário e fornece mensagens de erro úteis para orientar o jogador a inserir os movimentos corretos. Isso cria uma experiência de jogo robusta e fácil de usar.

def play_game(self):
   ...
   # Game over
   self.print_board()
   winner = self.check_winner()
   if winner == self.ai_player:
       print("\nAI wins!")
   elif winner == self.human_player:
       print("\nCongratulations! You win!")
   else:
       print("\nIt's a tie!")

Quando o jogo termina, o estado final do tabuleiro é exibido usando print_board() e o vencedor é determinado por check_winner(). O jogo pode terminar de três maneiras:

  1. A IA vence - Se check_winner() retornar o símbolo da IA ('X'), indicando que a IA alcançou uma linha vencedora
  2. Human wins - Se o site check_winner() retornar o símbolo do humano ('O'), indicando que o jogador conseguiu uma linha vencedora
  3. Empate - Se nenhum dos jogadores tiver vencido, mas o tabuleiro estiver cheio, o que significa que não há mais jogadas possíveis

A mensagem apropriada é exibida para anunciar o resultado do jogo. Isso fornece um feedback claro para o jogador sobre como o jogo foi concluído.

Etapa 6: Colocando tudo junto

Agora, é hora de colocar todo o código que escrevemos até agora em um script Python com o seguinte if/main a seguir, bem no final:

# Start the game
if __name__ == "__main__":
   game = TicTacToe()
   game.play_game()

Isso permite que o jogo seja iniciado assim que você executar o script com python script.py. Se você se perdeu em meio a todas as explicações e blocos de código, pode encontrar o código completo do jogo neste gist do GitHub.

Aqui está um exemplo de jogo que eu joguei:

❯ python tic-tac-toe.py
Welcome to Tic Tac Toe!
You are 'O' and the AI is 'X'
Enter positions (0-8) as shown below:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8


  |   | 
---------
  |   | 
---------
  |   | 

Your turn (0-8): 4
  |   | 
---------
  | O | 
---------
  |   | 

AI's turn...
X |   | 
---------
  | O | 
---------
  |   | 

Your turn (0-8): 5
X |   | 
----------
  | O | O
----------
  |   | 

AI's turn...
X |   | 
---------
X | O | O
---------
  |   | 

Your turn (0-8): 6
X |   | 
---------
X | O | O
---------
O |   | 

AI's turn...
X |   | X
---------
X | O | O
---------
O |   | 

Your turn (0-8): 1
X | O | X
---------
X | O | O
---------
O |   | 

AI's turn...
X | O | X
---------
X | O | O
---------
O | X | 

Your turn (0-8): 8
X | O | X
---------
X | O | O
---------
O | X | O

It's a tie!

Lembre-se de que, como o jogo da velha é um jogo simples, não há chance de vencer a IA. Ou termina em empate ou você perde!

Formalização do algoritmo Mínimo Máximo

Agora, vamos analisar a definição geral de algoritmo além do exemplo simples do jogo da velha.

O algoritmo Minimax pode ser formalmente definido como uma função recursiva que avalia as posições em um jogo de soma zero. Vamos detalhar seus componentes e propriedades formais.

Definição matemática

Para um estado de jogo s, o valor minimax V(s) é definido como:

V(s) =
   utility(s)                    if s is terminal
   max(V(s')) for all s' in S    if player = MAX
   min(V(s')) for all s' in S    if player = MIN

Onde:

  • s' representa os estados sucessores de s
  • S é o conjunto de todos os movimentos legais do estado s
  • utility(s) é a função de avaliação para estados terminais

Principais propriedades

1. Informações perfeitas

  • Todos os jogadores têm conhecimento completo do estado do jogo
  • Sem informações ocultas ou elementos aleatórios
  • Resultados determinísticos

2. Natureza de soma zero

  • O ganho de um jogador é exatamente igual à perda do outro jogador
  • A soma das utilidades de todos os jogadores é sempre zero
  • Para jogos de dois jogadores, os utilitários são normalmente {-1, 0, 1}

3. Jogo ideal

  • Pressupõe que ambos os jogadores tomem decisões ótimas
  • Garante o melhor resultado possível em um jogo perfeito
  • Leva a um equilíbrio de Nash em termos de teoria dos jogos

Análise de complexidade

Complexidade de tempo: O(b^m)

  • b = fator de ramificação (número de movimentos legais em cada estado)
  • m = profundidade máxima da árvore do jogo

Complexidade espacial: O(bm)

  • É necessário armazenar o estado do jogo em cada nível
  • Pode ser otimizado com aprofundamento iterativo

Função de avaliação

Para estados não terminais, a função de avaliação f(s) deve:

  1. Correlacionar com a probabilidade de ganhar
  2. Ser computacionalmente eficiente
  3. Manter o dimensionamento consistente durante todo o jogo

A definição formal:

f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ

Onde:

  • wᵢ são pesos para diferentes recursos
  • xᵢ são valores de recursos do estado do jogo
  • n é o número de recursos que estão sendo avaliados

Garantia de otimização

O algoritmo Minimax garante o jogo ideal nessas condições:

  1. Informações perfeitas
  2. Resultados determinísticos
  3. Pesquisa completa para estados terminais
  4. Avaliação precisa do estado do terminal

Isso o torna particularmente adequado para jogos como xadrez, jogo da velha e damas, em que essas condições são atendidas.

Variações e limitações avançadas

Embora o Minimax seja ótimo para jogos simples, como o jogo da velha, ele tem alguns problemas com jogos maiores. Vamos ver como podemos melhorá-lo e onde ele tem dificuldades.

Tornando o Minimax mais rápido: Poda alfa-beta

Imagine que você está jogando xadrez e pensando em suas jogadas. Se você encontrou uma jogada vencedora, não precisa verificar todas as outras jogadas possíveis, certo? A poda alfa-beta funciona da mesma forma: ela ajuda o computador a pular a verificação de movimentos que já sabemos que não serão melhores do que os que já encontramos.

Pense nisso da seguinte forma:

  • Você está comprando a barra de chocolate mais barata
  • Você tem US$ 1 para gastar
  • Se você encontrar uma barra de chocolate por 50 centavos, pode deixar de olhar as barras de chocolate que custam mais de US$ 1
  • Isso faz com que você economize tempo!

Limites de profundidade: Não olhar muito à frente

Em jogos grandes, como o xadrez, há muitos movimentos possíveis para que você possa verificar todos eles. Portanto, adicionamos um limite de profundidade:

  1. Olhe para frente apenas de 4 a 5 movimentos, em vez de olhar até o final
  2. Faça uma boa estimativa de quão boa é a posição naquele momento
  3. Escolha a melhor jogada com base nessas suposições

Você não pode planejar cada movimento até o final do jogo, mas pode planejar alguns movimentos com antecedência!

Onde o Minimax tem dificuldades

O Minimax não é perfeito. Aqui estão seus principais problemas:

1. Muitas opções

  • Jogos como o Go têm um número excessivo de movimentos possíveis
  • Mesmo computadores rápidos não conseguem verificar todas elas
  • É por isso que precisamos de outros métodos para jogos realmente complexos

2. Problemas de tempo

  • Quanto mais movimentos à frente você olhar, mais tempo levará
  • No xadrez, os computadores não podem examinar todas as jogadas possíveis
  • Eles precisam ser inteligentes quanto aos movimentos a serem verificados

3. Não é bom para jogos de incerteza

  • O Minimax funciona melhor quando você pode ver tudo
  • Não é bom para jogos de cartas em que você não sabe quais cartas os outros têm
  • Ele não consegue lidar bem com eventos aleatórios (como lançamentos de dados)

Soluções modernas

A IA dos jogos atuais geralmente combina o Minimax com outras técnicas interessantes:

1. Aprendizado de máquina

  • Os computadores podem aprender assistindo a muitos jogos
  • Isso os ajuda a fazer melhores suposições sobre boas jogadas
  • Jogos como AlphaGo usam isso para você vencer campeões humanos

2. Reconhecimento de padrões

  • Em vez de verificar cada movimento, procure padrões
  • Assim como os jogadores humanos reconhecem boas jogadas
  • Isso torna o computador muito mais rápido

3. Banco de memória

  • Lembre-se de posições que já foram vistas antes
  • Não perca tempo calculando a mesma coisa duas vezes
  • É como ter uma folha de dicas de bons movimentos!

A parte mais legal? Esses aprimoramentos ajudam os computadores a jogar quase tão bem quanto os humanos, e às vezes até melhor! Mas lembre-se: mesmo com todas essas adições sofisticadas, o Minimax ainda é a base que faz tudo funcionar.

Conclusão

Neste tutorial, exploramos o algoritmo Minimax desde seus conceitos básicos até a implementação prática. Aqui está o que aprendemos:

1. Conceitos básicos

  • Como o Minimax ajuda os computadores a tomar decisões em jogos
  • A diferença entre minimizar e maximizar os jogadores
  • Por que ele é chamado de "minimax" e como funciona

2. Habilidades de implementação

  • Criando um jogo da velha do zero
  • Escrevendo o algoritmo Minimax em Python
  • Teste e depuração da lógica do jogo

3. Tópicos avançados

  • Tornando o algoritmo mais rápido com o Alpha-Beta Pruning
  • Lidar com limitações em jogos complexos
  • Aprimoramentos modernos usando aprendizado de máquina

O que vem a seguir?

O algoritmo Minimax é apenas uma peça do quebra-cabeça da IA. Se você está animado para saber mais sobre IA e algoritmos, aqui estão alguns recursos excelentes para continuar sua jornada:

1. Algoritmos relacionados

2. Aplicativos de aprendizado de máquina

3. Trilhas completas de aprendizado

Lembre-se de que, independentemente de você estar criando um jogo simples ou um sistema de IA complexo, a compreensão de algoritmos como o Minimax oferece a você uma base sólida para tópicos mais avançados em inteligência artificial. Continue praticando, continue aprendendo e, o mais importante, continue programando!

Perguntas frequentes sobre o algoritmo Minimax

Qual é o grau de dificuldade para você entender e implementar o algoritmo Minimax?

O algoritmo Minimax é relativamente simples de entender, especialmente quando implementado em jogos simples como o jogo da velha. Embora o conceito de recursão possa ser desafiador para iniciantes, o princípio básico de alternar entre movimentos de maximização e minimização é intuitivo. Este tutorial divide a implementação em etapas gerenciáveis, tornando-a acessível para programadores com conhecimento básico de Python.

Posso usar esse algoritmo para outros jogos além do jogo da velha?

Sim, o algoritmo Minimax pode ser adaptado para muitos jogos de soma zero para dois jogadores com informações perfeitas, como xadrez, damas ou Connect Four. No entanto, para jogos mais complexos, você precisará implementar otimizações adicionais, como poda Alfa-Beta e limitação de profundidade, pois o número de movimentos possíveis aumenta exponencialmente.

Como é que a IA nunca perde no jogo da velha?

O algoritmo Minimax funciona simulando todos os possíveis estados futuros do jogo e escolhendo movimentos que levem ao melhor resultado possível. Em um jogo simples como o jogo da velha, há relativamente poucas jogadas possíveis, o que permite que a IA calcule a jogada ideal em cada situação. Como o jogo da velha é um "jogo resolvido", o jogo perfeito de ambos os lados sempre leva a um empate, e é por isso que a IA nunca pode perder.

Que conhecimento prévio você precisa ter para seguir este tutorial?

Você deve ter conhecimentos básicos de programação em Python, incluindo:

Entendimento de funções e classes

Familiaridade com listas e estruturas básicas de dados

Fluxo de controle básico (instruções if, loops)

O conhecimento sobre recursão é útil, mas não é necessário, pois o tutorial explica o conceito.

Por que esse algoritmo é importante para o desenvolvimento da IA?

O algoritmo Minimax é fundamental para você entender a teoria dos jogos e a tomada de decisões em IA. Ele apresenta conceitos importantes, como busca recursiva em árvore, pensamento contraditório e tomada de decisão ideal com informações perfeitas. Esses princípios formam a base para algoritmos de IA mais avançados usados em aplicativos modernos, desde jogos até planejamento estratégico e sistemas de suporte a decisões.


Bex Tuychiev's photo
Author
Bex Tuychiev
LinkedIn

Sou um criador de conteúdo de ciência de dados com mais de 2 anos de experiência e um dos maiores seguidores no Medium. Gosto de escrever artigos detalhados sobre IA e ML com um estilo um pouco sarcástico, porque você precisa fazer algo para torná-los um pouco menos monótonos. Produzi mais de 130 artigos e um curso DataCamp, e estou preparando outro. Meu conteúdo foi visto por mais de 5 milhões de pessoas, das quais 20 mil se tornaram seguidores no Medium e no LinkedIn. 

Temas

Principais cursos de IA

programa

AI Fundamentals

10hrs hr
Discover the fundamentals of AI, dive into models like ChatGPT, and decode generative AI secrets to navigate the dynamic AI landscape.
Ver DetalhesRight Arrow
Iniciar curso
Ver maisRight Arrow
Relacionado

tutorial

Uma introdução ao Q-Learning: Um tutorial para iniciantes

Saiba mais sobre o algoritmo mais popular de aprendizado por reforço sem modelo com um tutorial em Python.
Abid Ali Awan's photo

Abid Ali Awan

16 min

tutorial

Tutorial do Adam Optimizer: Intuição e implementação em Python

Compreender e implementar o otimizador Adam em Python. Com o PyTorch, você aprenderá a intuição, a matemática e as aplicações práticas do machine learning
Bex Tuychiev's photo

Bex Tuychiev

14 min

tutorial

Pesquisa binária em Python: Um guia completo para uma pesquisa eficiente

Aprenda a implementar a pesquisa binária em Python usando abordagens iterativas e recursivas e explore o módulo bisect integrado para obter funções de pesquisa binária eficientes e pré-implementadas.
Amberle McKee's photo

Amberle McKee

12 min

tutorial

Otimização em Python: Técnicas, pacotes e práticas recomendadas

Este artigo ensina a você sobre otimização numérica, destacando diferentes técnicas. Ele discute os pacotes Python, como SciPy, CVXPY e Pyomo, e fornece um notebook DataLab prático para você executar exemplos de código.
Kurtis Pykes 's photo

Kurtis Pykes

19 min

tutorial

Criando agentes LangChain para automatizar tarefas em Python

Um tutorial abrangente sobre a criação de agentes LangChain com várias ferramentas para automatizar tarefas em Python usando LLMs e modelos de bate-papo usando OpenAI.
Bex Tuychiev's photo

Bex Tuychiev

14 min

tutorial

Tutorial da API de assistentes da OpenAI

Uma visão geral abrangente da API Assistants com nosso artigo, que oferece uma análise aprofundada de seus recursos, usos no setor, orientação de configuração e práticas recomendadas para maximizar seu potencial em vários aplicativos de negócios.
Zoumana Keita 's photo

Zoumana Keita

14 min

Ver maisVer mais