Jogo da Velha: entendendo o algorítimo Minimax

Como mencionei no post Codepen.io, Rawgit, Cloudinary, eu participo do projeto #FreeCodeCamp, e lá um dos desafios front-end é construir um jogo chamado Tic Tac Toe, conhecido no Brasil como Jogo da Velha. Neste desafio em particular, o difícil não é construir a GUI, mas sim construir a inteligência do jogo.

Pesquisando como eu poderia fazer isso, me deparei com um ótimo artigo do Jason Fox, no neverstopbuilding.comTic Tac Toe: Understanding The Minimax Algorithm. Em conversa com ele, fui autorizado a fazer a tradução deste artigo. E explicação dele é muito boa e espero que gostem. Os exemplos são em ruby, mas ao final do artigo irei deixar meu github  com a transcrição que fiz para javascript

 

Tic Tac Toe: Understanding The Minimax Algorithm

 

First published on December 13, 2013, by Jason Fox on http://neverstopbuilding.com/minimax

Eu recentemente construí um jogo da velha imbatível. Ele foi um projeto muito engraçado e humilhante no qual eu aprendi uma tonelada de coisas. Se você quer ficar totalmente escolado nesse assunto, dê uma olhada aqui 

A fim de fazer o jogo imbatível, foi necessário criar um algorítimo que pudesse calcular todas os possíveis movimentos disponíveis e usar alguma métrica para determinar o melhor movimento possível. Depois de uma pesquisa extensiva ficou claro que o algorítimo correto para esse trabalho seria o algorítimo Minimax.

Demorou um pouco para eu entender como o algorítimo funciona e conseguir implementá-lo no meu jogo. Eu encontrei muitos exemplos de código e explicações, mas nenhum que examinasse de forma simples os detalhes do processo, como eu fiz aqui. Eu espero que este post te ajude de alguma maneira a apreciar a elegância deste algorítimo.

 

Descrevendo o Jogo da Velha perfeito

 

Para começar, vamos iniciar definindo o que significa jogar de forma perfeita o jogo da velha:

Se eu jogar perfeitamente, então todas as vezes que eu jogar eu irei ganhar o jogo, ou ao menos empatar. Além disso se eu jogar contra um oponente perfeito, eu sempre vou empatar o jogo.

Como podemos descrever estas situações de forma quantitativa? Vamos atribuir uma pontuação para as condições de “fim de jogo”.

 

  • Eu ganhei, uhull! Eu ganho 10 pontos.
  • Eu perdi, droga. Eu perco 10 pontos (porque o outro jogador ganha 10 pontos)
  • Eu empatei, tanto faz. Eu ganho zero pontos, ninguém ganha nada.

 

Então agora temos uma situação onde podemos determinar uma possível pontuação para qualquer estado de fim de jogo.

 

Olhando para um breve exemplo:

 

Para aplicar isto, vamos pegar um exemplo parecido com um estado de fim de jogo, onde está na minha vez de jogar. Eu sou o “X”. Meu objetivo aqui, obviamente, é maximizar minha pontuação.

A contrived end state for a tic tac toe game.

Se a primeira imagem representa o estado do jogo na minha vez de jogar, então eu tenho algumas escolhas que posso fazer, á 3 lugares que eu posso jogar, um deles resulta claramente em vitória e eu ganhando os 10 pontos. Se eu não fizer este movimento, o jogador “O” poderá facilmente ganhar. E eu não quero deixar o jogador “O” ganhar, então meu objetivo aqui, como primeiro jogador, deve ser de escolher o movimento que resulte em pontuação máxima.

 

Mas e sobre o jogador “O” ?

 

O que nós sabemos sobre o jogador “O”? Bem, nós poderíamos assumir que “O” também está jogando para ganhar o jogo, mas comparado a nós, que somos o primeiro jogador, “O” obviamente irá escolher um movimento que resulte na pior pontuação para nós, ele irá escolher um movimento que minimize nossa pontuação final. Vamos olhar as coisas do ponto de vista do jogador “O”, iniciando com dois outros estados de jogo atrás daquele em que ganharíamos imediatamente.

 

A move tree from the perspective of the other player, O

A escolha está clara, “O” poderia optar por qualquer um dos movimentos que resultam em uma pontuação de -10.

 

Descrevendo o Minimax

 

A chave para o algorítimo Minimax é uma troca de lugares entre os dois jogadores, onde o jogador da vez deseja o movimento que resulte no maior pontuação. Por sua vez, a pontuação para cada um dos movimentos disponíveis é determinada pelo jogador oponente quando ele escolhe dentre os movimentos disponíveis, aquele que lhe darão a pontuação mínima. E novamente, a pontuação mínima é decidida pelos movimentos do outro jogador tentando maximizar a pontuação, e essa troca acontece até chegar a um estado de fim de jogo.

