Teoria dos jogos - ESTRATÉGIAS DE MINIMAX E MAXIMIN

Prévia do material em texto

UNIVERSIDADE ESTÁCIO DE SÁ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
TEORIA DOS JOGOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
RIO DE JANEIRO 
2021 
 
 
 
ALUNOS: 
 
GUSTAVO MARTINS DA SILVA (201802431799) 
 LUYSA ANNE PETRONILHA DE ANDRADE (201802322604) 
RUTH BASTOS DE OLIVEIRA (201802226982) 
STEPHANI BARBOSA TORRES (201803178132) 
TIAGO BRANDÃO MORAES (201308085397) 
 
 
 
 
 
 
 
 
 
 
 
ESTRATÉGIAS DE MINIMAX E MAXIMIN 
 
 
 
 
 
 
 
 
 
 DOCENTE: EDUARDO DE OLIVEIRA ORMOND 
 
 
 
 
 
RIO DE JANEIRO 
2021 
 
 
 
 
 
 
SUMÁRIO 
 
 
INTRODUÇÃO .....................................................................................04 
MINIMAX E MAXIMIN ..........................................................................05 
ESTRATÉGIA MINIMAX E MAXIMIN ..................................................07 
CONTRIBUIÇÃO DA ESTRATÉGIA MINIMAX E MAXIMIN NA 
ADMINISTRAÇÃO................................................................................08 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Introdução 
 
A teoria dos jogos é o estudo das tomadas de decisões que um indivíduo 
realiza quando o resultado desta escolha depende do que outros indivíduos 
decidem, como em um jogo de estratégias. 
Essa teoria se desenvolveu a partir de estudos sobre economia e matemática, 
através de situações estratégicas em que um jogador precisa fazer as 
melhores escolhas, porém, existe uma relação de interdependência com outros 
jogadores. 
A interdependência nas situações estratégicas acontece quando há 
concorrência e, a ação de cada jogador, modificará o resultado dos outros 
jogadores e de todo o jogo. Esse estudo, então, passou a ter relação com o 
comportamento das pessoas, empresas e do governo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Minimax e Maximin 
 
 
• Jogo da Velha 
Uma versão simples do algoritmo minimax lida com jogos como o jogo da 
velha, no qual cada jogador pode ganhar, perder ou empatar. 
Se o jogador A pode vencer com um movimento, esse é o seu melhor 
movimento. Se o jogador B identifica que um movimento levará a uma situação 
em que o adversário pode ganhar no próximo movimento, e que existe outro 
movimento que poderá levar a uma situação em que o adversário pode, no 
máximo, empatar, então, este último é o melhor movimento para ele. Após 
algumas rodadas, é fácil identificar qual é o melhor movimento. 
O algoritmo minimax ajuda a encontrar a melhor jogada, ao se caminhar pelas 
opções válidas, a partir do fim do jogo. A cada passo, assume-se que o jogador 
maximizador está tentando maximizar as suas chances de ganhar, enquanto 
na próxima rodada o jogador minimizador está tentando minimizar as chances 
de isso acontecer (maximizando as chances de que ele próprio ganhe). O 
maximizador precisa escolher uma jogada que tem a maior dentre as menores 
pontuações que o minimizador pode fazer aquele ter. 
 
• Desempenho e Otimizações 
 
O algorítimo mimimax no Jogo da velha (ou em outros tipos de jogos) pode 
fazer muito processamento, o que pode fazer o algorítimo ser lento, por isso, 
deve ser importante fazer-se otimizações para que ele seja efetuado de forma 
rápida durante a execução do jogo. Para isso pode ser usado por exemplo 
a Poda alfa-beta. Também pode ser importante, principalmente em dispositivos 
com baixo poder de processamento como celulares, ou até em dispositivos 
mais potentes, que os códigos sejam otimizados para evitar-se gastos com 
processamento e tempo desnecessários pois como esse algoritmo faz muito 
processamento, principalmente nas análises das primeiras partidas, tais gastos 
podem ser muito aumentados e causarem um grande impacto na queda de 
desempenho. 
 
• Algoritimo 
Algoritmo minimax com limite de profundidade (usando uma heurística para 
terminar o vasculhamento após uma dada profundidade) em pseudocódigo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Estratégias de Minimax e Maximin 
 
Em teoria da decisão, o minimax (ou minmax) é um método para minimizar a 
possível perda máxima. Pode ser considerado como a maximização do ganho 
mínimo (maximin). Começa-se com dois jogadores 0-0 da teoria dos jogos, 
cobrindo ambos os casos em que os jogadores tomam caminhos alternados 
(por rodadas) ou simultaneamente. 
 
• Minimax 
 
Em 1928, John Von Neumann propôs o teorema Minimax que marca o início do 
que podemos chamar de teoria dos jogos modernos. 
Em um jogo de dois jogadores com soma zero, é racional para cada jogador 
escolher a estratégia que maximiza seu ganho mínimo, ou, de forma 
equivalente, que minimiza o ganho máximo do outro. O par de estratégias tal 
que cada jogador maximiza seu payoff mínimo é a "solução" do jogo. 
 
• Maximin 
 
O jogador Linha (que quer maximizar) olha para o pior caso que pode 
acontecer (o payoff mínimo ou nível de segurança) quando ele joga cada uma 
de suas estratégias e escolhe a estratégia que dá o máximo destas 
recompensas mínimas (o mais elevado nível de segurança). 
Isso é chamado de payoff maximin (com respeito a "estratégias puras"). Desta 
forma, o jogador Linha ganha pelo menos a recompensa maximin, 
independentemente do que o jogador Coluna faz. 
 
 
 
 
 
 
 
 
 
Contribuição da estratégia minimax e maximin na 
administração 
 
A teoria dos jogos faz parte de um dos ramos da matemática aplicada e da 
economia que tem como objetivo analisar situações estratégicas em que os 
envolvidos baseiem a sua conduta na expectativa de comportamento da 
pessoa com a qual interage. 
É a análise quantitativa de qualquer situação que envolva pelo menos duas 
partes em conflito com o objeto de indicar ótimas estratégias para cada uma 
delas e alcançar os melhores resultados possíveis. 
No meio de tanta informação sobre inteligência artifiial, os conceitos básicos 
que definem grande parte do dicionário de um profissional da área geralmente 
são esquecidos. 
Minimax é um algoritmo considerado como conhecimento básico dentro das 
competências de um Engenheiro de Inteligência Artificial e pode ser usado para 
o desenvolvimento de complexas aplicações, principalmente no âmbito de 
jogos, valendo-se do seu poderoso potencial de decisão. 
 
 Tomada de Decisão em Ambiente de Incerteza Maximax 
 
• Critério de decisão otimista 
• Encontra o melhor resultado possível, que maximiza o resultado 
 
Tomada de Decisão em Ambiente de Incerteza Maximin 
• Critério de decisão pessimista 
• Encontra a decisão que maximizará o mínimo resultado 
 
Esses dois tipos de tomada de decisão têm como fundamento analisar 
situações de conflito, nas quais os envolvidos baseiam suas decisões conforme 
a utilidade que se pretende agir, tendo que escolher a melhor estratégia, 
encontrando um equilíbrio que seja a melhor opção para se obter ganhos 
Assim, através desses fundamentos pode se melhor entender a melhor forma 
que seja favorável a si mesmo e também se torna necessário conhecer os 
motivos das outras partes envolvidas, já que pode ser aplicada nas ações do 
cotidiano, onde precisa se adequar o comportamento individual com a 
previsibilidade das ações das pessoas com as quais interagimos, de maneira 
competitiva ou cooperativa.