sexta-feira, 18 de janeiro de 2013

Estrutura da Inteligência Artificial Aplicada no Jogo Othello


Olá a todos
Em um comentário no meu blog o leitor e jogador Bruno me apresentou um link de um artigo feito por alunos da faculdade Unicamp , que falava sobre Inteligência Artificial usando o jogo Othello como plataforma , e eu tinha já adiantado que futuramente faria uma postagem sobre o tema , e esse dia chegou . Há um tempo eu fiz uma postagem sobre IA , foi logo no meu primeiro ano de blog , e eu achei que deixei até bem elucidado os conceitos básicos de operação de um programa , mas vejo agora nessa postagem a oportunidade de agregar mais alguns conhecimentos há vocês .
Ao contrário da minha primeira postagem sobre o tema , dessa vez eu não vou me alongar muito no assunto , tentarei ser um pouco mais sucinto . Vou falar somente da estrutura básica do estilo e tipo de programa que foi elaborado pelos alunos da Universidade , para maiores esclarecimentos deixarei alguns links abaixo na postagem , inclusive o link da minha primeira postagem sobre IA dos programas de Othello .
O artigo foca em três tópicos principais , são eles :
Heurística MiniMax Alpha-Beta Pruning
O que são eles ?
Heurística
Vamos começar pela Heurística , que é basicamente uma forma empírica de descobrimento dentro do aparato do intelecto humano ( Até onde sabemos por enquanto ) envolve raciocínio intuitivo dentro de um escopo onde prevalecem informações incompletas . E como isso se aplica dentro de uma “ máquina “ de jogar Othello ?
Não é difícil imaginar como , é só fazer uma analogia dentro da psicologia humana , de como usamos heurística no nosso dia a dia e nem nos damos conta , por exemplo : Vamos supor que você tem que sair de casa às 12h00 para ir trabalhar , levando em consideração que o seu carro está na oficina e você terá que ir a pé até a estação de trem ou ônibus mais próxima da sua casa , porém você olha para o céu e ele está nublado . O que fazer ? Você simplesmente pode se lembrar que no dia anterior começou a chover por volta das 12h30 , e você olha para o céu de novo e calcula que vai começar a chover mais ou menos há essa hora , mas tardar umas 12h40/50 , então você pega o guarda-chuva e sai para trabalhar , levando é claro um bilhete ou o dinheiro da condução . Isso que você acabou de fazer foi bolar uma estratégia para não se molhar com a chuva e não ficar sem transporte para ir trabalhar , isso é uma forma de Heurística . ( É claro que esse tema vai muito além do que isso , eu só estou querendo fornecer uma ideia geral e simples do que é uma Heurística na sua estrutura mais básica , vocês vão precisar disso para entender o que vou dizer a diante ) .
Bom , dentro de um programa de Othello não chove e nem tem carro na oficina e muito menos trem ou ônibus , então como formar uma estratégia para vencer no jogo Othello ? Simples , é só saber qual são as propriedades do jogo , e para se usar a Heurística no Othello basta fomentar os seguintes tópicos :
1 – Fase do Jogo
2 – Forçar cantos e potenciais
3 – A estabilidade de canto
4 – Estabilidade borda
5 – A estabilidade interior
6 – Mobilidade
7 – Vantagem de peças .
A partir dessas 7 variáveis ( Que são as possibilidades dentro desse mundo de bits , elas são nossa chuva , trânsito , trem , ônibus , horas , guarda-chuva e etc ) é que formamos a nossa base para agir sobre um plano de ataque e defesa , defesa essa que vai ficar por conta da MiniMax que trato a seguir .
MiniMax
Minimax seria a capacidade de tomar decisões prevendo o menor número de perdas possíveis , sei muito bem que isso tem ligação com a famosa Teoria dos Jogos que é aplicável em vários ramos dentro do conhecimento humano como Matemática , Filosofia , Ciência Militar , Engenharia , Ética e etc .
Mas vamos focar na sua vertente virtual , que dentro de um programa tem a missão de minimizar as perdas , dentro do Othello seria a capacidade de proteger o maior número de peças possíveis , e ao mesmo tempo que se defende consegue abrir vantagem sobre o oponente , até quem sabe uma possível vitória .
MiniMax Para Othello
Assim como a Heurística dentro da IA , a MiniMax também tem os seus tópicos , são eles :
( Copiadas na integra do artigo )
1 – Informação completa : Não há dados do jogo escondidos 2 – Determinístico : Uma ação determina uma mudança do estado do jogo , sem influência randômica . 3 – Baseado em Rodadas 4 – Temo Limitado : Nosso algoritmo não poderá ficar pensando por muito tempo .
Traduzindo tudo isso , a primeira seria a informação de que não há coisas escondidas no jogo Othello igual um jogo de baralho , pôquer , dominó e etc
O segundo onde diz que é determinista , e isso quer dizer que assim como um sistema caótico uma peça pode mudar todo o caminho de um jogo , igual a um “ Efeito Borboleta “ com uma pequena atitude você pode mudar todo o final . Mas sem se abster das regras simples , e não há regras que o tornam imprevisível como por exemplo os jogos onde se utiliza dados . ( O dado de 6 lados mesmo )
O terceiro é simples , é um jogo baseado em alternações de vez , uma vez é um jogador , na outra vez é o outro jogador , ao menos que alguém passe .
O quarto diz que o programa tem que ter um tempo mínimo de cálculo , pois ninguém está disponível para uma partida que dure horas .
Pronto , temos o arquétipo de um bom programa de Othello , agora se une a Heurística mais a Minimax para obter uma jogada boa , sabendo onde devemos focar para atacar e onde devemos focar para não deixar o adversário prosperar e autodefender -se . Esse programa estaria quase apto ao embate , eu disse quase , e é isso mesmo , quase . E eu explico por quê:
Porque falta uma outra pecinha ai do quebra-cabeça , e essa pecinha fundamental tem o nome de Alpha-Beta Pruning .
Alpha-Beta Pruning
Esse é o mais simples , e assim como os dois anteriores , também trabalha em conjunto , ele é o responsável por buscar e diminuir os “ Nós “ da árvore de possibilidades MiniMax , ou seja , assim que ele vê uma jogada ruim por essa levará a uma situação ruim , ele para e segue adiante na posição de um " Nó " melhor , se nessa linha ele encontrar novamente algo ruim , ele para e vai na direção do melhor “ Nó “ até encontrar a melhor jogada , é um software de força bruta , ele sozinho sem orientações não serviria de nada , mas com a função de avaliação e sabendo o que procurar ele se torna quase perfeito .
O artigo ainda fala algo que eu acho muito legal , sobre as descobertas dos resultados completos dos "Othello" em 4x4, e 6x6,( Sei que também há o 5x5 , esse eu fico devendo ).

