Post on 15-Apr-2017
Minimax e Corte Alfa-Beta
Marcos Thomaz da Silva
Mestrado em ComputaçãoDisciplina: Inteligência Artificial – Prof. Dr. José Francisco
Minimax
• Teoria minimax demonstrada por John von Neumann
• Método da teoria da decisão, • Objetiva minimizar a perda máxima possível, ou,
maximização do ganho mínimo;• Em jogos, visa decidir qual a melhor jogada;• Recebe com parâmetros a quantidade de jogadas
que serão avaliadas, avalia as opções (todas combinações), e retorna opção com maior ganho.
• Minimax tem um custo elevado de tempo
Minimax – Onde aplicar
• Teoria de Jogos: Jogo da Velha, Jogo de Damas;
• Apoio a tomada de decisões
MAX
MIN
MAX
Minimax - Demonstração
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
8
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
8
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 3
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 3
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1 7
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1 7
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1 4
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1 4
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
2
2 -1 4
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Minimax - Demonstração
4
2 -1 4
8 2 15 3 -1 5 7 4 9
Corte Alfa-Beta
• Uma variação do algoritmo minimax• Visa reduzir número de nós que são avaliados• Para de avaliar os nós quando sabe que o
mesmo possui resultados desfavoráveis• Não altera o resultado final, apenas reduz a
quantidade de iterações
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
8
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
8
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 3
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 3
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1 7
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1 7
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1 4
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1 4
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
2
2 -1 4
8 2 15 3 -1 5 7 4 9
MAX
MIN
MAX
Corte Alfa-Beta - Demonstração
4
2 -1 4
8 2 15 3 -1 5 7 4 9
Demonstração – Jogo da Velha
• Tendo o jogo abaixo, e sabendo que é a vez do jogador que usa “X”:
XOX
O
X O
Demonstração – Jogo da Velha
• Temos 3 locais para jogar e nenhuma delas finaliza diretamente. Sendo assim, é feita a avaliação usando minimax sobre qual local deve ser jogado.
• Como existem 3 locais, são avaliadas as 3 jogadas, sendo duas do jogador “X” e uma do jogador “O”
MAX
MIN
MAX
Demonstração – Jogo da Velha
XOX
O
X O
XOX
O
X OX O
XOX
O
X O
XXOX
O
X OX
XOX
O
X OX
XOX
O
X OXO
XOX
O
X OXO X
OX
O
X O
XO
XOX
O
X O
XOO
XOX
O
X OX
O