Produções em Tecnologia da Informação

Estudo Sobre Jogos e Assuntos Correlatos Focando a Inteligência Artificial
Written by Adonai Estrela Medrado   
Tuesday, 01 July 2008 14:39

Sobre

O material apresentado aqui é a compilação com pequenas alterações dos três primeiros capítulos do trabalho de mesmo título apresentado na Universidade Católica do Salvador em novembro/2002. A autoria original é de Adonai Medrado, Leandro Brito e Josevaldo Leal. As referências apresentadas ao final são as utilizadas no trabalho em sua íntegra.

Introdução

 

Jogo: uma forma geralmente recreativa incluindo qualquer atividade para diversão e geralmente estabelece uma situação que envolve rivalidade. [Britannica 02]

Jogo: (1) designação genérica de certas atividades cuja natureza ou finalidade é recreativa; diversão, entretenimento; (...) (2) atividade, submetida a regras que estabelecem quem vence e quem perde; competição física ou mental sujeita a uma regra, com participantes que disputam entre si por uma premiação ou por simples prazer. [Houaiss 01]

Jogo: (1) Passatempo, divertimento, recreação, lazer, esporte. [Oxford 94]

Todas as definições citadas já vêm durante anos e ainda vão perdurar durante muito tempo imutável, afinal estão corretas. O que não se encontra em nenhuma das definições é referência à inteligência artificial (IA). Não se consegue imaginar, hoje em dia, um jogo computadorizado vendável sem IA.

Grandes estudos foram feitos sobre os jogos a exemplo de John Von Neumann em 1944 (ver bibliografia), tanto visando mostrar sua importância para o desenvolvimento do raciocínio, espírito de grupo e coordenação nas crianças quanto para entender e classificar os diversos tipos de jogos. A frase popular “a vida é um jogo” parece ser uma extrapolação do conceito e resultado dos estudos realizados.

Os estudos sobre jogos geraram uma teoria conhecida como teoria dos jogos. Formalmente se diz que esta teoria é uma abordagem matemática utilizada para analisar situações de competição na qual os resultados não dependem somente na escolha de um, mas na escolha feita por outros. [Britannica 02]

As pessoas que se dedicavam ao estudo de inteligência artificial perceberam nos jogos um campo a ser explorado pois eles são problemas usualmente criados pelos seres humanos e para os seres humanos que têm um número de solução reduzida e regras bem definidas e claras.

A aplicação da IA em jogos levou ao desenvolvimento de uma séria de trabalhos e técnicas que muito contribuíram para a evolução da IA. Por este motivo o foco deste trabalho é jogos, teoria dos jogos, classificação e técnicas de inteligência artificial que podem ser aplicadas.

Motivação

Uma área bem desenvolvida como a de inteligência artificial em jogos pode sem sombra de dúvida ajudar na compreensão e solução de outros problemas do mundo real.

Neste contexto é de fundamental importância o conhecimento, ou no mínimo uma visão ampla da teoria que envolve esta área.

Objetivo

O objetivo deste trabalho é apresentar o conceito de jogos, teoria de jogos, as classificações dos jogos e também demonstrar algumas das técnicas mais aplicadas atualmente na solução de problemas relacionados aos jogos.

Não é objetivo deste trabalho entrar em detalhes sobre implementação destes métodos ou mesmo descrição matemática de algoritmos, no entanto é inevitável alguma referencia a estes tópicos, assim sendo acompanha este trabalho uma bibliografia que pode ajudar a interessados por um aprofundamento maior.

Jogos

A maioria dos jogos tem origem desconhecida. Vejamos por exemplo um dos jogos mais conhecidos e aquele ao qual a inteligência artificial tem despedido grandes esforços: o xadrez. Segue relato colhido em [AJAX 02]:

A origem do xadrez é certamente o maior mistério existente no mundo. Atribui tanto a origem do xadrez ao Rei Salomão quanto aos sábios mandarins contemporâneos de Confúcio. Mas outras pessoas também atribuem a origem do xadrez aos Egípcios.

O documento mais antigo, sobre o jogo do xadrez, é provavelmente a pintura mural da câmara mortuária de Mera, em Sakarah (nos arredores de Gizé, no Egito). Ao que parece, essa pintura, que representa duas pessoas jogando xadrez, ou algo semelhante, data de aproximadamente 3000 anos antes da era cristã.