Há 64 casas em um tabuleiro de Othello oficial de 8x8 , pois bem , 4 dessas casas já estão ocupadas com as duas peças brancas e pretas , sobrando 60 casas , que por sua vez é um número par , certo ? Quem começa a jogar no Othello oficial é o jogador com as peças pretas , que por sua vez tem uma imensa área par a sua espera , de 60 casas , e sabemos que pela Teoria do Número Par , quem começa a jogar em uma região par não terminará fazendo o último movimento pegando as últimas peças daquela região , então à priori sim , as peças pretas já começam o jogo em desvantagem .
Vamos ver sobre as outras versões de "Othello" o que acontece .
Posição Inicial
Valor das Posições
No "Othello" 4x4 , há 10 Milhões de possíveis jogadas , onde termina sempre com a peça branca vencendo com uma margem de 8 peças à frente do seu adversário , o jogo todo é calculado em 1 segundo .
No "Othello" 6x6 , que eu considero a versão mais chata do Othello , existem 3.5 Trilhões de possíveis jogadas , onde sempre a peça branca termina na frente com 4 peças sobre as pretas , o jogo todo é jogado em 100 horas .
Assim como acredito que alguns de vocês já saibam , o Othello 8x8 que é o nosso queridíssimo Othello oficial não está solucionado ainda , mas já podemos imaginar as proporções astronômicas que um cálculo para ele levaria . Estima-se que existam mais ou menos uns 10 seguidos de 54 zeros de “ Nós “ nessa projeção , é muita coisa .
Pessoal , o que colocarei abaixo é uma explanação sobre um assunto que foge um pouco do escopo do tema da postagem , mas tem unidade por digressão do assunto inicial .
Só para acrescentar , é lógico que não há pontos perfeitos em alguns dos trechos do artigo , tal como no começo quando disseram que o jogo foi inventado no ano de 1883 baseado no jogo GO . Ora , se foi em 1883 automaticamente entra em discrepância com a história oficial da invenção do jogo , onde diz que o jogo foi inventado em 1971 por Goro Hasegawa baseado no jogo GO . Ta bom , eu sei , realmente a história extra-oficial é a de que dois britânicos londrinos tiveram ideias parecidas para inventarem cada um ao seu modo o jogo Annexation e reversi em 1888 , ou meados desta mesma data , mas não há registros de que eles tenham se baseado no clássico chinês GO , então o que os estudantes do artigo fizeram nesse trecho foi uma misturéba , onde colocaram o GO na data de invenção de Mollett e Waterman os londrinos patenteadores da ideia . Mas olhem , existe sim a possibilidade de tanto Waterman e Mollett ( Não , se você acompanha o meu blog , você sabe que eles não eram sócios e teve um grande rolo na época por causa de brigas por patentes ) como também Goro Hasegawa terem se baseado no jogo GO , já que esse é sim bem antigo e tem uma dinâmica similar a jogo Othello , o que o poderia colocar tranquilamente como um “ primo “ do jogo Othello dentro desse ramo , porém essa ideia de unidade só vem de informações anedóticas , onde quem disse foram o Sr. Hasegawa e seu sócio na época , Jim Becker . Mas como já discuti isso aqui no meu blog algumas vezes e não quero me alongar muito dessa vez , eu vou deixar o link abaixo junto aos outros para você verem mais ou menos como que foi esse rolo na época lá na Inglaterra para que vocês tirem as suas conclusões . Mas só para terminar , agora esse ano e creio eu que desde do final do ano passado , ta tendo lá no Japão o Othello World Cup 2013 , onde ocorre alguns torneios separados por algumas categorias de jogadores convidados , e esse evento também está servindo para a divulgação do novo jogo do Sr. Hasegawa , o Miracle5 . Que é um jogo com uma estrutura muito similar ao já há muito tempo tradicional jogo Gomoku , só que em um tabuleiro dimencionalmente menor , eu joguei e vou deixá-lo ai para quem quiser jogar também , é legalzinho , mas nada de “ A grande invenção do milênio “ , e nem se propôs a isso , mas para uma mente que foi capaz de inventar um jogo tão complexo em suas minúcias como o Othello , eu sinceramente esperava mais . Outra coisa é que acredito eu que foi o primeiro jogo desde de que inventou o Othello em 1971 que ele criou , e para um inventor é muito tempo de espera , sabe , tudo isso só me leva a crer naquilo tudo que eu já tinha dito antes , o Othello não foi invenção , foi uma patentiação . A não ser que o Sr. Hasegawa tenha tido uma criptomnésia ( Estado psicológico onde alguém tem uma ideia alheia e acredita ser de sua autoria de forma inócua , ou seja , inocente ) eu acredito sim que a ideia original partiu dos londrinos no século passado ou todo mundo , incluindo Hasegawa , partiram da ideia base do jogo GO ( Inclusive existe artigos do jornal The New York Times de 1895 comparando o reversi ( A letra érre em minúscula mesmo por causa de patente )ao jogo GO) . O que não estaria errada com a versão oficial da criação do jogo na década de 1970 , mas o que é a meu ver é muito mais improvável de se acreditar levando em consideração a extrema similaridade entre o Othello e o Reversi londrino , que a ideia base partiu de lá mesmo , e não do jogo Go . Mas vai saber né ... .
Outro ponto que eles vacilaram um pouco foi ao poupar nomes como IAGO , que foi o primeiro software de Othello já criado , o campeão japonês de 1976 Fumio Fujita o derrotou , o jogo aconteceu em Pasadena na Califórnia , Estados Unidos e também The Moor , que foi o primeiro programa a conseguir ganhar de um jogador de Othello no mundo , e isso aconteceu em 1981 e o jogador foi Hiroshi Inouie , até então campeão mundial de Othello em 1977 e 1979 , durante um evento que reunia jogadores humanos e programas em um campeonato só . Um artigo que se sujeita a falar de software de inteligência artificial não pode cometer tais equívocos históricos , afinal de contas , são alunos universitários , certo ?
Obrigado a todos .
Encerrei o meu acréscimo aqui , com exceções dos dois links à mais que colocarei no final .
Pronto pessoal , falei o básico já , quem quiser saber mais se aprofunde no próprio artigo e nos links que deixarei no final da postagem .
Links :
Heurística - Wikipédia
http://pt.wikipedia.org/wiki/Heur%C3%ADstica
MiniMax - Wikipédia
http://pt.wikipedia.org/wiki/Minimax
Alpha-Beta Pruning
http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
Como um Programa Pensa - Othello Classic
http://othelloclassic.blogspot.com.br/2009/10/como-um-programa-pensa.html
Especial , Quem inventou o Othello , Mollett , Waterman ou Hasegawa ? Saiba um pouco mais dessa história .
http://othelloclassic.blogspot.com/2011/07/quem-inventou-o-othello-mollett.html
Miracle5 ( Está no site da Japan Othello Association )
http://www.othello.gr.jp/taiken/game.html
GO - Wikipédia
http://pt.wikipedia.org/wiki/Go
Gomoku - Wikipédia
http://pt.wikipedia.org/wiki/Gomoku
MC906 - Introdução à Inteligência Artificial
Prof. Anderson de Rezende Rocha
Alunos
Bruno Caminada
Daniel Machado Reis
Paolo B. Nunes da Silva
Stallin E. Ferreira da Silva
http://www.ic.unicamp.br/~rocha/teaching/2011s2/mc906/seminarios/2011s2-mc906-seminario-04.pdf
Página do Bruno , leitor que comentou no meu blog e me mostrou o link :
http://ishiai.multiply.com/

Nenhum comentário: