Menu

Jogo da Velha: entendendo o algorítimo Minimax

18 de maio de 2016 - algoritimo, FreeCodeCamp
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”.

 

 

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:

 

 

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

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:

 

 

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.

 

 

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

 

 

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:

 

 

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.

 

 

The following two tabs change content below.

Paulo Rodrigues

Software Architect / Software Engineer at Softplan
Passionate about technology, research and innovation. Interested in software development technologies such as Ruby on Rails, Python, AngularJS, RabbitMQ, microservices, SOA etc. Eager to learn and enthusiastic about topics ranging from computer science to machine learning and artificial intelligence .

Latest posts by Paulo Rodrigues (see all)

Deixe uma resposta

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

Clef two-factor authentication