Segundo alguns historiadores dos mais autorizados, que se dedicaram ao assunto, parece que seu berço foi a Índia, onde teria surgido por volta do século V ou VI de nossa era, derivado de antiqüíssimo jogo hindu que é conhecido por "Chaturanga", isto é, quatro lados. Daí teria passado à Pérsia onde foi buscar o mundo islâmico, que por sua vez o transmitira à Europa por duas vias distintas: Segundo uns, pela invasão muçulmana da Península Ibérica, e segundo outros, durante seu confronto Ocidente-Oriente quando da Primeira Cruzada.

No Brasil, o jogo existe desde 1808, quando D. João VI ofereceu a Biblioteca Nacional, no Rio de Janeiro, um exemplar do primeiro trabalho impresso sobre a matéria, de Autoria de Lucena. [AJAX 02]

Outro relato se segue sobre o jogo de Tênis extraído de [O Dia 02]:

Apesar de ser um esporte muito praticado atualmente, a origem do tênis é praticamente desconhecida. Algumas pessoas defendem a tese de que o esporte surgiu como uma variação dos antigos jogos de bola praticados pelos gregos, romanos e egípcios. Já foi provado que, nessa época, existiu um esporte onde as pessoas jogavam bola com as palmas das mãos. Inclusive, há relatos de que Ariston Carystius foi considerado o grande jogador de sua época.

Outros especialistas crêem que o tênis vem de um jogo romano chamado "haspastum", que foi adaptado pelo País Basco no século XII e renomeado de "jeu de paume", porque a bola era lançada contra uma parede com as palmas das mãos, coberta por uma luva ou por correias de couro. [O Dia 02]

E os exemplos são muitos incluindo o jogo de damas e até mesmo as olimpíadas. Existem muitas hipóteses mas, infelizmente, nenhuma comprovada. É certo que até o primeiro jogo e seu criador são totalmente desconhecidos.

Este fato, no entanto não parece ser por acaso já que a idéia de brincadeira é inata a um recém nascido de qualquer espécie, seja humana ou não. Então percebe-se claramente que é impossível dizer precisamente qual foi o primeiro jogo.

Mesmo os jogos desenvolvidos por adultos, a exemplo do tênis, são difíceis de encontrar o inventor, pois os jogos tratam-se geralmente de uma atividade coletiva na qual as regras sofrem grandes adaptações durante o tempo, principalmente nos primeiros momentos de surgimento.

No entanto, quando nos aproximamos da época atual, onde há uma maior preocupação com publicações e patentes a história começa a se modificar. Por exemplo, a história do vídeo game pessoal é bem conhecida e começou no MIT com Steve Russel e é descrita em [MARGAMES 02].

Aplicação e Utilidade

Vários trabalhos têm demonstrado a importância dos jogos de computadores seja no campo empresarial, militar, da educação ou da diversão.

No campo empresarial, trabalhos como [Vargas 96] que mostra como os jogos empresariais, podem ajudar no desenvolvimento e aprimoramento dos recursos humanos de uma empresa. No campo militar, os simuladores são um ótimo exemplo pois são capazes de treinar pessoas para as mais diversas situações até para aquelas que uma simulação no mundo real é impraticável. Na educação, podem-se citar vários exemplos de softwares utilizados para o crescimento intelectual das crianças como jogos que envolvam cálculos matemáticos e lógica.

Estudo

As aplicações dos jogos motivaram estudiosos de todo o mundo tanto a desenvolver técnicas de resolução quanto a proporem novos jogos que tivessem características reais.

Todos as conclusões e estudos realizados em jogos são englobados na chamada teoria dos jogos.

A teoria dos jogos tem uma história antiga e pode ser toda estudada em [Walker 95]. Um breve resumo a título de conhecimento:

  • 1920-1930: primeiros ensaior por Borel e Von Neuiman.

  • 1940: destaque para modelagem de conflitos militares e jogos envolvendo decisões econômicas.

  • 1950: vários trabalhos interessantes realizados demonstrando grande interesse sobre o tema.

  • 1960: menor quantidade de trabalhos significativos mostrando que houve uma queda de interesse.

  • 1970: interesse em jogos evolutivos.

Pode-se também destacar alguns trabalhos em especial:

  • Grande Avanço Teórico: The Theory of Games and Economic Behavior por John Von Neuman e Oskar Morgenstern.

  • Jogos Sociais: Dilema do Prisioneiro popularizado pelo matemático Albert W. Tucker..

  • Jogos Biológicos: Estratégia Evolucionariamente Estável: introduzida por John Maynard Smith no seu ensaio Game Theory and the Evolution of Fighting.


Categorias

Os jogos podem ser enquadrados em categorias que foram criadas para facilitar o estudo.

