Inteligência Artificial de Jogo de Tabuleiro: o Algoritmo Minimax: 8 Passos

2024 Autor: John Day | [email protected]. Última modificação: 2024-01-30 11:37

Você já se perguntou como são feitos os computadores contra os quais você joga xadrez ou damas? Bem, não procure mais, pois este Instructable para ele mostrará como fazer uma inteligência artificial (IA) simples, mas eficaz, usando o algoritmo Minimax! Usando o Algoritmo Minimax, a IA faz movimentos bem planejados e pensados (ou pelo menos imita um processo de pensamento). Agora, eu poderia simplesmente fornecer o código para a IA que eu fiz, mas isso não seria divertido. Vou explicar a lógica por trás das escolhas do computador.

Neste Instructable, irei guiá-lo através das etapas sobre como fazer uma IA para Othello (também conhecido como Reversi) em python. Você deve ter um entendimento intermediário de como codificar em python antes de abordar este projeto. Aqui estão alguns bons sites para se preparar para este Instructable: w3schools ou learnpython. No final deste Instructable, você deve ter uma IA que fará movimentos calculados e será capaz de derrotar a maioria dos humanos.

Como este Instructable tratará principalmente de como fazer uma IA, não explicarei como projetar um jogo em python. Em vez disso, darei o código para o jogo em que um humano pode jogar contra outro humano e modificá-lo para que você possa jogar um jogo em que um humano joga contra a IA.

Aprendi como criar essa IA por meio de um programa de verão no Columbia SHAPE. Eu me diverti lá, então dê uma olhada no site deles para ver se você estaria interessado.

Agora que tiramos a logística do caminho, vamos começar a programar!

(Eu coloquei algumas notas nas imagens, então certifique-se de olhar para elas)

Suprimentos

Isso é facil:

1) Computador com um ambiente python, como Spyder ou IDLE

2) Baixe os arquivos do jogo Othello do meu GitHub

3) Seu cérebro com paciência instalada

Etapa 1: Baixe os arquivos necessários

Ao entrar no GitHub, você verá 5 arquivos. Baixe todos os 5 e coloque-os todos na mesma pasta. Antes de executar o jogo, abra todos os arquivos no ambiente spyder.

Aqui está o que os arquivos fazem:

1) othello_gui.py este arquivo cria o tabuleiro do jogo para os jogadores jogarem (seja humano ou computador)

2) othello_game.py este arquivo joga dois computadores um contra o outro sem o tabuleiro e mostra apenas a pontuação e as posições de movimento

3) ai_template.py aqui é onde você colocará todo o seu código para fazer a sua IA

4) randy_ai.py esta é uma IA pré-fabricada que escolhe seus movimentos aleatoriamente

5) othello_shared.py um monte de funções predefinidas que você pode usar para fazer sua IA, como verificar se há movimentos disponíveis, a pontuação ou o estado do tabuleiro

6) Os três outros arquivos: Puma.py, erika_5.py e nathan.py, feitos por mim, Erika e Nathan, respectivamente, do programa SHAPE, são três AIs diferentes com códigos exclusivos

Etapa 2: como abrir e jogar Python Othello

Depois de abrir todos os arquivos, no canto inferior direito da tela, digite "run othello_gui.py" e pressione Enter no Console IPython. Ou no terminal Mac, digite "python othello_gui.py" (depois de estar na pasta certa, é claro). Em seguida, uma placa deve aparecer na tela. Este modo é o modo humano vs humano. A luz vai em segundo lugar e a escuridão primeiro. Olhe meu vídeo se você está confuso. iNo topo, há a pontuação de cada ladrilho de cor. Para jogar, clique em um espaço de movimento válido para colocar uma peça ali e, em seguida, dê o computador ao seu oponente, que fará o mesmo e repetirá.

Se você não sabe como jogar Othello, leia estas regras no site dos ultra boards:

As pretas sempre se movem primeiro. Um movimento é feito colocando um disco da cor do jogador no tabuleiro em uma posição que "flanqueie" um ou mais discos do oponente. Um disco ou fila de discos é flanqueado quando é rodeado nas extremidades por discos da cor oposta. Um disco pode flanquear qualquer número de discos em uma ou mais fileiras em qualquer direção (horizontal, vertical, diagonal)…. (termine de ler em seu site)

A diferença entre o jogo original e este jogo python é que quando não há mais movimentos válidos para um jogador, o jogo termina

Agora que você pode jogar com um amigo, vamos fazer uma IA com a qual você possa jogar.

Etapa 3: Algoritmo Minimax: Gerando cenários

Antes de falar sobre como escrever isso em código, vamos examinar a lógica por trás disso. O algoritmo minimax é um algoritmo de back-tracking para tomada de decisão e é normalmente usado em jogos de dois jogadores baseados em turnos. O objetivo desta IA é encontrar o próximo melhor movimento e os seguintes melhores movimentos até vencer o jogo.

