Vimos que nosso robô não teve tanta dificuldade para desvendar todos os tipos de ambientes e espaços de estados possíveis, em sua busca baseada em elementos de desempenho, funções de custo, subidas de encosta estocástica e problemas de busca on-line de explorações com observações parciais.
Mas e quando houver dois robôs competindo pelo mesmo objetivo, com a mesma capacidade neural artificial e mesmas condições iniciais? Teríamos um busca competitiva conhecida como Teoria dos Jogos. E o jogo mais famoso para iniciarmos uma discussão é o jogo determinístico de revezamento de dois jogadores de soma zero com informações perfeitas: o Xadrez.
A competição é gerada pela oposição de duas funções de utilidades, a função “jogador ganha” e a função “jogador perde”. O xadrez tem um fator médio de ramificação, tendo em media 50 movimentos por jogador. Assim, a árvore de busca em grafo tem aproximadamente 10.000.000.000.000.000.000.000.000.000.000.000.000.000 nós distintos!
Sendo assim, como um robô escolheria suas melhores decisões em um tempo limitado para as escolhas? Ele deverá ignorar as partes da árvore de busca que não vão fazer diferença na escolha final. A FUNÇÃO DE AVALIAÇÃO HEURÍSTICA permite a aproximação da verdadeira utilidade de um estado sem a necessidade de uma varredura completa e constante. Nosso robô competitivo passa a desconsiderar grandes partes da árvore. Essa técnica ficou conhecida como PODA ALFA-BETA.
A poda alfa-beta cabe em árvores com qualquer profundidade. Além do mais, ela pode ser aplicada para podar subárvores inteiras em lugar apenas de ramos ou folhas. O princípio geral é este: vamos considerar um nó n em algum lugar na árvore tal que o robô tenha a escolha de movimento que o levará até esse nó. Se o robô tiver uma escolha melhor m no nó pai de n, em qualquer ponto adicional acima dele, então n nunca será alcançado em um jogo real. O robô examina os descendentes do nó pai decidindo ou não pela poda.
A poda alfa-beta possui dois parâmetros que precisam agora de uma definição:
• Alfa – o valor da melhor escolha que encontrar até o momento para que sua decisão seja maximizada.
• Beta - o valor da melhor escolha que encontrar até o momento para que sua decisão seja minimizada.
Para o jogo de xadrez em questão, onde o tempo é determinante para a escolha de um movimento ótimo, os programas deveriam cortar a busca mais rapidamente. Foi o que propôs Claude Shannon em seu Programming a Computer for Playing Chess. Os estados de busca transformavam efetivamente nós terminais em folhas terminais. A função de avaliação estimaria novamente a utilidade de cada novo estado.
Você já deve ter desconfiado que nossa exploração está se dirigindo para um momento histórico no desenvolvimento da Inteligência Artificial. Um marco na história da humanidade. A época onde o melhor jogador de xadrez de todos os tempos enfrentou o maior pesadelo de sua vida. Quem foi esse jogador e qual o nome do adversário tão temido? Chegaremos lá em breve...
Nenhum comentário:
Postar um comentário