Existe uma divisão que leva em conta a quantidade de ação, aventura, estratégia, etc. que um jogo possui. No entanto para o estudo de inteligência artificial aplicada a jogos este tipo de divisão não é útil, pois não diz muito sobre o tipo de algoritmo que deve ser utilizado para resolvê-lo.

A inteligência artificial utiliza-se então das categorias adotadas pela teoria dos jogos que são (segundo [WIKIPEDIA 02]):

  • Soma Zero: todo jogo no qual um jogador (ou um grupo de jogadores) só ganha se outros jogadores perderem. Pocker é um bom exemplo assim como Xadrez, Dama ou Reversi.

  • Cooperativos: todo jogo de N jogadores em que o jogador N1 só obtenha sucesso se o jogador N2 ganhar devendo assim os N jogadores cooperarem para um atingir um objetivo em comum. Um exemplo deste tipo de jogo é a Política uma vez que os políticos devem colaborar para o bem do seu país. Se o país tiver sucesso, a política foi eficiente e todos ganham, caso contrário, a política não conseguiu encontrar uma solução para o problema, não foi eficiente e todos perdem.

  • Transparentes: todo jogo de N jogadores e de M informações em que os N jogadores têm acesso às N informações. Não deve ser considerada como informação a experiência de cada jogador. Xadrez, Dama e Reversi são jogos transparentes, pois todos os jogadores tem acesso a todas as informações sobre o jogo.

Considerações sobre Jogos

É inegável a importância dos jogos na história da humanidade ou mesmo das chamadas brincadeiras em outras espécies. Grande é o número de jogos mas antigos cuja origem é desconhecida, pois um jogo é uma atividade coletiva que sofre várias modificações ao longo do tempo.

Os jogos possuem as mais diversas utilidades e categorias. Estas duas características facilitam e dirigem os estudos tão importantes na área.

Algoritmos de Solução

Um jogo tem todas as características necessárias para ser um problema.

A segunda definição de problema pelo verbete do [Houaiss 01] diz que problema é um “obstáculo, contratempo, dificuldade que desafia a capacidade de solucionar de alguém”. Este alguém hoje em dia pode ser encarado como uma pessoa, um grupo de pessoas ou um algoritmo computacional.

De certo o jogo foi um dos primeiros problemas que algoritmos computacionais de inteligência artificial estudaram. Um caso clássico em que um problema existente ajudou muito um novo ramo da ciência a se desenvolver.

Jogos e Inteligência Artificial

A inteligência artificial com os jogos conseguiu evolui na sua busca por imitar o comportamento humano, criar uma mente inteligente. Resta saber qual (ou quais) característica tem um jogo para que sua solução seja tão adequada para a inteligência artificial.

Abaixo, uma lista de algumas das possíveis razões para a história de sucesso de IA com jogos.

  • O que leva a solução de um jogo pelo ser humano é a inteligência. E é esta inteligência que a IA tenta imitar e não qualquer outra característica humana.

  • São problemas de conhecimento total. As regras de um jogo, para que ele seja possível na prática, deve ser conhecido pelo menos por todos os seus participantes. Diferente de sentimentos como amor, ódio e raiva que nem os seres humanos conhecem completamente e são capazes de descrever com perfeição sem entrar em “contradição” a exemplo da frase popular: “amor e ódio andam juntos”.

  • Suas soluções têm forma de seqüência de situações legais e as transições de situações são finitas e conhecidas. Um jogo possui um número limitado de estados. Um exemplo simples, e convincente, é o xadrez: existem aproximadamente 10120 estados possíveis em um jogo de xadrez [Fiplac 02], o que, embora seja um número altíssimo para a maioria dos padrões, ainda é um limite.

Busca de Solução e Árvores

A busca de solução para o problema dos jogos geralmente está relacionada a buscas por um determinado estado em uma árvore ou grafos de estados.

Uma árvore, no entanto, é muito mais utilizada do que um grafo, pois a sua estrutura oferece algumas vantagens. Por exemplo, em uma árvore pode-se ter certeza de que um nó só será gerado e visitado uma vez. [Fiplac 02]

Existem algumas formas de se executar busca de solução em uma árvore ou em um grafo que contém os estados possíveis de um jogo. Estas formas podem ser classificadas genericamente como estratégia de busca cega e estratégia de busca heurística (ou simplesmente busca cega e busca heurística, ou ainda busca não informada e busca informada).

Busca Cega (ou Busca Não Informada)

A busca cega, também chamada de busca não informada, trabalha somente com as informações necessárias para distinguir o estado alvo de um estado não alvo.

