DESENVOLVIMENTO DE JOGOS NA WEB UTILIZANDO TEORIA COMBINATÓRIA DOS JOGOS
Descrição do Produto
MINISTÉRIO DA DEFESA EXÉRCITO BRASILEIRO DEPARTAMENTO DE CIÊNCIA E TECNOLOGIA INSTITUTO MILITAR DE ENGENHARIA CURSO DE GRADUAÇÃO EM ENGENHARIA DE COMPUTAÇÃO
LUCAS ROCHA GARCIA ROBINSON CALLOU DE MOURA BRASIL FILHO
DESENVOLVIMENTO DE JOGOS NA WEB UTILIZANDO TEORIA COMBINATÓRIA DOS JOGOS
Rio de Janeiro 2016
INSTITUTO MILITAR DE ENGENHARIA
LUCAS ROCHA GARCIA ROBINSON CALLOU DE MOURA BRASIL FILHO
DESENVOLVIMENTO DE JOGOS NA WEB UTILIZANDO TEORIA COMBINATÓRIA DOS JOGOS
Projeto de Fim de Curso apresentado ao Curso de Graduação em Engenharia de Computação do Instituto Militar de Engenharia, como requisito parcial para a obtenção do título de Engenheiro de Computação. Orientador: Prof. Marcos Veloso Peixoto - Docteur Orientador: Prof. Alex de Vasconcellos Garcia - D.Sc.
Rio de Janeiro 2016
c2016 INSTITUTO MILITAR DE ENGENHARIA Praça General Tibúrcio, 80 - Praia Vermelha Rio de Janeiro - RJ CEP 22290-270 Este exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-lo em base de dados, armazenar em computador, microfilmar ou adotar qualquer forma de arquivamento. É permitida a menção, reprodução parcial ou integral e a transmissão entre bibliotecas deste trabalho, sem modificação de seu texto, em qualquer meio que esteja ou venha a ser fixado, para pesquisa acadêmica, comentários e citações, desde que sem finalidade comercial e que seja feita a referência bibliográfica completa. Os conceitos expressos neste trabalho são de responsabilidade do(s) autor(es) e do(s) orientador(es). 006.6 G216d
Garcia, Lucas Rocha Desenvolvimento de Jogos na Web utilizando Teoria Combinatória dos Jogos / Lucas Rocha Garcia, Robinson Callou de Moura Brasil Filho, orientado por Marcos Veloso Peixoto e Alex de Vasconcellos Garcia - Rio de Janeiro: Instituto Militar de Engenharia, 2016. 67p.: il. Projeto de Fim de Curso (graduação) - Instituto Militar de Engenharia, Rio de Janeiro, 2016. 1. Curso de Graduação em Engenharia de Computação - projeto de fim de curso. 1. Teoria Combinatória dos Jogos. 2. MinMax. 3. Poda Alpha-Beta. 4. Método Monte Carlo. 5. Aplicação Web. 6. MVC. I. Peixoto, Marcos Veloso. II. Garcia, Alex de Vasconcellos . III. Título. IV. Instituto Militar de Engenharia.
1
INSTITUTO MILITAR DE ENGENHARIA
LUCAS ROCHA GARCIA ROBINSON CALLOU DE MOURA BRASIL FILHO
DESENVOLVIMENTO DE JOGOS NA WEB UTILIZANDO TEORIA COMBINATÓRIA DOS JOGOS Projeto de Fim de Curso apresentado ao Curso de Graduação em Engenharia de Computação do Instituto Militar de Engenharia, como requisito parcial para a obtenção do título de Engenheiro de Computação. Orientador: Prof. Marcos Veloso Peixoto - Docteur Orientador: Prof. Alex de Vasconcellos Garcia - D.Sc. Aprovado em 29 de Setembro de 2016 pela seguinte Banca Examinadora:
Prof. Marcos Veloso Peixoto - Docteur do IME - Presidente
Prof. Alex de Vasconcellos Garcia - D.Sc. do IME
Prof. Julio Cesar Duarte - D.Sc. do IME
Prof. Humberto Henriques de Arruda - M.Sc. do IME Rio de Janeiro 2016
2
A todos que apoiaram nossos sonhos, oferecemos hoje nossas conquistas.
3
AGRADECIMENTOS A Deus, nosso senhor, pela criação e o sustento de nossas vidas. Aos gigantes da ciência sobre os quais nos apoiamos durante nosso desenvolvimento acadêmico enquanto engenheiros. Aos nossos orientadores, Marcos Veloso e Alex Garcia, por guiarem nossos esforços, tornando possível a conclusão deste projeto. Aos professores do instituto que dividiram conosco seus conhecimentos, vivências e perspectivas. Aos nossos colegas de turma, verdadeiros amigos e companheiros, com os quais compartilhamos desafios e aprendizados no decorrer dos últimos cinco anos. Às nossas famílias, que sempre nos incentivaram, torceram, choraram, nos suportaram, porque sem eles não chegaríamos ao final desta jornada.
4
“Assim como o ferro afia o ferro, o homem afia seu companheiro. ” PROVÉRBIOS 27,17
5
SUMÁRIO
LISTA DE ILUSTRAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1
INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1
Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2
Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3
Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4
Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5
Organização da Monografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2
TEORIA DOS JOGOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1
Jogo Matemático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2
Classificação dos Jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3
Teoria Combinatória dos Jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4
Algoritmos e Métodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.1 MinMax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.2 Poda Alpha-Beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.3 Algoritmo de Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3
JOGOS IMPLEMENTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1
Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2
Nim 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3
Domineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4
Othello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4
ESPECIFICAÇÃO DO PROJETO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5
IMPLEMENTAÇÃO DO PROJETO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1
Implementação da Camada de Controle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2
Implementação da Camada de Visão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6
RESULTADOS DAS IMPLEMENTAÇÕES . . . . . . . . . . . . . . . . . . . . . . 38
7
CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
8
REFERÊNCIAS BIBLIOGRÁFICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6
9
APÊNDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
9.1
APÊNDICE 1: Descrição dos Casos de Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
9.2
APÊNDICE 2: Implementação da Jogada da Máquina . . . . . . . . . . . . . . . . . . . 50
9.3
APÊNDICE 3: Implementação da Heurística da Jogada da Máquina . . . . . . . 53
9.4
APÊNDICE 4: Manipulação do Jogo e Interfaceamento . . . . . . . . . . . . . . . . . . 56
9.5
APÊNDICE 5: Regras do Jogo e Validação de Movimentos (Domineering) . . 60
9.6
APÊNDICE 6: Programa para teste e validação . . . . . . . . . . . . . . . . . . . . . . . . . 63
7
LISTA DE ILUSTRAÇÕES FIG.2.1
Árvore de decisão MinMax (adaptado de (VISSER, 2007)). . . . . . . . . . . . 18
FIG.2.2
Exemplo de poda Alpha-Beta (adaptado de (VISSER, 2007)). . . . . . . . . . 20
FIG.2.3
Pasos do algoritmo de Monte Carlo (adaptado de (CHASLOT et al., 2008)). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
FIG.3.1
Sequência de jogadas em um jogo de Nim. . . . . . . . . . . . . . . . . . . . . . . . . . . 22
FIG.3.2
Sequência de jogadas em um jogo de Nim 2D. . . . . . . . . . . . . . . . . . . . . . . . 23
FIG.3.3
Sequência de jogadas em um jogo de Domineering. . . . . . . . . . . . . . . . . . . 24
FIG.3.4
Sequência de jogadas em um jogo de Othello. . . . . . . . . . . . . . . . . . . . . . . . 25
FIG.4.1
Diagrama de casos de uso.
FIG.4.2
Caso de uso da jogada do computador. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
FIG.5.1
Arquitetura da aplicação Web. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
FIG.5.2
À esquerda, função de valoração de maior preferência às bordas, e
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
à direita, realização do cálculo aproximado do nim-value. . . . . . . . . . . . . 34 FIG.5.3
Menu de jogos disponíveis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
FIG.5.4
Menu do jogo Domineering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
FIG.5.5
Espaço colorido de vermelho para indicar jogada. . . . . . . . . . . . . . . . . . . . . 37
FIG.5.6
Mensagens de término de jogo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
FIG.6.1
Aparência do Portal no EAD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
8
RESUMO No final da cadeira de Lógica no curso de Engenharia de Computação, no IME, os alunos devem desenvolver uma inteligência artificial capaz de jogar um jogo matemático estratégico contra um humano, usando a linguagem de programação Prolog e valorando cenários de acordo com regras específicas de cada jogo. Para apoiar o desenvolvimento desta atividade, este projeto tem por finalidade a aplicação da teoria dos jogos com a implementação de algoritmos de tomada de decisão genéricos. A estruturação do projeto foi feita seguindo a arquitetura MVC, com o intuito de modularizar cada camada da aplicação e facilitar o desenvolvimento, além de proporcionar a distribuição das diferentes responsabilidades para diferentes tecnologias. A implementação é dividida em três camadas: a primeira no lado do cliente, com a renderização do tabuleiro de jogo, com o intuito de facilitar a interação com o jogo, e a segunda e terceira do lado do servidor, contendo, respectivamente, a infraestrutura necessária para o funcionamento correto da aplicação em um portal Web, feita em ASP.NET, e a inteligência responsável pelas tomadas de decisão, implementadas em Prolog e processadas por um serviço SWI-Prolog. Para tanto, algoritmos como MinMax e técnicas como poda Alpha-Beta e métodos de Monte Carlo foram utilizadas nas inteligências de cada jogo. Este projeto contribuiu para o uso de métodos genéricos para aplicação em jogos matemáticos com interface gráfica feita de maneira modular, auxiliando estudos de aplicabilidade e desenvolvimento dessas tecnologias.
9
ABSTRACT At the end of the Computer Engineering’s Logic course at IME, the students must develop an artificial intelligence capable of playing strategic mathematical games against humans, using the programming language Prolog and valuing scenarios according to specific rules of each game. To aid the development of this activity, this project aims at applying game theory and implementing generic decision-making algorithms. The project was designed following the MVC architecture, in order to modularize each application layer and facilitate the development, providing the distribution of different responsibilities for different technologies. The implementation is divided into three layers: the first one on the client side, responsible for rendering the game board, in order to facilitate interaction with the game, and the second and third ones on the server side, responsible for, respectively, the infrastructure necessary for the proper functioning of the application in a Web portal, made in ASP.NET, and intelligence responsible for decision making, implemented in Prolog and processed by a SWI-Prolog service. For this, algorithms such as MinMax and techniques such as Alpha-Beta prunning and Monte Carlo methods were used in each game’s intelligence. This project contributed for the use of generic methods for mathematical game applications with modular graphic interfaces, aiding studies of applicability and development of those technologies.
10
1 INTRODUÇÃO
Existem muitos jogos milenares que ainda apresentam grandes desafios para a computação. Um dos objetivos constantemente almejados na área de computação é o desenvolvimento de máquinas e softwares que sejam capazes de tomar decisões em jogos estratégicos, assim como Xadrez e Go que possuem alto nível de complexidade e uma profunda árvore de jogadas possíveis. A teoria dos jogos é um conjunto de ferramentas analíticas que oferece auxílio para a análise de tomadas de decisão. Os modelos desta teoria têm aplicação em vários fenômenos observáveis, resultando em várias metodologias de abordagem de problemas em sua área de abrangência (OSBORNE et al., 1994). Desde o desenvolvimento de algoritmos a técnicas de computação avançada, várias metodologias já foram aplicadas a este campo de estudo. O Deep Blue foi um supercomputador acompanhado de um software desenvolvido pela IBM feito com o único propósito de jogar Xadrez. Ele tinha 256 co-processadores e era capaz de analisar em torno de 200 milhões de posições por segundo. Em maio de 1997, este computador se tornou o primeiro computador a vencer de um campeão mundial de Xadrez, derrotando o campeão Garry Kasparov, com um resultado equilibrado de 2 vitórias, 3 empates e 1 derrota (100, 2016). Em março de 2016, o computador AlphaGo, desenvolvido pela Google DeepMind, foi o primeiro computador a vencer de um campeão mundial de Go, derrotando o campeão Lee Sedol com 4 vitórias e 1 derrota. O AlphaGo utiliza milhares de CPUs em modo distribuído. Para decidir uma jogada, o software utiliza uma combinação de aprendizado de máquina com busca em árvore de Monte Carlo, algoritmo que explora a árvore a partir de buscas aleatórias, avaliando e valorando as jogadas, em busca das mais promissoras. A máquina foi treinada com jogadores profissionais e evoluiu por si com o uso de algoritmos genéticos (LIMITED, 2016). 1.1 MOTIVAÇÃO O desenvolvimento de softwares capazes de resolver jogos estratégicos, imitando o raciocínio humano, é um exercício matemático e tecnológico que tem grande impacto sobre múltiplas áreas do conhecimento. Existem vários trabalhos que citam a aplicabilidade da teoria dos jogos, como no cenário econômico, computando os valores monetários ideais 11
para um equilíbrio de mercado (NISAN et al., 2007), no cenário militar, auxiliando a alocação de recursos levando em consideração o que um exército inimigo é capaz de realizar (HAYWOOD JR, 1954) e no cenário administrativo, simulando ofertas de diferentes negociadores (ANPAD, 2006). Paralelamente, com a crescente evolução das tecnologias aplicadas à computação, o desenvolvimento de aplicações inteligentes se torna um assunto cada vez mais popular. Desta forma, o desenvolvimento acadêmico de metodologias na área de teoria dos jogos, com foco em computação, avança em duas frentes de exploração essenciais, a puramente matemática e a computacional. 1.2 OBJETIVO Este projeto tem por finalidade implementar, em uma plataforma Web, algoritmos de tomada de decisão genéricos para criar inteligências capazes de jogar jogos matemáticos estratégicos, valorando cenários de acordo com regras específicas de cada jogo desenvolvido neste projeto. As inteligências artificiais dos jogos utilizam métodos genéricos para a solução de problemas da teoria dos jogos, e métodos específicos, aproveitando aspectos inerentes de cada jogo para a otimização da tomada de decisão, com a finalidade de aprimorar a aplicação. 1.3 JUSTIFICATIVA Este projeto explora o uso dos algoritmos de teoria dos jogos em jogos matemáticos com o objetivo de mensurar resultados, e, portanto, estudar seu desempenho, expandindo as suas aplicações computacionais. A aplicação foi desenvolvida para auxiliar a cadeira de Lógica do curso de Engenharia de Computação, no IME, demonstrando para os alunos a implementação de algoritmos matemáticos com o auxílio da linguagem de programação Prolog, servindo como objeto de estudo. Nesse sentido, para que o projeto esteja disponível à consulta dos alunos do curso de lógica, criou-se uma disciplina no portal de ensino a distância do IME, plataforma EAD, com todo o material produzido durante o projeto, apresentado no formato de uma disciplina.
12
1.4 METODOLOGIA Primeiramente, um apanhado de técnicas e métodos de resolução de problemas da teoria dos jogos foi feito para a aplicação em jogos matemáticos. Em seguida, o estudo desses algoritmos foi realizado para a implementação da inteligência dos jogos, buscando técnicas genéricas que possam ser utilizadas em múltiplos jogos matemáticos. Para validar estes algoritmos, quatro jogos estratégicos foram selecionados: Nim, Nim 2D, Domineering e Othello. A inteligência foi implementada em SWI-Prolog enquanto que a infraestrutura da aplicação foi feita de forma modularizável e escalável em plataforma de desenvolvimento ASP.NET, em C# e JavaScript. Testes foram realizados para otimizar os algoritmos, com a adição de métodos específicos para os jogos, utilizando-se de particularidades. Os testes foram realizados em configurações diferentes do mesmo jogo, para verificar a adaptabilidade dos algoritmos. Por fim, o código fonte da aplicação foi disponibilizado em plataforma digital e abertamente acessível para que possa ser revisado pela comunidade e servir de base para trabalhos futuros.
1.5 ORGANIZAÇÃO DA MONOGRAFIA Este trabalho encontra-se organizado da seguinte forma: no capítulo 2, a teoria dos jogos será apresentada junto com as definições de jogo matemático, teoria combinatória dos jogos e os algoritmos utilizados, e, no capítulo 3, os jogos utilizados neste trabalho são apresentados, junto com suas regras e problemáticas. O capítulo 4 explana o planejamento do projeto, exibindo restrições e objetivos traçados. O capítulo 5 aborda as tecnologias, bibliotecas e infraestruturas utilizados para o desenvolvimento da aplicação, descrevendo a integração dos componentes gráficos e lógicos da aplicação segundo o modelo MVC. Os resultados observados das implementações estão expostos no capítulo 6. Por fim, as conclusões e considerações finais são evidenciadas no capítulo 7.
13
2 TEORIA DOS JOGOS
O propósito de se estudar e desenvolver a Teoria dos Jogos – desde do seu começo em 1928 quando John Von Neumann publica seu primeiro artigo sobre o tema – tem sido de aplicar seus conceitos em situações reais, nas esferas de Economia, Política, Negócios, Guerra, entre outras áreas (NEUMANN; MORGENSTERN, 1944). Faz-se isso através da análise do objeto matemático que dá nome à área: o jogo. Assim, também é interessante que se descreva o que é um jogo matemático. 2.1 JOGO MATEMÁTICO Jogos matemáticos devem ter um conjunto de regras coerentes. Regras ditam o que é permitido e o que não é permitido fazer. Jogos que podem ser analisados matematicamente possuem um conjunto rígido de movimentos possíveis, os quais são, em geral, conhecidos a priori (NISAN et al., 2007). O conjunto completo de regras descreve um jogo. Uma partida é uma instância do jogo. O jogador é o agente capaz de tomar decisões que afetem um jogo (BERLEKAMP et al., 2001). Em certas situações, chamadas de posições, que descrevem o estado de uma partida, um jogador é capaz de realizar um movimento ou ação. Uma estratégia é um plano, algoritmo, que diz ao jogador quais movimentos deve realizar em todas as posições possíveis. Jogos matemáticos podem admitir inúmeros resultados, cada um produzindo um pagamento ou retorno para os jogadores. Pagamentos podem ser de natureza monetária, ou podem simplesmente expressar a satisfação de ganhar o jogo. É mais usual representar os pagamentos por meio de uma matriz, consequentemente batizada de Matriz de Pagamento. O resultado de um jogo matemático não pode ser antevisto. Como as regras são impostas, isto implica que um jogo deve, necessariamente, conter elementos aleatórios ou mais do que um jogador. O jogo matemático requer o uso da inteligência, propondo aos jogadores ações distintas a serem escolhidas (PRISNER, 2014). O comportamento racional é geralmente assumido para todos os jogadores. Isto é, os jogadores têm preferências, opiniões sobre o jogo (incluindo os outros jogadores) e procuram otimizar seus retornos individuais. Além disso, cada jogador está ciente da 14
racionalidade dos demais jogadores (OSBORNE et al., 1994). Em jogos reais, é possível trapacear. Trapacear significa o não cumprimento das regras. A Teoria dos Jogos nem sequer reconhece a existência de fraudes. O objetivo de seu estudo é aprender a ganhar de forma lícita. 2.2 CLASSIFICAÇÃO DOS JOGOS Jogos podem possuir um ou mais jogadores, sendo jogos com múltiplos agentes (jogadores) mais comuns. Contudo, alguns jogos que são para mais de um jogador ainda podem ser jogados sozinho. A roleta, por exemplo, se encaixa na descrição já que o casino não conta como jogador desde que não tome qualquer decisão (PRISNER, 2014). Um jogo pode ter movimentos simultâneos ou sequenciais. Em um jogo simultâneo, cada jogador tem apenas um movimento, e todos os movimentos são feitos ao mesmo tempo (SBC, 2010). Num jogo sequencial, não há dois jogadores que se movem ao mesmo tempo, e é possível que jogadores tomem uma série de movimentos. Todavia, há jogos que não são nem simultâneos nem sequenciais. Jogos podem conter eventos aleatórios que influenciam o seu resultado. A estes chamamos movimentos aleatórios. Um jogo fornece informação perfeita se cada jogador, quando prestes a se mover, tem em memória todos os movimentos anteriores. Em contrapartida, um jogo fornece informação completa se todos os jogadores conhecem as regras do jogo, a ordem em que os jogadores se movem, todos os movimentos possíveis de cada posição, e os pagamentos para todos os resultados. Jogos que não são de informação completa são tipicamente mais difíceis de serem modelados. Diz-se que um jogo é de soma zero se a soma dos pagamentos para todos os possíveis resultados e considerando todos os jogadores é zero. Um jogador pode ter um retorno positivo somente se outro tem um retorno negativo. Poker e Xadrez são exemplos de jogos de soma zero bastante conhecidos e apreciados. Às vezes, a comunicação entre os jogadores é permitida antes do começo da partida ou da decisão dos movimentos. Jogos que permitem a comunicação muitas vezes também favorecem a cooperação entre jogadores. Comunicação também permite que jogadores blefem, ou seja, tentem manipular os movimentos dos demais. Mesmo que os jogadores negociem entre si, a questão é se o produto das negociações é aplicável ao Jogo. Assim, um jogo cooperativo é aquele em que o produto das negociações pode ser imposto pela força de um contrato. O contrato também deve descrever uma maneira de se distribuir os pagamentos entre os membros de cada coalizão, um grupo de 15
jogadores. Nos jogos em que o primeiro jogador que não puder fazer uma jogada perde, a inversão desta regra é chamada de “miséria” (BERLEKAMP et al., 2001). Um jogo pode ter uma quantidade finita (jogos da velha) ou praticamente infinita de jogadas (Xadrez). Ainda mais, um jogo com quantidade infinita de jogadas pode ser considerado cíclico se for possível retornar a estados anteriores, ou imparcial se os dois jogadores forem tratados de maneira idêntica (NISAN et al., 2007). 2.3 TEORIA COMBINATÓRIA DOS JOGOS Um jogo combinatório é um tipo de jogo matemático específico que tem, tipicamente, dois jogadores que jogam de maneira alternada com movimentos bem definidos, normalmente diferenciados em jogador esquerdo e direito. Não existem movimentos aleatórios e todos jogadores têm informação completa sobre o jogo (DEMAINE, 2001). Uma análise perfeita sobre um jogo combinatório deve prever quatro resultados finais a partir de jogadas perfeitas: o jogador esquerdo ganha, o jogador direito ganha, o primeiro jogador a jogar ganha e o segundo jogador a jogar ganha. Uma das tarefas de uma inteligência é analisar os cenários possíveis para cada jogada como uma dessas categorias. A inteligência então deve avaliar as jogadas utilizando uma estrutura profunda (CONWAY, 2001). Em teoria combinatória dos jogos, a convenção normal de jogo de um jogo imparcial é que o último jogador capaz de se mover seja o vencedor. Paralelamente, um jogo com a regra de miséria perturba essa convenção, declarando vencedor o indivíduo que normalmente seria considerado o perdedor. Contudo, ambas as regras possuem análise semelhante dentro da teoria. Um dos principais usos da teoria combinatória dos jogos envolve a compreensão de um objeto matemático peculiar chamado nimber. Nimbers, pela definição, são números ordinais dotados de operações de adição (nim-adition) e de multiplicação (nim-multiplication) próprias, distintas da simples adição e multiplicação ordinal por ordinal. Esses objetos são comumente usados para descrever jogos combinatórios, dando um valor (nim-value) a posições alcançáveis dentro de um jogo combinatório. Analisando o valor do nimber que descreve uma determinada posição, é possível determinar qual jogador estaria vencendo aquela posição. Se vale a regra normal de jogo, o jogador da posição está perdendo caso o valor do nimber dessa posição seja menor que 0, mas estaria ganhando caso esse valor seja maior que 0. Quanto a regra de miséria, obviamente, essas condições se invertem. Assim, para um jogador, seja ele um programa 16
de computador ou um ser humano, não é preciso calcular o nimber de um jogo de forma exata para determinar uma estratégia de vitória, basta saber uma boa aproximação. Em outras palavras, é pouco relevante saber o quão se está ganhando ou perdendo exatamente em cada posição para decidir-se uma boa jogada. Uma outra forma de entender a notação utilizada, seria dizer que quando o nim-value de um jogo é 0, significa que o primeiro jogador a realizar um movimento perde. Qualquer outro resultado é equivalente ao menor nim-value não contido no conjunto de próximas posições possíveis, ou seja, é calculado pelo MEx (Minimum Excludent) desse conjunto. Ainda através do estudo dos nimbers, foi produzido um dos resultados mais interessantes da teoria combinatória dos jogos, o teorema de Sprague-Grundy, que atesta que todo jogo imparcial, quando jogado na sua regra normal, é equivalente a um único nimber. Assim o valor de Grundy, ou nim-value, de um jogo imparcial é definido como o único nimber ao qual aquele jogo é equivalente. A implicação prática do teorema é que não importando o quão complexo seja um jogo, sempre é possível representa-lo por um nimber e, portanto, resolve-lo por analogia com um jogo mais simples. 2.4 ALGORITMOS E MÉTODOS Os algoritmos e métodos utilizados neste projeto foram os algoritmos MinMax junto com a poda Alpha-Beta e os métodos de Monte Carlo. Será feito uma breve descrição desses algoritmos e métodos. 2.4.1 MINMAX Provavelmente a técnica mais usada na resolução de jogos matemáticos, o algoritmo de MinMax objetiva minimizar a perda máxima em casos de pior cenário. A implementação correta do algoritmo depende estritamente da definição das regras de movimentação e da condição de término do jogo, sendo, portanto, uma solução genérica que pode ser aplicada a vários jogos (VISSER, 2007). O MinMax foi originalmente formulado para tratar de jogos de soma zero (nos quais o valor do MinMax converge para o valor do equilíbrio de Nash), sequências e de informação completa (NISAN et al., 2007). Todos os jogos que pretendemos abordar neste projeto se encaixam nessa definição (CONWAY, 2001). Contudo, é válido ressaltar que o conceito do MinMax pode ainda ser expandido para jogos mais complexos. Na versão mais simples do algoritmo, como se expõe na FIG.2.1, todo jogo termina em vitória e retorna “1”, derrota e retorna “-1” ou empate e retorna “0”. Só se conhece o valor 17
MinMax dessas condições de término. A melhor jogada possível é a de um movimento vencedor. Por outro lado, impedir que o jogador adversário possa fazer um movimento vencedor é melhor que permitir-lhe esse movimento. Perto do final do jogo, é mais fácil determinar o melhor movimento. Assim, o algoritmo avalia as jogadas de trás para a frente, a partir do final do jogo.
FIG. 2.1: Árvore de decisão MinMax (adaptado de (VISSER, 2007)). Em teoria combinatória dos jogos, o MinMax sofre uma mudança sutil, que torna o algoritmo mais apropriado a essa versão da teoria dos jogos. A mudança consiste em atribuir o valor de infinito positivo para uma jogada vencedora, de infinito negativo para uma jogada perdedora e o menor dentre os valores das possíveis respostas do jogador adversário para qualquer outro movimento. Desse modo, o jogador que procura maximizar o valor retornado pelo algoritmo é chamado de MAX e seu adversário, que busca minimizar o mesmo valor, de MIN – desta forma, deu-se o nome do algoritmo MinMax. Esse conceito simples pode ser estendido pela abstração de uma heurística que nos permita avaliar uma posição de jogo qualquer. Para tanto, são atribuídos valores finitos a cada posição, como uma estimativa do grau de certeza de que essa levará, indubitavelmente, a um cenário vitorioso. Ao analisar uma determinada posição, essa versão do MinMax preconiza que: • O jogo é descrito na forma de uma árvore de decisão, pela qual os nós representam as posições e as arestas representam os movimentos possíveis, sendo cada partida 18
um caminho único, sem desvios, entre a raiz da árvore e uma de suas folhas, de modo similar ao visto na FIG.2.1; • Por definição, pagamentos são avaliados sempre no referencial de MAX; • Partindo-se de qualquer posição que seja, MIN e MAX fazem seus movimentos sucessivamente, até atingir-se uma dada profundidade passada como parâmetro do algoritmo, diferentemente do que se pode observar na FIG.2.1, que executa uma busca total; • Tanto MIN quanto MAX escolhem seus movimentos de modo a potencializar seus pagamentos, supondo estar enfrentando um oponente com uma estratégia ótima. • O pagamento de uma posição é o valor MinMax referente ao nó da árvore de decisão que representa aquela posição; • A estratégia ótima é determinada pelo exame do valor MinMax de cada nó da árvore, até a profundidade passada; • O valor MinMax é obtido, recursivamente, ao se propagar os valores dos nós pais para seus nós filhos, seguindo a escolha e sequência de movimentos determinada pelos jogadores; • A profundidade do MinMax é igual à profundidade da árvore analisada. 2.4.2 PODA ALPHA-BETA A Poda Alpha-Beta é uma adição ao algoritmo do MinMax, cujo benefício encontra-se no fato de que ramos da árvore de decisão podem ser eliminados, sem que o resultado final difira do valor MinMax. Essa variação mantém duas variáveis globais: ALPHA, maior valor encontrado para MAX, e BETA, menor valor encontrado para MIN. Esses valores são atualizados conforme novos nós da árvore são explorados, como pode-se observar na FIG.2.2. A poda de um ramo da árvore ocorre durante a recursão, tão logo se descubra que o valor do nó corrente será menor que o valor de ALPHA (jogadas de MAX) ou maior que o valor de BETA (jogadas de MIN) (VISSER, 2007). A efetividade dessa aplicação, todavia, depende muito da ordem de avaliação dos nós filhos. Considerando-se “m” o número de movimentos e “p” a profundidade da busca, a p
complexidade temporal do algoritmo varia entre O(m 2 ) quando nós mais promissores são os primeiros a serem avaliados e O(mp ) quando nós mais promissores são os últimos a 19
FIG. 2.2: Exemplo de poda Alpha-Beta (adaptado de (VISSER, 2007)). serem avaliados. Nesse mesmo contexto, uma exploração aleatória dos nós resulta em complexidade temporal de aproximadamente O(m
3∗p 4
). Mesmo assim, no pior dos casos,
o Alpha-Beta MinMax é tão eficiente quanto o MinMax convencional. 2.4.3 ALGORITMO DE MONTE CARLO O método de Monte Carlo se baseia em resultados estatísticos tirados de amostragens aleatórias dentro de um determinado cenário. Consta em repetir simulações sucessivas para calcular probabilidades heuristicamente (HROMKOVIC, 2001). O método de Monte Carlo é ideal para obter aproximações numéricas de funções demasiado complexas, caso não seja viável obter uma solução determinística. Nesse sentido, tem sido largamente utilizado em simulações estocásticas, aplicado em áreas como a física, matemática e biologia. O nome do método faz referência ao famoso Cassino Monte Carlo, localizado no principado de Mônaco, em alusão a natureza aleatória da técnica semelhante a de jogos de azar (MOTWANI; RAGHAVAN, 1995). Em computação, um algoritmo baseado em Monte Carlo é um algoritmo que possui algum fator de aleatoriedade – normalmente baseado em geradores pseudoaleatórios – e que executam em tempo determinístico, mas cujo resultado pode apresentar um grau de incerteza controlado. Na prática, implementações algorítmicas desse tipo podem variar bastante entre si, muito embora a maioria siga o seguinte padrão: a) Modelar o problema definindo o domínio das entradas possíveis para o algoritmo; b) Gerar valores aleatórios para as entradas a partir de uma função de distribuição probabilística; c) Realizar uma computação determinística das entradas atribuindo valores aos resultados; 20
d) Agregar os resultados e obter uma estimativa para a solução do problema. Preferencialmente, para que se obtenham melhores resultados, o método deve ser aplicado por meio de um elevado número de simulações. Contudo, especialmente em um espaço mais contido de possibilidades, não se descarta a possibilidade de uma simplificação do método para obter-se resultados práticos sem tornar a solução excessivamente custosa. Na FIG.2.3 podemos ver um exemplo de funcionamento do algoritmo. O numerador de cada fração determina o número de vitórias calculadas a partir deste nó, enquanto o denominador determina o número de partidas jogadas a partir deste nó. As etapas de funcionamento, que estão ilustradas na FIG.2.3, são (CHASLOT et al., 2008): a) Seleção: a partir da raiz R, no caso representado na figura pelo nó-raiz com o valor 12/21, selecionar nós filhos, sucessivamente, até um dado nó folha L, representado na figura pelo nó folha com o valor 3/3; b) Expansão: caso o jogo não termine em L, com uma vitória/derrota para qualquer jogador, ou cria-se um ou mais nós filhos a L ou escolhe-se entre eles o nó C, representado na figura pelo nó com o valor 0/0; c) Simulação: jogar uma partida aleatória a partir do nó C; d) Correção: com o resultado da partida aleatória, atualizar as informações nos nós do galho de R para C.
FIG. 2.3: Pasos do algoritmo de Monte Carlo (adaptado de (CHASLOT et al., 2008)).
21
3 JOGOS IMPLEMENTADOS
Devido sua peculiar importância para o desenvolvimento do projeto, a escolha dos jogos a serem implementados mostrou-se uma tarefa crucial desde o princípio. Fazia-se necessário escolher um conjunto de jogos suficientemente expressivo, ou seja, que abrangesse o maior número possível de aspectos de um jogo matemático, mas sem inviabilizar uma implementação mais genérica da inteligência. Nesse sentido, foram escolhidos quatro jogos: Nim; Nim 2D; Domineering; Othello. 3.1 NIM Nim é um jogo de origem chinesa e teoria matemática completa. Jogado por dois jogadores, e, tradicionalmente, composto por três filas de 3, 5 e 7 peças. Entretanto, uma quantidade arbitrária de filas e peças por fila podem ser escolhidas contanto que duas filas não tenham a mesma quantidade de peças (BERLEKAMP et al., 2001). O jogo se segue da seguinte forma: os jogadores se revezam retirando uma quantidade qualquer de peças de qualquer fila, como pode-se observar na FIG.3.1. O jogador que retirar a última peça ganha. Na FIG.3.1 podemos observar que o jogador que fizer a próxima jogada vai perder o jogo. Alternativamente, seguindo a regra da miséria, o jogador que retirar a última peça perde.
FIG. 3.1: Sequência de jogadas em um jogo de Nim. Como normalmente é jogado em poucas filas com poucas peças, existe uma pequena variedade de jogadas por rodada, e, já que o número de rodadas do jogo não ultrapassa 22
o número de peças, a árvore de jogadas possível deste jogo para um tabuleiro jogável consegue ser produzida em tempo computacional razoável. Ainda, como um jogo matematicamente resolvido pela teoria combinatória dos jogos, o Nim tem uma fórmula vencedora tanto na sua regra normal quanto na regra da miséria. 3.2 NIM 2D A partir das regras do Nim, é possível abstrair algumas variações interessantes. Neste projeto, utiliza-se uma versão particular, nomeada Nim 2D, cuja maior amplitude de movimentos torna o jogo mais complexo (PEKING UNIVERSITY, 2016). Nesta variação, os jogadores podem retirar peças tanto das colunas quanto das filas, em qualquer posição do tabuleiro desde as peças retiradas estejam em sequência sem nenhuma peça retirada anteriormente no meio desta sequência, como pode-se observar na FIG.3.2. Uma inteligência pode ser desenvolvida com o auxílio de uma árvore de jogadas possíveis de altura delimitada e uma função de valoração adequada ao jogo.
FIG. 3.2: Sequência de jogadas em um jogo de Nim 2D.
3.3 DOMINEERING Domineering, também conhecido como Stop-Gate ou Crosscram, é um jogo matematicamente resolvido para alguns tamanhos de tabuleiro. Jogado por dois jogadores, tradicionalmente jogado em tabuleiros quadrados de 7x7 ou 8x8 (tabuleiro de damas). Entretanto, uma quantidade arbitrária de colunas ou linhas podem ser escolhidas (BERLEKAMP et al., 2001). O jogo se segue da seguinte forma: os jogadores se revezam colocando peças que ocupam duas casas do tabuleiro. Um jogador deve jogar as peças na vertical enquanto 23
o seu oponente as joga na horizontal, como observar-se na FIG.3.3. O jogador que não conseguir fazer uma jogada em sua rodada perde. Na FIG.3.3 podemos perceber que o jogador que joga peças na horizontal não pode realizar sua próxima jogada, e, portanto, perdeu o jogo. Tradicionalmente, um jogador assume peças voltadas ao norte e o outro jogador peças assume peças voltadas ao leste.
FIG. 3.3: Sequência de jogadas em um jogo de Domineering. Para tabuleiros mais jogados, incluindo o 8x8, a árvore de jogadas completa para um jogo de Domineering não é um desafio computacional simples em tempo de execução. Entretanto, uma árvore de altura limitada pode ser usada com o auxílio de uma função de valoração para a decisão de melhor jogada (BERLEKAMP et al., 2001). 3.4 OTHELLO Othello, também conhecido como Reversi, é um jogo de dois jogadores de cores diferentes, tipicamente jogado em um tabuleiro de oito colunas e fileiras. Inicialmente são colocadas quatro peças no centro do tabuleiro, duas de cada cor dispostas diagonalmente (QUAGLIO, 2013). Os jogadores jogam de forma sequencial e só se pode movimentar peças para casas ao redor de peças inimigas imediatamente próximas. Quando um jogador joga uma peça, qualquer peça do inimigo que estiver entre esta peça e outra peça do jogador, na vertical, 24
horizontal ou diagonal, é capturada e é transformada em uma peça deste jogador, como pode-se observar na FIG.3.4. Cada jogada deve capturar peças do oponente em suas jogadas. O jogo acaba quando não há casas vazias no tabuleiro ou quando não existem mais jogadas possíveis. Um jogador ganha o jogo quando este acaba e o jogador possui uma maior quantidade de peças. FIG.3.4 pode-se observar que o jogador azul ganhou o jogo pois possui mais peças que o adversário.
FIG. 3.4: Sequência de jogadas em um jogo de Othello. Apesar do tabuleiro 8x8, pela limitação de jogadas possíveis, o jogo de Othello, normalmente, não tem um processamento custoso da árvore de decisão, facilitando a utilização de algorítmicos que fazem a construção dessas árvores para determinar jogadas.
25
4 ESPECIFICAÇÃO DO PROJETO
A especificação do projeto foi realizada seguindo princípios da metodologia ágil, como a valorização da comunicação frequente entre as partes envolvidas e colaboração do cliente (PRESSMAN, 2005). Reuniões semanais com os orientadores tiveram o intuito de recolher insumos sobre as versões funcionais entregues a cada encontro, com especificação de próximos passos esperados para o próximo encontro. A descrição inicial do projeto previa o desenvolvimento de jogos educacionais em plataforma Web com inteligência artificial baseada na teoria dos jogos capaz de enfrentar de maneira satisfatória um jogador humano. Como requisitos, o projeto deveria ter uma interface gráfica de fácil uso, com opções de configuração de dificuldade e regras do jogo e múltiplos jogos matemáticos implementados. A partir desta orientação, foram traçados como objetivos primários o desenvolvimento do componente de inteligência artificial e a plataforma gráfica dos jogos. A cada versão estável, a inteligência foi avaliada pelos orientadores, junto com as funcionalidades gráficas da aplicação, com atenção para a agilidade e qualidade dos dois componentes, junto com a sua integração. A aplicação foi modelada de maneira modular, o que tornou possível o desenvolvimento desses componentes em paralelo, e facilitou a evolução da aplicação, viabilizando o desenvolvimento de módulos funcionais para facilitar testes. Na FIG.4.1 pode-se observar o diagrama de casos de uso usado para a modelagem do projeto demonstrando as funcionalidades especificadas, focando na chamada da jogada do computador, ponto fulcral da implementação. A descrição detalhada de cada caso de uso apresentado no diagrama, pode ser consultada no “APÊNDICE 1” deste documento. Todas as funcionalidades descritas na FIG.4.1 foram previstas para serem realizadas no cliente da aplicação, com exceção das configurações de jogo, que poderiam ser repassadas para a aplicação no servidor, e a execução da jogada do computador, que diz respeito ao caso de uso "COMPUTADOR REALIZA A JOGADA (CSU08)", descrito na FIG.4.2.
26
FIG. 4.1: Diagrama de casos de uso. A jogada do computador envolve a inteligência artificial da aplicação, e realiza a atividade de seleção de jogadas por parte da máquina, fluxo mais crítico da aplicação e mais estudado durante a implementação. Como discrimina a FIG. 4.2, após uma jogada do jogador, com exceção de uma ocasião de término de partida, há uma jogada do computador. Ainda mais, caso o jogo seja configurado para que o computador jogue primeiro, a partida já começa com uma requisição de jogada. A comunicação entre o cliente e o servidor responsável por processar a requisição de jogada da máquina deveria apresentar um tempo de resposta pequeno o bastante para não apresentar impacto no tempo de espera. Ainda mais, a jogada realizada pelo jogador não poderia demorar muito, visto que isto reduz a jogabilidade do jogo. Este último requisito tem impacto no algoritmo de inteligência desenvolvido, limitando configurações de complexidade que aumentam o tempo de análise requerido. 27
FIG. 4.2: Caso de uso da jogada do computador.
28
5 IMPLEMENTAÇÃO DO PROJETO
Para o desenvolvimento desta aplicação, diferentes tecnologias e bibliotecas de programação foram utilizadas, com o intuito de otimizar a ferramenta com o uso de ferramentas consolidadas. Este projeto foi arquitetado em uma plataforma de desenvolvimento Web da Microsoft, o ASP.NET, criado em 2001, sucessor da tecnologia ASP. O ASP.NET é amplamente utilizado por ser considerado estável, maduro e altamente produtivo, fornecendo suporte para desenvolvimento AJAX (DINO, 2010). O AJAX é um conjunto de técnicas que utilizam tecnologias como Javascript e XML para a comunicação entre o cliente e o servidor, fornecendo a opção de troca de dados sem que haja a recarga das páginas. As chamadas AJAX são muito utilizadas para comunicação entre scripts contidos no cliente e no servidor, tornando as páginas Web mais dinâmicas, evitando a recarga constante (REFSNES et al., 2010), essencial para o processamento contínuo dos algoritmos de decisão durante os jogos. Este projeto utiliza o modelo MVC para a sua arquitetura, um padrão existente desde os anos 70. O modelo MVC foi inventado por Trygve Reenskaug mas entrou em evidência em 2003 (PALERMO et al., 2012). O modelo MVC divide a aplicação Web em três camadas, como pode-se visualizar na FIG.5.1: modelo, visão e controle.
FIG. 5.1: Arquitetura da aplicação Web. 29
A camada de visão, mais abaixo na figura, contém os modelos de páginas Web em HTML, além do código em Javascript responsável pelos jogos, utilizando a camada de modelo para a parametrização e coleção de dados compartilhados com a camada de controle. A camada de controle, mais acima na figura, contém os métodos responsáveis pelo processamento, tipicamente contendo regras lógicas e processamento de dados. A camada de controle também abriga a infraestrutura de serviços utilizados no servidor. Nesta aplicação, esta camada tem a responsabilidade de processar o formato dos dados passados pelo cliente em formato JSON para o formato utilizado pelo código em Prolog. A camada de modelo, no meio da figura, contém as regras e formato da comunicação entre a visão e o controle, servindo como interface para a passagem de informações entre o cliente e o servidor da aplicação. As comunicações entre o cliente e servidor nos jogos em Javascript foram realizadas através de chamadas AJAX, evitando a recarga da página para a renderização dos tabuleiros. As chamadas são feitas entre jogadas do usuário, transmitindo informações do tabuleiro e configurações de jogo para a aplicação MVC através do protocolo de comunicação HTTP, POST. As informações são carregadas na camada de Modelo. O servidor, em seguida, realiza o call-back para o cliente com as informações da jogada da máquina. Durante o desenvolvimento do projeto houve controle de versões da aplicação. O versionamento possibilita a evolução da aplicação a partir da manutenção de versões estáveis. Além disto, o versionamento possibilita o acompanhamento das funcionalidades adicionadas no programa, armazenando o histórico de progresso do projeto. Para o facilitar o gerenciamento de versões, foi utilizado o sistema de versionamento chamado GIT (CONSERVANCY, 2016). Este projeto está sendo desenvolvido em um repositório do GitHub (https://github.com/coqueiro/teoriadosjogos), que utiliza o sistema de versionamento Git. 5.1 IMPLEMENTAÇÃO DA CAMADA DE CONTROLE A camada de controle desta aplicação contém três componentes, como vistos na FIG.5.1. O primeiro componente é o de controle da aplicação, que contém a infraestrutura necessária para a manutenção da página HTML da aplicação. O segundo componente contém os endpoints para as chamadas AJAX, realizadas durante a interação com os jogos. Esse componente realiza o interfaceamento com o terceiro componente, que mantém o processamento de um processo em SWI-Prolog, responsável pelas regras lógicas e decisões de 30
jogadas da inteligência artificial. O SWI-Prolog é uma implementação em código aberto da linguagem Prolog, em desenvolvimento contínuo desde 1987 e que conta com um rico conjunto de bibliotecas e ferramentas bem como uma documentação extensiva e uma comunidade ativa. O nome SWI deriva de Sociaal-Wetenschappelijke Informatica (holandês para Informática em Ciências Sociais), antigo nome do grupo de pesquisa, atualmente batizado de HCS (HumanComputer Studies), da Universidade de Amsterdã sobre o qual a maior parte do projeto inicial foi desenvolvida (WIELEMAKER et al., 2015). O motor do SWI-Prolog fornece compilação rápida e execução segura de vazamento de memória. Possui ainda boa escalabilidade, pois não impõe limite para o tamanho dos programas, para a extensão de fórmulas atômicas, para a aridade de termos ou para valores limite atribuídos a inteiros. Ainda, o SWI-Prolog dá suporte a multi-threading, sendo que o mesmo ambiente roda preferencialmente múltiplas execuções em uma mesma base de dados. Esses fatos são relevantes para a escolha da implementação vista, pois favorecem, no futuro e caso seja necessário, a continuidade do projeto. Prolog em si, como uma linguagem de programação, pode ser melhor entendida através de duas características principais: unificação e backtracking. A maneira como se combinam padrões é chamada de unificação, também descrita como a ligação de variáveis com predicados, sucessivamente, respeitando-se a ordem de escrita no código. Paralelamente, backtracking, ou a forma como se procuram por padrões, consta na busca repetida por soluções adicionais, onde o motor Prolog volta a um estado anterior e tenta novamente encontrar soluções dentro dos predicados descritos no código. Assim, durante a execução de um programa, restrições e corotinas anexam regras a dados, em busca de correspondências, por meio de chamadas ao código, via queries Prolog. Desse modo, o SWI-Prolog pode expressar naturalmente com um conjunto de regras simples, via predicados na forma de cláusulas de Horn, problemas logicamente complexos. Somando tudo isso ao fato de que a sua forte recursividade da linguagem funciona com grande eficiência em estruturas em forma de árvores e grafos, a versão SWI-Prolog é excelente para resolver quebra-cabeças e problemas de tomada de decisão, encaixando-se perfeitamente no desenvolvimento de jogos matemáticos e IA, escopo fundamental deste projeto. A implementação do código em Prolog foi feita de maneira modularizada, com aproveitamento de código entre diferentes aplicações de jogos. O algoritmo de MinMax com poda Alpha-Beta foi utilizado como base da inteligência para todos os jogos. Escolheu-se também utilizar uma função de valoração durante a execução do algoritmo, ao invés de se fazer uma busca em profundidade até o fim do jogo, devido ao alto fator de ramificação 31
dos jogos implementados. Ao fazer uso do MinMax ganha-se também a possibilidade de oferecer ao jogador mais do que um nível de dificuldade, bastando alterar a profundidade da busca até o ponto de cálculo da função de valoração. Procurando-se manter essa função de valoração o mais abrangente possível, lembrando que um dos propósitos do projeto é servir de modelo para futuras aplicações, tentou-se reproduzir no cálculo do valor de cada posição a ideia de um nimber. Pensar no resultado da função de valoração como um nimber possibilita, como assim diz o teorema de Sprague-Grundy, tratar da mesma maneira, heuristicamente, jogos distintos. Assim, aproveitando-se do fato que jogos combinatórios tipicamente acabam quando um jogador não pode mais realizar movimento algum, e que, como consequência da rotina de validação de movimento, dado uma posição qualquer seja fácil determinar o número de movimentos cabíveis a cada jogador, essa métrica — do número de movimentos cabíveis – foi escolhida como aproximação do nim-value para a função de valoração. Utilizando os métodos de Monte Carlo, foi inserida uma sub-rotina pseudoaleatória pareada à implementação do algoritmo de Alpha-Beta MinMax que serve como uma função de ajuste ao cálculo da posição. O resultado numérico de ajuste é dado pela iteração repetida de partidas pseudoaleatórias a partir de uma determinada posição, coletando-se a fração de vitórias obtidas em relação ao número de partidas jogadas. Essa estratégia se mostrou suficiente para jogos com um número finito – proporcional ao tamanho do tabuleiro – de jogadas, tais como o Nim, Nim 2D, Domineering e Othello. Procurou-se imitar, na medida do possível, o raciocínio humano. A parte de MinMax representa o quanto a máquina é capaz de analisar adiante da posição atual. O ajuste seria uma tentativa de reproduzir o instinto e a experiência que um jogador humano é capaz de experimentar. O código que decide os movimentos, pseudoaleatórios e determinísticos, para cada jogo é uma solução genérica e modularizada. Entretanto, as regras de cada jogo são específicas, assim como as limitações de cada movimento. Dessa forma a condição de término e o resultado final do jogo são consequência direta da aplicação do algoritmo genérico de movimentos às regras particulares de cada jogo. O algoritmo genérico desenvolvido – que executa o MinMax com poda Alpha-Beta, chamando a rotina de Monte Carlo e a função de valoração, particular ou generalizada, para cada jogo – está especificado no “APÊNDICE 2” deste trabalho. Essas chamadas por sua vez estão descritas no “APÊNDICE 3”. É importante pontuar que, para exemplificar melhor o código, sem sobrecarregar a leitura com informação repetitiva e pouco relevante, escolheu-se como exemplo a implementação do Domineering, pois esta embarca todos os 32
conhecimentos desenvolvidos. O SWI-Prolog admite interfaceamento com C/C++, permitindo chamadas ao código em Prolog bem como embedding do kernel SWI-Prolog em projetos C/C++ (WIELEMAKER et al., 2015). Essa interface, feita em baixo nível, para C/C++, serve ainda como base para o interfaceamento, de alto nível, através de bibliotecas específicas, com outras linguagens como C#, a qual também se utiliza neste projeto. Para o interfaceamento com o projeto foi utilizado a biblioteca Swi-cs-pl. A biblioteca Swi-cs-pl foi desenvolvida pelo engenheiro de software alemão Uwe Lesta. A Biblioteca foi desenvolvida em C# e fornece suporte à conexão de linguagens .NET com SWI-Prolog, com código open source disponível no GitHub. Ele foi utilizado como uma interface para o estabelecimento da conexão entre o SWI-Prolog e a aplicação em MVC, fornecendo conversão automática de tipos, mapeamento de exceções e suporte a queries para o SWI-Prolog de maneira síncrona (LESTA, 2013). O Swi-cs-pl fornece à aplicação em C# a possibilidade de inicialização e finalização do SWI-Prolog utilizando configurações de maneira dinâmica. Desta forma pode-se centralizar todas as aplicações necessárias em uma solução. O código de interfaceamento foi feito por meio de trocas de mensagens com o servidor C# da aplicação Web por meio de uma string padronizada que representa a posição corrente do tabuleiro. Manipular essa string é tarefa do código em Prolog, para a aplicação em C# basta traduzi-la. Escolheu-se o arranjo, ou matriz unidimensional, como estrutura padrão para a string do tabuleiro devido a facilidade de sua representação e tratamento em Prolog, graças ao grande poder de recursividade da linguagem. Essa representação também torna trivial resolver dois problemas de grande interesse da heurística dos jogos: dada uma peça achar sua posição ou dada uma posição ou achar sua peça ou declarar que está vazia. Após processar o movimento passado, se for atingida a condição de término do jogo, levanta-se uma flag determinando o resultado do jogo (true para vitória e false para derrota) e uma string com a posição final, apresentando o movimento como executado pela inteligência. A implementação em Prolog se encarrega de tratar a chamada do servidor C# e responder de modo apropriado, ou seja, como consequência, alguém que tenha visão somente da aplicação Web desconhece como roda de fato a inteligência do programa. O código em Prolog responsável pelo tratamento da string do tabuleiro e da chamada à jogada do computador pode ser consultado pelo “APÊNDICE 4”. Quanto à programação das regras, foi suficiente definir os movimentos acessíveis à cada jogador. Tomando como exemplo o jogo de Domineering, o jogador que realiza 33
jogadas na horizontal foi denominado como ‘horizontal’, enquanto o jogador que realiza jogadas na vertical foi denominado como ‘vertical’. Os movimentos, portanto, foram definidos pela casa superior à esquerda da posição conquistada. Obviamente, só estão disponíveis no tabuleiro as casas livres de peças – em branco. Essa parte da implementação está acessível ao leitor pelo “APÊNDICE 5” deste documento. Para melhor resultado em tempo de execução, fez-se um tratamento especial da função de valoração específica para o Domineering, que foi dividida em duas partes. A primeira – que é mais importante no começo do jogo – dá maior valor às posições imediatamente anteriores às bordas do tabuleiro, com o objetivo de proteger uma posição para ser futuramente preenchida. Já a segunda parte da função – mais relevante em fases mais avançadas do jogo – faz um cálculo aproximado do nim-value do tabuleiro, considerando linhas (para o jogador horizontal) e colunas (para o jogador vertical) isoladamente, bem como o cálculo genérico, que conta o número de movimentos possíveis para cada jogador, ponderando entre os dois. Para tanto, implementou-se uma heurística específica para esse cálculo, no qual posições vazias consecutivas tem mais valor que posições vazias isoladas. Essa implementação pode ser vista no “APÊNDICE 2” e no “APÊNDICE 3” deste documento. O resultado de uma jogada seguindo cada qual das funções de valoração está explicitado na FIG.5.2. À esquerda da figura, pode-se observar que todas as jogadas foram nas bordas, enquanto à direita da figura, pode-se observar que o jogador amarelo (na inteligência implementada) valorizou isolar o espaço no tabuleiro, indicado pela cor rosa.
FIG. 5.2: À esquerda, função de valoração de maior preferência às bordas, e à direita, realização do cálculo aproximado do nim-value.
34
5.2 IMPLEMENTAÇÃO DA CAMADA DE VISÃO A camada de visão contém páginas em HTML que carregam os métodos em Javascript utilizados nos jogos. Todos os componentes de tabuleiro junto com os menus necessários, foram implementados com a biblioteca CRAFTY, otimizando a criação de elementos HTML, tornando possível a modularização de funções usadas em vários menus e jogos. A biblioteca Crafty é um framework flexível para o desenvolvimento de jogos em Javascript, com código aberto e desenvolvido de maneira aberta através do GitHub. Ele foi utilizado para a construção e disposição correta dos tabuleiros e componentes, fornecendo ferramentas para a criação de componentes acionáveis ao clique (STOWASSER, 2016). A biblioteca de Javascript para a criação da interface dos jogos fornece a possibilidade de modularização dos componentes e das telas, facilitando a renderização de menus e estados de cada jogo. Além disto, a biblioteca Crafty tem documentação clara, fornece suporte aos navegadores mais modernos e tem comunidade ativa, facilitando o desenvolvimento, implementação e distribuição da aplicação. Os métodos Javascript dos jogos contém regras sobre as jogadas possíveis. Desta forma o jogo não realiza inúmeras chamadas ao servidor, reservando a comunicação para a passagem das jogadas válidas que devem ser processadas pelo servidor. Cada jogo tem configurações ajustáveis pelo usuário que são armazenadas na sessão. Estas configurações são utilizadas tanto no cliente, para a construção do jogo, quanto no servidor, como parâmetros passados para a inteligência do jogo. As configurações estão presentes na tela inicial do jogo, e não podem ser mudadas durante as partidas. Ao inicializar a aplicação há uma tela de menu com botões indicando todas as opções de jogos implementados. Cada botão pode ser pressionado para direcionar o usuário para o jogo selecionado, terminando a tela atual e inicializando a tela referente ao jogo, como pode-se observar na FIG.5.3. Todas as telas foram feitas de maneira modular, facilitando a implementação de novos jogos e controle de erros. Cada jogo implementado tem um menu que contêm botões para ajuste de configurações, o nome do jogo disposto no meio e um botão para começar o jogo. Todo jogo tem configurações de tamanho de tabuleiro e dificuldade. No jogo de Nim e Nim2D as configurações de tamanho de tabuleiro fornecem a opção de modificar o número de peças da menor fileira, a diferença de quantidade de peças entre peças adjacentes e o número de fileiras. No jogo Othello e Domineering o usuário tem a opção de definir a quantidade de linhas e colunas do tabuleiro. Todos os jogos têm configuração de dificuldade, que aumenta a profundidade de aná35
FIG. 5.3: Menu de jogos disponíveis. lise do algoritmo MinMax. Os jogos Nim e Nim2D têm a opção de ativação da regra miséria. Nos parágrafos seguintes desta seção, as figuras mostradas serão referentes ao jogo de Domineering, pois ele abrange todas as funcionalidades dos jogos de maneira análoga. Na FIG.5.4, pode-se observar os botões de configurações presentes no menu de começo de jogo.
FIG. 5.4: Menu do jogo Domineering. Após o início de um jogo, o jogador pode interagir com o tabuleiro pressionando nos espaços de jogadas válidas para cada rodada. No tabuleiro de Domineering e Othello, o jogo mostra quais as jogadas válidas modificando as cores dos espaços quando o usuário passa o ponteiro por cima deles, como pode-se observar na FIG.5.5. 36
FIG. 5.5: Espaço colorido de vermelho para indicar jogada. Após cada jogada o jogo trava até que o computador faça a sua jogada, impedindo o jogador de realizar jogadas ilegais. Com o término do jogo, seguindo as respectivas regras de cada jogo, uma caixa de mensagem aparece em frente ao tabuleiro, travando qualquer interação com o mesmo e mostrando uma mensagem de vitória ou derrota com um botão que retorna o usuário para o menu do jogo, como pode-se observar na FIG.5.6.
FIG. 5.6: Mensagens de término de jogo.
37
6 RESULTADOS DAS IMPLEMENTAÇÕES
O produto do projeto foi uma plataforma Web de jogos matemáticos embutida na plataforma de ensino a distância do IME, de acordo com o planejamento e os termos acordados nas reuniões entre os graduandos e os orientadores. O projeto tem o intuito de servir como objeto de estudo para alunos da graduação cursando a cadeira de Lógica, com a finalidade de ser aprimorado em projetos posteriores. A aplicação foi desenvolvida com o uso de métodos em JavaScript para a interface dos jogos, infraestrutura em C#, para a arquitetura MVC da aplicação. Todos os métodos, técnicas e boas práticas de programação derivaram dos conhecimentos ministrados durante as cadeiras de programação do curso de Engenharia de Computação do IME e estudos posteriores. Os métodos em JavaScript foram implementados com o auxílio da biblioteca gráfica Crafty. Os elementos Web criados se mostraram bastante fluídos, sem sinal de comportamento inesperado. A arquitetura programada em C# se mostrou robusta para a escala da aplicação, realizando a comunicação entre os componentes com raras falhas. Para a tomada de decisões de jogadas, utilizou-se uma implementação de inteligência artificial em Prolog com o motor SWI-Prolog, baseada em conhecimentos ministrados durante a cadeira de Lógica. Obteve-se um algoritmo parcialmente genérico e totalmente parametrizável sendo, não obstante, constatada a necessidade de refinamentos específicos referentes a cada jogo, devido, sobretudo, à profundidade das árvores exploradas. Nesse sentido, particularidades dos jogos, referentes às regras de movimentação, foram exploradas mostrando-se uma alternativa eficiente a soluções totalmente genéricas, sem a necessidade da criação de uma função avaliadora especializada para cada jogo. Buscou-se, ainda, garantir um certo grau de ordenação na busca do MinMax, para potencializar a poda Alpha-Beta ao máximo, reduzindo assim o tempo de execução. Paralelamente, percebeu-se que o ajuste por métodos de Monte Carlo, quando comparado com a implementação da inteligência sem o ajuste, tomou decisões mais inteligentes perto do fim do jogo, quando existem uma quantidade menor de sequências de jogadas possíveis. Percebeu-se, durante o desenvolvimento, que a delimitação das jogadas possíveis que um jogador pode realizar devem ser implementadas no lado do cliente, com o auxílio de métodos em JavaScript, para evitar múltiplas chamadas ao servidor com o intuito de in38
vestigar a validade de cada tentativa de jogada, que aumentariam a chance de sobrecarga do componente em SWI-Prolog. Observou-se que dessa forma a aplicação consegue limitar as jogadas do jogador em tempo hábil, sem interferência negativa na jogabilidade. Quanto ao visual da página no EAD do IME, buscou-se mantê-la simples, como pode ser bem visto na FIG 6.1, similar a um curso normal do instituto caso fosse disponibilizado para a plataforma. Nesse sentido, os alunos que acessarem o portal do EAD terão acesso à implementação – por meio de uma URL posta na página – mas também ao código fonte em Prolog e material de leitura complementar – envolvendo conceitos de teoria dos jogos e as regras e estratégias dos jogos implementados.
FIG. 6.1: Aparência do Portal no EAD. 39
7 CONCLUSÃO
Foi apresentado anteriormente como justificativa que este projeto deverá servir de suporte para o desenvolvimento de jogos matemáticos em Prolog, por parte dos alunos da cadeira de Lógica no curso de Engenharia de Computação do IME. Respeitou-se isso pois, consultando o material produzido durante este projeto, disponibilizado via EAD, como foi exposto no capítulo anterior, cujo conteúdo engloba tanto a teoria necessária à compreensão do projeto quanto o código fonte da aplicação final, devidamente comentado e legível, os alunos terão um melhor embasamento técnico, como se deseja. Neste projeto, uma plataforma Web com jogos estratégicos foi implementada com o intuito de apoiar a cadeira de Lógica no curso de Engenharia de Computação, no IME, na qual os alunos devem desenvolver uma inteligência capaz de jogar um jogo matemático contra um humano, usando a linguagem de programação Prolog. Para cumprir este objetivo, este projeto envolveu o desenvolvimento de algoritmos capazes de resolver problemas de teoria dos jogos com métodos genéricos, utilizando o algoritmo MinMax com poda Alpha-Beta e métodos de Monte Carlo para evitar o uso de algoritmos de valoração específicos para cada jogo, como indicado na seção 4.1 deste relatório, de implementação da camada de controle. A implementação dos jogos foi feita e conectada à inteligência matemática com sucesso. O jogo foi feito de maneira modular para ser instalado no portal de ensino a distância do Instituto Militar de Engenharia com interface gráfica descrita na seção 4.2. Ainda mais, todo o código foi disposto em ambiente digital aberto para estudos e otimizações. O desempenho da inteligência genérica também expôs a dificuldade da aplicação de um algoritmo capaz de tomar decisões ótimas em um pequeno tempo, demonstrando que métodos de valoração específicos são necessários para jogos com grande quantidade de jogadas possíveis, e com possibilidade de um número infinitos de jogadas possíveis, como indicado no capítulo 5, de resultados das implementações. Este projeto contribuiu para o uso de métodos genéricos para aplicação em jogos matemáticos com interface gráfica feita de maneira modular, auxiliando o estudo da aplicabilidade e desenvolvimento dessas tecnologias. Para trabalhos futuros, o algoritmo pode ser otimizado para realizar jogadas melhores mais rapidamente. Isso pode ser realizado através do aprimoramento dos algoritmos gené40
ricos, pela criação de funções avaliadoras específicas a cada jogo ou ainda aproveitando-se, como pontuado na seção 5.1, o suporte a multi-threading do SWI-Prolog. Mais jogos podem ser implementados, tais como Xadrez e Go, jogos matematicamente mais complexos que os abordados neste projeto. Ainda pode-se, também, tornar o algoritmo mais genérico e eficiente, com a intenção de criar uma biblioteca para jogos combinatórios em Prolog.
41
8 REFERÊNCIAS BIBLIOGRÁFICAS
IBM
100.
DeepBlue.
Disponível
em:
. Acesso em:
08 mai.
de 2016. BERLEKAMP, E. R.; CONWAY, J. H. ; GUY, R. K.
Winning Ways, for Your
Mathematical Plays: Games in particular. 2. ed. New York: AK Peters Ltd, 2001. CHASLOT, G. M. J.; WINANDS, M. H.; HERIK, H. J. V. D.; UITERWIJK, J. W. ; BOUZY, B. Progressive strategies for monte-carlo tree search. New Mathematics and Natural Computation, v. 4, n. 3, p. 343–357, 2008. GITHUB - SOFTWARE FREEDOM CONSERVANCY. Git-–fast-version-control. Disponível em: . Acesso em: 08 mai. de 2016. CONWAY, J. H. On Numbers and Games. 2. ed. New York: AK Peters Ltd, 2001. DEMAINE, E. D. Playing games with algorithms: Algorithmic combinatorial game theory. In: INTERNATIONAL SYMPOSIUM ON MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE, 3., 2001, Marianske Lazne. Proceedings... Heidelberg: Springer, 2001, p. 18–33. DINO, E. Programming ASP. NET MVC 2. Seattle: Microsoft Press, 2010. 415 p. (Relatório Técnico, 2011940367). ENCONTRO NACIONAL DA ASSOCIAÇÃO NACIONAL DE PÓS-GRADUAÇÃO E PESQUISA EM ADMINISTRAÇÃO (ANPAD), 30., 2006. Anais... [S.l.: s.n.], 2006. HAYWOOD JR, O. Military decision and game theory. Journal of the Operations Research Society of America, v. 2, n. 4, p. 365–385, 1954. HROMKOVIC, J. Algorithmics for hard problems - introduction to combinatorial optimization, randomization, approximation, and heuristics. Heidelberg: Springer, 2001. ISBN 978-3-540-66860-2.
42
JORNADA DE ATUALIZAÇÃO EM INFORMÁTICA (SBC), 29., 2010. Anais... [S.l.: s.n.], 2010. LESTA,
U.
nect
Swi-cs-pl
.NET
languages
-
A
CSharp
with
class
SWI-Prolog.
library
to
Disponível
.
Acesso
em:
conem: 08
mai. de 2016. DEEPMIND TECHNOLOGIES LIMITED.
AlphaGo – The first computer pro-
gram to ever beat a professional player at the game of go. Disponível em: . Acesso em: 08 mai. de 2016. MOTWANI, R.; RAGHAVAN, P. Randomized Algorithms. Cambridge: Cambridge University Press, 1995. 132 p. NEUMANN, J. V.; MORGENSTERN, O. Theory of Games and Economic Behavior. Princeton: Princeton University Press, 1944. NISAN, N.; ROUGHGARDEN, T.; TARDOS, E. ; VAZIRANI, V. V.
Algorithmic
Game Theory. Cambridge: Cambridge University Press, 2007. OSBORNE,
M.
game
theory.
J.;
RUBINSTEIN,
MIT
Press
A.
;
Books,
OTHERS. v.
1,
1994.
A
course
Disponível
in em:
. Acesso em: 08 mai. de 2016. PALERMO, J.; BOGARD, J.; HEXTER, E.; HINZE, M. ; SKINNER, J. ASP. NET MVC 4 in Action. Greenwich: Manning Publications, 2012. PEKING UNIVERSITY, PKU.
PKU JudgeOnline:
2D Nim. Disponível em:
. Acesso em: 11 ago. de 2016. PRESSMAN, R. S.
Software engineering: a practitioner’s approach. London:
Palgrave Macmillan, 2005. PRISNER, E. Game theory: through examples. Washington: Mathematical Association of America, 2014. QUAGLIO, VINÍCIUS GOMES. Técnicas de Inteligência Artificial aplicadas ao Jogo Othello: Um estudo comparativo. Disponível em: . Acesso em: 08 mai. de 2016. REFSNES, JIM.
HEGE
AND
Learn
REFSNES,
JavaScript
and
STÅLE Ajax
with
AND
REFSNES,
w3shools.
Disponível
KAI em:
0, moves(Pos, BoardSize, PosList),!, bestBound(PosList, BoardSize, Alpha, Beta, GoodPos, Val, Depth, BDepth) ; turnNumber(TurnNumber), TurnNumber >= BoardSize - 3, % Rotina de abertura staticValuationOpen(Pos, BoardSize, Val,_),! % MinMax + poda ; turnNumber(TurnNumber), TurnNumber < BoardSize - 3, % Rotina normal TurnNumber >= 2, staticValuation(Pos, BoardSize, SVal),! % MinMax + poda dinamicValuation(Pos, BoardSize, DVal, BDepth), % Monte Carlo Val is SVal + DVal,! ) .% Retorno da Posicao % Definindo sinal da funcao de valoracao staticValuationOpen(Turn/Board, BoardSize, Res) :boardBonusOpen(Turn, Board, BoardSize, ResBonus),
50
( min2Move(Turn/_), Res is - ResBonus ; max2Move(Turn/_), Res is ResBonus ),!. staticValuation(Turn/Board, BoardSize, Res) :- % Definindo sinal boardBonus(Turn, Board, BoardSize, ResBonus), ( min2Move(Turn/_), Res is - ResBonus ; max2Move(Turn/_), Res is ResBonus ),!. dinamicValuation(Turn/Board, BoardSize, Res, BDepth) :playRandomLoop(Board, BoardSize, Turn, Wins, Losses, BDepth), ( min2Move(Turn/_), Res is Losses - Wins ; max2Move(Turn/_), Res is Wins - Losses),!. bestBound([Pos|PosList], BoardSize, Alpha, Beta, GoodPos, GoodVal, Depth, BDepth) :NewDepth is Depth - 1, loopAlphaBeta(Pos, BoardSize, Alpha, Beta, _, Val, NewDepth, BDepth), goodEnough(PosList, BoardSize, Alpha, Beta, Pos, Val, GoodPos, GoodVal, Depth, BDepth). goodEnough([], _, _, _, Pos, Val, Pos, Val, _, _) :-!. % Parada goodEnough(_, _, Alpha, Beta, Pos, Val, Pos, Val, _, _) :( min2Move(Pos), Val > Beta,! % Max atingiu limite superior ; max2Move(Pos), Val < Alpha,! % Min atingiu limite inferior ) . goodEnough(PosList, BoardSize, Alpha, Beta, Pos, Val, GoodPos, GoodVal, Depth, BDepth) :newtBound(Alpha, Beta, Pos, Val, NewAlpha, NewBeta), % Ajusta limites bestBound(PosList, BoardSize, NewAlpha, NewBeta, Pos1, Val1, Depth, BDepth), betterBound(Pos, Val, Pos1, Val1, GoodPos, GoodVal). % Ajustando limites newtBound(Alpha, Beta, Pos, Val, Val, Beta) :-
51
min2Move(Pos), Val > Alpha,!. % Max aumentou limite superior newtBound(Alpha, Beta, Pos, Val, Alpha, Val) :max2Move(Pos), Val < Beta,!. % Min diminuiu limite inferior newtBound(Alpha, Beta, _, _, Alpha, Beta). % limites nao mudaram % Acha qual a melhor Posicao dado seu Retorno betterBound(_, _, Pos1, Val1, Pos1, Val1). % Fim betterBound(Pos, Val, _, Val1, Pos, Val) :- % Pos > Pos1 ( min2Move(Pos), Val > Val1,! ; max2Move(Pos), Val < Val1,! ) .
52
APÊNDICE 3: IMPLEMENTAÇÃO DA HEURÍSTICA DA JOGADA DA MÁQUINA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% HEURISTICA DA JOGADA DO COMPUTADOR %%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Funcao de valoracao da abertura boardBonusOpen(Turn, Board, BoardSize, Bonus) :enemy(Turn, EnemyTurn), countBonus(Turn, EnemyTurn, Board, BoardSize, Bonus, BoardSize, 0). countBonusOpen(_, _, _, _, Bonus, 0, Bonus) :-!. % Fim countBonusOpen(Turn, EnemyTurn, Board, BoardSize, Bonus, Loop, CounterBonus) :incrementalBonusBorder(Turn, Loop, Board, BoardSize, BonusBT), incrementalBonusBorder(EnemyTurn, Loop, Board, BoardSize, BonusBE), NewCounterBonus is CounterBonus + 2*BonusBT - BonusBE, NewLoop is Loop - 1, countBonusOpen(Turn, EnemyTurn, Board, BoardSize, Bonus, NewLoop, NewCounterBonus). % Calculo da funcao de valoracao (abertura Domineering) incrementalBonusBorder(v, Line, Board, BoardSize, Bonus) :( findPiece(Board, BoardSize, v, Line, 2), findPiece(Board, BoardSize, e, Line, 1) -> BonusA is 1 ; BonusA is 0), Aux is BoardSize - 1, ( findPiece(Board, BoardSize, v, Line, Aux), findPiece(Board, BoardSize, e, Line, BoardSize) -> BonusB is 1 ; BonusB is 0), Bonus is BonusA + BonusB. incrementalBonusBorder(h, Col, Board, BoardSize, Bonus) :-
53
( findPiece(Board, BoardSize, h, 2, Col), findPiece(Board, BoardSize, e, 1, Col) -> BonusA is 1 ; BonusA is 0), Aux is BoardSize - 1, ( findPiece(Board, BoardSize, h, Aux, Col), findPiece(Board, BoardSize, e, BoardSize, Col) -> BonusB is 1 ; BonusB is 0), Bonus is BonusA + BonusB. % Funcao de valoracao normal boardBonus(Turn, Board, BoardSize, Bonus) :enemy(Turn, EnemyTurn), countBonus(Turn, EnemyTurn, Board, BoardSize, Bonus, BoardSize, 0). countBonus(_, _, _, _, Bonus, 0, Bonus) :-!. % Fim countBonus(Turn, EnemyTurn, Board, BoardSize, Bonus, Loop, CounterBonus ) :incrementalBonusBorder(Turn, Loop, Board, BoardSize, BonusBT), incrementalBonusBorder(EnemyTurn, Loop, Board, BoardSize, BonusBE), incrementalBonusField(Turn, Board, BoardSize, Loop, BonusFT, BoardSize, 0), incrementalBonusField(EnemyTurn, Board, BoardSize, Loop, BonusFE, BoardSize, 0), NewCounterBonus is CounterBonus + 2*BonusBT - BonusBE + BonusFT - BonusFE, NewLoop is Loop - 1, countBonus(Turn, EnemyTurn, Board, BoardSize, Bonus, NewLoop, NewCounterBonus). incrementalBonusField(Sign, Board, BoardSize, _, Bonus, _, _) :moves(Sign/Board, BoardSize, PosList),!, length(PosList, Res), Bonus is Res.
54
% Busca de Monte Carlo playRandomLoop(Board, BoardSize, Sign, Wins, Losses, Loop) :countGames(Board, BoardSize, Sign, Wins, Losses, Loop, 0, 0). countGames(_, _, _, CounterWin, CounterLoss, 0, CounterWin, CounterLoss ) :-!. % Fim countGames(Board, BoardSize, Sign, Wins, Losses, Loop, CounterWin, CounterLoss) :playRandom(Board, BoardSize, Sign, Win, Loss), NewCounterWin is CounterWin + Win, NewCounterLoss is CounterLoss + Loss, NewLoop is Loop - 1, countGames(Board, BoardSize, Sign, Wins, Losses, NewLoop, NewCounterWin, NewCounterLoss). playRandom(Board, BoardSize, Sign, Win, Loss) :-% Jogo aleatorio ( moveRandom(Board, BoardSize, Sign, NewBoard),! -> enemy(Sign, NewSign), playRandom(NewBoard, BoardSize, NewSign, Loss, Win),! ; Win is 0, Loss is 1, true ) .
55
APÊNDICE 4: MANIPULAÇÃO DO JOGO E INTERFACEAMENTO
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%% MANIPULACAO DO JOGO %%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Convencoes turnToSign(v, v). turnToSign(h, h). enemy(v, h). enemy(h, v). nextPlayer(v, h). nextPlayer(h, v). % Guarda pecas no tabuleiro putSign(Board, BoardSize, Line, Col, Sign, NewBoard) :Place is ((Line - 1) * BoardSize) + Col, Board =.. [b|List], replace(List, Place, Sign, NewList), NewBoard =.. [b|NewList]. % Manipulacao de particulas atomicas replace(List, Place, Val, NewList) :replace(List, Place, Val, NewList, 1). replace( [], _, _, [], _). replace([_|Xs], Place, Val, [Val|Ys], Place) :NewCounter is Place + 1, !, replace(Xs, Place, Val, Ys, NewCounter). replace([X|Xs], Place, Val, [X|Ys], Counter) :NewCounter is Counter + 1, replace(Xs, Place, Val, Ys, NewCounter).
56
% Retorna, numericamente, a posicao de uma peca findPiece(Board, BoardSize, S, Line, Col) :arg(Num, Board, S), Temp is Num / BoardSize, ceiling(Temp, Line), Col is Num - ((Line - 1) * BoardSize). % Recebe a peca correta getPiece(Board, BoardSize, Line, Col, P) :getPos(Board, BoardSize, Line, Col, P), ( P = v ; P = h). % Recebe a posicao getPos(Board, BoardSize, Line, Col, Sign) :Num is ((Line - 1) * BoardSize) + Col, arg(Num, Board, Sign). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% PREDICADOS CENTRAIS DO JOGO %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Define tamanho do tabuleiro setBoardSize(BoardSize) :retractall(boardSize(_)), assert(boardSize(BoardSize)). % IA joga na vertical computerV :retractall(min2Move(_)),retractall(max2Move(_)), assert(min2Move(h/_)),assert(max2Move(v/_)). % IA joga na horizontal computerH :retractall(min2Move(_)),retractall(max2Move(_)),
57
assert(min2Move(v/_)),assert(max2Move(h/_)). % Movimento do Jogador (P1=(X1,Y1) superior/esquerda de P2=(X2,Y2)) playHuman(NewBoard, Sign, Board, X1, Y1, X2, Y2) :boardSize(BoardSize), move(Board, BoardSize, Sign, X1, Y1, X2, Y2, NewBoard),!.% Jogada % Movimento da IA playComputer(NewBoard, Sign, Board, Level, Victory, Defeat) :boardSize(BoardSize), ( validMove(Board, BoardSize, Sign, _),! -> Defeat = false, moveComputer(NewBoard, Sign, Board, Level),!, victoryBoard(NewBoard, Sign, Victory),! ; Defeat = true, NewBoard = Board, Victory = false ) ,!. moveComputer(NewBoard, Sign, Board, Level) :boardSize(BoardSize), gameRunDown(BoardSize, Board, TurnNumber), retractall(turnNumber(_)), assert(turnNumber(TurnNumber)), callMinMax(Sign/Board, BoardSize, -1000000, 1000000, _/NewBoard, _, Level, 10),!. gameRunDown(BoardSize, Board, TurnNumber) :Board =.. [b|ListBoard], countElements(ListBoard, e, Empty), TurnNumber is Empty / BoardSize.
58
countElements([X|T], X, Y):countElements(T, X, Z), Y is 1 + Z. countElements([X1|T], X, Z):X1 \= X, countElements(T, X, Z). countElements([], _, 0). victoryBoard(Board, Sign, Victory) :boardSize(BoardSize), enemy(Sign, EnemySign), ( validMove(Board, BoardSize, EnemySign, _),! -> Victory = false ; Victory = true).
59
APÊNDICE 5: REGRAS DO JOGO E VALIDAÇÃO DE MOVIMENTOS (DOMINEERING)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% JOGADAS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Realiza o movimento das pecas move(Board, BoardSize, Sign, NewBoard) :validMove(Board, BoardSize, Sign, NewBoard).%Valida o movimento. move(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard) :validMove(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard). % Um movimento e valido se: validMove(Board, BoardSize, Sign, NewBoard) :validStdMove(Board, BoardSize, Sign, _, _, _, _, NewBoard). validMove(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard) :validStdMove(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard). %Movimento normal. % Valida um movimento normal validStdMove(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard) :validateMove(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2), movePiece(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard). % Valida um unico movimento normal validateMove(Board, BoardSize, v, ToL1, ToC1, ToL2, ToC2) :findPiece(Board, BoardSize, e, ToL1, ToC1), ToL2 is ToL1 + 1, ToC2 is ToC1, findPiece(Board, BoardSize, e, ToL2, ToC2). validateMove(Board, BoardSize, h, ToL1, ToC1, ToL2, ToC2) :-
60
findPiece(Board, BoardSize, e, ToL1, ToC1), ToL2 is ToL1, ToC2 is ToC1 + 1, findPiece(Board, BoardSize, e, ToL2, ToC2). % Realiza um movimento normal movePiece(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard) :putSign(Board, BoardSize, ToL1, ToC1, Sign, TempBoard), putSign(TempBoard, BoardSize, ToL2, ToC2, Sign, NewBoard). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% JOGADAS PSEUDO-ALEATORIAS %%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Realiza o movimento das pecas moveRandom(Board, BoardSize, Sign, NewBoard) :validMoveRandom(Board, BoardSize, Sign, NewBoard).%Valida o movimento. moveRandom(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard) :validMoveRandom(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard).%Valida o movimento. % Um movimento e valido se: validMoveRandom(Board, BoardSize, Sign, NewBoard) :validStdMoveRandom(Board, BoardSize, Sign, _, _, _, _, NewBoard). validMoveRandom(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard) :validStdMoveRandom(Board, BoardSize, Sign, ToL1, ToC1, ToL2, ToC2, NewBoard). % Movimento normal. % Valida um movimento normal, quer-se realizar somente uma jogada. validStdMoveRandom(Board, BoardSize, Sign, _, _, _, _, NewBoard) :moves(Sign/Board, BoardSize, PosList),!, random_member(_/NewBoard, PosList),!.
61
% Proximos movimentos moves(Turn/Board, BoardSize, [B|Bs]) :nextPlayer(Turn, NextTurn), findall(NextTurn/NewBoard, validMove(Board, BoardSize, Turn, NewBoard), [B|Bs]).
62
APÊNDICE 6: PROGRAMA PARA TESTE E VALIDAÇÃO
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Author: Robinson Callou % Date: 02/04/2016 % % Domineering modelo Jogador Vs IA com multiplas dificuldades % Indicacao: 2-Principiante, 3-Amador, %
4-intermediario, 5-Avancado, 6-Mestre
% % setBoardSize(BoardSize). - Define tamanho do tabuleiro % computerV. - IA joga na vertical % computerH. - IA joga na horizontal % - Movimento do Jogador (P1=(X1,Y1) superior/esquerda de P2=(X2,Y2)) % playHuman(NewBoard, Sign, Board, X1, Y1, X2, Y2). % - Movimento da IA % playComputer(NewBoard, Sign, Board, Level, Victory, Defeat). % % Tabuleiro inicial (exemplo) % % 1 2 3 4 5 6 7 8 % 1| | | | | | | | | % 2| | | | | | | | | % 3| | | | | | | | | % 4| | | | | | | | | % 5| | | | | | | | | % 6| | | | | | | | | % 7| | | | | | | | | % 8| | | | | | | | | % %
63
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% PREDICADOS CENTRAIS DO TESTE %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Global parameter boardSize(9). % Initial board initBoard( b( e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e, e,e,e,e,e,e,e,e,e ) ). % Gameplay :-dynamic min_to_move/1, max_to_move/1. % AI Vs AI play(PlayLevel1, PlayLevel2) :initBoard(PlayBoard), callPlay1(PlayLevel1, PlayLevel2, PlayBoard). callPlay1(Level1, Level2, Board) :printBoard(Board),
64
retractall(max2Move(_)), retractall(min2Move(_)), assertz(min2Move(v/_)),assertz(max2Move(h/_)), playComputer(NewBoard, v, Board, Level1, Victory, Defeat),!, ( Victory = true, Defeat = false,! ; Victory = true, Defeat = false,! ; callPlay2(Level2, Level1, NewBoard) ) . callPlay2(Level1, Level2, Board) :printBoard(Board), retractall(max2Move(_)), retractall(min2Move(_)), assertz(min2Move(h/_)),assertz(max2Move(v/_)), playComputer(NewBoard, h, Board, Level1, Victory, Defeat),!, ( Victory = true, Defeat = false,! ; Victory = true, Defeat = false,! ; callPlay1(Level2, Level1, NewBoard) ) . % Input Process process(X1/Y1, X1, Y1). % Prints printBoard(Board) :boardSize(BoardSize), write(' '), printHeader(BoardSize, 1),
65
printBoardLines(Board, BoardSize, BoardSize, 1). printHeader(0, _) :-nl, !. printHeader(Loop, Num) :write(' '), write(Num), NewLoop is Loop - 1, NewNum is Num + 1, printHeader(NewLoop, NewNum). printBoardLines(_, _, 0, _) :-!. printBoardLines(Board, BoardSize, Loop, Num) :write(Num), printLine(Board, BoardSize, Num), NewLoop is Loop - 1, NewNum is Num + 1, printBoardLines(Board, BoardSize, NewLoop, NewNum). printLine(Board, BoardSize, Num) :write('|'), printLine(Board, BoardSize, Num, 1). printLine(_, BoardSize, _, Loop) :Loop is BoardSize + 1, nl,!. printLine(Board, BoardSize, Num, Y1) :getSign(Board, BoardSize, Num, Y1, S), write(S), write('|'), Y2 is Y1 + 1, printLine(Board, BoardSize, Num, Y2). printBoardList([]) :-!. printBoardList([_/Board|PosList]) :printBoard(Board), printBoardList(PosList).
66
% Recebe o simbolo getSign(Board, BoardSize, Line, Col, Sign) :getPos(Board, BoardSize, Line, Col, S), sign(S, Sign). % Notacao sign(v, 'V'). % Peca sign(h, 'H'). % Peca sign(e, ' '). % Casa vazia %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% FIM DO PROGRAMA %%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
67
Lihat lebih banyak...
Comentários