Agora, como o algoritmo determinaria qual movimento é o melhor? Pare e pense em como você escolheria o próximo movimento. A maioria das pessoas escolheria o movimento que lhes daria mais pontos, certo? Ou, se estivessem pensando no futuro, escolheriam a jogada que configuraria uma situação em que poderiam ganhar ainda mais pontos. A última maneira de pensar é a maneira como o Algoritmo Minimax pensa. Ele antecipa todas as futuras configurações do tabuleiro e faz o movimento que levaria à maioria dos pontos.

Eu chamei isso de algoritmo de retrocesso, porque ele começa primeiro criando e avaliando todos os estados futuros da placa com seus valores associados. Isso significa que o algoritmo jogará o jogo o quanto for necessário (fazendo os movimentos para si mesmo e para o oponente) até que todos os cenários do jogo tenham sido jogados. Para acompanhar todos os estados do tabuleiro (cenários), podemos desenhar uma árvore (veja nas fotos). A árvore na imagem acima é um exemplo simples de um jogo do Connect 4. Cada configuração do tabuleiro é chamada de estado do tabuleiro e seu lugar na árvore é chamado de nó. Todos os nós na parte inferior da árvore são os estados finais do tabuleiro depois de fazer todos os movimentos. Obviamente, alguns estados do tabuleiro são melhores para um jogador do que para o outro. Então, agora temos que fazer a IA escolher para qual estado da placa ela deseja chegar.

Etapa 4: Minimax: Avaliação das configurações da placa

Para dar valores aos estados do tabuleiro, temos que aprender as estratégias do jogo que estamos jogando: neste caso, as estratégias de Othello. Como este jogo é uma batalha de inverter os discos do adversário e seus, as melhores posições de disco são aquelas que são estáveis e não podem ser invertidas. O canto, por exemplo, é o local onde, quando um disco é colocado, não pode ser alterado para a outra cor. Portanto, aquele local seria extremamente valioso. Outras boas posições incluem as laterais do tabuleiro, que permitiriam que você pegasse muitas pedras. Existem mais estratégias neste site.

Agora podemos atribuir valores às posições de cada conselho estadual do conselho. Quando uma posição é ocupada pela peça do AI, então você dá um certo número de pontos dependendo da posição. Por exemplo, em um tabuleiro onde a peça do AI está no canto, você pode dar um bônus de 50 pontos, mas se estiver em um local desfavorável, a peça pode ter o valor 0. Depois de levar em consideração todos os valores de as posições, você atribui um valor ao estado do conselho. Por exemplo, se o IA tem uma peça no canto, o estado do tabuleiro pode ter uma pontuação de 50, enquanto outro estado do tabuleiro com a peça do IA no meio tem uma pontuação de 10.

Há muitas maneiras de fazer isso e tenho três heurísticas diferentes para avaliar as peças do tabuleiro. Eu o encorajo a fazer seu próprio tipo de heurística. Eu carreguei três AIs diferentes em meu github por três fabricantes diferentes, com três heurísticas diferentes: Puma.py, erika5.py, nathanh.py.

Etapa 5: Algoritmo Minimax: escolhendo a melhor jogada

Agora seria bom se a IA pudesse apenas escolher todos os movimentos para chegar ao estado do tabuleiro com a pontuação mais alta. Mas lembre-se que a IA também estava escolhendo os movimentos do oponente quando estava gerando todos os estados do tabuleiro e se o oponente for inteligente, não permitirá que a IA alcance a pontuação mais alta do tabuleiro. Em vez disso, um oponente inteligente faria o movimento para fazer a IA ir para o estado mais baixo do tabuleiro. No algoritmo, chamamos os dois jogadores de jogador maximizador e jogador minimizador. O AI seria o jogador que maximiza, uma vez que deseja obter o máximo de pontos para si mesmo. O oponente seria o jogador que minimiza, já que o oponente está tentando fazer o movimento onde a IA obtém menos pontos.

Uma vez que todos os estados do cartão são gerados e os valores atribuídos aos cartões, o algoritmo começa a comparar os estados do cartão. Nas fotos, criei uma árvore para representar como o algoritmo escolheria seus movimentos. Cada divisão nos ramos é um movimento diferente que a IA ou o oponente pode jogar. À esquerda das linhas de nós, escrevi se o reprodutor de maximização ou minimização está indo. A linha inferior contém todos os estados do tabuleiro com seus valores. Dentro de cada um desses nós há um número e essas são as pontuações que atribuímos a cada uma das placas: quanto mais altas, melhor é para a IA ter.

Definições: nó pai - um nó que resulta ou cria nós abaixo dele; a origem dos nós filhos - os nós que vêm do mesmo nó pai