Alguns algoritmos possuem tal filosofia. Dentre eles podemos citar como principais (todos considerando busca em uma árvore) segundo [Kendall 01]:

  • Breadth-First (Busca em Amplitude): neste tipo de busca um nível N somente deve ser expandido quando todos os nós do nível N-1 tiverem sido encontrados. Esta estratégia tem como benefício ser completa (acha a solução), no entanto ela requer muita memória pois trabalha guardando todos os nós intermediários na memória.

  • Depth-First (Busca em Profundidade): nesta busca o próximo nó do nível N só será expandido se o nó da posição imediatamente anterior já tiver todos os seus filhos expandidos. Este algoritmo requer muito menos memória do que a busca por amplitude, já que só é necessário guardar o caminho da raiz até o final do nó que está sendo expandido. No entanto, ele é incompleto (pode não encontrar a solução) pois é possível que siga por um determinado ramo da árvore indeterminadamente.

  • Depth-Limited (Busca em Profundidade Limitada): é uma busca em profundidade que limita quantos nós o algoritmo poderá descer. Obviamente esta busca é incompleta.

  • Iterative Deepening (Busca em Profundidade Interativa): faz uma busca em profundidade limitada fazendo variação de limite quando necessário. É completa e encontra a solução ótima.

Busca Heurística (ou Busca Informada)

A idéia de heurística é a de uma técnica que algumas vezes pode funcionar e em outras não. A maioria das coisas na vida tem solução heurística. Entretanto, o termo heurística também pode ser utilizado em outro contexto, quando se deseja encontrar a melhor solução baseada em uma função de avaliação.

Com base nesta função de avaliação e em alguns parâmetros pré-definidos, a heurística pode ajudar a encontrar não somente a melhor solução, mas uma das melhores soluções.

Existem alguns problemas em que as soluções por busca cega não são adequadas por considerarem várias opções inadequadas. Um exemplo clássico é a escolha de uma rota para viajar de uma cidade A para B. A depender da finalidade da viajem algumas rotas são decididamente inaceitáveis e outras podem ser consideradas. As soluções heurísticas, mais especificamente seus algoritmos levam em considerações informações específicas sobre o problema.

Pode-se destacar os seguintes algoritmos de busca heurística:

  • Best-First (Busca pelo Melhor Primeiro): de forma simplificada pode-se dizer que o Best-First faz uma busca em profundidade em uma lista de estados organizados seguindo algum critério específico em que se pode localizar no início da lista, os primeiros estados que devem ser analisados e no final da lista estarão localizados os últimos estados que devem ser analizados.

  • Subida de Encosta (Hill Climbing): o algoritmo de busca de subida de encosta toma como informação pertinente o estado atual, o estado alvo e avalia a distância dos outros estados para tentar chegar o mais próximo possível do estado alvo. Caso a distância de qualquer outro estado seja melhor do que a distância atual o algoritmo então passa a assumir este ponto melhor como posição atual. Este procedimento é repetido em cada busca. É evidente que a distância para o estado alvo deve ser conhecida ou estimada.
    Alguns, a exemplo de [Fiplac 02], classificam estes algoritmos em duas subcategorias:

    • Subida de Encosta Simples: o algoritmo sempre toma como próximo estado o primeiro estado que encontrar maior que o atual.

    • Subida de Encosta Pela Trilha Mais Íngreme: o algoritmo sempre toma como próximo estado aquele maior que o atual e mais próximo do estado alvo.

Alguns algoritmos menos conhecidos, mas também utilizados são (ainda segundo [Fiplc 02]):

  • Agenda: lista de tarefas que um sistema pode realizar. Uma tarefa é composta por (1) uma lista de justificativas para a tarefa e (2) um peso que dirá o quando uma tarefa é útil. Constitui um meio de integrar informações de uma variedade de fonte em um programa já que cada fonte simplesmente acrescenta tarefas e justificativas à agenda.

  • Redução de problemas: decompõe um problema em um conjunto de problemas menores.

  • Satisfação de Restrições: encontra algum estado do problema que satisfaça determinadas restrições.

  • Análise Meio-Fim: detectar diferenças entre o estado corrente e o estado meta.

Existem ainda outros algoritmos avançados de busca heurística não citados aqui, mas podem ser encontrados em [Bresina 98] como por exemplo o algoritmo HBSS e ESQ que lidam com agendas.

Considerações Sobre Algoritmos

Embora existam diversos algoritmos para resolução dos problemas dos jogos, cada um tem sua característica específica e se prestam a fins bem distintos. Alguns, por exemplo, dão a garantia que a solução se ela existir será encontrada, outros não. O indivíduo que tentar aplicar estes algoritmos deve saber escolher qual atende às suas necessidades. 

Conclusão

