Observação! Este artigo também foi traduzido parajaponês,Português, erusso. Eu realmente aprecio os leitores que me procuraram e traduziram este artigo.
Recentemente, construí um jogo imbatível de jogo da velha. Foi um projeto divertido e muito humilhante que me ensinou muito. Se você quiser estudar totalmente, dê ojogo da velha, uma chance aqui.
Para tornar o jogo imbatível, foi necessário criar um algoritmo que pudesse calcular todos os movimentos possíveis disponíveis para o jogador do computador e usar alguma métrica para determinar o melhor movimento possível. Após extensa pesquisa, ficou claro que oMinimáximoalgoritmo era adequado para o trabalho.
Demorou um pouco para entender realmente o algoritmo e implementá-lo em meu jogo. Encontrei muitos exemplos de código e explicações, mas nenhum que realmente orientasse um simplório como eu nos meandros do processo. Espero que este post ajude alguns de vocês a apreciar a elegância desse algoritmo.
Descrevendo um jogo perfeito de Tic Tac Toe
Para começar, vamos começar definindo o que significa jogar um jogo da velha perfeito:
Se eu jogar perfeitamente, toda vez que jogar, ou ganharei o jogo ou empatarei. Além disso, se eu jogar contra outro jogador perfeito, sempre empatarei.
Como poderíamos descrever essas situações quantitativamente? Vamos atribuir uma pontuação às "condições finais do jogo:"
- Eu ganhei, viva! Eu ganho 10 pontos!
- Eu perco, merda. Perco 10 pontos (porque o outro jogador ganha 10 pontos)
- Eu desenho, tanto faz. Eu ganho zero pontos, ninguém ganha nenhum ponto.
Portanto, agora temos uma situação em que podemos determinar uma pontuação possível para qualquer estado final do jogo.
Olhando para um breve exemplo
Para aplicar isso, vamos dar um exemplo perto do final de um jogo, onde é a minha vez. Eu sou X. Meu objetivo aqui, obviamente, émaximizarminha pontuação final do jogo.
Se o topo desta imagem representa o estado do jogo que vejo quando chega a minha vez, então tenho algumas escolhas a fazer, há três locais onde posso jogar, um dos quais resulta claramente na minha vitória e na conquista dos 10 pontos. Se eu não fizer esse movimento, O poderia facilmente vencer. E eu não quero que O vença, então meu objetivo aqui, como primeiro jogador, deveria ser escolher o lance de pontuação máxima.
Mas e quanto a O?
O que sabemos sobre O? Bem, devemos assumir que O também está jogando para ganhar este jogo, mas em relação a nós, o primeiro jogador, O quer, obviamente, quer escolher o lance que resulta na pior pontuação para nós, ele quer escolher um lance que iriaminimizarnossa pontuação final. Vejamos as coisas da perspectiva de O, começando com os outros dois estados do jogo acima, nos quais não vencemos imediatamente:
A escolha é clara, O escolheria qualquer um dos movimentos que resultasse em uma pontuação de -10.
Descrevendo Minimax
A chave para o algoritmo Minimax é um vaivém entre os dois jogadores, onde o jogador cuja "vez é" deseja escolher a jogada com a pontuação máxima. Por sua vez, as pontuações para cada uma das jogadas disponíveis são determinadas pelo jogador adversário que decide qual das jogadas disponíveis tem a pontuação mínima. E as pontuações para os movimentos dos jogadores adversários são novamente determinadas pelo jogador que joga a vez, tentando maximizar sua pontuação e assim por diante, até um estado final na árvore de movimentos.
Uma descrição para o algoritmo, assumindo que X é o "jogador que toma a vez", seria algo como:
- Se o jogo terminar, retorne a pontuação da perspectiva de X.
- Caso contrário, obtenha uma lista de novos estados do jogo para cada movimento possível
- Crie uma lista de pontuações
- Para cada um desses estados, adicione o resultado minimax desse estado à lista de pontuações
- Se for a vez de X, retorne a pontuação máxima da lista de pontuações
- Se for a vez de O, retorne a pontuação mínima da lista de pontuações
Você notará que esse algoritmo é recursivo, ele alterna entre os jogadores até que uma pontuação final seja encontrada.
Vamos percorrer a execução do algoritmo com a árvore de movimentos completa e mostrar por que, algoritmicamente, o movimento vencedor instantâneo será escolhido:
- É a vez de X no estado 1. X gera os estados 2, 3 e 4 e chama minimax nesses estados.
- O estado 2 empurra a pontuação de +10 para a lista de pontuação do estado 1, porque o jogo está no estado final.
- Os estados 3 e 4 não estão nos estados finais, então 3 gera os estados 5 e 6 e chama minimax neles, enquanto o estado 4 gera os estados 7 e 8 e chama minimax neles.
- O estado 5 coloca uma pontuação de -10 na lista de pontuação do estado 3, enquanto o mesmo acontece para o estado 7, que coloca uma 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 finais, e assim ambos adicionam a pontuação de +10 às listas de movimentos dos estados 3 e 4.
- Como é a vez de O nos estados 3 e 4, O procurará encontrar a pontuação mínima e, dada a escolha entre -10 e +10, ambos os estados 3 e 4 produzirão -10.
- Finalmente, a lista de pontuação para os estados 2, 3 e 4 é preenchida com +10, -10 e -10 respectivamente, e o estado 1 que busca maximizar a pontuação escolherá o movimento vencedor com pontuação +10, estado 2.
Isso certamente é muito para absorver. E é por isso que temos um computador executando esse algoritmo.
##Uma versão codificada do Minimax Esperamos que agora você tenha uma noção aproximada de como o algoritmo minimax determina o melhor movimento a ser jogado. Vamos examinar minha implementação do algoritmo para solidificar o entendimento:
Aqui está a função para pontuar o jogo:
# @player é a vez de jogar playerdef score(game) if game.win?(@player) return 10 elsif game.win?(@opponent) return -10 else return 0 endendBastante simples, retorne +10 se o jogador atual vencer o jogo, -10 se o outro jogador vencer e 0 em caso de empate. Você notará queQuemo jogador não importa. X ou O é irrelevante, apenas quem é a vez.
E agora o algoritmo minimax real; observe que nesta implementação umescolhaoumoveré simplesmente um endereço de linha/coluna no tabuleiro, por exemplo [0,2] é o quadrado superior direito em um tabuleiro 3x3.
def minimax(jogo) retornar pontuação(jogo) se game.over? pontuações = [] # uma matriz de pontuações moves = [] # uma matriz de movimentos # Preencher a matriz de pontuações, recorrendo conforme necessário game.get_available_moves.each do |move| Possible_game = game.get_new_state(move) pontuações.push minimax(possible_game) moves.push move end # Faça o cálculo mínimo ou máximo if game.active_turn == @player # Este é o cálculo máximo max_score_index = pontuações.each_with_index.max[ 1] @choice = moves[max_score_index] return score[max_score_index] else # Este é o cálculo mínimo min_score_index = score.each_with_index.min[1] @choice = moves[min_score_index] return score[min_score_index] endendQuando este algoritmo é executado dentro de umJogador Perfeitoclasse, a escolha final do melhor movimento é armazenada no@escolhavariável, que é então usada para retornar o novo estado do jogo em que o jogador atual se moveu.
##Um jogador perfeito, mas fatalista A implementação do algoritmo acima levará você a um ponto em que seu jogo da velha não pode ser vencido. Mas uma nuance interessante que descobri durante os testes é que um jogador perfeito deve ser sempre perfeito. Por outras palavras, numa situação em que o jogador perfeito acabará por perder ou empatar, as decisões sobre a próxima jogada são bastante fatalistas. O algoritmo diz essencialmente: "ei, vou perder de qualquer maneira, então realmente não importa se eu perderei nos próximos ou em 6 movimentos a partir de agora."
Eu descobri isso passando uma placa obviamente manipulada, ou uma com um "erro" para o algoritmo e pedindo a próxima melhor jogada. Eu esperava que o jogador perfeito pelo menos resistisse e bloqueasse minha vitória imediata. No entanto, não:
Vamos ver o que está acontecendo aqui examinando a árvore de movimentos possíveis (observe que removi alguns dos estados possíveis para maior clareza):
- Dado o estado do tabuleiro 1, onde ambos os jogadores estão jogando perfeitamente, e O é o jogador do computador. O escolhe o movimento no estado 5 e perde imediatamente quando X vence no estado 9.
- Mas se O bloquear a vitória de X como no estado 3, X obviamente bloqueará a vitória potencial de O como mostrado no estado 7.
- Isso coloca duas vitórias certas para X, conforme mostrado nos estados 10 e 11, portanto, não importa qual movimento O escolha no estado 7, X acabará vencendo.
Como resultado desses cenários, e do fato de estarmos iterando em cada espaço em branco, da esquerda para a direita, de cima para baixo, sendo todos os movimentos iguais, ou seja, resultando em uma perda para O, o último movimento será escolhido como mostrado no estado 5, pois é o último dos movimentos disponíveis no estado 1. A matriz de movimentos é: [superior esquerdo, superior direito, meio-esquerdo, meio-centro].
O que um maldito mestre do jogo da velha deve fazer?
Combatendo o Bom Combate: Profundidade
A principal melhoria deste algoritmo, de modo que, independentemente da disposição do tabuleiro, o jogador perfeito jogará perfeitamente até o seu fim, é levar em consideração a "profundidade" ou o número de turnos até o final do jogo. Basicamente o jogador perfeito deve jogar perfeitamente, mas prolongar o jogo tanto quanto possível.
Para conseguir isso subtrairemos a profundidade, ou seja, o número de turnos, ou recursões, da pontuação final do jogo, quanto mais turnos menor será a pontuação, quanto menos turnos maior será a pontuação. Atualizando nosso código acima, temos algo parecido com isto:
def pontuação(jogo, profundidade) if game.win?(@player) return 10 - profundidade elsif game.win?(@oponente) return profundidade - 10 else return 0 endenddef minimax(jogo, profundidade) return score(game) if game .sobre? profundidade += 1 pontuações = [] # uma matriz de pontuações moves = [] # uma matriz de movimentos # Preencher a matriz de pontuações, recorrendo conforme necessário game.get_available_moves.each do |move| Possible_game = game.get_new_state(move) pontuações.push minimax(possible_game, profundidade) moves.push move end # Faça o cálculo mínimo ou máximo se game.active_turn == @player # Este é o cálculo máximo max_score_index = pontuações.each_with_index. max[1] @choice = moves[max_score_index] return score[max_score_index] else # Este é o cálculo mínimo min_score_index = score.each_with_index.min[1] @choice = moves[min_score_index] return score[min_score_index] endendPortanto, cada vez que invocamos o minimax, a profundidade é incrementada em 1 e quando o estado final do jogo é finalmente calculado, a pontuação é ajustada pela profundidade. Vamos ver como isso fica em nossa árvore de movimentos:
Desta vez, a profundidade (mostrada em preto à esquerda) faz com que a pontuação seja diferente para cada estado final, e como a parte do nível 0 do minimax tentará maximizar as pontuações disponíveis (porque O é o jogador que toma a vez), o -6 a pontuação será escolhida por ser maior que a dos demais estados com pontuação -8. E assim, mesmo diante da morte certa, nosso jogador confiável e perfeito agora escolherá o movimento de bloqueio, em vez de cometer morte por honra.
Para concluir
Espero que toda essa discussão tenha ajudado você a entender melhor o algoritmo minimax e talvez como dominar um jogo da velha. Se você tiver mais dúvidas ou algo estiver confuso, deixe alguns comentários e tentarei melhorar o artigo. Todo o código-fonte parameu jogo da velhapode serencontrado no github.
