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:
- 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.
- 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ó.
- 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
Histograma -Distribuição Fitness x Partículas- (Iteração: 0)
Distribuição das partículas no espaço de busca (Iteração: 0)
Histograma - Distribuição de Fitness das partículas (Iteração: 10000) 
Distribuição das posições das partículas na região de busca (Iteração: 10000)
![PythonBrasil[9]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_u_6gvMftUsloD4_VnlOd-UumWX1RDjM4wQzOj6OoOk85pJiCbFVDVnm9fMd8LWsGeL5BTCJIHod2whTo6JLt_bDuOh2D-zrN0m_e2OQhJnqa9_P8m13TT8bwhbn1iQZ0tclWQfqRm8KFYyyj5F0094jBl_DgvDww=s0-d)
Posts