Percebe-se claramente a importância e a aplicação dos jogos nas diversas áreas de conhecimento desde a educação, passando pelas empresas e chegando até a área militar.

A inteligência artificial tem dado uma contribuição significativa para que novos jogos possam ser criados e desenvolvidos a ponto que não é comercialmente concebível lançar um novo jogo no mercado para que seja vendido sem nenhuma ou uma fraca inteligência artificial.

A IA dá ao jogo o desafio atuando como um dos jogadores que se adapta às situações como também, em alguns casos, ao nível do oponente.

Deve-se também ter em mente que a teoria dos jogos é antiga como observamos em [Walker 95], data de antes de cristo e foi construída para estudar os jogos, os quais têm a origem tão antiga que nem é conhecida e a sua criação parece estar ligada à essência dos seres vivos, principalmente dos mais jovens.

Por todos os motivos exibidos neste trabalho e em toda a bibliografia por que ele se baseia, chega-se à conclusão de que é necessário um investimento na solução de jogos pois assim consegue-se que duas promissoras áreas da ciência avancem: a inteligência artificial e a teoria dos jogos.

Referências

[Britannica 02] Enciclopédia Britannica 2002. Versão em CD-ROM.

[Houaiss 01] Dicionário Houaiss 2001 Versão em CD-ROM.

[AJAX 02] Associação de Jogadores Amadores de Xadrez. História do Xadrez. Disponível utilizando o protocolo http em: http://www.ajaxclube.com.br/historia/historia.htm (Acessado em 15/09/02)

[O Dia 02] O Dia. História Do Tênis. Disponível utilizando o protocolo http em: http://odia.ig.com.br/sites/ataque/rolandgarros/historia.htm (Acessado em 30/09/02)

[Margames 02] Margames. A história dos videogames. Disponível utilizando o protocolo http em: http://www.margames.com.br/memoria/memo2.htm (Acessado em 25/09/02)

[Vargas 96] VARGAS, Flor de Maria Milagros Tapi. Dissertação submetida à Universidade Federal de Santa Catarina para a obtenção do Grau de Mestre em Engenharia. Disponível utilizando o protocolo http em http://www.eps.ufsc.br/disserta96/vargas/index/index.htm (Acessado em 30/09/02)

[Wikipedia 02] Wikipedia The Free Enciclopédia. Disponível utilizando o protocolo http em: http://www.wikipedia.org/wiki/Game_theory (Acessado em 01/10/02)

[Walker 95] Walker, Paul. An Outline of The History of Game Theory. Disponível utilizando protocolo http em: http://william-king.www.drexel.edu/top/class/histf.html. (Acessado 01/10/02)

[Fiplac 02] FIPLAC, Faculdades Integradas do Planalto Central. Inteligência Artificial. Disponível utilizando protocolo http em: http://www.oitavofiplac.kit.net/index_ia.htm e http://www.oitavofiplac.kit.net/ia/suplementos/indexsupl.html. (Acessado em 30/09/02) Observação: os arquivos devem ser baixados alguns em formatos Portable Document Format outros em PostScript.

[Kendall 01] KENDALL, Graham. Introduction to Artificial Intelligence - Blind Searches, 27/09/01. Disponível utilizando protocolo http em: http://www.cs.nott.ac.uk/~gxk/courses/g5aiai/003blindsearches/blind_searches.htm (Acesso em 02/10/02)

[BRESINA 98] BRESINA, John L. 1998. Stochastic Heuristic Search and Evaluation Methods for Constrained Optimization. Ph.D. Dissertation. Rutgers University, New Brunswick, NJ. Disponível via protocolo http em: http://ic.arc.nasa.gov/ic/projects/xfr/sampling/thesis/index.html (Acesso 02/10/02)

[Shook] SHOOK, John. William James – Filosofia. University of State of Oklahoma. Disponível utlizando protocolo http em: http://www.filosofia.pro.br/textos/william_james.htm.

[Zaro] ZARO Milton Antonio e TIMM, Maria Isabel. Desenvolvimento De Hipermídia Para Ensinar E Aumentar A Criatividade: Uma Experiência Pedagógica No Lmm: Laboratório De Medições Mecânicas/Ufrgs. Disponível utilizando protocolo http em: http://www.nmead.ufrgs.br/nmead/public2.htm

[Filho 98] FILHO, Plínio Cornélio. O MODELO DE SIMULAÇÃO DO GPCP-1: JOGO DO PLANEJAMENTO E CONTROLE DA PRODUÇÃO. Disponível utilizando protocolo http em: http://www.eps.ufsc.br/disserta98/plinio/

 

Last Updated on Tuesday, 01 July 2008 14:53