Jogo da velha no Arduino com IA (algoritmo Minimax): 3 etapas

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

Neste Instructable, vou mostrar como construir um jogo Tic Tac Toe com uma IA usando um Arduino. Você pode jogar contra o Arduino ou assistir o Arduino jogar contra si mesmo.

Estou usando um algoritmo chamado "algoritmo minimax", que pode ser usado não apenas para construir uma IA para o jogo da velha, mas também para uma variedade de outros jogos como Four in a Row, damas ou até mesmo xadrez. Jogos como o xadrez são muito complexos e requerem versões muito mais refinadas do algoritmo. Para o nosso jogo Tic Tac Toe, podemos usar a versão mais simples do algoritmo, que não deixa de ser bastante impressionante. Na verdade, a IA é tão boa que é impossível vencer o Arduino!

O jogo é fácil de construir. Você só precisa de alguns componentes e do esboço que escrevi. Também adicionei uma explicação mais detalhada do algoritmo, se você quiser entender como ele funciona.

Etapa 1: construir e jogar

Para construir o jogo Tic Tac Toe, você precisará dos seguintes componentes:

• Um Arduino Uno
• 9 LEDs RGB WS2812
• 9 botões de pressão
• alguns cabos de fio e jumper

Conecte os componentes conforme mostrado no esboço do Fritzing. Em seguida, faça upload do código para o seu Arduino.

Por padrão, o Arduino dá a primeira volta. Para tornar as coisas um pouco mais interessantes, o primeiro movimento é escolhido aleatoriamente. Após o primeiro movimento, o Arduino usa o algoritmo minimax para determinar o melhor movimento possível. Você inicia um novo jogo reiniciando o Arduino.

Você pode assistir o Arduino "pensar" abrindo o Serial Monitor. Para cada movimento possível, o algoritmo calcula uma classificação que indica se esse movimento levará a uma vitória (valor de 10) ou uma perda (valor de -10) para o Arduino ou a um empate (valor de 0).

Você também pode assistir o Arduino jogar contra si mesmo removendo o comentário da linha "#define DEMO_MODE" no início do esboço. Se você carregar o esboço modificado, o Arduino fará o primeiro movimento aleatoriamente e, em seguida, usará o algoritmo minimax para determinar o melhor movimento para cada jogador em cada turno.

Observe que você não pode vencer o Arduino. Cada jogo terminará em empate ou você perderá, se cometer um erro. Isso ocorre porque o algoritmo sempre escolhe o melhor movimento possível. Como você deve saber, um jogo de Tic Tac Toe sempre terminará em empate se ambos os jogadores não cometerem erros. No modo de demonstração, todos os jogos terminam empatados porque, como todos sabemos, os computadores nunca cometem erros;-)

Etapa 2: O Algoritmo Minimax

O algoritmo consiste em dois componentes: uma função de avaliação e uma estratégia de busca. A função de avaliação é uma função que atribui um valor numérico às posições do conselho. Se a posição for uma posição final (ou seja, uma posição onde o jogador azul ou vermelho ganhou ou onde nenhum jogador ganhou), a função de avaliação é muito simples: digamos que o Arduino joga azul e o jogador humano joga vermelho. Se a posição for uma posição vencedora para o azul, a função atribuirá um valor de 10 a essa posição; se for uma posição vencedora para o vermelho, a função atribui um valor de -10 à posição; e se a posição for um empate, a função atribui um valor de 0.

Quando for a vez do Arduino, ele quer escolher um lance que maximize o valor da função de avaliação, pois maximizar o valor significa que ele vai preferir uma vitória ao empate (10 é maior que 0) e preferirá um empate à derrota (0 é maior que -10). Por um argumento análogo, o oponente quer jogar de forma a minimizar o valor da função de avaliação.

Para uma posição não final, o algoritmo calcula o valor da função de avaliação por uma estratégia de busca recursiva. Partindo da posição atual, simula alternadamente todos os movimentos que o jogador azul e o jogador vermelho podem realizar. Isso pode ser visualizado como uma árvore, como no diagrama. Quando chega a uma posição final, ele começa a recuar, levando o valor da função de avaliação do nível de recursão inferior para o nível de recursão superior. Ele atribui o máximo (se na etapa de recursão correspondente for a vez do jogador azul) ou o mínimo (se na etapa de recursão correspondente for a vez do jogador vermelho) dos valores da função de avaliação do nível de recursão inferior para a posição no nível de recursão mais alto. Finalmente, quando o algoritmo termina de dar um passo para trás e chega à posição atual novamente, ele executa aquele movimento (ou um dos movimentos) que tem o valor máximo da função de avaliação.

Isso pode parecer um pouco abstrato, mas na verdade não é tão difícil. Considere a posição mostrada no topo do diagrama. Na primeira etapa de recursão, existem três movimentos diferentes que o azul pode realizar. Blue tenta maximizar o valor da função de avaliação. Para cada um dos movimentos que o azul pode realizar, existem dois movimentos que o vermelho pode realizar. O vermelho tenta minimizar o valor da função de avaliação. Considere o movimento em que o azul joga no canto superior direito. Se o vermelho jogar na caixa central, o vermelho venceu (-10). Se, por outro lado, o vermelho jogar na caixa inferior central, o azul vencerá na próxima jogada (10). Portanto, se o azul joga no canto superior direito, o vermelho vai jogar na caixa central, pois isso minimiza o valor da função de avaliação. Analogamente, se o azul for reproduzido na caixa inferior central, o vermelho voltará a ser reproduzido na caixa central, pois isso minimiza a função de avaliação. Se, por outro lado, o azul joga na caixa central, não importa qual lance o vermelho faz, o azul sempre vencerá (10). Uma vez que o azul deseja maximizar a função de avaliação, ele irá jogar na caixa central, uma vez que essa posição resulta em um valor maior da função de avaliação (10) do que os outros dois movimentos (-10).

Etapa 3: Solução de problemas e outras etapas

Se você apertar um botão e um LED diferente do correspondente ao botão acender, você provavelmente confundiu os fios dos pinos A0-A2 ou 4-6 ou conectou os LEDs na ordem errada.

Observe também que o algoritmo nem sempre escolhe necessariamente um movimento que permitirá ao Arduino vencer o mais rápido possível. Na verdade, passei algum tempo depurando o algoritmo porque o Arduino não escolheu um movimento que teria sido um movimento vencedor. Levei algum tempo até perceber que, em vez disso, ele havia escolhido uma jogada que garantia que venceria uma jogada depois. Se desejar, você pode tentar modificar o algoritmo para que ele sempre prefira uma jogada vencedora a uma vitória posterior.

Uma possível extensão deste projeto seria usar o algoritmo para construir um AI para um 4x4 ou mesmo 5x5 Tic Tac Toe. No entanto, observe que o número de posições que o algoritmo precisa examinar cresce muito rapidamente. Você precisará encontrar maneiras de tornar a função de avaliação mais inteligente, atribuindo valores a posições que não são finais, com base na probabilidade de a posição ser boa ou ruim para o jogador em questão. Você também pode tentar tornar a pesquisa mais inteligente interrompendo a recursão mais cedo se um movimento se revelar menos digno de uma exploração mais aprofundada do que movimentos alternativos.

O Arduino provavelmente não é a melhor plataforma para tais extensões devido à sua memória limitada. A recursão permite que a pilha cresça durante a execução do programa e, se a pilha crescer muito, pode corromper a memória do programa, causando travamentos ou comportamento errático. Escolhi o Arduino para este projeto principalmente porque queria ver se isso poderia ser feito e para fins educacionais, não porque seja a melhor escolha para esse tipo de problema.