A inteligência artificial vem crescendo em alta velocidade nos últimos anos, e uma das áreas em que ela mais cresce, é a área dos games. Os games são uma das maiores fontes de entretenimento, e os investimentos em jogos são altíssimos e recompensadores, e por esse motivo o avanço da IA dos games cresce em alta velocidade.
Os jogos estão cada vez mais fantásticos e mais próximos da realidade, e isso graças aos estudos e melhorias na IA relacionada a eles. Podemos hoje, ter uma conversa longa com NPCs (non-player character ou Personagens não jogáveis), disputar uma corrida de alta velocidade em uma pista de quilômetros de distância contra vários adversários em jogos de corrida, encontrar jogos em que os personagens se esquivam ou se adaptam às condições do momento para combater contra ou com você, e ainda jogos de tabuleiro com uma capacidade incrível de criar jogadas as vezes melhores do que as que um ser humano criaria.
O foco da IA é mantido nas áreas da movimentação dos personagens, tomada de decisões e na estratégia. A IA dos jogos procura melhorar a diversão dos usuários através de uma boa coerência com o contexto do jogo gerando maior imersão dos jogadores.
Modelo simples, de alto nível, para integração de um modulo de IA em um jogo.
Referências:
http://www.oficinadanet.com.br/artigo/ciencia/o-que-e-inteligencia-artificial
Luger, Georde F. Inteligência artificial: estruturas e estratégias para solução de problemas complexos Porto alegre Bookmann, 2004.
“Inteligência Artificial (IA) é um ramo da ciência de computação que tem como foco elaborar dispositivos que simulem a capacidade de raciocínio humano.”
A Inteligência Artificial é um dos assuntos mais interessantes de serem tratados. No mundo ela está presente nos mais diversos meios, como robótica, filmes, máquinas fotográficas, corretores ortográficos, e muitos outros. Mas e nos Jogos Eletrônicos, como ela é aplicada?
Com o avanço da tecnologia, os videogames estão cada vez mais comuns na sociedade, possuindo até mesmo campeonatos com prêmios milhonários.
O setor de videogames é hoje um dos setores mais rentáveis do entretenimento. De acordo com uma pesquisa do instituo New Zoo, o Brasil está em 11º lugar no ranking mundial e em 1º lugar na América Latina. Isso torna o mercado de games muito mais atraente, e ao mesmo tempo desafiador. [1]
Fora isso, os games atuamente estão em um patamar artístico e realistico impensável a anos atrás. Com o avanço da tecnologia, a qualidade gráfica dos jogos estão cada vez melhor, e o realismo cresce junto. Hoje temos jogos de simuladores de corrida extremamente reais, como o jogo Gran Turismo, e outros jogos que visam simular a vida cotidiana, como o jogo The Sims, onde é possivel trabalhar, construir um casa, se casar, ter filhos, etc. Já outros possuem enredos incriveis, e que mais se parecem com um filme.
Mas por trás disso tudo, temos um elemento que é essêncial em praticamente todos eles: a Inteligência Artificial. É a partir dela que são definidas as particularidades do jogo, a dificuldade, como os inimigos vão se comportar, e muitos mais.
Abaixo citaremos vários meios onde a Inteligência Artificial é utilizada no mundo dos games, desde as técnicas mais usadas em cada gênero de jogo como também sistemas inteligentes que são capazes de jogar sozinhos, sem a interferência humana.
Programas inteligentes
Nomeado de Piglet, o programa de inteligência artificial, desenvolvido por Daniel Shumway, é capaz de aprender a jogar qualquer jogo, e também de simular o modo de agir particular do ser humano.
A versão atual do projeto, consegue controlar jogos das plataformas Game Boy e Game Boy Color. Ele foi criado a partir da linguagem de programação Lua, e interage com o cenário e os personagens com o propósito de cumprir um objetivo.
A estratégia da IA é alterada conforme as partidas, se, por exemplo, ela se depara com um obstáculo que não consegue ultrapassar, o mesmo será evitado nas próximas partidas ou uma forma diferente de atravessá-lo será encontrada.
O software também é programado para errar de propósito, buscando imitar a forma humana e de aumentar a naturalidade.
“Imagine que você precisa jogar com os olhos vendados e que um de seus amigos fica responsável por lhe dizer o que acontece toda a vez em que um botão é pressionado. Sua única interface será, assim, a descrição feita por seu amigo. Se algo mudar no cenário, um alerta será feito por ele. E, apesar de soar de um jeito estranho, este tipo de ligação funciona surpreendentemente bem”, observa Shumway.[2]
Outro projeto parecido com o projeto Piglet é o que está sendo trabalhado por um universidade da Alemanha, onde foi desenvolvido um método de I.A. para que o protagonista Mario, do jogo Super Mario World, jogasse sozinho.
A equipe utilizou a ferramente Sphinx, da universidade Carnegie-Mellon, para que o personagem reconhecesse as falas, e reter todos os conhecimentos que lhe são passados.
O seu comportamente é baseado em estatísticas internas como saciedade e curiosidade. Quando ele está com “fome”, Mario passa a pegar moedas, e, quando se sente curioso, ele explora o cenário ativamente. Dessa forma ele aprendeu a utilizar elementos do cenário e ultrapassar obstáculos.
Em certo ponto foi ordenado que ao personagem matar um Goomba (inimigos do jogo), sem saber nada sobre ele. Ao pular sobre ele, e perceber que o inimigo morreu, Mario aprendeu que esse era um resultado satisfatório e que traria resultados. [3]
Mais sobre o projeto pode ser visto no vídeo publicado no Youtube.
Muitas pessoas desconhecem esse fato, mas a gigante Google, também possui um projeto na área de Inteligência Artificial aplicada aos jogos.
A aproximadamente um ano atrás, ela comprou a startup britânica DeepMind, especializada em inteligência artificial, por aproxidamente US$ 500 milhões.
Mais recentemente a I. A. desenvolvida pela DeepMind foi aplicada em 49 jogos de Atari 2600, e o resultado obtido nunca foi tão “humano”.
O aprendizado foi feito da seguinte forma: o sistema foi instruido sobre como jogar apenas um dos jogos, e os outros 48 restante foi aprendido por conta própria na base da tentativa e erro e do registro de padrões.
Esse forma de aprendizado é bem semelhante com a dos humanos, mesmo com as limitações da I.A.
O pradrão de aprendizado do DeepMind se baseia nos resultados satisfatórios obtidos, como uma morte evitada ou uma maior pontução obtida durante as tentativas.
Abaixo um vídeo do DeepMind jogando o jogo BreakOut pela primeira vez, onde é possivel observar que durante as primeiras jogando ocorrem muitos erros nas jogadas, e que ao final, a I.A. já desenvolveu uma tática para jogar de forma mais precisa com base nos padrões obtidos.
Porém, uma das principais limitações do DeepMind é a “memória a curto prazo”, pois ele é incapaz de fazer planos para mais que alguns segundo a frente, sabendo lidar apenas com táticas de recompensa imediata.
É bem provável que em versões futuras isso mude, e o DeepMind consiga traçar estratégias de longo prazo, e desse forma veremos cada vez a I.A. se aprimorar e trazer beneficios para os mais diversos meios do nosso dia a dia. [4]
A Inteligência Artificial no desenvolvimento de Jogos
No mundo dos jogos eletrônicos a Inteligência Artificial está presente em praticamente todos os lugares. Mesmo os jogos mais simples possuem algum tipo de inteligência, na maioria das vezes, buscando dificultar o jogo.
O exemplo mais claro são os jogos de luta. Neles é possível notar que nas primeiras partidas, tudo parece ser muito fácil, e, conforme o jogador avança, tudo fica mais dificil.
Isso acontece pois máquina começa a identificar os padrões utilizados pelo jogador, e então encontra uma forma de combatê-lo, utilizando defesas e contra-ataques, com um tempo de resposta extremamente alto, que nenhum ser humano seria capaz de acompanhar.
Os títulos de tiro em primeira pessoa (FPS – First Person Shooter) são outros que possuem bastante usa da Inteligência artificial. Nas primeiras versão do jogo Counter Strike – famoso jogo do gênero – os BOTS – inimigos controlados pela máquina – possuiam pouca inteligência, podendo algumas vezes ficam em campo aberto totalmente desprotegidos. Já nas versões mais atuais, os inimigos conseguem utilizar objetos do cenário e detectar a melhor estratégia para derrotar os jogadores. [5]
Técnicas de Inteligência Artificial
FPS (Fisrt Person Shooter)
As técnicas mais utilizas nos jogos FPS são as de máquinas de estado finita (FSM – Finite State Machine) e a Lógia Fuzzy.
Segundo Karlsson (2005, p.19) Uma máquina de estados “é basicamente composto por um conjunto de estados e um conjunto de regras de transição entres estes estados”, Karlsson (2005, p19). Ou seja, o personagem está configurado com um série de regras e possui regras de transição para ver se o personagem deve alterar seu estado inicial, como por exemplo, se ele viu um oponente e se vale a pena ir atrás dele.
Adicionalmente existe dois tipos de FSM, as do tipo determinístico (AFD) e não-determinístico (AFN). Onde, no determinístico, para cada estado há exatamente uma transição para cada entrada possível, e no não-determinístico, pode haver nenhuma, uma ou mais. A desvatangem da FSM são os comportamentos repetitivos (“quanto mais complexo for o ambiente, aumenta o número de estados e transições na qual o FSM terá de prever” (Karlsson, 2006)).
Já á Logica Fuzzy ou Lógica Difusa permite representar valores além da lógica clássica, representa somente por 0 (FALS) e 1 (VERDADEIRO), permitidando representar vários eventos não contáveis (ou imprecisos), como por exemplo 0,5 (“TALVEZ).
Uma possibilidade é utilizar a lógica Fuzzy e a FSM, criando as Fuzzy FSMs (FuSMs), criando assim máquina de estado finitas com lógica Fuzzy, dando mais “inteligência” para os oponentes contralados pela máquina.
Jogos de Estratégia
A inteligência em jogos desse gênero pode ser divida em basicamente dois níveis: um nível com os problema de navegação de unidades, onde geralmente é usado um algoritmo do tipo A*. Em segundo nível o planejamento estratégico/tático, que determina o ritmo de produção de elementos do jogo, como unidades e instalações, e também a frequência dos ataques do jogador.
Para isso, os métodos utilizados em geral são simplesmente máquinas de estado aliadas a sistemas baseados em regras parametrizáveis de forma a permitir o ajuste da dificuldade e jogabilidade. (TATAI, 2003, p. 31)
Outra técnica que pode ser utilizada, segundo VIERIA (2005, p. 13) é o sistema baseado em planejamento. O planejamento de IA nos jogos é o armazenamento de “planos de ação”, e faz com que o usuário escolha o plano mais adequado em uma situação. Uma vantagem desta técnica é que as ações do personagem não são tão repetitivas.
Jogos de Corrida
Esse gênero de jogo é outro dentre os mais jogados no mundo. Existem franquias para os mais diversos gostos, como os da franquia Need For Speed, que são do tipo arcade e para jogadores mais casuais, e também os da franquia Gran Turismo, em que o foco é o simulação, onde é possivel controlar a troca de marchas, o tipo de pneu para determinada clima ou pista, e até a economia de gasolina, para que não acabe durante a corrida.
Uma das técnicas que podem ser utilizadas é a de algoritmos genéticos (AG). Um algoritmo genético são uma classe de algoritmo evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade, mutação, seleção natural, e recombinação.
Em um jogo de corrida, a aplicação desse tipo de algoritmo é util para criar vários tipo de carros, baseando-se em um deles. Isso diminui o tempo gasto para criação e aumenta a variedade de elementos dentro do jogo.
Jogos de Futebol
Os jogos de futebol são um dos tipos mais populares no Brasil, afinal, é o esporte mais adorado no país.
Uma das técnicas aplicadas em jogos de futebol é a de redes neurais. Elas são redes computadorizadas onde a sua estrutura é similar a um cérebro humano, tendo nós de rede (neurônios) e conexões entre os nós. A vantagem na rede neural é que ela pode aprender e amarzenar informações para uso posterior. Num game de futebol, a aplicação de redes neurais pode ser utilizada para que “jogadores de futebol aprendam a interceptar a bola durante uma partida” (KARLSSON, 2006, p.33)
Outra técnica é a Fuzzy, onde já comentamos sobre seu uso nos jogos FPS. Ela pode ser aplicada por exemplo para definir se durante uma cobrança de pênalti o chute foi forte ou não.
Técnicas Comuns
Além das técnicas já apresentadas, pode destacar outras que são comuns em jogos de vários gêneros.
Algoritmos de Path-finding – Na maior parte dos jogos, os personagens precisam saber “o que fazer” ou qual trajeto seguir. Para isso eles precisam ter noção do espaço em que estão. Um BUG recorrente que acontece em vários jogos são personagens que atravessam paredes ou até mesmo objetos que deveriam impossibilitá-los de prosseguir. É justamente nesse ponto que é usado o Path-Fiding.
Os programadores aplicam algoritmos de path-finding (ou definição de caminhos) para determinar a rota que o personagem deverá traçar, para que não ocorram problemas durante o jogo.
Além disso, o algoritmo deverá calcular outros possíveis objetos que podem ser gerados durante o decorrer do jogo, como outros personagens ou até mesmo novos obstáculos gerados durante uma alteração no ambiente. Uma situação comum seria onde um prédio é derrubado durante uma partida, logo, os personagens que antes deveriam dar a volta, podem agora caminhar sobre os destroços do mesmo.
Com isso, podemos notar que o Path-Finding é um dos algoritmos mais importantes no desenvolvimento de jogos.
Agentes – Uma agente inteligente pode ser um personagem que pode raciocinar e tomar suas próprias decisões, baseado tanto em regras quanto no cenário do jogos. Além disso, é possível criar emoções que podem deixar um personagem mais realista.
Segundo Karlsson (2005, p. 39), uma abordagem para se utilizar em agentes é a arquitetura BDI, baseada em 3 conceitos: crenças, desejos e intenções.
Na abordagem filosófica, crença é um conhecimento na qual a pessoa acredita, como a religiosidade. São regras que as pessoas tenta seguir para se sentir bem.
No conceito de agentes num sistema computadorizado, as crenças são regras que o agente se baseia para executar suas ações, e mesmo que a crença seja “inválida”, o agente ainda continua a crer nela e a utiliza-lá para executar suas ações (Karlsson, 2005).
Os desejos são objetivos que o agente quer (“deseja”) e intenções são regras na qual o agente pode seguir (como por exemplo, entrar em um casa pela janela).
Ao projetar um agente baseando-se no modelo BDI, são especificados suas crenças e desejos iniciais e a escolha das intenções e, conseqüentemente, das ações a serem tomadas, fica a cargo do agente (dentro do espaço de ações possíveis) o que pode acarretar em novos problemas. (Karlsson, 2005). [6]
Referências:
- http://jogos.uol.com.br/ultimas-noticias/2014/06/25/brasil-sera-maior-mercado-de-games-na-america-latina-em-2014-diz-pesquisa.htm – 25/06/2014 – Data de acesso: 02/06/2015
- http://www.tecmundo.com.br/inteligencia-artificial/69168-ajoelhem-humanos-programa-ia-aprende-jogar-games-criado.htm – 10/12/2014 – Matéria escrita por Ramon Voltolini – Data de acesso: 30/05/2015.
- http://www.tecmundo.com.br/inteligencia-artificial/72828-projeto-coloca-inteligencia-artificial-mario-sim-video.htm – 20/04/2015 – Matéria escrita por Akira Suzuki – Data de acesso: 30/05/2015.
- http://www.tecmundo.com.br/inteligencia-artificial/75568-inteligencia-artificial-google-aprende-jogar-titulos-atari-2600.htm – Materia escrita por Carlos Eduardo Ferreia – 26/02/2015 – Data de Acesso: 30/05/2015.
- http://www.tecmundo.com.br/futuro/7725-inteligencia-artificial-mitos-e-verdades.htm – 14/06/2011 – Materia escrita por Felipe Gugelmin – Data de acesso: 30/05/2015.
- http://gamehall.uol.com.br/selectgame/artigos-e-tutoriais/estado-da-arte-da-inteligencia-artificial-para-jogos-eletronicos – Data de acesso: 31/05/2015.
História da Inteligência Artificial
A construção de maquinas capazes de executar tarefas consideradas inteligentes já é bastante antiga. Seu desenvolvimento é dado com hardwares disponíveis em cada época. Como o caso do Ábaco e das primeiras calculadoras mecânicas.
O interesse por tal criação era tão grande que surgiram vários casos de fraudes, como exemplo do jogador de xadrez. Tratava-se de uma caixa de madeira, com um busto de um turco em escala natural e que era responsável pelos movimentos das peças em um tabuleiro em uma mesa. Surgiram varias explicações fantásticas para seu funcionamento só que o fato é que existia uma pessoa em seu interior que tomava as decisões do jogo. Entre outros também foram criados como, por exemplo, o pato digeridor e o flautista.
Porem o desejo da criação de uma maquina que realmente fosse capaz de jogar xadrez continuou gerando interesse que em 1967, o programa de computador MacHack, desenvolvido pelo MIT (Massachusetts Institute of Technology) venceu o filosofo Dreyfus. Em 1997, o campeão mundial de xadrez Garry Kasparov, disputou seis partidas com o computador Deep-Blue (256 cpus), obtendo três vitorias, dois empates, o que representa um resultado muito significativo para as maquinas.
O termo IA é razoavelmente novo, tendo surgido em 1956, a partir de uma reunião com cientistas de varias áreas do conhecimento, interessados na criação de maquinas inteligentes e também no modo como elas afetariam os processos existentes. O MIT propôs a divisão da historia da IA a três épocas:
Época clássica (1956-1970) – Sua finalidade era simular a inteligência humana, o que levou grande quantidade de fracassos, devido à complexidade computacional dos problemas envolvidos. Programa da época GPS (General Problem Solver);
Época romântica (1970-1980) – Sua finalidade era simular o comportamento humano em situações restritas, e a formalização matemática passou a ser mais exigida. Vários sistema especialistas foram implementados com sucesso, porem, novamente, a dificuldade de adaptação e subestimação da quantidade de informação necessária para resolver problemas, geraram novos fracassos;
Época moderna (1980-1990) – dificuldade de sistemas em resolver problemas específicos dando maior ênfase às ferramentas para o desenvolvimento de sistemas especialistas ofereceu ao usuário maior facilidade para projetar sistemas e assim tratar de problemas mais específicos.
O que fica claro em cada época é uma sequencia de mudanças e metas que deveriam ser atingidas. Os objetivos sugeridos sofrem influencia dos diferentes grupos de pesquisadores da IA, que acreditam em duas possibilidades e as denominam em IA forte e IA fraca. No primeiro caso as maquinas serão capazes de pensar como uma pessoa, e a segunda acreditam apenas na possibilidade das maquinas simularem o comportamento humano porem sem real consciência de suas ações.
Apesar de tantas dificuldades encontradas, a IA apresentou um grande desenvolvimento durante a sua trajetória. Alguns fatos marcantes que estão bastante relacionados com o desenvolvimento do próprio computador.
384-322: Aristóteles formula um conjunto de leis que governam o pensamento
1500: Leonardo da Vince projeta uma calculadora mecânica
1739: Hume introduz o principio da indução
1818: Mary Shelley publica o romance Frankenstein
1835: o relé elétrico inventado por Joseph Henry
1847: George Boole desenvolve a lógica simbólica e, em seguida, a lógica binária
1879: Frege desenvolve o calculo dos predicados
1917: Karel Capek cria o termo “Robot”
1930: Shannomn demonstra a lógica de Boole utilizando circuitos elétricos
1937: Turing publica “sobre números computáveis” (Maquina de Turing)
1940: Atanosoff e Berry criam o primeiro computador eletrônico, o ABC
1940: Robinson, computador baseado em relés, decodificado códigos binários
1943: “Colossus” usava válvulas para ajudar os britânicos a quebrar códigos alemães
1943: McCulloch e Pitts propõem uma arquitetura para a rede neural
1945: Vannevar Bush publica um estudo sobre o modo como as pessoas pensam
1946: Construido o primeiro computador digital programável “ENIAC”
1947: Schockley, Brittain e Ardeen inventam o transmissor no Bell Labs
1950: Isaac Asimov cria a peça “Eu, Robô”
1950: Shannon propõe um programa de xadrez
1950: Turing propõe um Teste para avaliar a inteligência dos computadores
1955: Newell, Shaw e Simon desenvolvem a “IPL-11”, a primeira linguagem de IA
1956: CIA consolida o projeto GAT maquina de tradução
1956: Ulam cria o “MANIC I”, um programa de xadrez capaz de vencer humanos
1956: Criado o termo “Inteligência Artificial”
1957: Criado o Solucionador de Problemas Gerais (GPS)
1958: Invenção do circuito integrado
1959: Minsky e McCarthy criam o Laboratório de Inteligência Artificial do MIT
1959: Programa de xadrez de Samuel vence bons Jogadores
1960: Computadores de Defesa enganam-se confundindo a Lua com mísseis
1962: Surge a primeira indústria de robôs comerciais
1963: Sistema SABRE (America Airlines) é o primeiro sistema de reservas aéreas
1965: Iniciado o projeto do sistema especialista DENDRAL
1966: Weizenbaum cria o programa ELIZA, que se comporta como um psicanalista
1970: É criado o PROLOG (Colmeraurer)
1971: Desenvolvido o primeiro Microprocessador (Intel 4004)
1972: Dreyfus publica “O que o computador não pode fazer”
1974: Shortliffe publica tese sobre o MYCIN, sistema especialista na área médica
1974: Primeiro computador contralado por computador
1975: Primeiro computador pessoal – Altair 8800 (256 bytes de memória)
1978: O sistema especialista Prospector realiza uma descoberta importante
1979: Associação medica americana afirma que o MYCIN é tão bom quanto o medico humano
1981: IBM introduz o computador pessoal (PC)
1981: Kazuhiro Fuchi anuncia o Projeto japonês para a quinta geração
1982: John Hopfield ressuscita as redes neurais
1983: Asimov escreve “Robots of Dawn”
1984: Comunidade europeia inicia o programa ESPIRIT
1984: robô “Wabot-2” toca um órgão a partir de partituras
1985: Minsky publica “A sociedade da mente”
1986: Robô de Anderson vence partida de ping-pong disputada contra os humanos
1986: A polícia de Dallas usa um robô para invadir um apartamento
1987: É atingida a marca de 1900 sistemas especializados em operação
1987: O sistema XCON configura computadores, fazendo o trabalho de 300 pessoas
1992: Projeto da quinta geração japonesa é finalizado
2005: Sistema CogVis deduz as regras de um jogo a partir da observação
2008: Robô assistente de cirurgia é usado em Hospital de São Paulo
2008: Robô operário é usado no Japão
Historia da Inteligência Artificial nos Jogos
A história inicial dos jogos mecânicos foi marcada por numerosas fraudes. A mais notória dessas fraudes foi a do Barão Wolfgang Von Kempelen (1734-1804, “o turco”), um suposto autômato jogador de xadrez que derrotou o Napoleão antes de ser exposto como um armário de truques de mágica que alojava um especialista humano em xadrez (consulta Levitt, 2000). Ele jogou de 1769 até 1854. Em 1846, Charles Babbage (que tinha ficado fascinado com o turco) parece ter colaborado para a primeira discussão séria sobre a viabilidade dos jogos de xadrez e damas por computador (Morrison e Morrison, 1961). Ele também projetou, mas não construiu uma máquina de uso especial para jogar o jogo da velha. A primeira máquina para jogos verdadeira foi construída por volta de 1890 pelo engenheiro espanhol Leonardo Torres y Quevedo. Ele se especializou no final do jogo de xadrez “KRK” (rei e torre contra rei), garantindo uma vitória com rei e torre a partir de qualquer posição.
Konrad Zuse (1965), primeira pessoa a projetar um computador programável, desenvolveu ideias bastante detalhadas sobre a possibilidade de jogar xadrez por computador.
Em 1951, Alan Turing escreveu o primeiro programa de computador capaz de jogar uma partida de xadrez completa (consulte Turing et al., 1953). Porém, o programa de Turing nunca funcionou de fato em um computador; ele foi testado por simulação manual contra um jogador humano muito fraco, que o derrotou. Enquanto isso, D. G. Prinz (1952) escreveu e realmente executou um programa que resolvia problemas de xadrez, embora não jogasse uma partida completa. Alex Bernstein escreveu o primeiro programa a jogar uma partida completa de xadrez padrão (Bernstein e Roberts, 1958; Bernstein et al., 1958).
John McCarthy concebeu a ideia de busca alfa-beta em 1956, embora não a tivesse publicado. O programa de xadrez NSS (Newell et al., 1958) usava uma versão simplificada da alfa-beta; ele foi o primeiro programa de xadrez a usá-la. De acordo com Nilsson (1971), o programa de jogo de damas de Arthur Samuel (Samuel, 1959, 1967) também utilizava alfa-beta, embora não o mencionasse nos relatórios publicados sobre o sistema. Os documentos que descrevem alfa-beta foram publicados no início da década de 1960 (Hart e Edwards, 1961; Brudno, 1963; Slagle, 1963b). Uma implementação completa de alfa-beta é descrita por Slagle e Dixon (1969) em um programa para o jogo Kalah. Alfa-beta também foi usada pelo programa de xadrez “Kotok-McCarthy” escrito por um aluno de John McCarthy (Kotok, 1952).
A primeira partida de xadrez por computador apresentou o programa de Kotok-McCarthy e o programa “ITEP” escrito em meados da década de 1960 no Instituto de Física Teórica e Experimental de Moscou (Adelson-Velsky et al., 1970). Essa partida intercontinental foi disputada por telégrafo. Ela terminou com a vitória de 3 a 1 para o programa do ITEP em 1967. O primeiro programa de xadrez a competir com sucesso contra seres humanos foi o MacHack seis (Greenblatt et al., 1967).
A partir do primeiro ACM North American Computer-Chess Championship em 1970, a competição entre os programas de xadrez se tornou séria.
Em 1974, o primeiro World Computer-Chess Championship foi realizado em Estocolmo e foi vencido por Kaissa (Adelson-Velsky et al., 1975), outro programa do ITEP. Kaissa utilizou a abordagem muito mais direta de busca alfa-beta exaustiva combinada com busca de quiescência. O domínio dessa abordagem foi confirmado pela vitória convincente do programa CHESS 4.6 no World Computer-Chess Championship de 1977. O CHESS 4.6 examinava até 400.000 posições por movimento e tinha a classificação 1.900.
Uma versão posterior do MacHack 6 de Greenblatt foi o primeiro programa de xadrez a funcionar em hardware personalizado, projetado especificamente para xadrez (Moussouris et al. 1979), mas o primeiro programa a alcançar sucesso notável pelo uso de hardware personalizado foi Belle (Condon e Thompson, 1982). O hardware de geração de movimentos e avaliação de posições de Belle permitia que ele explorasse vários milhões de posições por movimento. O Belle alcançou a classificação 2.250, tornando-se o primeiro programa em nível de mestre. O sistema HITECH, também um computador de uso especial, foi projetado pelo primeiro campeão mundial de xadrez por correspondência Hans Berliner e por seu aluno Carl Ebeling na CMU com a finalidade de permitir o cálculo rápido de funções de avaliação (Ebeling, 1987; Berliner e Ebeling, 1989). Gerando cerca de 10 milhões de posições por movimento, o HITECH se tornou o campeão mundial norte-americano de computadores em 1985 e foi o primeiro programa a derrotar um mestre humano, em 1987.
O algortimo expectiminimax foi proposto por Donal Michie (1966), embora – é claro – ele decorra diretamente dos princípios de avaliação de árvore de jogo criados por Von Neumann e Morgenstern. Bruce Ballard (1983) estendeu a poda alfa-beta para cobrir árvores com nós de acaso. O primeiro programa gamão bem-sucedido foi o BKG (Berliner, 1977, 1980b). Esse foi o primeiro programa derrotar um campeão mundial humano em um jogo clássico importante (Berliner, 1980a). Berliner reconheceu de imediato que essa foi uma partida de exibição muito breve (e não uma disputa pelo campeonato mundial) e que o BKG teve muita sorte com os dados.
O jogo de damas em vez do xadrez, foi o primeiro dos jogos clássicos disputado inteiramente por um computador. Christopher Strachey (1952) escreveu o primeiro programa funcional para jogo de damas. Schaeffer (1977) apresenta um relatório completo e altamente legível do desenvolvimento de seu programa Chinook, campeão mundial de jogo de damas.
Os primeiros programas para jogar Go foram desenvolvidos um pouco mais tarde que os de damas e xadrez (Lefkovitz, 1960; Remus, 1962) e progrediram mais lentamente. Ryder (1971) utilizou uma abordagem baseada em busca pura com uma variedade de métodos de poda seletiva para superar o fator de ramificação. Zobrist (1970) utilizou regras de condição-ação para sugerir movimentos plausíveis ao surgirem padrões conhecidos. Reitman e Wilcox (1979) combinaram regras e busca para obter um bom efeito, e os programas mais modernos seguiram essa abordagem híbrida. Müller (2002) resume o estado da arte do jogo Go por computador e fornece muitas referências. Anshelevich (2000) emprega técnicas relacionadas para o jogo de Hex. O Computer Go Newsletter, publicado pela Compute Go Association, descreve os desenvolvimentos atuais.
Referências
Artero, Almir Olivette – Inteligência Artificial: teoria e prática / Almir Olivette Artero. – São Paulo : Editora Livraria da Física, 2009.
Russell, Stuart J. (Stuart Jonathan) – Inteligência artificial: tradução da segunda edição / Stuart Russell, Peter Norvig ; tradução de PubliCare Consultoria. – Rio de Janeiro: Elsevier, 2004 – 12ª Reimpressão.
Links Úteis
http://pt.wikipedia.org/wiki/Minimax
http://finslab.com/enciclopedia/letra-e/expectiminimax-arvore.php
A inteligência artificial é parte da ciência da computação e inclui o uso das estruturas de dados, Algoritmos e as linguagens e técnicas de programação, para representar o conhecimento, aplicar esse conhecimento através das linguagens e implementá-las.
Embora sabermos reconhecer um comportamento inteligente ao ver, é improvável definir a inteligência o suficiente para auxiliar na avaliação de um programa de computador supostamente inteligente, capturando a vitalidade e a complexidade da mente humana.[1]
Inteligência artificial (IA) tem atraído muitos pesquisadores ao longo de sua história e, embora, a ideia possa parecer até simples, principalmente, por causa da sua ampla divulgação em filmes de ficção científica, que a todo momento apresenta robôs e humanoides com um comportamento inteligente, a criação de máquinas realmente inteligentes continua sendo um grande desafio.
A inteligência artificial é uma forma de simular a inteligência natural (IN), e por isso, grandes partes da publicação na área apresentam ao leitor algumas definições para a (IN). Como tentativa de lançar alguma luz sobre o seu mecanismo de funcionamento.
Um computador pode ser considerado inteligente se possui qualquer uma das habilidades mentais que fazem uma pessoa ser considerada inteligente, tais como: a capacidade de racionar e de realizar inferências; a capacidade de resolver problemas; a capacidade de acumular conhecimento; a capacidade de falar línguas humanas; dentre outras coisas.
As principais áreas de inteligência artificial são:
- Robótica;
- Visão por computador;
- Processamento de linguagem natural;
- Sistemas especialistas;
- Reconhecimento de padrões;
- Base de dados inteligentes;
- Prova de teoremas;
- Jogos;
A atuação em jogos envolve o uso de estratégia a raciocínio, próprios de seres inteligentes. Assim ao longo dos anos, a área de jogos tem sido um laboratório importante para o desenvolvimento de várias técnicas de IA. Atualmente, vários jogos de ultima geração agregam técnicas de IA, o que significa que os personagens controlados pela máquina tem o seu comportamento alterado dependendo do tipo de comportamento do usuário ou ainda modificam sua estratégia após uma derrota, caracterizando um aprendizado com a sua própria experiência.[2]
Em IA, os “jogos” normalmente são de um tipo bastante especializado. Em ambientes determinísticos completamente observáveis em que existem dois agentes em que as ações se alternam, onde os valores no fim do jogo são sempre iguais e opostos. Por exemplo, se um jogador ganha um jogo de xadrez (+1), o outro necessariamente perde (-1).
A natureza abstrata dos jogos os torna interessantes para estudo. Dependendo do jogo, é necessária apenas uma pequena quantidade de ações, com regras precisas. Já jogos como o hóquei, têm descrições muito mais complexas, e uma quantidade muito maior de ações possíveis de se executar e regras imprecisas.
A participação em jogos foi uma das primeiras tarefas empreendidas em IA. Por volta de 1950, quase ao mesmo tempo em que os computadores se tornaram programáveis, o xadrez foi estudado por Konrad Zuse (o criador da teoria da informação), por Norbert Wiener (o criador da moderna teoria de controle) e por Alan Turing. Desde então, houve um progresso constante no padrão dos jogos, até o ponto em que as máquinas ultrapassaram os seres humanos nos jogos de damas e Othello, derrotaram campeões humanos (embora não todas as vezes) em xadrez e gamão, e são competitivos em muitos outros jogos. A principal exceção é o Go, em que computador funcionam no nível amador.
A primeira máquina para jogos verdadeira foi construída por volta de 1890 pelo engenheiro espanhol Leonardo Torres y Quevedo. Ele se especializou no final do jogo de xadrez “KRK” (rei e torre contra rei), garantindo uma vitória com rei e torre a partir de qualquer posição.
Em 1951, Alan Turing escreveu o primeiro programa de computador capaz de jogar uma partida de xadrez completa. Porém, o programa de Turing nunca funcionou de fato em um computador; ele foi testado por simulação manual contra um jogador humano muito fraco, que o derrotou. Enquanto isso, D. G. Prinz (1952) escreveu e realmente executou um programa que resolvia problemas de xadrez, embora não jogasse uma partida completa. Alex Bernstein escreveu o primeiro programa a jogar uma partida completa de xadrez padrão (Bernstein e Roberts, 1958; Bernstein et al., 1958).[3]
- Luger, George F. Inteligência Artificial: estruturas e estratégias para a solução de problemas; Porto Alegre: Bookmann, 2004
- Artero, Almir Olivette – Inteligência Artificial: teórica e prática /
Almir Olivette Artero – São Paulo: Editora Livraria da Física, 2009 - Russel, Stuart J. (Stuart Jonathan) – Inteligência artificial : tradução da segunda edição / Stuart Russell, Peter Norvig – Rio de Janeiro, 2004.
Inteligência Artificial - Games 