MinMax

UNIJUÍ – Universidade Regional do Noroeste do Estado do Rio Grande do Sul

MiniMax

Trabalho Estrutura de Dados II
Prof. Marcos Ronaldo Melo Cavalheiro

Alunos: Átila Cordeiro Biolchi Micael Thales Hentges

Novembro de 2014

Sumário

1. Minimax 2
1.1. Introdução 2
1.2. Entendendo o problema 2
1.3. MinMax ou Mini-Max 2
2. Método da Força Bruta 4
3. Pesquisa Exaustiva 5
4. Algoritmo Guloso 6
5. Dividir e Conquistar 6
6. Backtracking 8
7. Referencias Bibliográficas: 9

1. Minimax

1.1. Introdução
Para iniciarmos a falar sobre minimax precisamos ententer que, este tema é um dos teoremas fundamentais da teoria dos jogos. Estudado por John von Neumann e Oskar Morgenstern (1944 ), o estudo inicial sofreu varias mudanças ao longo das últimas 60 anos, foi aprofundada e generalizada. Refinamentos ainda estão sendo feitas, no entanto, pelo menos desde o final dos anos 1970, tem sido possível dizer com confiança que a teoria dos jogos é uma ferramenta importantíssima.
Alguns autores afirmam que a que conhecimento sobre teoria dos jogos remonta tempos antigos. Um exemplo seria dois textos de Platão , o Laches e o Simpósio(aproximadamente 400 anos A/C).

1.2. Entendendo o problema
Em um jogo, cada jogador, enfrenta uma escolha entre duas ou mais possíveis estratégias . A estratégia é um "programa de jogo" predeterminado que lhe diz quais ações tomar em resposta a todas as estratégias possíveis outros jogadores podem usar. Os jogos mais simples (a partir do ponto de vista da estrutura lógica) são aqueles em que os agentes têm informação que em cada ponto onde a estratégia de cada agente diz para ela tomar uma ação, ela sabe tudo o que aconteceu no jogo até aquele momento, ou seja, um tabuleiro de movimentos sequenciais em que ambos os jogadores assistir toda a ação (e conhecem as regras em comum), como jogo da velha.

1.3. MinMax ou MiniMax
Em