Os nós vazios representam qual movimento a IA fará para chegar ao melhor estado do tabuleiro. Ele começa comparando os filhos do nó mais à esquerda: 10, -3, 5. Uma vez que o jogador que maximiza faria o movimento, ele escolheria o movimento que lhe daria mais pontos: 10. Então, nós então selecionamos e armazenamos isso mova com a pontuação do tabuleiro e escreva-o no nó pai. Agora que 10 está no nó pai, agora é a vez dos jogadores minimizadores. No entanto, o nó ao qual compararíamos 10 está vazio, então temos que avaliar esse nó primeiro antes que o jogador minimizador possa escolher. Portanto, voltamos à vez do jogador de maximização e comparamos os filhos do nó adjacente: 8, -2. A maximização escolherá 8 e escreveremos isso no nó pai vazio. Agora que o algoritmo terminou de preencher os espaços vazios para os filhos de um nó acima dele, o jogador de minimização pode comparar esses filhos - 10 e 8 e escolher 8. O algoritmo então repete esse processo até que toda a árvore seja preenchida. No final deste exemplo, temos a pontuação 8. Esse é o estado do tabuleiro mais alto que a IA pode jogar, assumindo que o oponente está jogando de forma ideal. Assim, a IA escolherá o primeiro movimento que leva ao estado 8 do tabuleiro e, se o oponente jogar de forma otimizada, a IA deve fazer todos os movimentos para chegar ao estado 8 do tabuleiro. (Siga as notas nas minhas fotos)

Eu sei que foi muito. Se você é do tipo que precisa que alguém converse com você para entender algo, aqui estão alguns vídeos que assisti para me ajudar a entender a ideia por trás disso: 1, 2, 3.

Etapa 6: Algoritmo Minimax: Pseudocódigo

Depois de entender a lógica por trás do algoritmo minimax, dê uma olhada neste pseudocódigo (as funções que são universais para todos os códigos) da Wikipedia:

função minimax (nó, profundidade, maximizingPlayer) é

se a profundidade = 0 ou o nó for um nó terminal, então

retornar o valor heurístico do nó

se maximizingPlayer então

valor: = −∞

para cada filho do nó faça

valor: = max (valor, minimax (filho, profundidade - 1, FALSO))

valor de retorno

else (* minimizando o jogador *)

valor: = + ∞

para cada filho do nó faça

valor: = min (valor, minimax (filho, profundidade - 1, VERDADEIRO))

valor de retorno

Esta é uma função recursiva, o que significa que ela chama a si mesma continuamente até chegar a um ponto de parada. Primeiro, a função assume três valores, o nó, profundidade e de quem é a vez. O valor do nó é o local onde você deseja que o programa comece a pesquisar. A profundidade é a distância que você deseja que o programa pesquise. Por exemplo, no meu exemplo de árvore, ele tem uma profundidade de 3, porque pesquisou todos os estados do tabuleiro após 3 movimentos. Claro, gostaríamos que a IA verificasse cada estado do tabuleiro e escolhesse uma vitória vencedora, mas na maioria dos jogos onde existem milhares, senão milhões de configurações de tabuleiro, seu laptop em casa não será capaz de processar todas essas configurações. Portanto, limitamos a profundidade de pesquisa do AI e o colocamos no melhor estado da placa.

Este pseudocódigo está reproduzindo o processo que expliquei nas duas etapas anteriores. Agora vamos dar um passo adiante e corrigir isso no código Python.

Etapa 7: fazendo sua IA com Ai_template.py

Antes de dar uma olhada em meu código do Minimax AI, tente fazer seu próprio AI com o arquivo ai_template.py e o pseudo-código de que falamos na última etapa. Existem duas funções no template ai chamadas: def minimax_min_node (board, color) e def minimax_max_node (board, color). Em vez de fazer com que a função minimax se chame recursivamente, temos duas funções diferentes, que se chamam. Para criar a heurística para avaliar os estados do conselho, você terá que criar sua própria função. Há funções predefinidas no arquivo othello_shared.py que você pode usar para construir seu AI.

Assim que tiver sua IA, tente executá-la em randy_ai.py. Para executar dois ais um contra o outro, digite "python othello_gui.py (insira o nome do arquivo ai).py (insira o nome do arquivo).py" no terminal mac ou digite "execute othello_gui.py (insira o nome do arquivo ai).py (insira o nome do arquivo).py "e certifique-se de que está no diretório correto. Além disso, veja meu vídeo para ver as etapas exatas.

Etapa 8: É hora de fazer o AI Fight

Agora pegue um monte de amigos do seu computador e faça-os projetar sua própria IA! Depois, você pode fazer uma competição e fazer com que sua IA duque. Esperançosamente, mesmo que você não pudesse construir sua própria IA, você seria capaz de entender como o algoritmo minimax funciona. Se você tiver alguma dúvida, fique à vontade para postar qualquer dúvida nos comentários abaixo.