Conceito de Minneapolis Jonah von Neumanna

Resumo – Alguns problemas reais hoje em dia estão totalmente ligados com inteligência artificial, ou essa é a solução para os problemas. Alguns desses problemas estão relacionados com jogos digitais e ambientes competitivos, em que as metas dos agentes estão em conflito, dando origem a busca competitiva.

Na área de IA (Inteligência artificial), jogos são problemas de busca competitiva em ambientes determinísticos e completamente observáveis. Além disso, jogos são considerados um desafio para a inteligência humana e um assunto atraente para IA. Nesse sentido, resolveremos o problema clássico do jogo da velha utilizando o algoritmo minimax. O jogo questão trata-se de um exemplo fácil de entender, mas poderemos aplicar o algoritmo em situações mais complexas posteriormente. Vale ressaltar que o algoritmo não consegue 100% de aproveitamento quando está em execução, ou seja, o usuário tem a chance de “ganhar” da inteligência artificial utilizando minimax. Testes mostram que existe pelo menos uma jogada que a inteligência nunca consegue prever. Convidamos você para jogar o jogo com a nossa implementação do algoritmo e descobrir qual jogada é essa.

Abstract – Some real life problems are totally connected to artificial intelligence or it is the solution to problems. Some of these problems are related with digital games and competitive environments, in which the goals of the agents are in conflict, resulting in a competitive search.

In AI (Artificial Intelligence), games are problems of competitive search on a fully observable deterministic environment. In addition, games are considered to be a challenge to human intelligence, thus an attractive matter for AI. Accordingly, we will resolve the classic problem of tic-tac-toe utilizing the minimax algorithm. The tic-tac-toe example is for understanding purposes, but the algorithm can be applied to more complex situations. It is important to emphasize that minimax cannot hold a 100% use and the user has the chance to “win” the game. Tests have shown that there is at least one movement sequence that the algorithm cannot predict. We invite you to play the game with our implementation of the algorithm and find out what that sequence is.

I. INTRODUÇÃO

Como explicado por Tinne Hoff Kjeldsen em seu artigo intitulado de “John von Neumann’s Conception of the Minimax. Theorem: A Journey Through Different Mathematical Contexts”. O algoritmo minimax for demonstrado por Von Neumann que com isso foi considerado o pai da teoria dos jogos em 1926. [1]

Podemos entender que o nosso objetivo em jogos onde existem no máximo dois jogadores, está inteiramente voltado para encontrar o melhor caminho, rota, percurso ou movimento para MAXIMIZAR o resultado obtivo e paralelamente MINIMIZAR o resultado obtido pelo adversário.

Na aplicação demonstrada, veremos que a IA faz o papel, hora do primeiro jogador - que por acordo será chamado de jogador-max – e hora do segundo jogador – jogador-min -.

II. DEFINIÇÃO DO PROBLEMA

Neste projeto veremos um exemplo prático de uso do algoritmo minimax e como ele poderá ajudar a desenvolver novas ferramentas onde o problema principal gira em torno de busca competitiva. O jogo da velha trata-se de uma competição entre dois jogadores que escolhem uma marcação cada um, geralmente um círculo (O) e um xis (X). No nosso caso, um dos jogadores será representado pela IA, tomando decisões baseadas em movimentos feitos anteriormente, dando a impressão de que existem dois jogadores de fato jogando e tentando ganhar. O objetivo é conseguir três (O) ou três (X) em linha, podendo ser horizontal, vertical ou diagonal, e ao mesmo tempo, quando possível, impedir o adversário de ganhar na próxima jogada.

Dividindo o jogo em etapas e analisando o algoritmo, podemos formular um diagrama da árvore do algoritmo minimax para o jogo da velha, a figura 1 ilustra todas as possíveis combinações para os primeiros três movimentos.

Figura 1 – Arvore para o jogo da velha

O problema em questão trata-se de como utilizar o algoritmo para que este seja capaz de prever os movimentos necessários de acordo com a movimentação de um jogador. Jogar pode ser visto como uma generalização do problema de procura em espaço de estados, em que existem agentes hostis que procuram diminuir o nosso próprio valor.

Para facilitar a identificação da melhor jogada usam-se heurísticas para auxiliar a exploração das árvores que descrevem o espaço de estados, associadas a técnicas de corte da árvore e funções de avaliação que permitem calcular a utilidade de um estado sem explorar toda a sub-árvore respectiva.

Neste tipo de jogo percebe-se a total incerteza sobre qual será a próxima jogada do oponente e em contra partida temos todas as informações necessárias para que possamos entender e fazer especulações sobre o que poderá acontecer, baseando sempre em conhecimento prévios ou em IA capaz de optar por caminhos com maior probabilidade de sucesso. Dentre estas informações disponíveis, citamos algumas como:

 Quantidade máxima de movimentos que podem ser feitos;

 Quantidade de movimentos restantes;

 Espaço limitado para se fazer à próxima jogada.

Todas essas informações e mais algumas são levadas em consideração para que se possa construir uma inteligência artificial para resolver os problemas que o pensamento humano não consegue, perceba que o espaço limitado para se fazer à próxima jogada pode ser algo realmente pequeno para uma IA, mas pode ser algo extremamente grande para uma mente humana. Como mostrado no exemplo do jogo de xadrez onde, em média o fator de ramificação é igual a 35, ou seja, o seu número de vizinhos é 35, isso quer dizer que a mente humana teria que armazenar entender e tomar uma decisão tendo 35 possibilidades de escolha, o que não é uma tarefa assim tão simples. Este é exatamente o tipo de problema que temos em mãos e o problema que resolveremos utilizando uma inteligência artificial. [2]

III. SOLUÇÃO DO PROBLEMA

A solução deste problema é encontrar a melhor estratégia, chamada de estratégia ótima de cada rede, de forma a maximizar a audiência. Disso resulta que tanto o jogador quanto a IA tomarão decisões que podemos classificar como de o menor risco possível. Cristiane dos Santos Costa [3], ao escrever seu artigo “Teoria dos jogos e a relação entre o "teorema minimax" de John Von Neumann e o