Uma descrição para o algorítimo, assumindo que “X” é o jogador da vez, seria algo como isto:

 

  • Se o jogo acabou, retorne a pontuação da perspectiva de “X”
  • Do contrário, obtenha uma lista de novos estados de jogo para todos os possíveis movimentos.
  • Cria uma lista de pontuação
  • Para cada um desses estados, adicione o resultado minimax que resulta a lista de pontuação
  • Se for a vez de “X” jogar, retorne a maior pontuação da lista de resultados
  • Se for a vez de “O” jogar, retorne a menor pontuação da lista de resultados

 

Você vai notar que este algorítimo é recursivo, ele alterna entre as trocas de jogadores até encontrar a pontuação final.

Vamos examinar o a execução deste algorítimo com toda a árvore de movimentos, e mostrar porque, algoritmicamente, o movimento vencedor instantâneo será escolhido:

Full minimax move tree

  • É a vez do jogador “X” no estado 1. “X” gera os estados 2, 3 e 4 e chama o minimax nesses estados.
  • O estado 2, insere a pontuação de +10 na lista de pontuação do estado 1, porque o jogo chega a um estado final.
  • O estado 3 e 4 não são estados de fim de jogo, o estado 3 gera dois novos estados, 5 e 6 e chama o minimax para eles, enquanto o estado 4 gera o estado 7 e 8 e chama o minimax para eles.
  • O estado 5 insere a pontuação de -10 na lista de pontuação do estado 3, enquanto o mesmo acontece para o estado 7 que insere a pontuação de -10 na lista de pontuação do estado 4.
  • Os estados 6 e 8 geram os únicos movimentos disponíveis, que são estados de fim de jogo, ambos adicionam a pontuação de +10 a lista de movimento dos estados 3 e 4.
  • Por ser a vez do jogador “O” nos estados 3 e 4, “O” irá procurar a pontuação miníma, e entre as opções -10 e +10, ambos os estados 3 e 4 ficarão com -10.
  • Finalmente a lista de pontuação para os estados 2, 3 e 4 são populadas com +10, -10 e -10 respectivamente, e o estado 1 buscando movimento que lhe dará a vitória, irá buscar pela pontuação máxima, que nesse caso está no estado 2 (+10).

Certamente a muita coisa pra ser fazer. E é por isso que nós temos um computador para executar esse algorítimo.

 

A versão codificada do Minimax

 

Espero que neste ponto você já tenha uma ideia aproximada de como o minimax determina a melhor jogada. Então vamos examinar minha implementação do algorítimo para solidificar este entendimento.

Aqui está a função para determinar a pontuação do jogo:

 

# @player is the turn taking player
def score(game)
    if game.win?(@player)
        return 10
    elsif game.win?(@opponent)
        return -10
    else
        return 0
    end
end

 

Bem simples, retorna +10 se o jogador corrente vence o jogo, e -10 se oponente vence o jogo ou zero para empate. Você notará que quem é o jogador não importa. “X” ou “O” é irrelevante, somente o jogador da vez importa saber.

E agora o algorítimo minimax; note que nessa implementação a escolha ou movimento é simplesmente as coordenadas (linha e coluna) na mesa de jogo, por exemplo, [0, 2] é o quadrado direito no topo numa mesa  de 3 linhas por 3 colunas.

 

def minimax(game)
    return score(game) if game.over?
    scores = [] # an array of scores
    moves = []  # an array of moves

    # Populate the scores array, recursing as needed
    game.get_available_moves.each do |move|
        possible_game = game.get_new_state(move)
        scores.push minimax(possible_game)
        moves.push move
    end

    # Do the min or the max calculation
    if game.active_turn == @player
        # This is the max calculation
        max_score_index = scores.each_with_index.max[1]
        @choice = moves[max_score_index]
        return scores[max_score_index]
    else
        # This is the min calculation
        min_score_index = scores.each_with_index.min[1]
        @choice = moves[min_score_index]
        return scores[min_score_index]
    end
end

 

Quando o algorítimo roda dentro da classe PerfectPlayer, a última escolher do melhor movimento é armazenada na variável @choice, que é então é usada para retornar um novo estado de jogo onde o jogador corrente fez o movimento.

 

Um perfeito mas fatalista jogador

 

Implementar o algorítimo acima irá te levar a um ponto onde seu jogo da velha não poderá ser abatido. Mas uma nuance interessante que descobri enquanto testava é que um jogador perfeito deve sempre ser perfeito. Em outras palavras, em situações onde um jogador perfeito poderá perder ou empatar, as decisões sobre o próximo movimento são bastante fatalistas. Neste caso, o algorítimo diz essencialmente que: “Hey, eu irei perder de qualquer maneira, então realmente não me importa se eu perder na próxima jogada ou nos próximos 6 movimentos”.

