Jogo da velha

Existem 2 tipos de agentes inteligentes para o jogo da velha: o agente que faz a melhor jogada analisando a situação atual, o que significa que para sua próxima jogada o seu movimento atual vai ser realmente útil; e o agente que planeja as suas jogadas, este que age com estratégia. O agente que faz a melhor jogada olha para o tabuleiro e se pergunta: "O que pode me fazer ganhar ou perder ?" . Já o agente estratégico pode fazer jogadas que aparentemente não tem sentido, mas que futuramente vão decidir a partida.
Teoria da decisão, Minimax ou MinmaxMinimax lida com jogos como jogo da velha, no qual cada jogador pode ganhar, perder ou empatar. No nosso exemplo específico que é o jogo da Velha, você pode considerar que após a sua jogada, o adversário vai escolher a melhor jogada possível e então você a partir dessa melhor jogada já pensa na melhor que você pode fazer e assim sucessivamente. Por exemplo, vamos chamar um jogador de MIN e outro de MAX (daí veio nome: MINIMAX). O jogador MAX sempre considera que MIN vai escolher a jogada que o deixa na pior situação (pior caso para MAX) e que ele (o MAX) vai escolher a melhor jogada para si. O algoritmo minimax ajuda a encontrar a melhor jogada ao caminha pelas opções válidas a partir do fim do jogo. A cada passo assume-e que o jogador MAX está tentando maximizar as chances de MAX ganhar, enquanto na próxima rodada o jogador MIN está tentando minimizar as chances de isso acontecer (ao maximizar as chances de que ele próprio ganhe).
Resumindo, o jogador usando o algoritmo miniMax constrói uma árvore de jogadas achando que ambos (ele mesmo e o adversário) sempre escolherão soluções ótimas para si mesmos. Veja um exemplo de uma possível parte de uma árvore de jogo da velha. Atente apenas para o detalhe que nessa árvore temos a impressão que começou no MIN, quando na verdade começa no MAX. Eu escolhi essa parte do meio da árvore.

http://www.rodrigovaz.xpg.com.br/ajm.png
Árvore de busca de uma partida de Jogo da velha
Os