Daniel Oliveira E Higor Eduardo JVelha

Daniel Oliveira Martins
Higor Eduardo Borges Galdino
ADS FATEC – 2014

Teoria
O algoritmo MiniMax é bastante utilizado, diversos códigos encontrados utilizam o mesmo para resolver o problema do jogo da velha. É possível jogar Humano X Computador. Não foram encontradas maneiras de vencer o computador, suas jogadas são sempre as melhores possíveis. O jogo foi feito para empatar, caso ambos os jogadores façam as melhores jogadas possíveis, assumindo que a cada jogada, o jogador 1 tenta maximizar as chances dele ganhar, enquanto o jogador 2 tenta minimizar as chances de isso acontecer, maximizando as próprias chances de ganhar.
Exemplo:
ROTINA minimax(nó, profundidade) SE nó é um nó terminal OU profundidade = 0 ENTÃO RETORNE o valor da heurística do nó SENÃO SE o nó representa a jogada de algum adversário ENTÃO α ← +∞ PARA CADA filho DE nó α ← min(α, minimax(filho, profundidade-1)) FIM PARA RETORNE α SENÃO α ← -∞ PARA CADA filho DE nó α ← max(α, minimax(filho, profundidade-1)) FIM PARA RETORNE α FIM SE
FIM ROTINA
Wikipedia, acesso em 08/08/2014.

O algoritmo NegaMax nega o valor da heurística correspondente ao nível onde teria que minimizar, assim, maximiza sempre. Funciona para jogo entre 2 humanos e não trata os jogadores separadamente.
Exemplo:
ROTINA negamax(nó, profundidade) SE nó é um nó terminal OU profundidade = 0 ENTÃO RETORNE o valor da heurística do nó SENÃO α ← -∞ { a avaliação é idêntica para ambos os jogadores } PARA CADA filho DE nó α ← max(α, -negamax(filho, profundidade-1)) FIM PARA RETORNE α FIM SE
FIM ROTINA
Wikipedia, acesso em 08/08/2014.

Referências Bibliográficas
Wikipedia - http://pt.wikipedia.org/wiki/Minimax
AIMotion – http://aimotion.blogspot.com.br/2009/01/aprenda-aplicar-inteligencia-artificial.html?_sm_au_=ihG5s1tQrS7ZD7jk