Eu descobri isso ao passar dados manipulados para o algorítimo, ou com “enganos” e pedir a ele que me retornasse a melhor jogada seguinte. Eu espera que o “jogador perfeito” me fizesse ter um jogo mais difícil e bloqueasse a minha vitória imediata, mas ele não fez isso.

 

A perfect player commits seppuku.

 

Vamos ver o que acontece aqui olhando através da árvore de movimentos possíveis (aviso, eu removi alguns movimentos possíveis para clarificar o exemplo):

A move tree where X always wins.

  • Dado o estado 1 onde ambos os jogadores são jogadores perfeitos, e “O” é o computador. “O” escolhe o movimento no estado 5 e imediatamente perde quando “X” ganha no estado 9.
  • Mas se “O” bloquear a vitória de “X” no estado 3, “X” irá obviamente bloquear uma vitória potencial de “O” no estado 7.
  • Isso nos dará pelo menos duas possibilidades de vitórias de “X”, como visto nos estados 10 e 11.

 

Como resultado destes cenários, e pelo fato que estamos interagindo através de cada espaço em branco, da esquerda para direita e de cima para baixo, todos os movimentos são iguais, isso é, resultando na derrota de “O”, o último movimento será escolhido como visto no estado 5  e como último movimento disponível no cenário 1.

Então o que diabos, faria um mestre do jogo-da-velha?

 

Lutando uma boa luta: Profundidade

A chave para melhorar esse algorítimo, de tal modo que, não importe o arranjo do jogo, já que o jogador perfeito sempre jogará de forma perfeita até a morte, é levar em conta o numero de jogadas disponíveis para o fim de jogo. Basicamente o jogador perfeito deve jogar perfeitamente, mas também prolongar o jogo o máximo possível.

Afim de conseguir isso, iremos subtrair a profundidade, que é o numero de jogadas, do resultado final do jogo. Quanto mais jogadas melhor a pontuação. Atualizando nosso código, teremos algo que se parece com isso:

 

def score(game, depth)
    if game.win?(@player)
        return 10 - depth
    elsif game.win?(@opponent)
        return depth - 10
    else
        return 0
    end
end

def minimax(game, depth)
    return score(game) if game.over?
    depth += 1
    scores = [] # an array of scores
    moves = []  # an array of moves

    # Populate the scores array, recursing as needed
    game.get_available_moves.each do |move|
        possible_game = game.get_new_state(move)
        scores.push minimax(possible_game, depth)
        moves.push move
    end

    # Do the min or the max calculation
    if game.active_turn == @player
        # This is the max calculation
        max_score_index = scores.each_with_index.max[1]
        @choice = moves[max_score_index]
        return scores[max_score_index]
    else
        # This is the min calculation
        min_score_index = scores.each_with_index.min[1]
        @choice = moves[min_score_index]
        return scores[min_score_index]
    end
end

 

Então cada vez que invocarmos o minimax, a profundidade é subtraída em 1 unidade, e quando chegamos ao final do jogo e a pontuação é ajustada pela profundidade. Vamos ver como isso se parece na árvore de movimentos:

End states taking depth into account.

Desta vez, a profundidade (mostrado em preto a esquerda) faz com que a pontuação mude para cada estado de fim de jogo, e porque o nível 0 parte do minimax que irá tentar maximizar a pontuação disponível, a pontuação de -6 será escolhida por ser a maior dentre os possíveis estados de fim de jogo (-8 seriam as outras). E mesmo diante de uma morte certa,  o nosso jogador perfeito agora irá escolher um movimento de bloqueio, ao invés de morrer com honra 🙂

 

Concluindo

 

Eu espero que toda essa discussão tenha ajudado você a compreender o algorítimo minimax, e talvez, como dominar o jogo da velha. Se você tiver dúvidas ou achou algo confuso, deixe um comentário e eu tentarei melhorar o artigo. Todo o meu código para o jogo da velha pode ser encontrado no github.

 

Notas do tradutor:

Como dito pelo Jason, espero que esta tradução tenha ajudado você a entender um pouco mais sobre o algorítimo minimax. Se você encontrar algum erro de tradução ou tiver dúvidas quanto ao algorítimo, por favor deixe um comentário.

Deixo aqui também meu github com o código em javascript, o mesmo projeto que utilizei para o FreeCodeCamp.

 

 

0 comments on “Jogo da Velha: entendendo o algorítimo MinimaxAdd yours →

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *