Avaliação de aprendizagem de agentes baseados em sistemas ...‡… · Catalogação na fonte Bibliotecária Jane Souto Maior, CRB4 -571 F224a Farias , Denys Lins de Avaliação

Pós-Graduação em Ciência da Computação

“AVALIAÇÃO DE APRENDIZAGEM DE AGENTES

BASEADOS EM SISTEMAS CLASSIFICADORES PARA

JOGOS DIGITAIS”

Por

Denys Lins de Farias

Dissertação de Mestrado

Universidade Federal de Pernambuco

[email protected]

www.cin.ufpe.br/~posgraduacao

RECIFE 2014

Universidade Federal de Pernambuco

CENTRO DE INFORMÁTICA

PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

Denys Lins de Farias

AVALIAÇÃO DE APRENDIZAGEM DE AGENTES BASEADOS EM SISTEMAS CLASSIFICADORES PARA JOGOS DIGITAIS

ORIENTADOR: Geber Lisboa Ramalho CO-ORIENTADOR: Ricardo Martins de Abreu Silva

RECIFE 2014

Este trabalho foi apresentado à Pós-Graduação em Ciência da

Computação do Centro de Informática da Universidade Federal de

Pernambuco como requisito parcial para obtenção do grau de Mestre em

Ciência da Computação.

Catalogação na fonte

Bibliotecária Jane Souto Maior, CRB4-571

F224a Farias, Denys Lins de Avaliação de aprendizagem de agentes baseados em

sistemas classificadores para jogos digitais / Denys Lins de Farias. – Recife: O Autor, 2014.

100 f.: il., fig., tab. Orientador: Geber Lisboa Ramalho. Dissertação (Mestrado) – Universidade Federal de

Pernambuco. CIN. Ciência da Computação, 2014. Inclui referências.

1. Ciência da computação. 2. Aprendizagem de máquina. 3. Jogos digitais. 4. Otimização. I. Ramalho, Geber Lisboa (orientador). I. Título. 004 CDD (23. ed.) UFPE- MEI 2014-162

Dissertação de Mestrado apresentada por Denys Lins de Farias à Pós-

Graduação em Ciência da Computação do Centro de Informática da

Universidade Federal de Pernambuco, sob o título “Avaliação de

Aprendizagem de Agentes Baseados em Sistemas Classificadores para

Jogos Digitais” orientada pelo Prof. Geber Lisboa Ramalho e aprovada pela

Banca Examinadora formada pelos professores:

______________________________________________

Prof. Sérgio Ricardo de Melo Queiroz Centro de Informática / UFPE

______________________________________________ Prof. André Mauricio Cunha Campos

Departamento de Informática e Matemática Aplicada / UFRN

_______________________________________________ Prof. Geber Lisboa Ramalho

Centro de Informática / UFPE Visto e permitida a impressão. Recife, 4 de setembro de 2014. ___________________________________________________

Profa. Edna Natividade da Silva Barros Coordenadora da Pós-Graduação em Ciência da Computação do Centro de Informática da Universidade Federal de Pernambuco.

À minha mãe Nilsa, com amor.

Agradecimentos

À minha mãe, Nilsa Tigre, por todo o esforço realizado e todo o amor ensinado.À minha família e meus amigos, pelo carinho e compreensão de sempre.Aos meus colegas do Centro de Informática, pela abertura de diálogo e incrível solicitude,

importantes na compreensão de muitos problemas.Ao meu orientador, Geber Ramalho, por ter acreditado neste trabalho, por compartilhar

sua experiência e por todo o acompanhamento durante o mestrado.Ao meu co-orientador, Ricardo Martins, pelas novas ideias e perspectivas agregadas ao

trabalho.A todos que de alguma forma colaboraram para a realização deste trabalho, através da

palavra ou do exemplo.

There are times, at least for now, when we must be content to love the

questions themselves.

—NEIL DEGRASSE TYSON

Resumo

A diversão dos jogos digitais está relacionada com a proposição de níveis adequadosde desafios, para que o jogador não se frustre com desafios muito difíceis, nem fique entediadocom desafios muito fáceis. As soluções propostas na literatura para este problema, chamadode Ajuste Dinâmico de Dificuldade (Dynamic Difficulty Adjustment, DDA), utilizam agentesadaptativos que buscam adequar seu comportamento às capacidades do jogador humano contraquem jogam. Algumas técnicas (aprendizagem por reforço, algoritmos genéticos, Dynamic

Scripting) podem ser adaptadas para que o agente atue de forma sub-ótima, isto é, que elejogue menos bem diante de um jogador humano pouco experiente ou pouco habilidoso. Porém,quando se enfrenta jogadores muito experientes ou habilidosos, tais agentes não conseguematuar no nível do jogador. Estas técnicas podem ser vistas, simplificadamente, como sistemasde regras condição-ação em que se pode aprender os pesos de tais regras ou criar novas regras.Nessa estrutura, existe uma classe de algoritmos de aprendizagem online, os chamados SistemasClassificadores (SCs), que permite tanto aprender pesos de regras quanto criar novas regras, masque, até onde sabemos, ainda não foi utilizada em DDA.

Diante deste cenário, o objetivo deste trabalho foi de avaliar a aplicabilidade de SC a DDA.Como sabemos que SC, a exemplo de Dynamic Scripting, pode ser facilmente adaptada parater um desempenho subótimo, nós nos focamos em avaliar se SC poderia ter uma competênciamelhor do que os outros, em particular do que aprendizagem por reforço, a melhor das técnicasem avaliação anterior. Para tanto, tivemos de enfrentar o conhecido problema da parametrizaçãodos SCs, e o fizemos utilizando a técnica de otimização F-Race, o que gerou dois agentesbaseados em SCs com parâmetros diferentes.

Como caso de estudo, adotamos o jogo de luta em tempo real Knock’em, utilizado emoutros trabalhos. Conduzimos um experimento para avaliar a competência entre os agentesbaseados em SCs e um baseado em Q-Learning, contra agentes de comportamento aleatórioe previsível. Os resultados indicaram que o agente parametrizado pelo F-Race obteve melhordesempenho que o agente de referência contra oponente previsível, perdendo contra o agentede comportamento aleatório. Verificamos a viabilidade do uso de SCs em DDA, em uma sériede partidas, na qual o agente operou no nível dos oponentes, mas apresentou razoável variaçãonos resultados. Realizamos mais um experimento entre o agente proposto parametrizado peloF-Race e o baseado em Q-Learning, contando com avaliação quantitativa e qualitativa. Ambosagentes apresentaram bons resultados, com o agente de referência obtendo maior vantageminicial, porém os jogadores foram capazes de reverter a situação ao longo do experimento.

Palavras-chave: Sistemas Classificadores. Agentes Adaptativos. Aprendizagem de Máquina.F-Race.

Abstract

The fun of digital games is related to the proposition of adequate levels of challenge inorder not to get the player frustrated with many difficult challenges, neither to get him boredwith challenges too easy for him. The proposed solutions in the literature for this problem, calledDynamic Difficulty Adjustment (DDA), use adaptive agents trying to adjust their behaviour tothe capabilities of the human player against whom they play. Some techniques (reinforcementlearning, genetic algorithms, Dynamic Scripting) can be adapted so the agent act in a sub-optimalway, that is, it plays not so well in front of an inexperienced or poorly skilled human player.However, when facing highly experienced or skilled players, such agents fail to act on theplayer’s level. These techniques can be seen, simply, as a condition-action rules in which theycan learn the weights of these rules or create new rules. In this structure, there is a class of onlinelearning algorithms called Classifier Systems (CS), which allows both learning weights of rulesand creating new rules, but, to our knowledge, has not yet been used in DDA.

Given this scenario, the objective of this study was to evaluate the applicability of CS’s inDDA. As we know that CS, like Dynamic Scripting, can be easily adapted to have a sub-optimalperformance, we focus on assessing whether CS could have a better competence than otherscould, in particular than reinforcement learning, which is the better technique in a previousevaluation. To do so, we had to face the known issue of parameters setting of CS’s, and wedid it by using the optimization technique F-Race, which spawned two CS’s based agents withdifferent parameters.

As a case study, we adopted the real-time fighting game Knock’em used in other works.An experiment was conducted to assess competence among agents based on CS’s and one basedon Q-Learning against agents with random and predictable behaviour. The results showedthat the agent parameterized by F-Race yields better performance than the referral agent doesagainst the predictable opponent, losing against the agent with random behaviour. We verifiedthe feasibility of using CS’s in the context of DDA, in a series of matches, in which the agentoperated at the level of opponents, but showed reasonable variation in the results. We carriedout another experiment between the proposed agent parameterized by F-Race and the one basedon Q-Learning, relying on quantitative and qualitative assessment. Both agents showed goodresults, with the referral agent getting higher initial scores, but the players were able to reversethe situation throughout the experiment.

Keywords: Classifier Systems. Adaptive Agents. Machine Learning. F-Race.

Lista de Figuras

3.1 Captura de uma partida do jogo Knock’em . . . . . . . . . . . . . . . . . . . . 36

4.1 Arquitetura do Sistema Classificador baseado em Precisão (eXtended Classifier

System (XCS)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.2 Desempenho médio de 3 séries de 200 ciclos com 1 partida de treinamento (con-

tra RDPlayer) e 4 partidas de teste (contra RDPlayer) entre o agente XCSPlayer

v.1 e RLTPlayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.3 Desempenho médio de 3 séries de 200 ciclos com 1 partida de treinamento (con-

tra RDPlayer) e 4 partidas de teste (contra SMPlayer) entre o agente XCSPlayer

v.1 e RLTPlayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.1 Número de configurações candidatas sobreviventes ao longo da corrida. . . . . 615.2 A evolução do desempenho acumulado das configurações candidatas ao longo

da corrida. Em destaque, a média tracejada em vermelho, a mediana contínuapreta, regiões definidas pelos quartis em cinza claro, "fios de bigode"em cinzaescuro, a região pontilhada indicando a existência de apenas duas configuraçõescandidatas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.3 Desempenho médio de 3 séries de 200 ciclos com 1 partida de treinamento (con-tra RDPlayer) e 4 partidas de teste (contra RDPlayer) entre o agente XCSPlayer




tra RDPlayer) e 4 partidas de teste (contra RDPlayer) entre o agente XCSPlayer

v.1 e XCSPlayer v.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665.6 Desempenho médio de 3 séries de 200 ciclos com 1 partida de treinamento (con-


v.1 e XCSPlayer v.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1 Desempenho médio dos treinamentos realizados pelos professores contra os trêsavaliadores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.2 1100 ciclos de 1 partida de treino e 1 partida de teste contra RDPlayer . . . . . 736.3 1100 ciclos de 1 partida de treino e 1 partida de teste contra SMPlayer . . . . . 746.4 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.1 e

RDPlayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.5 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.1 eSMPlayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.6 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.2 eRDPlayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.7 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.2 eSMPlayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

7.1 Pontuação média dos participantes por série de partidas, na ordem de ocorrên-cia: na etapa de treinamento (1), nas três rodadas de avaliação contra agenteRLTPlayer (2,4,6) e agente XCSPlayer v.2 (3,5,7); pontuação negativa indicavantagem do agente sobre o participante; cruzes representam a média do conjunto. 88

Lista de Tabelas

4.1 Parâmetros do Agente RLTPlayer . . . . . . . . . . . . . . . . . . . . . . . . 504.2 Parâmetros do Agente XCSPlayer . . . . . . . . . . . . . . . . . . . . . . . . 56

6.1 Médias dos agentes avaliados contra RDPlayer - dados da Figura 6.2 . . . . . . 736.2 Desvio padrão dos agentes avaliados contra RDPlayer - dados da Figura 6.2 . . 746.3 Valores-p do teste de Wilcoxon para amostras independentes em lutas contra

RDPlayer - dados da Figura 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . 746.4 Médias dos agentes avaliados contra SMPlayer - dados da Figura 6.3 . . . . . . 756.5 Desvio padrão dos agentes avaliados contra SMPlayer - dados da Figura 6.3 . . 756.6 Valores-p do teste de Wilcoxon para amostras independentes em lutas contra

SMPlayer - dados da Figura 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . 756.7 Médias do agente XCSPlayer v.1 contra RDPlayer por intervalo e respectivos

valores-p do teste de Wilcoxon para amostras independentes em relação à médianula - dados da Figura 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.8 Médias do agente XCSPlayer v.1 contra SMPlayer por intervalo e respectivosvalores-p do teste de Wilcoxon para amostras independentes em relação à médianula - dados da Figura 6.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.9 Médias do agente XCSPlayer v.2 contra RDPlayer por intervalo e respectivosvalores-p do teste de Wilcoxon para amostras independentes em relação à médianula - dados da Figura 6.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.10 Médias do agente XCSPlayer v.2 contra SMPlayer por intervalo e respectivosvalores-p do teste de Wilcoxon para amostras independentes em relação à médianula - dados da Figura 6.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

7.1 Médias gerais dos participantes em cada série de lutas e valores-p do teste deWilcoxon pareado - dados da Figura 7.1 . . . . . . . . . . . . . . . . . . . . . 87

Lista de Acrônimos

AG Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

AR Aprendizagem por Reforço . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

DDA Dynamic Difficulty Adjustment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

DS Dynamic Scripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

IA Inteligência Artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

NPC Non-Player Character . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

SC Sistema Classificador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

XCS eXtended Classifier System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

ZCS Zeroth-Level Classifier System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Sumário

1 Introdução 161.1 Motivação do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.3 Estrutura da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2 Inteligência Artificial em Jogos Digitais 192.1 Desenvolvimento de Jogos Digitais . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Inteligência Artificial em Jogos Digitais . . . . . . . . . . . . . . . . . . . . . 20

2.2.1 Problemas Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . 212.2.1.1 Comportamento de Agentes . . . . . . . . . . . . . . . . . . 212.2.1.2 Ajuste Dinâmico de Dificuldade . . . . . . . . . . . . . . . 212.2.1.3 Modelagem de Experiência de Jogadores . . . . . . . . . . . 222.2.1.4 Outros Problemas . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 Ajuste de Dificuldade em Jogos . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.1 Ajuste Manual de Dificuldade . . . . . . . . . . . . . . . . . . . . . . 232.3.2 Ajuste Dinâmico de Dificuldade . . . . . . . . . . . . . . . . . . . . . 24

2.3.2.1 Aprendizagem no Comportamento de Personagens . . . . . . 252.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Trabalhos Relacionados 293.1 Balanceamento com Dynamic Scripting . . . . . . . . . . . . . . . . . . . . . 293.2 Balanceamento baseado em Algoritmos Genéticos . . . . . . . . . . . . . . . . 303.3 Balanceamento baseado em Aprendizagem por Reforço . . . . . . . . . . . . . 32

3.3.1 Abordagem de Balanceamento baseada em Desafio . . . . . . . . . . . 333.4 Experimentos com DDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.5 Caso de Estudo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.6 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Solução Proposta e sua Evolução 384.1 Sistemas Classificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.1.1 Primeiras Investigações . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2 Sistema Classificador baseado em Precisão . . . . . . . . . . . . . . . . . . . 40

4.2.1 Sistema de Desempenho . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.2 Sistema de Atribuição de Crédito . . . . . . . . . . . . . . . . . . . . 424.2.3 Sistema de Descoberta . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.3 Interface dos Agentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.4 Agentes de Referência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.5 Agente XCS Básico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.5.1 Experimento Preliminar . . . . . . . . . . . . . . . . . . . . . . . . . 524.6 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5 Configuração Automática de Parâmetros do Agente Proposto 575.1 F-Race . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.1.1 Funcionamento da Técnica . . . . . . . . . . . . . . . . . . . . . . . . 585.1.1.1 Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.1.1.2 Testes de Hipótese . . . . . . . . . . . . . . . . . . . . . . . 585.1.1.3 Condição de Parada . . . . . . . . . . . . . . . . . . . . . . 59

5.1.2 Aplicação do F-Race na Corrida . . . . . . . . . . . . . . . . . . . . . 595.1.3 Análise da Corrida . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.1.4 Dificuldades de Implementação . . . . . . . . . . . . . . . . . . . . . 635.1.5 Experimento Preliminar . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.2 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6 Experimentos entre Agentes 686.1 Metodologia Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.2 Treinamento Offline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.2.1 Metodologia Específica . . . . . . . . . . . . . . . . . . . . . . . . . . 696.2.2 Resultados do Experimento . . . . . . . . . . . . . . . . . . . . . . . 70

6.3 Avaliação de Competência Adquirida . . . . . . . . . . . . . . . . . . . . . . 726.3.1 Metodologia Específica . . . . . . . . . . . . . . . . . . . . . . . . . . 726.3.2 Resultados do Experimento . . . . . . . . . . . . . . . . . . . . . . . 736.3.3 Análise de Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.4 Avaliação de Ajuste Dinâmico de Dificuldade . . . . . . . . . . . . . . . . . . 776.4.1 Metodologia Específica . . . . . . . . . . . . . . . . . . . . . . . . . . 776.4.2 Resultados dos Experimento . . . . . . . . . . . . . . . . . . . . . . . 786.4.3 Análise de Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

7 Experimento entre agentes e humanos 827.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

7.1.1 Etapa de Treinamento . . . . . . . . . . . . . . . . . . . . . . . . . . 837.1.2 Etapa de Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 857.1.3 Dados Coletados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

7.2 Resultados do Experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867.3 Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

8 Conclusão 918.1 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Referências 96

161616

1Introdução

Este capítulo apresenta um breve contexto do trabalho. Primeiro, as principais motivaçõesdo problema escolhido são apresentadas. Em seguida, são declarados os objetivos que orientamnossa investigação. A última seção oferece uma visão geral dos demais capítulos.

1.1 Motivação do Trabalho

A indústria de jogos digitais, ou simplesmente de jogos como considerado neste traba-lho, mostrou-se bastante aquecida nos últimos anos. Ocorreram lançamentos de títulos comarrecadações recordes para toda indústria de entretenimento, amadurecimento dos sistemas dedistribuição digital e da estratégia de autopublicação, diversificação de público alvo e de modelosde negócios (e.g. freemium, pay what you want, jogos baseados em anúncios). Enquanto aplataforma móvel consolidou-se com parcela significativa do mercado, a plataforma tradicionalde computadores e consoles ficou mais equipada tanto em hardware quanto em ferramentas dedesenvolvimento disponíveis.

Essa condição tem permitido o desenvolvimento de jogos mais complexos, com gráficosmais realistas, enredos mais elaborados. Porém, algumas áreas da produção de jogos aindaavançam lentamente, como é o caso da inteligência artificial. Além de problemas recorrentes,como por exemplo comportamento e credibilidade de personagens, existem problemas maisrecentes a ser tratados por ela também, como a geração automática de conteúdo e a modelagemde experiência do jogador (YANNAKAKIS; TOGELIUS, 2014).

Um problema importante é o de ajuste dinâmico de dificuldade, ou Dynamic Difficulty

Adjustment (DDA). Se o jogo, como atividade interativa que impõe desafios ao jogador (JUUL,2003), apresenta nível de dificuldade incompatível com o nível de experiência de quem joga,a satisfação do jogador pode se comprometer pela frustração com um jogo muito difícil oupelo desinteresse com um jogo muito fácil. Assim, torna-se crítico ajustar adequadamente adificuldade.

Soluções propostas para o problema de DDA são caracterizadas em geral como mecanis-mos que avaliam a dificuldade percebida pelo jogador com base na evolução dele, adaptando-se

1.2. OBJETIVOS 17

a ela continuamente. O conceito de adaptação está associado a outros dois conceitos: compe-tência e desempenho (CHOMSKY, 1965). A competência se refere ao conhecimento que oagente adquire sobre os estados e as ações. O desempenho é traduzido como o nível de uso dacompetência, ou o nível de atuação do agente. Essa separação permite que o conhecimento doagente não esteja condicionado ao nível de atuação do agente. Assim, enquanto o desempenhoevolui (para acompanhar um oponente mais difícil) e regride (para atuar contra um oponentemais fácil), a competência somente evolui (o agente acumula conhecimento, sem esquecê-lo).

Algumas das soluções para o problema (SPRONCK; SPRINKHUIZEN-KUYPER;POSTMA, 2004; ANDRADE et al., 2005) obtiveram êxito em estimar a dificuldade e adaptar onível de dificuldade de um jogo ao nível do jogador. Por outro lado, indicaram que a aprendiza-gem de competência pela inteligência artificial ainda é um problema em aberto. As soluçõesdependem de bastante conhecimento heurístico ou acabam por não alcançar um nível satisfatóriode desempenho contra jogadores mais experientes ou mais habilidosos.

Essas soluções podem ser simplificadas como sistemas de regras condição-ação querealizam aprendizagem de pesos das regras ou são capazes de gerar novas regras. Uma classe dealgoritmos que possui essas características é a de Sistemas Classificadores (SCs) (HOLLAND;REITMAN, 1977; BOOKER; GOLDBERG; HOLLAND, 1989), os quais permitem realizarambas as operações em tempo de execução. Apesar da similaridade de características e do tempode existência da técnica, existem poucas aplicações na área de jogos e, até onde sabemos, não háaplicação em DDA.

Neste contexto, investigamos a viabilidade de aplicação de sistemas classificadores aoproblema de DDA. Uma vez que pudemos testar o ajuste de atuação de uma versão mais básicadesses sistemas (FARIAS, 2011), e conferimos que é possível adaptá-los para atuar em nívelsubótimo, o escopo deste trabalho concentra na capacidade do sistema adquirir competência emcomparação às outras soluções, em especial, a baseada em Aprendizagem por Reforço (AR),considerada a melhor das técnicas em avaliação anterior (ANDRADE et al., 2005).

1.2 Objetivos

A principal questão que o trabalho busca responder é "Dado que há espaço para melhoria

no problema de ajuste dinâmico de dificuldade, a aplicação de sistemas classificadores é viável

como solução para aquisição de competência em jogos de luta de tempo real?". Essa perguntanos leva à seguinte: "Sistemas classificadores apresentam bom desempenho comparados a outra

abordagem da literatura para o mesmo problema?". Outra questão possível é "A abordagem

baseada em sistemas classificadores é adequada para a adaptação da dificuldade ao nível do

oponente no problema tratado?".Este trabalho tem por objetivos testar a viabilidade de aplicação e o desempenho de

sistemas classificadores no problema de aprendizagem de competência de agentes individuais,em jogos de luta de tempo real. Além disso, o trabalho avalia a aplicação dessa abordagem no

1.3. ESTRUTURA DA DISSERTAÇÃO 18

contexto de adaptação dinâmica de dificuldade.

1.3 Estrutura da Dissertação

Este primeiro capítulo trata das motivações para o trabalho e dos objetivos definidos.O segundo capítulo introduz o leitor ao processo de criação de jogos, listando em seguida osproblemas mais comuns enfrentados pela equipe de desenvolvimento cujas soluções se utilizamde Inteligência Artificial (IA). O foco do capítulo passa então a ser o problema de ajuste dinâmicode dificuldade, explicando um pouco mais sobre o processo de balanceamento, os conceitosbásicos envolvidos e as abordagens mais comuns para tratá-lo.

No terceiro capítulo, são apresentadas as principais técnicas na aplicação de DDA emtempo real, destacando como adquirem competência e como adaptam o nível de dificuldade, alémdos aspectos mais relevantes que influenciaram a escolha da abordagem estudada. Além disso,são relatados os experimentos que antecederam o trabalho e levantou informações relevantespara pesquisa, além da explicação do caso de estudo. No quarto capítulo, é apresentada aabordagem proposta, explicando desde a visão mais geral de SC, comentando o primeiro trabalhocom um algoritmo da classe, e resultando na explicação detalhada da arquitetura, dos métodosutilizados, e das dificuldades de implementação encontradas, concluindo com a discussão detestes preliminares. O quinto capítulo trata da etapa de parametrização automática do agenteconstruído, explicando como o algoritmo F-Race procurou uma configuração melhor para oagente. Ao final do capítulo, novos testes preliminares são relatados, comparando previamenteas parametrizações realizadas manual e automaticamente.

O sexto capítulo concentra o desenvolvimento dos experimentos entre agentes. Ocapítulo relata o planejamento e a realização dos experimentos, do treinamento à avaliação decompetência, concluindo com uma demonstração de aplicação em DDA. No sétimo capítulo, éregistrado o experimento entre agentes avaliados e jogadores humanos. Esse capítulo mostra asetapas na concepção do experimento, quais os métodos utilizados para que os jogadores possamavaliar quantitativamente e qualitativamente nossa proposta, e a que resultados chegamos. Nooitavo capítulo, sintetizamos as conclusões que encontramos das experiências ocorridas ao longode todo o trabalho, identificando os pontos fortes e os pontos fracos da abordagem analisadaneste trabalho, e avaliando o impacto gerado pela parametrização do agente. Além disso, ocapítulo aponta oportunidades de investigação e possíveis aspectos a serem trabalhados commais cuidado.

191919

2Inteligência Artificial em Jogos Digitais

Esse capítulo inicia com uma breve descrição do processo de concepção e produção deum jogo digital. Em seguida, lista os problemas mais comuns no desenvolvimento de um jogopara os quais soluções são propostas envolvendo técnicas de IA. A partir daí, o capítulo focano problema de balanceamento de dificuldade, descrevendo-o melhor, apontando os conceitosenvolvidos e as abordagens existentes. E então, é discutido o subproblema de aprendizagem docomportamento de agentes, apontando os cuidados exigidos.

2.1 Desenvolvimento de Jogos Digitais

A Inteligência Artificial é apenas uma das partes que constituem um jogo, envolvendooutras áreas em seu desenvolvimento. É utilizada tanto em soluções de controle durante aexecução do jogo como também para auxiliar em sua etapa de preparação. Antes de discutirsobre os problemas relacionados à IA, é válido conhecer um pouco do processo de criação deum jogo.

A construção de um jogo exige a integração de diferentes áreas. Uma equipe geralmenteé composta por programadores, designers, artistas, músicos, roteiristas, produtores e testadores(game testers). Conforme o projeto pretendido, mais funções podem ser necessárias, e de acordocom o tamanho da equipe seus integrantes podem assumir múltiplas funções.

A primeira etapa na criação de um jogo digital é a de design, na qual o conceito dojogo é concebido. O elemento-chave nessa etapa é o game designer, responsável por construiro arcabouço conceitual para o jogo, na maioria das vezes, em colaboração com o restante daequipe.

É ele quem define as mecânicas do jogo, isto é, os conjuntos de regras que regem ajogabilidade, e consequentemente a maneira pela qual o jogador interage com tudo o que estácontido no jogo (SCHELL, 2008). A partir das mecânicas, ele pode elaborar os desafios a seremapresentados ao jogador, a arquitetar os tipos de conflitos que o jogador deve enfrentar durantesua experiência com o jogo.

O game designer também define o enredo para o jogo e o mundo virtual onde a história

2.2. INTELIGÊNCIA ARTIFICIAL EM JOGOS DIGITAIS 20

acontece, dividido em mapas ou fases. Além disso, ele concebe quais os cenários existentes pelomundo do jogo e quais elementos que o compõem, como itens, artefatos e fenômenos.

Os objetivos, diálogos e comportamentos de personagens são definidos também pelogame designer. Personagens que representam o jogador são conhecidos como avatar, enquantoque personagens controlados pelo computador são conhecidos como Non-Player Characters

(NPCs).Todos esses detalhes são registrados no documento de game design, que serve de referên-

cia para o trabalho dos demais na equipe. Nesse sentido, o game designer atua como um diretorna construção do jogo, articulando as ações dos diferentes profissionais durante o processo dedesenvolvimento a fim de gerar um produto jogável coeso.

A etapa seguinte é a de produção, ou de desenvolvimento, onde os integrantes vão sedividir para trabalhar nas diferentes atividades envolvidas na implementação do jogo, regidospelo documento de game design. São algumas delas: construção de mapas ou fases (level design),produção artística, modelagem e animação de cenários, personagens e artefatos visuais, produçãosonora, composição musical, dublagem, desenvolvimento do enredo, design de interface do jogoe da IA. Todas essas atividades interagem com uma atividade comum, a de programação, quecodifica todo o material junto com as mecânicas do jogo em um sistema integrado, além deconstruir ferramentas de apoio à produção.

Durante a fase de produção, são realizados testes para avaliar diferentes soluções propos-tas, alterações em técnicas ou simulações e integração das partes. Já ao final dessa fase, os testessão voltados para garantir a qualidade do jogo, os quais incluem o ajuste da dificuldade do jogo,a avaliação por mecânicas inconsistentes e a correção de eventuais erros.

2.2 Inteligência Artificial em Jogos Digitais

Para atender as metas de design e resolver problemas de desenvolvimento durante oprojeto de jogos digitais, as soluções criadas podem assumir uma perspectiva top-down ou bottom-

up. Na primeira, a solução é pensada como um sistema único geral que processa e controlatodos os elementos relevantes no problema considerado (MILLINGTON; FUNGE, 2009). Asegunda perspectiva considera a construção de mecanismos individuais, modelados como agentesinteligentes, a fim de obter como resultado a soma de suas interações (MILLINGTON; FUNGE,2009).

Os personagens controlados pelo computador, os NPCs, são geralmente modeladoscomo agentes. Esses agentes podem assumir um comportamento autônomo e costumam serimplementados através de scripting. Essa técnica permite ao programador codificar a lógica detomada de decisão dos agentes, que é traduzida em seu comportamento.

2.2. INTELIGÊNCIA ARTIFICIAL EM JOGOS DIGITAIS 21

2.2.1 Problemas Relacionados

Durante a etapa de desenvolvimento do jogo, a equipe enfrenta alguns problemas, rela-cionados aos desafios propostos e às tecnologias envolvidas, que podem ser solucionadas comajuda de IA. Existem tanto casos clássicos, com técnicas maduras e soluções suficientes parauma parcela de problemas, quanto outros mais recentes, que ampliam e aprofundam as suasaplicações. A seção seguinte descreve brevemente algumas categorias de problemas relacionados.Uma categorização mais detalhada pode ser encontrada em YANNAKAKIS; TOGELIUS (2014).

2.2.1.1 Comportamento de Agentes

Este problema corresponde ao processo de tomada de decisão que ocorre com um agentea todo momento do jogo. A tomada de decisão considera se os agentes aprendem com aexperiência ou não. Em agentes que não aprendem, as soluções propostas podem ser orientadas aestados ou a objetivos. Quanto ao grau de autonomia da tomada de decisão, pode ocorrer tanto anível individual quanto a nível tático e estratégico, considerando nesses dois últimos a interaçãocom outros agentes.

Devido ao grau de controle oferecido e ao sucesso obtido, as técnicas mais utilizadas paraagentes que não aprendem envolvem scripting, máquinas de estado (muitas vezes hierárquicas) eárvores de decisão, e mais recentemente árvores de comportamento (behavior trees) e planejado-res (YILDIRIM; STENE, 2008; MILLINGTON; FUNGE, 2009). Já para agentes que aprendem,algumas aplicações encontradas utilizam aprendizagem por reforço (GRAEPEL; HERBRICH;GOLD, 2004; MCPARTLAND; GALLAGHER, 2011), algoritmos evolucionários (DEMASI;OLIVEIRA CRUZ, 2003; SMALL; CONGDON, 2009) e redes neurais (BAUCKHAGE; THU-RAU; SAGERER, 2003).

2.2.1.2 Ajuste Dinâmico de Dificuldade

Enquanto o ajuste de dificuldade mais comum em um jogo acontece manualmente duranteo seu desenvolvimento, este problema trata do ajuste de dificuldade quando ocorrer em tempo deexecução do jogo (in-game), o ajuste dinâmico de dificuldade, ou DDA. Em geral, a dificuldadeé influenciada por três fatores: cenários, parâmetros e comportamento dos personagens. Emrelação ao comportamento do agente, ele pode tanto atuar em seu melhor nível de desempenho,quanto assumir um comportamento subótimo, conforme uma função de atuação. No caso desteproblema, a função de atuação é escolhida de forma que o agente busque atuar no nível dojogador. Mais detalhes sobre DDA são encontrados na Seção 2.3.

As soluções que tratam deste problema envolvem abordagem econômica sobre controlede parâmetros (HUNICKE; CHAPMAN, 2004), scripting dinâmico, ou Dynamic Scripting (DS)(SPRONCK; SPRINKHUIZEN-KUYPER; POSTMA, 2004), funções de desafio para NPCintegradas a aprendizagem por reforço (ANDRADE et al., 2005) e algoritmos coevolucionários(DEMASI; OLIVEIRA CRUZ, 2003).

2.3. AJUSTE DE DIFICULDADE EM JOGOS 22

2.2.1.3 Modelagem de Experiência de Jogadores

Refere-se aos estudos multidisciplinares na construção de modelos computacionaisde experiência do jogador (YANNAKAKIS; TOGELIUS, 2014). Esses modelos podem seraproveitados para adaptar o jogo conforme os padrões de comportamento do jogador ou asatisfação estimada, oferecendo uma experiência personalizada.

Muitos dos trabalhos estão fundamentados em conceitos qualitativos como a teoriado flow (CSIKSZENTMIHALYI, 1990) e a teoria da diversão (KOSTER, 2004). Entre asabordagens existentes, existem as que se baseiam em autoavaliação do jogador, em dadosfísicos e emocionais observados, e dados comportamentais registrados na interação com o jogo(NACKE et al., 2009; YANNAKAKIS, 2012). Existem aplicações que adaptam o jogo a partirde modelos de experiência com o uso de aprendizagem por reforço (ANDRADE et al., 2005),redes neurais (PEDERSEN; TOGELIUS; YANNAKAKIS, 2009), algoritmos evolucionários(VERMA; MCOWAN, 2005), scripting dinâmico (SPRONCK; SPRINKHUIZEN-KUYPER;POSTMA, 2004), entre outros (YANNAKAKIS, 2008).

2.2.1.4 Outros Problemas

Ainda que não diretamente relacionados a este trabalho, podemos citar problemas comunsà aplicação de IA tais como: movimentação de personagens (HART; NILSSON; RAPHAEL,1968; REYNOLDS, 1999), interface do agente com o ambiente do jogo (TOZOUR, 2001;MILLINGTON; FUNGE, 2009), credibilidade de NPC (LOYALL, 1997; TOGELIUS et al.,2012), geração automática de conteúdo (HASTINGS; GUHA; STANLEY, 2009; RIEDL; THUE;BULITKO, 2011), simulação física e animação (MILLINGTON; FUNGE, 2009), narrativacomputacional (MATEAS; STERN, 2003) e IA como foco do game design (YANNAKAKIS;TOGELIUS, 2014). Na prática, os problemas são inter-relacionados, exigindo soluções queintegrem métodos diferentes, cada qual mais apropriada a uma particularidade a ser resolvida.Este trabalho, por exemplo, considera o problema do ajuste dinâmico de dificuldade realizadoatravés da adaptação no comportamento de um NPC.

2.3 Ajuste de Dificuldade em Jogos

O ajuste (ou balanceamento) de dificuldade em um jogo pode ser definido como aadaptação automática do desafio apresentado ao jogador humano. O objetivo do ajuste é ode obter uma "partida acirrada", na qual a habilidade do computador no jogo se compara àhabilidade do jogador (SPRONCK et al., 2006).

O mecanismo que realiza o ajuste de dificuldade deve ser equilibrado o suficientepara não entediar o jogador com situações simples, repetitivas, constantemente previsíveis oupouco frequentes. Da mesma forma, o ajuste não deve apresentar desafios tão frequentes quedesestimulem o jogador, ou tão complexos que ele não possa resolvê-los.


O ajuste deve ser realizado de forma a estimular o jogador a desenvolver a habilidadeexigida para a solução dentro de suas capacidades, como também a fim de evitar que ele exploredeficiências da IA para trapacear o jogo. Por exemplo, um jogo de luta não deveria permitir aexecução de um golpe especial com resultado tão desproporcional a ponto do jogador baseartoda a sua estratégia de combate apenas em aplicá-lo.

Durante o período de desenvolvimento do jogo, o game designer é o responsável porplanejar os desafios a serem enfrentados pelo jogador. O balanceamento desses desafios se dáatravés da definição inicial de parâmetros (e.g. atributos de itens e personagens), composiçãodas fases, e do comportamento de NPCs.

O nível de dificuldade dos desafios em um jogo é definido com base nos perfis estimadosde jogadores e refinado exaustivamente com rodadas de testes. Dessa forma, o processo debalanceamento tende a ser complicado e propenso a erros. Em especial, o momento mais críticodo processo de ajuste da dificuldade é a parte inicial do jogo, quando o jogador apresenta a maiorvariação em suas habilidades. Adicionalmente, esse é o momento em que o jogador tem seuprimeiro contato com o jogo, de forma que a qualidade do balanceamento realizado pode mantero interesse do jogador ou não.

O ajuste de dificuldade pode ser realizado por uma abordagem manual ou dinâmica. Asseções a seguir explicam cada uma delas em mais detalhes.

2.3.1 Ajuste Manual de Dificuldade

Na abordagem manual, a dificuldade do jogo é definida em níveis pré-definidos (i.e. fácil,médio, difícil), durante o período de desenvolvimento, para que o jogador escolha aquele queacredita ser o mais apropriado para si, sendo a mais utilizada. Para cada nível, as técnicas destaabordagem definem os parâmetros relacionados aos desafios, como a força de um golpe em umjogo de luta ou o quanto de magia um golpe especial utiliza.

Nesta abordagem, o game designer tem controle sobre todo o processo de balanceamento,da construção dos elementos do jogo (e.g. cenários, personagens) ao ajuste dos parâmetros eà forma como os desafios são apresentados. Geralmente os desafios são agrupados por fasesou estágios de dificuldade crescente, de forma a estabelecer etapas na evolução de habilidadedo jogador. Isso impõe que os jogadores têm acesso a novas fases à medida que aumentam dehabilidade pelo nivelamento imposto pelas fases anteriores (ANDRADE et al., 2005). As fasesatuam então como barreiras de nivelamento, que servem para garantir que todos os jogadoresque passarem por ela tenham um nível mínimo de habilidade e se sintam motivados a evoluir suahabilidade. Assim o game designer sabe quando é adequado apresentar algum tipo de desafiodado as barreiras que o jogador conseguiu superar.

Como cada fase normalmente se baseia em um nível fixo de habilidade, torna-se inviávelao game designer mapear todas os níveis de habilidade dos jogadores. Assim, o jogo nãoconsidera as diferentes habilidades específicas e formas de aprender dos jogadores (ANDRADE


et al., 2005). Há ainda para cada nível de habilidade a dificuldade por parte da equipe dedesenvolvimento em realizar repetidos testes a fim de se ajustar adequadamente cada parâmetrodo jogo. Devido a essa complexidade, é mais provável que a IA não consiga lidar com táticasnão previstas e que seja explorada pelos jogadores para derrotar oponentes fortes (PONSEN;SPRONCK, 2004).

Agravam o problema o fato dos jogos apresentarem nesta abordagem um número li-mitado de opções de níveis de dificuldade (três ou quatro, em geral) e que os jogadores nãoconseguem definir o nível de dificuldade mais apropriado para suas habilidades. Além disso, aconfiguração da dificuldade de forma geral afeta apenas os atributos dos personagens controladospor computador, mas não sua tática - de modo que em um modo difícil de jogo, apesar deterem mais “força”, por exemplo, os oponentes exibem comportamento similar ao modo fácil(SPRONCK et al., 2006). Esses aspectos podem ser resolvidos com a abordagem dinâmica,explicada a seguir.

2.3.2 Ajuste Dinâmico de Dificuldade

A abordagem de ajuste dinâmico de dificuldade consiste em utilizar mecanismos queautomaticamente identifiquem as características específicas e o comportamento do jogador, ecom base em sua experiência adapte os desafios ao seu nível de habilidade. Esses mecanismossão responsáveis por tornar a partida equilibrada em dificuldade, justa para todos os jogadores,e flexível em relação às novas e diferentes táticas que os jogadores podem adotar e às formasque podem aprender. Assim, o ajuste da dificuldade deve tanto acompanhar a evolução quantoa regressão do jogador, que pode ocorrer, por exemplo, após um longo período de tempo seminteração entre ele e o jogo.

Além disso, os mecanismos de balanceamento não devem apenas oferecer uma experiên-cia mediana de dificuldade, mas também adicionar alguma imprevisibilidade, alternando entredesafios difíceis (os momentos de tensão) e os desafios fáceis (os momentos de relaxamento)(ANDRADE et al., 2005). Isso tem por objetivo estimular o jogador a evoluir e manter o contínuointeresse pelo jogo.

A adaptabilidade dos mecanismos de balanceamento é possível através da avaliação donível de dificuldade percebido pelo jogador. Diferente da abordagem manual, esses mecanismosnão identificam o nível de dificuldade de forma discreta através das fases e da seleção dedificuldade, mas a partir de uma função que traduza um estado do jogo em um valor indicativodo nível de dificuldade percebido pelo jogador. Essa função, conhecida como função desafio oufunção de facilidade, opera sobre um conjunto discreto (e.g. fácil, médio, difícil) ou contínuode valores, o qual for mais relevante ao problema. Fica a cargo do game designer o trabalho dedefinir a função desafio mais adequada para o jogo.

É necessário que a função desafio seja confiável e rápida o suficiente de modo a nãogastar muitos recursos computacionais (DEMASI; OLIVEIRA CRUZ, 2003). Como essa função


é utilizada com bastante frequência e idealmente ela seria instantânea, a eficiência é maisimportante que a precisão.

A função desafio geralmente se baseia em funções heurísticas simples, relativas aodomínio do jogo, que podem considerar por exemplo pontuação geral, número de desafiosvencidos pelo jogador ou pontos de vida ao fim de uma fase. No nosso estudo de caso, a funçãodesafio utilizada se baseou na diferença de pontos de vida dos oponentes. A dificuldade é ajustadade acordo com intervalos considerados pelo game designer.

Para o ajuste dinâmico ser efetivo, no caso em que a dificuldade está associada ao com-portamento de personagens, é necessário que esses tenham uma IA competente o suficiente paraacompanhar a habilidade do jogador, qualquer que seja seu nível. A competência pode ser obtidaa partir de conhecimento específico do domínio fornecido pelo game designer ou aprendendo daexperiência com o usuário. A próxima seção trata do subproblema da aprendizagem necessária àadaptação da dificuldade.

2.3.2.1 Aprendizagem no Comportamento de Personagens

A inteligência de um agente em muitos casos é resultado de regras específicas deter-minadas em tempo de desenvolvimento do jogo que fazem uso de trapaça (cheating), isto é,não possuem as mesmas limitações impostas ao jogador. A trapaça pode ser feita de váriasformas, entre elas: a IA tem acesso a todas as informações do mapa desde o início de umapartida; inicia em condições melhores de recurso ou atributos de personagens; ou ainda temacesso à entrada de comandos do jogador antes mesmo de ser processada no fluxo normal dojogo. Esse último caso por exemplo pode acontecer em um jogo de luta, onde o agente oponentepercebe se o jogador inicia as instruções de golpe especial antes de ser executadas, permitindointervir antecipadamente com a melhor ação. Quando bem executada, a trapaça cria a ilusão decompetência do personagem para o jogador.

Entretanto, por vezes as limitações de uma solução como essa tornam-se evidentes aojogador. Podem ocorrer previsibilidade em sequências de ações que se mostram repetitivas,falta de generalização quando o personagem não consegue acompanhar o jogador em umasituação não prevista durante o desenvolvimento do jogo ou mesmo percepção da trapaça pelojogador. Nesses casos, o jogador pode ter sua suspensão de descrença diminuída, ocasionando suafrustração. A capacidade do ajuste de dificuldade acaba sendo limitada às regras determinadaspelo game designer, geralmente não acompanhando jogadores mais experientes. Além disso, ocomportamento previsível de um agente torna o desafio menor do ponto de vista do jogador terde descobrir táticas de enfrentá-lo. Em um jogo de luta, por exemplo, isso reduz a experiênciade jogo ao aperfeiçoamento no controle do avatar, de modo que tão logo o jogador aprenda aexplorar as falhas do agente oponente, o jogo em si não representa mais desafio a ele, podendo ojogador perder o interesse pelo jogo.

Nesse contexto, as soluções com aprendizagem são vistas como fortes alternativas parao problema. Elas são capazes, por exemplo, de descobrir comportamentos mais eficazes para


NPCs, desafios mais adequados à competência do jogador e aventuras mais interessantes ao perfildele. Isso possibilita não só experiências personalizadas no jogo, mas também menos esforçopara a equipe de desenvolvimento em problemas de difícil solução manual. Como exemplo, autilização de redes neurais no jogo de corrida Colin McRae Rally 2.0 (Codemasters, 2000) nãosó construiu agentes capazes de dirigir veículos com resultados de tempo satisfatórios, comotambém fez com que os desenvolvedores não precisassem implementar um conjunto complexode regras para o controle dos veículos (GENERATION5, 2001).

O processo de aprendizagem está associado a um mecanismo de adaptação. Essemecanismo por si só permite apenas a alteração de comportamento do agente dentro do escopode possibilidades definido ainda na criação do jogo. A integração com a aprendizagem estendea capacidade de adaptação, como também a de ajuste da dificuldade, ao incorporar novasinformações ao processo, conferindo robustez no sentido que permite lidar com situações nãoprevistas pelos desenvolvedores.

Quando a aprendizagem aproveita o processo de adaptação para testar hipóteses formu-ladas sobre parâmetros ou comportamentos, isto é, quando a adaptação interfere no processode aprendizagem, ela opera em modo online. Esse modo acontece enquanto o jogador estáinteragindo com o jogo, possibilitando uma resposta mais dinâmica e conferindo maior potencialpara adaptação. Tal característica permite, por exemplo, a implementação de agentes que imitamo jogador, aprendendo seu comportamento sem qualquer conhecimento prévio. Entretanto, aaprendizagem online exige maior cuidado para manter comportamento crível, ser executada efi-cientemente com os demais componentes do jogo em tempo real, prender o interesse do jogadorao adaptar-se rapidamente e lidar adequadamente com o ruído do ambiente (MANSLOW, 2002).

A aprendizagem opera em modo offline quando ocorre separada do processo de adaptação.Seu processo lida primeiro com a extração de dados disponíveis sobre os jogadores ou sobre omundo, a fim de gerar informação útil a ser utilizado depois no ajuste de comportamento oude parâmetros no jogo. Essa abordagem tem sido usada para aprender características táticasem mapas multijogadores, para produzir rotas e dados para movimentação mais precisos, porexemplo (MILLINGTON; FUNGE, 2009).

Uma vantagem da aprendizagem offline sobre a online é a menor imprevisibilidade daadaptação, consequência da separação entre o seu processo e o de aprendizagem. Isso facilita otrabalho de busca e reprodução de erros (debugging), tornando-a mais atraente aos desenvolve-dores. Se utilizada fora do período de execução do jogo, a restrição de operar em tempo real érelaxada, podendo então explorar melhor as hipóteses criadas durante a aprendizagem. Aindaassim, deve-se ter o cuidado em escolher uma técnica que seja estável e possa convergir, a fimde não prejudicar o desempenho da adaptação. Caso ocorra aprendizagem offline durante osperíodos do jogo sem interação com o jogador, e.g. telas de carregamento e de resumo de parti-das, deve-se levar em consideração a disponibilidade de recursos computacionais e a ausênciade intervenção por parte da equipe de desenvolvimento ou do game designer, característicasencontradas na abordagem online.

2.4. CONCLUSÃO 27

Há o risco em qualquer das abordagens quanto ao direcionamento da aprendizagem.O agente pode não explorar o suficiente o espaço de decisões e aprender apenas sequênciasruins de ações. Ou ainda, o agente pode se especializar contra um jogador, mas não adaptar-sesatisfatoriamente bem contra outros jogadores. Esses casos podem ser minimizados tomandocuidado em definir tempo de execução e, quando possível, variabilidade de exemplos suficientesao processo de aprendizagem.

É preciso definir uma métrica de desempenho apropriada para guiar a aprendizagemdo agente. Sua medida deve representar a qualidade de uma ação decidida pelo agente noambiente. Uma escolha pouco cuidadosa pode resultar no problema anterior de direcionamentoda aprendizagem. Além disso, essa escolha pode atribuir uma mesma avaliação a variaçõessignificativas nos parâmetros considerados relevantes pelo processo de aprendizagem, preju-dicando na diferenciação de decisões boas e ruins (MANSLOW, 2002). Além da atenção naescolha da métrica, sua função de avaliação deve atender às restrições da abordagem escolhida:a aprendizagem online exige uma função, rápida o suficiente, que avalie decisões dentro dolimitado intervalo de tempo destinado ao processamento do agente, assim como exige a funçãodesafio para o ajuste dinâmico de dificuldade.

Outro ponto a ser considerado é a incorporação de conhecimento prévio na inicializaçãoda aprendizagem do agente. O início da adaptação sem conhecimento é instável, uma vez que oagente tem muitas hipóteses a ser testadas sobre o comportamento do jogador, podendo levartempo até o agente adquirir competência suficiente para representar algum desafio ao jogador.Além disso, o desempenho do agente evolui e estabiliza de forma lenta, o que não interessa emsituações nas quais o NPC do agente tenha pouco tempo de vida ou de interação, tais comodurante uma partida de jogo de luta ou unidade de esquadrão em jogos militares. A inserçãode conhecimento prévio agiliza a aprendizagem do agente, reduzindo o escopo das descobertasnecessárias à adaptação.

Como forma de tratar essas peculiaridades, os jogos lançados pela indústria que incluemaprendizagem possuem soluções híbridas, onde o problema geral do jogo é dividido em problemasmenores, simples e bem definidos, e diferentes técnicas são aplicadas para tratar os casos emque são mais apropriadas, tendo como resultado a integração de todas as soluções menores. Aredução no número de aspectos tratados por técnica tem por finalidade facilitar o controle nostestes durante o desenvolvimento e aumentar a previsibilidade do comportamento ao longo dojogo.

2.4 Conclusão

Esse capítulo apresentou alguns problemas tratados durante o desenvolvimento de umjogo. Mostrou quais os tipos de problemas que os desenvolvedores enfrentam cuja solução podeser auxiliada com o uso de IA. Em seguida, o capítulo foca no problema de ajuste dinâmico dedificuldade, explicando conceitos, vantagens e deficiências das duas abordagens existentes. O

2.4. CONCLUSÃO 28

capítulo abordou também os principais conceitos e detalhes relacionados à aprendizagem deagentes, necessária à adaptação dinâmica de dificuldade em comportamento de agentes.

No próximo capítulo são explorados trabalhos relacionados, contendo uma breve descri-ção do funcionamento de suas soluções.

292929

3Trabalhos Relacionados

Este capítulo apresenta as principais soluções encontradas na literatura para o problemade ajuste dinâmico de dificuldade no comportamento de agentes. Cada solução tem seu funci-onamento geral explicado, bem como discutidos o método de adaptação e o de aprendizagemenvolvida. Depois, são apresentados os experimentos que compararam essas três abordagens.Ao final, é apresentado o caso de uso no qual são executadas as simulações e realizados osexperimentos.

3.1 Balanceamento com Dynamic Scripting

A técnica de Dynamic Scripting (DS) (SPRONCK; SPRINKHUIZEN-KUYPER; POSTMA,2003) é um aprimoramento do uso de scripts, bastante comum na indústria para definir o com-portamento de agentes. Scripts são conjuntos de regras de comportamento sobre um domíniodefinidas por pares condição-ação. A condição corresponde à representação de um possívelestado no ambiente percebido por um agente inteligente e a ação corresponde à interferência doagente no estado atual, gerando algum sinal de reforço ou recompensa.

Nesse contexto, a solução por DS seleciona regras para serem executadas através doscript do agente, com base em um mecanismo de aprendizagem que associa a cada regra umpeso, o qual determina a qualidade da regra dada a sua condição e a probabilidade da regra serescolhida para ter sua ação executada. É necessário então que para cada situação haja alternativade escolha.

A aprendizagem se dá através da resposta que o ambiente devolve ao agente após aaplicação da ação de uma regra, a qual tem seu peso aumentado para uma resposta positiva ediminuído para uma resposta negativa. Os pesos são atualizados por treinamento offline (PON-SEN; SPRONCK, 2004) ou durante a execução do jogo. Com o passar do tempo, as regras maiseficientes tendem a possuir maiores pesos, corrigindo possíveis ruídos introduzidos inicialmenteno peso das regras, e revelando as regras mais adequadas para cada jogador enfrentado.

Entre as estratégias existentes na literatura para adaptar a técnica de DS ao contexto deDDA, a mais utilizada é a eliminação de regras fortes (top culling).

3.2. BALANCEAMENTO BASEADO EM ALGORITMOS GENÉTICOS 30

A estratégia de eliminação de regras define um valor máximo de peso na seleção deregras. O balanceamento provém do ajuste do limite de acordo com o nível do jogador: o limiteaumenta quando o nível do jogador está alto e o limite diminui caso contrário. O reajuste depesos ocorre tanto nas regras que atingem o limite quanto as demais, aproveitando todas asoportunidades de aprendizagem. Essa estratégia se mostrou a mais eficiente dentre as existentes(SPRONCK et al., 2006).

Entre os fatores atrativos para a utilização dessa abordagem estão a similaridade como uso clássico de script e a simplicidade nos processos de aprendizagem e adaptação. Devidoà popularidade do uso de scripting na indústria de jogos, a técnica possui a vantagem de serfacilmente entendida e aplicada pelos desenvolvedores.

Outro destaque da técnica é a inserção de conhecimento explícito por parte do game

designer, que pode aproveitar seu conhecimento do domínio na inicialização das regras edos pesos. Esse aspecto não apenas garante a qualidade esperada do conhecimento que oagente possui para atuar no jogo, como também possibilita maior controle sobre os possíveiscomportamentos tomados pelo agente.

A vantagem da técnica em relação à aprendizagem que realiza é a maior previsibilidadeda adaptação para os desenvolvedores. Isso se deve ao fato da base de regras ser conhecida desdeo início, o que diminui as chances de situações indesejadas ocorrerem inesperadamente.

Por outro lado, a base de regras é criada manualmente, tendendo a aumentar a complexi-dade conforme o comportamento esperado do agente e as interações nas quais está envolvido.Essa complexidade pode resultar na vulnerabilidade da IA, o que permite aos jogadores tomarvantagem ao explorar possíveis falhas no comportamento do agente, prejudicando a experiênciacom o jogo.

Além disso, a natureza estática das regras não prepara o comportamento dos agentescontra táticas do jogador que não foram previstas durante a etapa de desenvolvimento (PONSEN;SPRONCK, 2004). Esse aspecto torna-se mais evidente quão maior a complexidade do jogo.

3.2 Balanceamento baseado em Algoritmos Genéticos

A abordagem apresentada por DEMASI; OLIVEIRA CRUZ (2003), ao contrário daanterior, não se baseia em regras, mas em algoritmos genéticos coevolucionários de temporeal (WIEGAND; LILES; DE JONG, 2002) que codificam características de comportamentocomo genes dos agentes aprendizes. Eles são avaliados por uma função heurística dependentedo domínio do problema chamada de função facilidade, cujo valor de aptidão indica o quãoadaptado está cada agente ao nível do jogador. Essa função é capaz de realizar essa avaliaçãoassim que ela conhece o desempenho de toda a população, sendo a partir dela que se determinase os agentes devem evoluir ou não.

Uma característica desta abordagem é o fato da evolução ser enviesada por um grupode agentes objetivos, que possuem comportamentos alvos, considerados os melhores para

3.2. BALANCEAMENTO BASEADO EM ALGORITMOS GENÉTICOS 31

determinadas situações. Novos agentes são criados conforme uma das quatro variantes descritasadiante, sendo em geral, a partir dos operadores genéticos (EIBEN; SMITH, 2003) de cruzamentoentre os agentes considerados mais aptos (com troca de características codificadas como genes),seguido de mutação (mudança aleatória de genes) em cada indivíduo da prole resultante. Osmais adaptados ao nível do jogador tendem a ser preservados e utilizados como pais na criaçãode indivíduos para uma nova geração. Ao longo das gerações, os indivíduos objetivos se revezamcomo reprodutores, conforme demandar a experiência de dificuldade estimada para o jogador.

Quando os agentes são destruídos no contexto do jogo ou ficam estagnados por umperíodo pré-definido de tempo, a função de facilidade decide se a então geração de agentes evoluiou é mantida. Existem duas formas de evoluir: uma se dá através da comparação da quantidadede genes diferentes entre dois agentes e da modificação gradativa dos genes a fim de diminuirsua diferença genética; outra é a evolução através do cruzamento entre os agentes mais aptos eos modelos. Para o problema de DDA, os autores apresentam quatro variantes de produção dosmodelos.

A primeira variante consiste na definição manual dos agentes modelos, quando deve exis-tir um modelo para cada nível de dificuldade desejado. A evolução se dá através do cruzamentoentre os agentes mais aptos e os modelos.

A segunda variante difere em relação à criação dos modelos, os quais passam a ser geradosatravés de treinamento offline. O objetivo é fazer com que tenham um bom comportamento inicialsem uso de conhecimento explícito do domínio. O treinamento pode ser realizado testandoagentes aprendizes contra agentes de comportamento aleatório, humanos ou outros agentesaprendizes (self-learning).

A terceira variante não utiliza modelos para guiar o processo evolutivo. A evoluçãoacontece apenas com os dados presentes durante a execução (online) e as operações tradicionaisde recombinação e mutação. Nessa variante, os agentes mais aptos de uma população sãoreunidos em um conjunto. Novos agentes são criados a partir da recombinação entre agentesdesse conjunto. Esse conjunto é modificado toda vez que um agente for mais apto que o pior doconjunto, de modo que a priorizar os mais adaptados.

A quarta variante corresponde à utilização híbrida das variantes anteriores, obtendo-semodelos manualmente ou por treinamento offline numa primeira etapa (respectivamente primeirae segunda variantes) para então passar a operar em modo online conforme a terceira variante.Assim, é possível acelerar a adaptação dos agentes a partir de conhecimento explícito do domínio,mas permitindo a livre evolução dos agentes, sem a referência de objetivos fixos.

Nesta abordagem, a aprendizagem ocorre simultaneamente à adaptação na medida emque o algoritmo busca novos agentes mais aptos a partir dos agentes mais aptos existentes. Acapacidade de gerar novos agentes em modo online permite ao algoritmo adaptar-se a situaçõesimprevistas. Isso resulta na busca por estratégias novas, adaptadas ao jogador, sem a necessidadede inserção explícita de conhecimento, o que diminui o esforço envolvido para a aplicação comosolução.

3.3. BALANCEAMENTO BASEADO EM APRENDIZAGEM POR REFORÇO 32

Por outro lado, mesmo com a definição de agentes objetivos finais e intermediários(utilizados para adaptar o nível de dificuldade entre agentes finais), não é possível controlartotalmente o processo evolutivo. Esta abordagem pode explorar agentes cujos comportamentossão indesejados ou que atuem fora do nível de atuação esperado em dado momento. Além disso,não há garantia de se encontrar uma boa solução, característica comum aos algoritmos genéticos(EIBEN; SMITH, 2003).

3.3 Balanceamento baseado em Aprendizagem por Reforço

A abordagem realizada por ANDRADE et al. (2005) é caracterizada por um problemade aprendizagem por reforço, no qual o agente atua sobre o ambiente com base em sinais dereforço retornados após a execução de suas ações. Essa classe de problemas consiste em umagente aprender a política de ação que maximize a satisfação de seus objetivos, isto é, em que oagente procura aprender o conjunto de ações para os estados do problema as quais retornam osmaiores sinais de reforço (SUTTON; BARTO, 1998). Uma das principais características dessaabordagem é que não há supervisão para o treinamento do agente, de forma que ele aprende portentativa e erro quais as melhores ações sem conhecimento prévio das regras que relacionam asações aos estados.

Existem muitas técnicas para solucionar o problema de aprendizagem por reforço. O tra-balho do autor utilizou a técnica Q-Learning (WATKINS; DAYAN, 1992) devido principalmentea quatro propriedades interessantes para o contexto do problema. A primeira é a capacidadede aprender a política de ação ótima para um dado objetivo sem a necessidade de construir ummodelo do ambiente. A segunda característica é o fato da técnica ser off-policy, isto é, ela nãoprecisa seguir a melhor política de ação para que possa aprendê-la, deixando livre a escolha dapolítica de ação a ser seguida - no caso, determinada pelo mecanismo de adaptação da dificuldade.A terceira é a existência da garantia de convergência para a melhor solução desde que todas ascombinações de estado-ação sejam visitadas o suficiente. A última característica é a relativasimplicidade comparada a outras técnicas de aprendizagem por reforço. Como estudo de casofoi utilizado o Knock’em (NETO et al., 2003) para jogos de luta, o mesmo servido de estudo decaso para este trabalho.

Para o contexto de balanceamento dinâmico, o autor desenvolveu uma abordagem debalanceamento baseado em desafio, inspirada nos conceitos de competência e desempenho

(CHOMSKY, 1965). A competência é definida como o conhecimento que o agente possui sobreos estados e as ações. O desempenho está relacionado ao nível de uso da competência, ouseja, qual o nível de atuação do agente efetivamente. Dessa forma, o autor pretende separar oconhecimento de um agente e a execução da decisão tomada. A diferença é sutil, mas significativa:o conhecimento evolui, mas não regride, como pode acontecer com o desempenho, de forma queo agente não perde conhecimento ao reduzir seu nível de dificuldade.

A competência é adquirida à medida que o agente descobre a melhor política de ação

3.3. BALANCEAMENTO BASEADO EM APRENDIZAGEM POR REFORÇO 33

através da técnica de aprendizagem por reforço. A técnica Q-Learning utiliza uma matrizbidimensional para armazenar valores de utilidade a cada par estado-ação, valores os quaisestimam o sinal de reforço médio futuro de se tomar uma ação a partir de um estado. Nessecaso a competência é sempre adquirida, pois os valores da matriz são atualizados tanto portreinamento offline como durante a execução do jogo.

O desempenho ocorre através da avaliação do nível do jogador baseada na função desafioe executa a ação mais próxima do nível de habilidade estimado do jogador. Assim, para umjogador iniciante o sistema vai selecionando ações subótimas até compatibilizar o nível do agentecom o do jogador, enquanto que para um jogador avançado o sistema seleciona gradativamenteseleções melhores, possivelmente escolhendo a solução ótima ANDRADE et al. (2005).

A separação do problema em competência e desempenho põe o foco da aprendizagemna busca pelo maior nível de dificuldade, i.e. pelo melhor desempenho para o problema, e o daadaptação na estimativa mais precisa do nível de dificuldade percebido pelo jogador. Além disso,essa melhor definição dos mecanismos de aprendizagem e adaptação permite ao game designer

variar as técnicas utilizadas sob a mesma arquitetura, a fim de testar aquelas que melhor atendamseus interesses, e.g. representação da base de conhecimento, inicialização flexível.

Entretanto, é preciso cuidado ao definir a política de ação e os parâmetros utilizados afim de evitar alterações bruscas no comportamento do agente. Outro detalhe é a representaçãotabular utilizada pelo Q-Learning para registrar as estimativas de utilidade sobre o espaço depares estado-ação, cujo tamanho pode inviabilizar a utilização dessa técnica de aprendizagem.

3.3.1 Abordagem de Balanceamento baseada em Desafio

Essa abordagem consiste de uma função heurística de desafio, que infere o nível dedificuldade percebido pelo oponente em um dado estado. A partir do nível de desafio indicadopela função, a política de seleção de ação é ajustada, adaptando o comportamento do agente.

A função desafio observa a diferença de pontos de vida entre os lutadores, como descritona equação abaixo:

nível de desafio =

fácil, se ∆PV < 0

médio, se ∆PV < 10

difícil, senão

� �3.1

onde ∆PV corresponde à diferença de pontos de vida entre o agente e o oponente, nessa ordem.O agente atualiza o nível de desafio periodicamente, a cada 100 ciclos de execução do agente.

Iniciando no nível de dificuldade mais difícil contra o oponente (o nível 1), a atualizaçãodo nível de desafio ativa o ajuste do nível de dificuldade seguido pelo agente, de modo que seo nível de desafio está difícil, o agente diminui o nível em um ponto; se o desafio está fácil, oagente aumenta o nível em um ponto; e se o desafio está médio, ele mantém o nível como está.O nível de dificuldade seguido pelo agente corresponde à ordem das ações definida segundoa política de ação. Para a política determinística (a melhor ação a ser executada), o nível de

3.4. EXPERIMENTOS COM DDA 34

dificuldade 1 implica na seleção da 1ª ação, o nível 2 implica na seleção da 2ª ação, e assimsucessivamente.

3.4 Experimentos com DDA

Essa seção descreve os experimentos relatados por ANDRADE et al. (2005), nos quaisas três abordagens acima foram comparadas. Cada uma das abordagens foi implementada comoum agente adaptativo no jogo de luta Knock’em, explicado na Seção 3.5. Todas utilizam a funçãodesafio da Seção 3.3.1 para realizar o balanceamento.

O agente baseado em AR realizou treinamento offline contra oponente de comportamentoaleatório durante 50 partidas. O agente baseado em Algoritmo Genético (AG) utilizou 5 modelosde evolução, com diferentes níveis de aptidão, construídos a partir de treinamento offline comoponente de comportamento aleatório. O agente baseado em DS não foi treinado, tendo suasregras e pesos definidos manualmente.

Os agentes foram colocados para lutar contra 3 oponentes cada, que simulam estratégiasdiferentes: um agente de comportamento previsível, um agente de comportamento imprevisível,e um agente que aprende por reforço previamente treinado. Cada agente foi avaliado através de30 lutas contra cada oponente, durante as quais permanecia aprendendo.

A análise de desempenho foi realizada pela diferença de pontos de vida ao final de cadaluta. O objetivo dos agentes foi de aproximar seu desempenho médio a zero.

Os resultados desse primeiro experimento indicaram que o agente baseado em AR conse-guiu atuar, na média, no mesmo nível de seus oponentes, independentemente da competência.Em relação aos outros dois agentes, eles variaram muito bruscamente de acordo com o oponenteenfrentado, e não conseguiram atuar sempre no mesmo nível do oponente. O agente baseado emAR mostrou-se o melhor agente nesse experimento.

O experimento seguinte consistiu na avaliação do balanceamento de agentes contrahumanos. Os mesmos agentes acima foram utilizados, com algumas modificações de parâmetrospara aproveitar as melhorias aprendidas durante o experimento anterior.

Este experimento foi dividido em duas fases. Na primeira fase, com duração mínimade 3 lutas com o treinador, os humanos foram postos para enfrentar dois tipos de agentes: umtreinador e um avaliador. O treinador foi representado por um dos três agentes acima, escolhidoaleatoriamente pelo sistema. O avaliador foi um agente de referência, o agente baseado em ARsem o balanceamento, treinado com agente de comportamento aleatório. O jogador avançava defase quando conseguia derrotar o treinador três vezes e o avaliador, em vitórias consecutivas. Emcaso de alguma derrota, o processo da primeira fase recomeçava. O intuito desta fase foi o de ojogador aprender habilidade básica para a próxima fase.

A segunda fase, o jogador devia lutar 5 lutas contra cada um dos 3 lutadores acima, e maisoutros 2, o agente de comportamento previsível e o agente baseado em AR sem balanceamento.Durante o experimento, os jogadores foram acompanhados por um especialista, e ao fim do

3.5. CASO DE ESTUDO 35

jogo, realizaram um questionário para avaliar o jogo e os 5 agentes, de maneira que não osidentificasse.

Doze jogadores, divididos em iniciantes e avançados participaram do segundo experi-mento. O grupo de jogadores iniciantes perdeu para o treinador da primeira fase por poucospontos, mas logo avançaram. O grupo de jogadores avançados avançaram para a fase seguintesem derrotas. Os resultados da segunda fase mostraram que nenhum agente foi capaz de derrotar,na média, um dos doze jogadores. O agente que ofereceu maior dificuldade foi o agente baseadoem AR sem balanceamento. Além disso, o experimento revelou que o agente baseado em ARatuou quase que otimamente na maioria do tempo e que o treinamento offline realizado não foi osuficiente para enfrentar jogadores humanos.

A partir dos resultados desses experimentos, foi possível identificar a oportunidade depesquisa por um agente que tivesse um nível de desempenho melhor no contexto de DDA.A seção seguinte apresenta o estudo de caso utilizado pelos experimentos desta seção, comotambém, deste trabalho.

3.5 Caso de Estudo

O ambiente utilizado para a execução dos experimentos da seção anterior é o jogoKnock’em (NETO et al., 2003). Ele será utilizado na implementação da solução proposta e naexecução dos experimentos deste trabalho. Os principais motivos para a adoção desse ambientepara nosso estudo são: a disponibilidade do código, o ambiente suficientemente satisfatório parao desenvolvimento da abordagem proposta e validado pelo trabalho de ANDRADE et al. (2005),além deste servir como referência para o mesmo problema.

Os lutadores de uma partida possuem atributos como força, agilidade, resistência, poderespiritual, pontos de vida e pontos de magia, que influenciam no poder de suas habilidades. Elessão postos para se enfrentar dentro de um limite de tempo, cada qual com uma quantidade depontos de vida e de magia. A partida acaba quando um deles perde todos os pontos de vida ouquando o tempo disponível se esgota. O vencedor é o lutador que termina a partida com maispontos de vida, podendo haver empate. A Figura 3.1 ilustra uma partida do jogo, apresentandona região superior os pontos de vida e de magia bem como o tempo restante.

Como visto na Figura 3.1, o jogo possui uma perspectiva bidimensional lateral, permi-tindo ao jogador se movimentar livremente na horizontal e através de pulos na vertical, dentrodos limites do cenário. Cada lutador pode executar ações de movimentação, golpes, agachamentoe bloqueio. A movimentação pode ocorrer através de andar para frente (em direção ao oponente),andar para trás (fugindo do oponente) ou pulo, que por sua vez pode ou não ocorrer para frente epara trás também. Os golpes básicos possíveis são socos e chutes, ambos com variações fortes ourápidas. Além desses, há o golpe especial, no qual o agente dispara uma bola de fogo consumindoparte de seus pontos de magia. Os pontos de magia recarregam com o tempo, bastando o lutadoresperar em caso de pontos insuficientes para o uso do golpe especial.

3.5. CASO DE ESTUDO 36

Figura 3.1: Captura de uma partida do jogo Knock’em

A cada quadro apresentado na tela, ocorre um ciclo de processamento do jogo, no qual échecada a condição dos lutadores. A tomada de decisão é concedida ao fim da execução da açãoescolhida anteriormente, caso não haja impedimento externo, e.g. durante animação introdutóriaou animação em que o lutador recebe dano do oponente. Uma vez que o processamento ocorrede maneira síncrona e sem restrição de tempo para a tomada de decisão do agente, conformeobservado neste ambiente de experimentos, o custo computacional exigido pelo processamentodos agentes impacta diretamente na taxa de atualização de quadros na tela, e, consequentemente,no desempenho de execução do jogo.

Em relação às propriedades teóricas do jogo, o Knock’em pode ser classificado como umjogo:

� competitivo de dois jogadores em tempo real;

� de soma zero, no qual o ganho de um lutador representa a perda do outro;

� de estados e ações discretos;

� de resultados determinísticos às ações dos lutadores;

3.6. CONCLUSÃO 37

� de informação imperfeita, uma vez que a tomada de decisão dos lutadores ocorresimultaneamente;

� de informação incompleta, considerando que os lutadores desconhecem a estratégiado oponente;

O projeto do jogo Knock’em conta não somente com o sistema principal do jogo, no qualo jogador enfrenta diferentes lutadores em cenários diversos em uma progressão crescente dedificuldade dentro do contexto de uma narrativa. Ele contém também dois sistemas auxiliares:um simulador e um sistema de playtest. O simulador executa uma sequência de partidasentre agentes em dois modos, treinamento e validação, possibilitando a realização de testespreliminares, treinamento offline e os experimentos da Seção 6. Já o sistema de playtest permiteque jogadores humanos possam testar agentes implementados no projeto em uma sequência departidas.

3.6 Conclusão

Este capítulo apresentou três abordagens diferentes para o ajuste dinâmico de dificuldadeno comportamento de agentes, descrevendo seu funcionamento em geral e suas características,comentando sobre os processos de aprendizagem e adaptação. Em seguida, foram explicados osexperimentos que antecederam este trabalho, revelando a dificuldade em competir contra umhumano, e destacando o desempenho do agente baseado em AR sem balanceamento. Por fim, foiexplicado o caso de estudo considerado tanto nos experimentos passados quanto nos realizadosneste trabalho.

O próximo capítulo apresenta a abordagem estudada neste trabalho, detalhando o funcio-namento de sistemas classificadores. Além disso, são descritas as primeiras investigações sobrea viabilidade da abordagem, expondo as dificuldades encontradas e as alternativas encontradas.

383838

4Solução Proposta e sua Evolução

Este capítulo inicia com uma ideia geral da técnica na qual se baseia a abordagem estu-dada. Na seção seguinte, os primeiros experimentos com sistemas classificadores no problemade DDA são descritos. Em seguida, é detalhada a técnica utilizada para a construção do agenteproposto para o problema. Depois, é explicada a interface utilizada pelos agentes no caso deestudo, assim como o funcionamento dos agentes utilizados como referência nos experimentos.Além disso, detalhes sobre a implementação e decisões de configuração do agente propostosão observados. Por fim, é realizada uma breve discussão sobre a experiência com os testespreliminares executados pelo agente implementado, incluindo hipóteses formadas a partir dosresultados.

4.1 Sistemas Classificadores

A abordagem que investigamos utiliza um sistema adaptativo composto por uma basede regras, sobre as quais opera um algoritmo genético e um mecanismo de reforço, conhecidocomo sistema classificador (BOOKER; GOLDBERG; HOLLAND, 1989). Vale salientar que anomenclatura dessa família de algoritmos, apesar de similar, não se refere aos classificadoresestatísticos encontrados na área de aprendizagem de máquina supervisionada. Ainda que ossistemas classificadores realizem um processo de classificação (identificando regras do tipo"se estado então ação"), costumam ser aplicados em problemas de decisões encadeadas nosquais buscam aprender sequências de ações a partir da utilidade de estados quanto a objetivos,adotando uma abordagem de aprendizagem por reforço.

Na utilização de um mecanismo de aprendizagem por reforço, esses sistemas modelamos problemas como um Processo de Decisão Markoviano. Nesse processo, em dado momento, osistema, representado por um agente, captura do ambiente um estado s ∈ S, sobre o qual devedecidir qual ação tomar de A. Ao escolher a ação a ∈ A, possui uma probabilidade Pa(s,s′) dechegar ao estado s′. Após a transição, recebe o retorno correspondente, Ra(s,s′). As funções deprobabilidade de transição P e de recompensa R devem satisfazer a propriedade de Markov, aqual exige que para calcular uma função para o estado destino s′ não haja dependência além

4.1. SISTEMAS CLASSIFICADORES 39

do estado de origem s e da ação escolhida a. O processo é definido então pela tupla <S, A, P,R>, onde S é um conjunto de estados finito, A é um conjunto de ações finito, P é uma função deprobabilidade de transição, e F é uma função de recompensa.

O problema passa a ser o de encontrar uma função π que informe qual a melhor ação aser tomada em cada estado, maximizando a recompensa acumulada esperada. Nesse contexto, osistema classificador busca aprender sobre o ambiente, com base na experiência acumulada emregras, que competem para executar uma ação, como em DS. Assim como na abordagem comQ-Learning, o sinal de reforço obtido ao alcançar o estado seguinte é utilizado para atualizar asregras que foram disparadas, ajustando as estimativas sobre os pares de estado-ação. O algoritmoé capaz de produzir regras novas e potencialmente melhores com a ajuda de um algoritmogenético.

As similaridades com as abordagens apresentadas anteriormente são grandes, mas aindaassim a aplicação de sistemas classificadores na área de jogos de computador é pouco explorada.Excetuando-se a investigação teórica, os exemplos encontrados foram aplicações em jogo defutebol (SATO; KANNO, 2005) e em combate de tanques (NIDORF; BARONE; FRENCH,2010), sem referência de aplicação para o problema de DDA. Dada a situação, consideramosuma boa oportunidade investigar a aplicação do sistema classificador no contexto de DDA

Entre os atrativos, estão a capacidade de aprender em tempo real, a similaridade comsistemas especialistas em relação ao uso de regras, a capacidade de inserção de regras por partedo game designer e a de construir regras generalizáveis através do algoritmo genético.

4.1.1 Primeiras Investigações

O nosso primeiro trabalho investigou a construção de um agente baseado no sistemaclassificador Zeroth-Level Classifier System (ZCS) (WILSON, 1994), balanceado através datécnica de top culling. Utilizamos como base para implementação da técnica e execução doexperimento, o jogo de luta Knock’em, descrito na Seção 3.5.

A técnica é formada por uma base de regras generalizáveis. Cada regra possui umamedida de predição de recompensas a serem recebidas pelo agente caso executem sua ação,estando satisfeita sua condição. As principais diferenças dessa para outras técnicas de SCs sãoas equações do processo de atualização das regras (chamado bucket brigade), o conjunto deaplicação do algoritmo genético, e principalmente a medida de aptidão se basear na predição dasregras.

O balanceamento do agente é feito pela técnica top culling. Essa técnica utiliza a funçãodesafio da Seção 3.3.1 para adaptar o nível de dificuldade a ser aplicado pelo agente, através doajuste de limite de predição das regras.

O agente ZCS compôs uma equipe de agentes da equipe de teste contra a equipe deadversários, composta por um agente previsível, um agente imprevisível e um agente aprendiz,baseado em Q-Learning. O experimento consistiu para cada agente de teste em uma série de

4.2. SISTEMA CLASSIFICADOR BASEADO EM PRECISÃO 40

50 partidas de avaliação, contra cada agente da equipe de adversários. Antes da avaliação, osagentes realizaram treinamento offline de 1000 partidas, contra o agente de comportamentoaleatório. Os resultados indicaram mau desempenho na adaptação do agente ZCS.

As limitações encontradas no algoritmo nos levou a explorar outro algoritmo da classe SC,o sistema classificador baseado em precisão eXtended Classifier System (XCS) (WILSON, 1995),detalhado na próxima seção. Uma vez que o balanceamento ocorria em agentes semelhantes(como o Dynamic Scripting) e houve evidência de maior necessidade de pesquisa em relação àcompetência, como visto na Seção 3.4, focamos nossa atenção para o problema de aquisição decompetência por parte do agente XCS, para aplicação em DDA.

4.2 Sistema Classificador baseado em Precisão

O sistema classificador baseado em precisão (WILSON, 1995) é um sistema de aprendi-zagem composto por três subsistemas: um sistema de regras, com mecanismos de seleção deregras e de decisão; um sistema de reforço (ou atribuição de crédito), que atualiza regras combase na técnica de Q-Learning (WATKINS; DAYAN, 1992); e um sistema de descoberta deregras, que se utiliza de um algoritmo genético para gerar e eliminar regras. A visão geral dosistema XCS pode ser vista na Figura 4.1. É apresentado a seguir o funcionamento do sistemaclassificador baseado em precisão utilizado, conforme a implementação de BUTZ (2005).

Figura 4.1: Arquitetura do Sistema Classificador baseado em Precisão (XCS)


4.2.1 Sistema de Desempenho

O sistema de regras, também conhecido como sistema de desempenho, é composto poruma população [P] de regras, ou classificadores, as quais são da forma condição-ação. A condi-ção corresponde a um estado do ambiente, representado como um conjunto de característicasobservadas, as quais são codificadas em uma cadeia de símbolos, ou, mais comumente, emuma cadeia binária. Além disso, cada característica de uma observação pode ser codificadacom um símbolo de generalização #, ou don’t care, em que seu valor não é definido, podendoser assumido qualquer símbolo possível para a respectiva característica. A ação correspondeà resposta que o agente pode realizar no ambiente, codificada também por um conjunto desímbolos, sem possibilidade de generalização.

Vale ressaltar que este sistema classificador é do tipo Michigan-style, em que cadaclassificador representa uma solução parcial, ao contrário do tipo Pittsburgh-style, em quecada um representaria uma solução completa. Cada regra possui um conjunto de parâmetrosassociados, ou atributos, entre as quais os três básicos são:

� predição p, uma média da recompensa recebida com a ativação da regra;

� erro de predição ε , uma média do erro calculado para a medida de predição;

� aptidão F , medida de precisão da regra na estimativa da predição, uma função inversaà medida de erro de predição;

� numerosidade num, quantidade de cópias da regra na população, atualizada peloalgoritmo genético, como medida de representatividade na população;

A população de regras pode ser inicializada vazia, gerada aleatoriamente ou carregada deum conjunto de regras já existentes, com os respectivos atributos associados. O número totalde regras (soma de numerosidades das regras) deve respeitar o limite imposto pelo tamanhopopulacional máximo N.

A cada início de ciclo, os detectores do sistema mapeiam estímulos de entradas em umnovo estado. Regras cuja condição seja satisfeita pelo estado capturado compõem o conjuntode regras compatíveis [M]. Em seguida, é calculado o array de predições P(A), formado pelasmédias das predições existentes em [M] ponderadas pelas respectivas aptidões.

Uma ação é escolhida com base no array P(A) calculado. Existem maneiras distintaspara escolher a ação. A mais simples é a escolha da ação que possua a maior predição em P(A),utilizada principalmente em ciclos de usufruto. Outra possível é a escolha de ação aleatória,que não considera valores de predição, sorteia uma ação existente no conjunto [M], utilizada emciclos de exploração. Para manter o equilíbrio entre a exploração necessária à aprendizagem e ousufruto desejado durante as avaliações, existem outras políticas de seleção de ação. Na políticade seleção e-greedy, é escolhida uma ação aleatória existente em [M] com probabilidade deexploração e, ou a ação com a maior predição em P(A). Por sua vez, a política de seleção softmax


atribui a cada ação uma probabilidade de ser escolhida Prob(a), definida pela distribuição deGibbs, ou Boltzmann, seguinte:

Prob(a) =eP(a)/τ

∑ni=1 eP(i)/τ

� �4.1

onde P(a) é a predição da ação a, n é o número de ações existentes em [M] e τ é o parâmetrode temperatura, que diminui com o tempo. A política softmax inicialmente escolhe as açõescom aproximadamente a mesma probabilidade, tendendo a escolher mais a ação com maiorpredição em P(A) ao longo do tempo. Na política de seleção da roleta, também conhecida comoproporcional, cada ação possui uma probabilidade de ser escolhida proporcional à sua prediçãoem P(A).

Após selecionada, a ação é executada no ambiente, retornando o sinal de reforço imediator. As regras do conjunto [M] que possuem a regra selecionada formam o conjunto de ação [A].Dois atributos associados às regras estão relacionados ao conjunto [A]: a experiência exp, quecorresponde ao número de participações em conjuntos [A] até então, e à estimativa de tamanhode nicho (conjunto de ação) as.

4.2.2 Sistema de Atribuição de Crédito

A etapa de atualização tem por objetivo ajustar as estimativas das regras de acordo como retorno obtido nas tomadas de decisões. É a parte do sistema que identifica quais regras sãoúteis em termos de recompensa futura e que incentiva a descoberta de regras melhores (LANZI,2008).

O processo desta etapa opera sobre o conjunto [A]−1 formado no ciclo anterior. O sinalde reforço imediato r é utilizado pelo sistema de atribuição de crédito para atualizar os atributosε , p e F das regras. A atualização é realizada com base no valor da predição de recompensa P,calculado como:

P = r+ γ ∗maxP(A)−1� �4.2

onde γ é um fator de desconto (0 < γ ≤ 1) e maxP(A)−1 é a maior predição encontrada no arrayde predição do ciclo anterior P(A)−1.

Ao início da etapa de atualização, o valor de exp é aumentado em uma unidade. Paracada regra do conjunto [A]−1, os valores de ε , p e as são atualizados segundo a regra delta deWidrow-Hoff (WIDROW, 1960), como nas equações abaixo:

ε ← ε +β (|P− p|− ε)� �4.3

p← p+β (P− p)� �4.4

as← as+β ( ∑c∈[A]−1

numc−as)� �4.5


onde β é a taxa de aprendizagem, de valor fixo (β = β f ixo) ou decrescente com a experiência daregra (β = βdec

βdec+1+exp ).A atualização da aptidão F exige mais passos, sendo preciso calcular a precisão relativa

da predição estimada pelas regras. Primeiro, é calculada a precisão absoluta κ de cada regra apartir do valor de ε , conforme a seguinte equação:

κ =

1, se ε < ε0

α(ε/ε0)−ν , senão

� �4.6

onde ε0 é o parâmetro de tolerância máxima no erro de predição, ν é o parâmetro que regula ograu da queda de precisão e α é o parâmetro associado à diferença entre a precisão da regra eprecisão geral no conjunto (BUTZ, 2005). Em seguida, a precisão relativa κ ′ é calculada paracada regra conforme:

κ′ =

κ ∗num∑c∈[A]−1 κc ∗numc

� �4.7

Por fim, a aptidão F é calculada com base na precisão relativa κ ′, também pela regra delta:

F ← F +β (κ ′−F)� �4.8

A atualização da regra é realizada na ordem: exp, e, p, as e F . É possível atualizar apredição p antes do erro e. Isso permite uma aprendizagem inicial mais rápida em problemasmais simples, mas pode atrapalhar em problemas mais complexos. A estratégia consideradana explicação, com o erro atualizado antes, é mais conservativa, e parece trabalhar melhor emproblemas mais difíceis BUTZ; WILSON (2001).

Caso a regra não tenha experiência suficiente (exp < 1/β ), é empregada a técnica MAM(moyenne adaptive modifiee) no lugar da regra delta, a fim de minimizar a sensibilidade inicial àconfiguração inicial de seus atributos (WILSON, 1995). Nas Equações 4.3, 4.4 e 4.5, o termo β

é substituído pela razão 1/exp.O algoritmo opera sobre sequências de estados definidas como problemas de aprendiza-

gem, divididas em problemas de classificação e problemas de múltiplos passos. Em problemasde classificação, os estados são independentes, enquanto que em problemas de múltiplos passos,os estados são encadeados, exigindo distribuição do sinal de reforço por todas as regras queparticipam da sequência de decisões.

A etapa de atribuição de crédito funciona como descrito acima para problemas demúltiplos passos, como é o de comportamento de agentes. Adicionalmente, no ciclo final deum problema, a etapa de atualização realiza o mesmo processo, com duas exceções apenas. Aprimeira é que o processo realizado considera o conjunto final [A] no lugar do conjunto anterior[A]−1, incluindo as equações de atualização. A segunda exceção é que a predição de recompensaP não é definida como na Equação 4.2, mas igual ao sinal de reforço imediato, P = r. Esse modoadicional de atualização no ciclo final de um problema de múltiplos passos é o único modo de


atualização que ocorre em um problema de classificação, sem a atualização de conjuntos de açãopassados.

Ainda quanto à atualização de regras, é possível integrar a técnica de descida do gradiente(gradient descent), que realiza uma otimização local de acordo com a maior taxa de variaçãonos valores dos atributos das regras (BUTZ; GOLDBERG; LANZI, 2005). Seu uso conferiumaior robustez ao algoritmo em relação à escolha dos parâmetros em problemas de múltiplospassos. Para tal, basta multiplicar o termo β (P− p) na Equação 4.4 pela razão F

FT, onde FT é o

somatório das aptidões F no conjunto sobre o qual opera o sistema de atribuição de crédito.

4.2.3 Sistema de Descoberta

Ao final de cada ciclo, após a etapa de atualização das regras, realiza-se um teste parasaber se o algoritmo genético pode ser aplicado sobre o conjunto de ação passado [A]−1. O testeverifica o número médio de ciclos desde o qual as regras do conjunto considerado não participamdo processo realizado pelo algoritmo genético, média essa ponderada pela numerosidade de cadaregra. Apenas se o número médio de ciclos exceder o limite definido pelo parâmetro θAG, oalgoritmo genético é aplicado.

O papel do algoritmo genético no sistema classificador é o de criar uma base de regrasque resolvam o problema cooperativamente (BULL; KOVACS, 2005). Diferente do cenáriode otimização tradicional, a busca nesta etapa não é pela melhor regra, mas por um conjuntode regras diversas que representem com precisão o conhecimento sobre o problema e sejamutilizadas na construção de um comportamento confiável.

Inicialmente, as regras são selecionadas para reprodução, processo em que geram novasregras. Entre os métodos de seleção possíveis, os mais comuns são: o método da roleta e ométodo de seleção por torneio. O método da roleta procede da mesma forma que explicado paraa seleção de ação na Seção 4.2.1, com a diferença que neste processo a chance individual deseleção é proporcional à aptidão F , e não à predição p da regra. O método de seleção por torneioconsiste na seleção aleatória de uma fração τ do conjunto de ação considerado, a partir da qual éescolhida a regra com maior aptidão.

Para cada uma das duas regras selecionadas, é gerada uma regra “filha” idêntica, commesmos valores de atributos, exceto pela experiência exp e pela numerosidade num, que sãoreiniciadas para os valores 0 e 1, respectivamente. Essas novas regras compõem a prole, enquantoas que as geraram são conhecidas como indivíduos pais nessa fase. Realiza-se o teste para aprobabilidade χ de ocorrer cruzamento na condição de cada regra da prole. Se o teste nãofalhar, o cruzamento pode acontecer de diferentes formas, tais como cruzamento uniforme,cruzamento em um ou dois pontos. O cruzamento uniforme procede da seguinte maneira: paracada símbolo codificado nas regras é feito um teste de probabilidade de 50% para a permutaçãodos símbolos de mesma posição na prole. O cruzamento em um ponto sorteia aleatoriamenteum ponto intermediário na cadeia de cada regra da prole, de modo que os símbolos após esse


ponto são permutados entre as regras. De maneira similar, o cruzamento em dois pontos sorteiaaleatoriamente dois pontos intermediários diferentes nas regras da prole, de maneira que ossímbolos entre esses pontos são permutados entre as regras. Após a aplicação do cruzamento, osvalores de p, e e F da prole são atualizados para as médias dos respectivos valores dos pais, como valor da aptidão F reduzida por um fator de desconto parametrizado.

Em seguida, a operação de mutação é aplicada em cada regra da prole, com umaprobabilidade de mutação por símbolo definida pelo parâmetro µ . Em caso de sucesso no teste,a mutação pode acontecer de dois modos: guiado e livre. No primeiro modo, o novo símbolo éescolhido com mesmas chances entre o símbolo de generalização # (don’t care) e o respectivosímbolo no estado considerado pelo conjunto de ação. No segundo modo, o novo símbolo ésorteado aleatoriamente entre todos os símbolos possíveis para a posição.

Após a mutação, a prole é inserida na população. Caso o tamanho da população (total dosvalores de numerosidade na população) seja extrapolado, é ativado um processo de eliminação,no qual são selecionadas regras proporcionalmente aos votos de eliminação associados, como intuito de eliminar aquelas que são experientes e relativamente de baixa aptidão. Esse votoé calculado com base na estimativa de tamanho de nicho as multiplicada pela numerosidadenum da regra. Outro fator é aplicado ao voto se a experiência exp superar o limite definidopelo parâmetro θdel e ao mesmo tempo possuir a aptidão média individual F/num menor queuma fração δ da aptidão média da população. O fator extra é dado pela razão entre a aptidãomédia da população e a aptidão média individual. A regra escolhida tem então sua numerosidadediminuída por uma unidade, sendo efetivamente descartada da população se a numerosidadechegar a zero.

Além do processo de descoberta do algoritmo genético, há o mecanismo de covering

(WILSON, 1986), que opera quando, ao se criar o conjunto de classificadores compatíveis[M], ele resulta vazio ou o número de ações disponíveis entre as regras nele contidas é menorque o número mínimo definido pelo parâmetro θMNA. Nessa situação, ele cria uma nova regracom os símbolos da condição correspondentes à codificação do estado, mas com probabilidadede generalização por símbolo P#, e com ação aleatória. Essa nova regra é então adicionadaà população, e serve como uma hipótese a ser testada condizente com a realidade (MOIOLI;VARGAS; VON ZUBEN, 2008). A inserção e eliminação de regras na população seguemconforme explicado para o algoritmo genético.

Devido aos operadores de cruzamento, mutação e covering, não é necessário que o agentecontenha todas as combinações possíveis de regras, como ocorre com o Q-Learning. Isso épossível uma vez que eles criam e adaptam regras que são pertinentes à experiência que o agentepassa.

Uma tarefa opcional do sistema de descoberta é a de realizar subsunção de regras, istoé, de integrar uma regra de condição mais específica em uma regra de condição mais genérica,ambas com a mesma ação. Uma condição é mais genérica que outra, se a primeira puder serativada por todos os estados que ativam a segunda, mas não for possível o inverso. Para realizar a

4.3. INTERFACE DOS AGENTES 46

subsunção, é necessário que a regra mais genérica tenha experiência maior que o parâmetro θsub

e o erro de predição menor que a limite de tolerância máxima permitida por ε0. Se as condiçõespara a subsunção forem satisfeitas, a regra mais genérica tem sua numerosidade aumentada pelovalor da numerosidade da regra mais específica, e essa por sua vez é eliminada da população. Épossível realizar a subsunção ao fim da aplicação do algoritmo genético ou ao fim da fase deatualização das regras. No primeiro caso, antes de inserir a prole na população, a subsunçãoé checada a fim de integrar as regras dela aos pais, mais experientes e possivelmente maisgenéricos. No segundo caso, a subsunção é checada para todas as regras do conjunto de açãorecém-atualizado integrarem a regra mais genérica do conjunto.

4.3 Interface dos Agentes

As ações tomadas pelos lutadores dependem de como o agente que o implementa percebeo estado do ambiente da partida. A forma como as ações e os estados são codificados determinao tamanho e o relevo do espaço de pares estado-ação, sobre o qual o agente realiza a busca pelosseus objetivos. Isso impacta na capacidade de interação do agente com o ambiente, onde em umaextremidade o agente pode não conseguir capturar dados relevantes para tomar uma decisão, eem outra extremidade dados desnecessários podem atrapalhar a busca do agente.

Além disso, a representação de estados e ações tem impacto direto no tempo que oagente que aprende leva para explorar o espaço de busca por comportamentos apropriados paracada situação. As características consideradas relevantes e a resolução de seus valores podemintroduzir considerável ruído na aprendizagem. A situação se agrava pela necessidade dos agentesrevisitarem continuamente os estados, no lento e gradual processo de aprendizagem. Assim, éimportante representar adequadamente o estado do ambiente e a ação do agente, simplificandoquando possível, a fim de agilizar a aprendizagem.

Utilizamos uma representação de estado do ambiente encontrada no projeto do jogocujos atributos possuem valores discretos, reduzindo o espaço de busca e expondo apenas osdados considerados relevantes. Quanto ao espaço de ações, o golpe especial é a única ação queexige do jogador humano a realização de uma sequência específica de movimentos e golpes paraser ativada, mas que no caso dos agentes é simplificado apenas como uma opção de ação.

Representamos um estado do ambiente S pela tupla de símbolos:

S = (Sagente,Soponente,D,Magente,Moponente,F)

Sagente representa o estado atual do agente: parado, pulando, agachado. Soponente representa oestado atual do oponente: parado, pulando, agachado, atacando, atacando e pulando simultanea-mente, atacando e agachando simultaneamente, bloqueando. D representa a distância do agenteao oponente: perto (ao alcance de um golpe), médio, longe. Magente e Moponente significam adisponibilidade de pontos de magia do agente e do oponente respectivamente para usar golpe

4.3. INTERFACE DOS AGENTES 47

especial: suficiente, insuficiente. F significa o estado da bola de fogo lançada pelo oponente:perto, médio, longe, inexistente.

Os valores possíveis para o estado do agente são aqueles em que ele pode realizar atomada de decisão. Já o conjunto de estados possíveis do oponente é reduzido ao abstrair quequalquer dos quatro golpes básicos representa um ataque.

Quanto às ações, pode decidir por: realizar soco forte, soco rápido, chute forte, chuterápido, usar golpe especial, pular, pular para frente (em direção ao oponente), pular para trás(fugindo do oponente), bloquear, andar para frente, andar para trás, agachar, permanecer parado.Algumas ações como as de bloqueio e de movimentação lateral são repetições dessas ações, de40 e de 20 ciclos de decisão respectivamente. As demais acontecem em uma animação de tempofixo que dura apenas um ciclo de decisão.

Os agentes do jogo consultam uma função fornecida pelo sistema para checar se umaação é proibida em dado estado. O sistema proíbe a execução de golpe especial sem pontosde magia suficientes como também proíbe a realização de outras ações que não sejam golpesbásicos enquanto o agente pula. A mesma função também implementa duas regras heurísticasque impedem a execução de ações desnecessárias em certas situações, com intuito de agilizar aaprendizagem do agente. São elas a execução de golpes básicos à distância e a realização depulos à distância sem haver bola de fogo disparada pelo oponente.

Para os agentes que utilizam reforço do ambiente para a aprendizagem, adotamos o sinalde reforço definido na Equação 4.9.

reforçot = (PVoponentet−1−PVoponentet )− (PVagentet−1−PVagentet ) = ∆oponentet −∆agentet

� �4.9

Para calcular o sinal de reforço recebido em um dado momento t, é necessário calcularantes os pontos de vida PV perdidos pelo agente e pelo oponente, entre o ciclo anterior t−1 eo ciclo corrente t. O sinal reforçot é igual à diferença de pontos de vida do oponente ∆oponentet

menos a diferença de pontos de vida do agente ∆agentet .O intervalo máximo do sinal de reforço é o mesmo da pontuação final da partida, que

é de [-100,100], definido pela quantidade inicial de 100 pontos de vida do agente. Porém, oataque mais efetivo entre as ações possíveis, no melhor caso, retira 40 pontos de vida, conformeimplementado no sistema do jogo. Assim, o intervalo prático do sinal de reforço é de [-40,40],no qual sinais positivos indicam sucesso em uma situação, e.g. a aplicação efetiva de um golpe, esinais negativos indicam falha em uma situação, e.g. o recebimento de um ataque do oponente.

A Equação 4.9 também foi adotada pelos agentes baseados em reforço desenvolvidos emoutros trabalhos (ANDRADE et al., 2005). Sua adoção permite que, ao invés do agente recebero sinal de reforço apenas na avaliação do objetivo final (vencer a partida), ele o receba após aexecução de cada ação, no cumprimento de subobjetivos (vencer situações), o que agiliza suaaprendizagem (MATARIC, 1994).

4.4. AGENTES DE REFERÊNCIA 48

4.4 Agentes de Referência

Uma vantagem do uso da plataforma Knock’em é a existência de agentes pré-implementados.Para esse trabalho, utilizamos como referência três agentes: um agente baseado em máquina deestados (SMPlayer), um agente de comportamento aleatório (RDPlayer) e um agente baseadoem aprendizagem por reforço (RLTPlayer).

O agente SMPlayer é implementado como um conjunto de regras que mapeiam estadosa ações. Como as regras são definidas em tempo de desenvolvimento, apresenta comporta-mento previsível. Uma simplificação do comportamento do agente SMPlayer em pseudocódigoencontra-se no Algoritmo 1.

Algoritmo 1 Tomada de Decisão do Agente SMPlayer1: função TomarDecisão(estado)2: se (Distância(estado) = perto) e (Oponente(estado) = atacando) então3: retorna ação← andarParaTrás4: fim5: se BolaDeFogo(estado) = perto então6: retorna ação← bloquear7: fim8: se Oponente(estado) = agachado então9: retorna ação← pularParaFrente

10: fim11: se Distância(estado) = perto então12: i← SortearNúmeroAleatório(0,3)13: se (i = 0) então14: retorna ação← socoForte15: senão se (i = 1) então16: retorna ação← socoRápido17: senão se (i = 2) então18: retorna ação← chuteForte19: senão20: retorna ação← chuteRápido21: fim22: fim23: se (Distância(estado) = média) ou (Distância(estado) = longe) então24: retorna ação← andarParaFrente25: fim26: fim

O agente RDPlayer executa ações aleatoriamente, tendo como exceção apenas as res-trições que o sistema informa aos agentes, como exposto anteriormente. Assim, devido àausência de estratégia na tomada de decisão, esse é considerado o agente mais imprevisível. Opseudocódigo no Algoritmo 2 demonstra como ocorre a seleção de ação desse agente.

O agente RLTPlayer implementa a técnica Q-Learning (WATKINS; DAYAN, 1992),sendo a mesma implementação utilizada por ANDRADE et al. (2005). Segue a mesma aborda-

4.5. AGENTE XCS BÁSICO 49

Algoritmo 2 Tomada de Decisão do Agente RDPlayer1: função TomarDecisão2: ação← indefinida3: enquanto ação = indefinida faça4: intençãoDeAção← SortearAçãoAleatória5: permitida← ChecarSeAçãoPermitida(intençãoDeAção)6: se (permitida) então7: ação← intençãoDeAção8: fim9: fim

10: retorna ação11: fim

gem vista na Seção 3.3, com a exceção de que atua no melhor nível. Ele armazena uma matrizbidimensional SxA onde armazena as estimativas para todos os pares estado-ação possíveisconforme a descrição na Seção 4.3. A tomada de decisão ocorre com base nessa matriz e napolítica de seleção de ação definida na Tabela 4.1. Após a execução da ação em dado estado,o valor correspondente ao par na matriz é atualizado com base na estimativa de melhor valorobtido a partir do novo estado, de maneira similar à atualização de predição de regras que ocorrena Seção 4.2.2. O comportamento do agente pode ser visto no pseudocódigo do Algoritmo 3.

Algoritmo 3 Tomada de Decisão do Agente RLTPlayer1: função TomarDecisão(estado−1, ação−1, reforço−1, estado)2: ciclos−1← ObterNúmeroDeCiclosDeAção(ação−1)3: se decaimentoDeαQ = ativado então4: αQ← CalcularTaxaDeAprendizagem(númeroDeVisitas, quocienteDeVisitasDeαQ)5: fim6: AtualizarNúmeroDeVisitas(estado−1, ação−1)7: melhorQ← ObterMelhorValorQ(estado)8: AtualizarValorQ(estado−1, ação−1, αQ, ciclos−1, reforço−1, melhorQ)9: ação← SelecionarAção

10: retorna ação11: fim

A política de seleção de ação pode variar conforme o experimento apresentado, sendoexplicitado quando for conveniente. As configurações utilizadas pelo autor foram testadas,resultando na escolha do conjunto de parâmetros da Tabela 4.1.

4.5 Agente XCS Básico

A abordagem proposta nesse trabalho é implementada pelo agente XCSPlayer com basena técnica XCS detalhada na Seção 4.2.

As regras acompanham a codificação do estado e da ação, como descritos na Seção 4.3.Enquanto a representação do ambiente tem todos os valores de sua tupla bem definidos, as regras


Parâmetro ValorγQ (Fator de desconto) 0.9αQ (Coeficiente de aprendizagem) 0.5Quociente de visitas do αQ 10Decaimento do αQ desativadoPolítica de seleção de ação softmaxTemperatura (softmax) 1.0Taxa de exploração (e-greedy) -

Tabela 4.1: Parâmetros do Agente RLTPlayer

têm capacidade de generalização com a possibilidade de uso do símbolo # (don’t care) na cadeiade símbolos da condição.

Uma adaptação foi realizada na Equação 4.2, que originalmente não considera açõesde tempos diferentes. O problema antes modelado como um Processo de Decisão Markovianopassa a ser tratado como um Processo de Decisão Semi-Markoviano (PDSM), que mantém aspropriedades da modelagem anterior, mas que trata de problemas com duração de tempo variável.Assim, adaptamos a Equação 4.2, com base na solução implementada pela técnica Q-Learning

(WATKINS; DAYAN, 1992), trocando apenas o termo γ pelo termo γ t , onde t é o intervalo detempo para a ação executada pelo conjunto de ação considerado para atualização.

A descrição simplificada do agente XCSPlayer é encontrada no pseudocódigo do Al-goritmo 4. Os procedimentos nele abstraídos são vistos na Seção 4.2. Uma descrição maisdetalhada da técnica base foi publicada por BUTZ; WILSON (2001).

O agente XCSPlayer foi construído com foco em uma arquitetura parametrizável datécnica XCS. Além dos parâmetros numéricos do algoritmo básico, a configuração do agenteimplementado inclui parâmetros relativos à sua arquitetura e à sua política de aprendizagem.

Os parâmetros relacionados à arquitetura do agente estão associados aos procedimentose às considerações que interferem no modo como funciona. Alguns desses parâmetros sãovariações comuns consideradas na literatura sobre a técnica XCS, tais como o uso do métodode descida de gradiente (gradient descent) ou não na equação de atualização de predição dasregras, o uso de taxa de aprendizagem fixa ou decrescente, a ordem de atualização dos atributosdas regras, o tipo de seleção de pais, de operadores de cruzamento e mutação, e sobre o uso desubsunção de regras.

Adicionalmente, pensamos em uma modificação como parâmetro de decisão associadoao mecanismo de reforço. Traçando um paralelo entre a atualização de valores Q no Q-Learning

e de valores de predição de regra no XCS, constatamos que enquanto no primeiro a atualizaçãoconsidera estimativas correntes na distribuição do reforço (WATKINS; DAYAN, 1992), o segundotradicionalmente atualiza as predições com atraso de um ciclo de decisão (WILSON, 1995).Assim, integramos a opção de atualização “antecipada” à arquitetura do agente, de forma aatualizar regras com predição mais recente, ao molde do algoritmo Q-Learning. A modificaçãocausada pela antecipação no fluxo do algoritmo é visualizada no Algoritmo 4.


Algoritmo 4 Tomada de Decisão do Agente XCSPlayer1: função TomarDecisão(estado−1, ação−1, reforço−1, estado)2: ciclos−1← número de ciclos de ação−13: fimDeProblema← ChecarFimDeProblema(reforço−1)4: se atualização antecipada = ativada então5: [M]← FiltrarRegrasAtivadas([P], estado)6: P(A)← GerarVetorDePrediçõesPorAção([M])7: maxP(A)← valor máximo em P(A)8: se fimDeProblema então9: AtualizarRegras([A]−1, reforço−1)

10: AplicarAG([A]−1, estado−1) . Mutação guiada depende de estado11: senão se [A]−1 não está vazio então12: recompensa−1← CalcularRecompensa(reforço−1, ciclos−1, maxP(A))13: AtualizarRegras([A]−1, recompensa−1)14: AplicarAG([A]−1, estado−1)15: fim16: P(A)← GerarVetorDePrediçõesPorAção([M]))17: maxP(A)← valor máximo em P(A)18: senão19: se [A]−2 não está vazio então20: recompensa−2← CalcularRecompensa(reforço−2, ciclos−2, maxP(A)−1)21: AtualizarRegras([A]−2, recompensa−2)22: AplicarAG([A]−2, estado−2)23: fim24: se fimDeProblema então25: AtualizarRegras([A]−1, reforço−1)26: AplicarAG([A]−1, estado−1)27: senão . Variáveis internas utilizadas na próxima tomada de decisão28: estado−2← estado−129: [A]−2← [A]−130: reforço−2← reforço−131: ciclos−2← ciclos−132: fim33: [M]← FiltrarRegrasAtivadas([P], estado)34: P(A)← GerarVetorDePrediçõesPorAção([M]))35: maxP(A)← valor máximo em P(A)36: fim37: ação← SelecionarAção38: [A]← FiltrarRegrasComAçãoEscolhida([M], ação)39: [A]−1← [A] . Variável interna utilizada na próxima tomada de decisão40: maxP(A)−1← maxP(A) . Idem41: retorna ação42: fim


Também colocamos um parâmetro relativo à delimitação das sequências de decisõesconsideradas como problemas individuais, uma vez que a literatura aponta a dificuldade datécnica em aprender cadeias de ações muito longas (WILSON; GOLDBERG, 1989; BARRY,2002). A criação desse parâmetro permite definir se um problema deve ser considerado peloagente como sendo toda a sequência de ações de uma luta (associado ao objetivo final) ou comosendo alguma sequência parcial com resultado de sucesso ou falha (associado aos subobjetivos).Nesse último caso, o problema seria considerado como qualquer sequência de ação que resultasseem reforço diferente de zero, podendo ser tão breve quanto golpes básicos consecutivos e tãolongo quanto uma partida inteira de esquivas. Sob essa condição, uma partida de luta deixa deapresentar apenas uma oportunidade de experiência à aprendizagem do agente e passa a forneceruma coleção de experiências menores, o que renderia mais chances de aprender a um agente parauma mesma quantidade de partidas.

Outro parâmetro influenciado por essa questão de delimitação de escopo do problemaconsiderado pelo agente é o que define a política de seleção de ação. Vimos na literatura tantoexemplo de política gulosa que determina o turno de exploração (exploration) ou de usufruto(exploitation) por problema (WILSON, 1995) ou por ação (BUTZ; WILSON, 2001). As duasvariações foram consideradas na arquitetura do sistema.

A política de seleção de ação não é só parametrizável por tipo de seleção, como tambémpor tipo de partida. O intuito dessa divisão está em facilitar os experimentos que contémintervalos exclusivos de aprendizagem e intervalos intercalados entre aprendizagem e avaliaçãodo agente. Assim, há parâmetros de política individuais para os tipos de partida.

Por fim, alguns parâmetros numéricos têm seu valor definido em relação ao intervalo dereforço que o agente pode receber. Uma vez que o agente foi codificado para tratar esse intervalode maneira independente de contexto, esses parâmetros foram adaptados para corresponder aproporções do reforço máximo recebido pelo agente. São essas adaptações as proporções paravalor de predição inicial das regras, valor de erro de predição inicial das regras, e o valor limitede tolerância de erro utilizado no cálculo de aptidão das regras.

Consideramos esses parâmetros discutidos além dos demais numéricos na configuraçãodo agente XCSPlayer. Baseamos as primeiras configurações manuais naquelas utilizadas emproblemas similares encontrados na literatura (WILSON, 1995; BUTZ, 2005), adaptando asescolhas à medida que realizamos alguns poucos testes. A Tabela 4.2 lista os parâmetrosutilizados pelo agente na primeira coluna e a configuração feita manualmente na terceira coluna.

4.5.1 Experimento Preliminar

Os primeiros experimentos para avaliação do XCSPlayer foram executados com a con-figuração definida manualmente, conforme os valores da terceira coluna na Tabela 4.2. De-nominamos essa primeira versão, parametrizada manualmente, de XCSPlayer v.1. O intuitodeste experimento inicial foi o de nos prover uma percepção sobre a capacidade do agente


adquirir competência contra um agente de comportamento imprevisível (RDPlayer), avaliandoseu desempenho contra os agentes básicos, SMPlayer e RDPlayer. Acreditamos que o agenteimprevisível como treinador rendesse maior diversidade de situações aos agentes treinados, porisso sua escolha em detrimento dos outros agentes. O agente de referência utilizado foi o agenteRLTPlayer, configurado segundo a Tabela 4.1.

Para cada agente básico utilizado para avaliação, foram feitas 3 séries de 200 ciclossequenciais de treinamento e teste. Cada ciclo corresponde a uma partida de treinamento contrao agente RDPlayer e 4 partidas de teste contra um dos agentes básicos. As séries foram iniciadassem conhecimento inicial: nenhuma regra na população do agente XCSPlayer v.1 e tabela devalores Q inicializada com zeros no agente RLTPlayer. Visto essa limitação, foi permitida aatualização de regras ao longo de todas as partidas, de treinamento e de teste. Enquanto o agenteRLTPlayer utilizou a mesma política de ação durante treinamento e teste, o agente propostoseguiu uma política diferente em cada tipo de partida, utilizando a política indicada na Tabela 4.2durante o treinamento, e jogando em seu melhor nível (seleção da melhor regra) em partidas deteste. Adotamos esse detalhe como medida de controle para a estabilidade do algoritmo.

Os resultados são mostrados na Figura 4.2 e 4.3, que apresenta o desempenho médio daspartidas de teste por ciclo entre as séries executadas.

Figura 4.2: Desempenho médio de 3 séries de 200 ciclos com 1 partida de treinamento(contra RDPlayer) e 4 partidas de teste (contra RDPlayer) entre o agente XCSPlayer v.1 e

RLTPlayer

O gráfico da Figura 4.2 mostra a dificuldade maior do agente XCSPlayer v.1 em formaruma boa política de ação em meio à imprevisibilidade do oponente. A diferença de desempenhotorna-se mais evidente por volta do 30º ciclo, quando, com algum ruído, o agente RLTPlayer

consegue manter ou subir o seu nível, ao passo em que o agente XCSPlayer v.1 oscila bastante


em torno de um mesmo valor ao longo do experimento.

Figura 4.3: Desempenho médio de 3 séries de 200 ciclos com 1 partida de treinamento(contra RDPlayer) e 4 partidas de teste (contra SMPlayer) entre o agente XCSPlayer v.1 e

RLTPlayer

Quanto à avaliação com agente previsível, na Figura 4.3, o desempenho do agenteXCSPlayer v.1 se manteve similar, com uma média um pouco menor e uma variação um poucomaior. O comportamento esperado foi apresentado pelo agente RLTPlayer, que diante de umcomportamento menos diverso do oponente, conseguiu aproveitar melhor a experiência dotreinamento.

Se por um lado o desempenho do agente XCSPlayer v.1 não foi expressivo, ao menos ficoudemonstrada a viabilidade de execução da técnica para aplicação no problema de aprendizagemem jogos de luta. Alguns tipos de configuração parecem ter causado impacto no consumo derecursos, com momentos de baixa taxa de atualização da tela. O cuidado na escolha dos valorespara a configuração do agente deve atender suficientemente bem essa questão.

Quanto ao entendimento dos resultados obtidos neste experimento, uma possível causapara o desempenho similar entre agentes de comportamentos tão diferentes, por parte do agenteXCSPlayer v.1, poderia ser a quantidade de tempo insuficiente para uma efetiva aprendizagem.Agentes que utilizam técnicas de Aprendizagem de Máquina são conhecidos como aprendizeslentos, e demoram a convergir. Entretanto, o agente RLTPlayer mostrou a tendência da aprendi-zagem nas curvas de desempenho do experimento. Supondo que o tempo não fosse adequado, oagente proposto deveria ao menos revelar o mesmo direcionamento.

A experiência de implementação nos mostrou a dificuldade em obter uma parametrizaçãoadequada ao agente. Além do elevado número de parâmetros, a utilização de valores indicadosna aplicação da técnica XCS em outros trabalhos não resultou em desempenho satisfatório.

4.6. CONCLUSÃO 55

Seria exaustivo continuar o processo de parametrização manual, em busca de uma configuraçãorazoável, sem um direcionamento melhor.

Focamos então na investigação de uma forma automática de otimizar a configuração doagente proposto. Encontramos no F-Race (BIRATTARI et al., 2002) a alternativa robusta paraesse problema.

4.6 Conclusão

Neste capítulo, introduzimos a solução abordada. Foi apresentada a visão geral de umsistema classificador, a modelagem de problema utilizada, bem como os fatores que a tornamatraente. Comentamos sobre uma investigação inicial com uma versão anterior de SC e a mudançade foco para a técnica abordada. Em seguida, esclarecemos em detalhes o funcionamento desistemas classificadores baseados em precisão. Descrevemos quais as informações observadaspelo agente no jogo, como ele pode agir e em quais situações o sistema do jogo interfere emsuas ações. Explicamos também os procedimentos executados pelos agentes de referência.Depois, relatamos o desenvolvimento do agente proposto, os detalhes adaptados, os parâmetrostradicionais e os adicionais de nossa parte. Comentamos ainda os primeiros testes com o agenteparametrizado manualmente, apontando as dificuldades encontradas e as hipóteses formadas.

No próximo capítulo, é detalhado o processo de parametrização automática. Encontram-se também os testes preliminares que avaliam o agente proposto parametrizado com o F-Race

contra sua versão parametrizada manualmente e os demais agentes vistos na Seção 4.4.

4.6. CONCLUSÃO 56

Parâmetro Valores Considerados Valor EscolhidoManualmente

Valor Escolhidopelo F-Race

tamanho máximo da população 1000;4000;7000;10000 2620 4000pirel (predição inicial deregra relativa à recompensa máxima)

-1;-0.8;-0.6;-0.4;-0.2;0;0.2;0.4;0.6;0.8;1 0 0.6

eirel (erro inicial de prediçãode regra relativo à recompensa máxima)

0.01;0.1;0.2;0.3;0.4;0.5;0.6;0.7;0.8;0.9;1 1 1

fi (aptidão inicial de regra)0.01;0.05;0.1;0.15;0.2;0.25;0.3 0.01 0.01

política de seleção de ação para treino

aleatória;e-greedy por ação;e-greedy por problema;softmax

e-greedy por problema e-greedy por ação

taxa de exploração [e-greedy] 0.4;0.5;0.6;0.7 0.5 0.4temperatura [softmax] 1;3 - -

seleção de paisseleção proporcional;seleção por torneio seleção por torneio seleção por torneio

τ (tamanho do torneio)[seleção por torneio] 0.2;0.4;0.6;0.8;1.0 0.4 0.8

método de atualização por reforço padrão;gradient descent padrão padrão

γ (fator de desconto)0.2;0.3;0.4;0.5;0.6;0.7;0.8;0.85;0.9;0.95;1 0.9 0.95

tipo de β (taxa de aprendizagem) fixo;decrescente fixo decrescente

β f ixo [β fixo]0.1;0.2;0.3;0.4;0.5;0.6;0.7;0.8;0.9 0.5 -

βdec (quociente de β )[β decrescente] 1;3 - 3

α (taxa de queda na aptidão)0.01;0.1;0.2;0.3;0.4;0.5;0.6;0.7;0.8;0.9;1 0.1 0.1

ε0rel (limite de tolerânciade erro relativo à recompensa máxima)

0.01;0.1;0.2;0.3;0.4;0.5;0.6;0.7;0.8;0.9 0.01 0.01

ν (expoente de queda na aptidão) 1;3;5;7;9 5 1atualização com reforço antecipado sim;não não simatualização de erro antes da predição sim;não sim nãofim de problema em reforçodiferente de zero sim;não sim não

θAG (tempo médio mínimo paraativação de algoritmo genético)

10;20;30;40;50;60;70;80;90;100;110 25 80

χ (probabilidade de aplicaçãode cruzamento)

0.5;0.55;0.6;0.65;0.7;0.75;0.8;0.85;0.9;0.95;1 1 0.55

µ (probabilidade de mutaçãopor símbolo)

0.01;0.059;0.108;0.157;0.206;0.255;0.304;0.353;0.402;0.451;0.5

0.1 0.059

tipo de cruzamentoum ponto;dois pontos;uniforme uniforme um ponto

tipo de mutação guiada;livre livre livreredução de aptidão em novas regras 0.01;0.1;0.2;0.3;0.4;0.5 0.1 0.3θMNA (número mínimode ações possíveis para o estado) 1;5;9;13 13 5

P# (probabilidade de generalizaçãopor símbolo em covering)

0.01;0.1;0.2;0.3;0.4;0.5;0.6;0.7;0.8;0.9 0.8 0.2

θdel (limiar de experiênciapara fator de eliminação) 10;20;30;40;50 20 40

δ (limiar de aptidão médiapopulacional para fator de eliminação)

0.01;0.1;0.2;0.3;0.4;0.5;0.6;0.7;0.8;0.9 0.1 0.6

subsunção em algoritmo genético sim;não sim simsubsunção em conjunto de ação [A] sim;não não nãoθsub (limiar de experiênciapara subsunção) 5;15;25;35;45 20 35

Tabela 4.2: Parâmetros do Agente XCSPlayer

575757

5Configuração Automática de Parâmetros doAgente Proposto

No capítulo anterior, foi apresentada em mais detalhes o desenvolvimento da soluçãoproposta por este trabalho, e a dificuldade de parametrização do agente construído. Neste capítulo,relatamos a etapa de parametrização automática. Descrevemos a técnica utilizada, desde seufuncionamento até sua utilização. Comentamos as decisões tomadas quanto à amostragemde configurações candidatas e à definição da avaliação considerada pela técnica. Tambémexplicamos o procedimento pelo qual as configurações são refinadas, e até quando o processoocorre. É realizada o balanço do processo de parametrização. Em seguida, expomos problemastécnicos encontrados para a execução e qual a solução encontrada. Finalmente, a melhorconfiguração encontrada é avaliada em um experimento preliminar.

A exploração de configurações de parâmetros para o agente XCSPlayer mostrou-se inviá-vel de ser realizada manualmente. Buscamos uma forma de executá-la de maneira automática eque fosse adequada à quantidade de parâmetros. Além disso, dado o custo de execução de umapartida de luta para a avaliação do agente proposto, era desejável que a solução fosse econômicana busca das configurações. Existe um algoritmo adequado para essas características. Ele é umprocesso automatizado, que permite a exploração simultânea do espaço de configurações, e, porser um algoritmo de corrida, as configurações vão sendo descartadas com o tempo, evitandoavaliar configurações estatisticamente piores que outras. Esta técnica é chamada F-Race.

5.1 F-Race

O algoritmo F-Race é um procedimento offline de otimização automática de parâmetrosde meta-heurísticas. Seu funcionamento pode ser descrito como um algoritmo de corrida comdesign de blocos (MARON; MOORE, 1993, 1997; BOX; HUNTER; HUNTER, 2005), no qualum dado conjunto de configurações candidatas Θ é avaliado iterativamente por instâncias deproblema I. Ao longo do tempo, as configurações consideradas piores são descartadas, assimque haja evidências suficientes. O procedimento acontece enquanto não se alcançar o critério de

5.1. F-RACE 58

condição desejado.

5.1.1 Funcionamento da Técnica

5.1.1.1 Avaliação

O algoritmo de corrida tem por base um conjunto de configurações candidatas Θ. Essasconfigurações são avaliadas passo a passo na corrida.

Em cada passo l, cada candidata θ é avaliada sob as mesmas condições por uma instânciail do conjunto de instâncias I, sorteada aleatoriamente de acordo com a distribuição PI . Aavaliação de uma configuração candidata θ j dada uma instância il resulta em um rank Rl j, queaponta o desempenho daquela candidata em relação às demais no passo l, baseada na medida decusto ou valor da função objetivo considerada. À medida que o número de passos aumenta, asconfigurações candidatas sobreviventes mantêm uma soma de seus ranks R j.

5.1.1.2 Testes de Hipótese

Ao final de cada passo, é aplicado um teste de hipótese não-paramétrico para determinara eliminação de configurações candidatas. O teste de hipótese utilizado é o teste de Friedman,de análise de variância por ranks. Ele assume a estrutura descrita acima de avaliações das m

configurações candidatas nos k blocos independentes por ranks.As hipóteses consideradas pelo teste são:

Hipótese nula (H0): cada rank de configuração candidata em um bloco é igualmente provável.

Hipótese alternativa (H1): existe ao menos uma configuração candidata que tende a ser melhor

avaliada que pelo menos uma outra.

Duas estatísticas para o teste são apresentadas por CONOVER (1999):

T1 =(m−1)∑

mj=1(R j− k(m+1)

2 )2

∑kl=1 ∑

mj=1 R2

l j−km(m+1)2

4

� �5.1

T2 =(k−1)T1

k(m−1)−T1

� �5.2

A estatística utilizada T2 tem aproximação mais precisa que T(1), segundo o autor. Se ahipótese nula é verdadeira, a estatística T2 pode ser aproximada pela distribuição F com (m−1)e (k−1)(m−1) graus de liberdade, supondo que a hipótese nula é verdadeira. A hipótese nula érejeitada com um nível de significância α se a estatística T2 for maior que o quantil de ordem1−α dessa distribuição.

Não sendo rejeitada a hipótese nula, todas as configurações candidatas avançam parao próximo passo. Caso contrário, confirmando-se a rejeição da hipótese nula, é realizado

5.1. F-RACE 59

um segundo teste, post-hoc, no qual são realizadas comparações múltiplas entre pares deconfigurações candidatas. As configurações candidatas θ j e θh são consideradas diferentes se

R j−Rh√2k(1− T

k(m−1) )(∑kl=1 ∑

mj=1 R2

l j−km(m+1)2

4 )

(k−1)(m−1)

> t1−α/2

� �5.3

onde t1−α/2 é o quantil de ordem 1−α/2 da distribuição t de Student com (k−1)(m−1) grausde liberdade.

Todas as configurações candidatas que sejam consideradas diferentes da candidata quepossui menor soma de ranks pelo teste post-hoc são eliminadas. As candidatas sobreviventesavançam para o próximo passo.

Ao restarem duas configurações candidatas na corrida, utiliza-se teste de Wilcoxonpareado ao invés do teste de Friedman, segundo o algoritmo original (BIRATTARI et al., 2010).A versão considerada do teste de Wilcoxon pareado é descrita por CONOVER (1999).

5.1.1.3 Condição de Parada

A corrida prossegue enquanto a condição de parada não for atingida. São possíveiscondições de parada: número mínimo de sobreviventes, número de passos convergidos e númeromáximo de avaliações realizadas.

5.1.2 Aplicação do F-Race na Corrida

Primeiramente, determinamos o conjunto de configurações candidatas Θ à corrida.Definimos intervalos que consideramos mais adequados para a busca em alguns parâmetros,assim como a resolução na discretização de valores contínuos, conforme demonstra a segundacoluna da Tabela 4.2.

Com os níveis dos parâmetros definidos, o passo seguinte é a definição do método deamostragem. O grande número de configurações possíveis para o agente proposto exige umaamostragem cuidadosa, especialmente pelo custo computacional exigido pelas avaliações. Aopção por um delineamento fatorial completo mostra-se inviável, ao considerar todo o conjuntode combinações de parâmetros existentes. O delineamento de experimento puramente aleatório,por sua vez, não apresenta qualquer garantia quanto à representatividade do espaço de busca emquestão, ainda mais na proporção observada em nosso caso.

Buscamos então uma amostra quase uniforme de pontos, que melhor representasse oespaço de configurações, observando a variabilidade dos parâmetros, tanto no número de níveisquanto no tipo. Aproximamos essa meta realizando uma amostragem quase balanceada e quaseortogonal. O fato de ser quase balanceada significa que o número de ocorrência de pontos pornível em cada parâmetro é aproximadamente igual, enquanto que por ser quase ortogonal, o graude correlação máximo entre os pontos de quaisquer dois parâmetros é mínimo (VIEIRA et al.,

5.1. F-RACE 60

2011). Isso confere uma distribuição de pontos mais equilibrada no espaço de configuraçõesdelimitado. A amostragem resultou em 512 configurações candidatas.

As configurações candidatas foram avaliadas em uma sequência de partidas contrao agente SMPlayer descrito na Seção 4.4. Cada avaliação é antecedida por 30 partidas detreinamento de 30 segundos cada, com população de regras vazia inicialmente, e 5 partidasde teste de mesma duração, com aprendizagem ativada durante todas elas. O desempenho doagente é representado pela média do placar final das lutas de teste, nas quais atuou no seu melhordesempenho.

Consideramos como instância de problema execuções de luta contra a máquina de estado,cuja variabilidade se daria pela sequência gerada de números pseudoaleatórios a partir de umasemente fornecida a cada bloco. Então, o espaço de sementes compõe o conjunto de instâncias I.O gerador de números aleatórios utilizado pelos agentes nesse trabalho é a versão SFMT doMersenneTwister (SAITO; MATSUMOTO, 2008) implementado em C++ por FOG (2014).

Em relação aos testes de hipótese, definimos o nível de significância em α = 5%, paratodos os testes. O teste de Wilcoxon pareado, o teste F de Fisher e o teste t de Studentforam importados da biblioteca ALGLIB (BOCHKANOV; BYSTRITSKY, 2014), enquanto quecodificamos o teste de Friedman junto ao F-Race.

Estabelecemos arbitrariamente como condição de parada o número máximo de 12 milavaliações individuais, suficientes para 20 avaliações completas de Θ, ou o número máximo de10 passos sem mudança de liderança, i.e. sem nova melhor configuração candidata. Além disso,definimos que durante os primeiros 15 passos não haveria aplicação do teste de hipótese, a fimde reunir evidência suficiente para realizar as eliminações.

5.1.3 Análise da Corrida

Ao longo de 117 passos (ou rodadas), foram realizadas ao todo 11024 avaliações deconfigurações candidatas, cada uma com 35 partidas entre lutadores. A região acinzentada nográfico da Figura 5.1 apresenta a evolução do número de configurações sobreviventes ao longo dacorrida, e sua área corresponde ao esforço computacional total exigido em número de avaliações.A região hachurada, por sua vez, representa a alocação do mesmo esforço computacional emuma busca por força bruta, na qual seriam distribuídas avaliações uniformemente entre as 512configurações candidatas iniciais, sem eliminação. A comparação entre as regiões revela aprincipal característica do F-Race: uma alocação de recursos computacionais mais eficiente paraa exploração de configurações candidatas estatisticamente melhores (BIRATTARI et al., 2010).Com aproximadamente a mesma quantidade de avaliações, é possível observar que a busca porforça bruta resulta em um conjunto de configurações candidatas maior (aproximadamente 100configurações), desperdiçando recursos computacionais em candidatas estatisticamente piores,ao contrário da melhor configuração candidata encontrada pelo F-Race.

Um dos intervalos mais evidentes no gráfico é o dos 15 primeiros passos, que avaliam todo

5.1. F-RACE 61

Figura 5.1: Número de configurações candidatas sobreviventes ao longo da corrida.

conjunto inicial de configurações, custando quase 70% dos recursos computacionais empregadosna corrida. Esses primeiros passos com a avaliação de todo o conjunto inicial de configuraçõescandidatas servem para coletar evidências suficientemente fortes para a utilização adequadado teste de hipótese. Essa etapa inicial resulta no alto número de eliminações efetuadas nos5 passos seguintes, diminuindo o ritmo a partir de então, até alcançar o passo 83. Esse passoinicia a corrida entre apenas duas configurações candidatas, que de início se alternam entreos ranks, estendendo a corrida por mais de 30 passos. Antes disso, no passo 92, o critério deparada de convergência é disparado. Entretanto, ele foi ignorado, uma vez que restavam apenas 2configurações candidatas, o custo computacional já estava muito menor que o existente no inícioda corrida, e os valores P apresentavam uma tendência decrescente. O critério que se efetivou,portanto, foi a obtenção de apenas uma configuração candidata sobrevivente ao fim do passo117, cujos parâmetros estão listados na quarta coluna da Tabela 4.2.

No gráfico da Figura 5.2, são apresentados os resultados acumulados das avaliaçõesfeitas pelas configurações candidatas. As regiões sombreadas delimitam o espaço observadoda distribuição desses resultados acumulados, representando os 25% piores na parte inferiormais clara, os 50% centrais à distribuição na região mais escura, e os 25% melhores na regiãodestacada acima dessas. Os limites externos das regiões são calculados do mesmo modo que os"fios de bigode"(whiskers) de um gráfico boxplot (TUKEY, 1977).

Relacionando os dados dos dois gráficos, é possível identificar momentos opcionais detérmino. Os 20º e 33º passos são interessantes do ponto de vista que, logo após a desaceleraçãoinicial das eliminações, possuem conjunto de configurações candidatas razoavelmente menor,

5.1. F-RACE 62

Figura 5.2: A evolução do desempenho acumulado das configurações candidatas aolongo da corrida. Em destaque, a média tracejada em vermelho, a mediana contínua preta,regiões definidas pelos quartis em cinza claro, "fios de bigode"em cinza escuro, a região

pontilhada indicando a existência de apenas duas configurações candidatas.

com resultados menos dispersos. Restam em cada passo 20% e 9% das configurações iniciais,respectivamente, ambas com dispersão 80% menor que o desvio-padrão calculado para o pri-meiro passo. Essas características podem resultar em um conjunto de configurações candidatassuficientemente satisfatórias, de acordo com o problema a que se aplica o F-Race.

Outro ponto é a partir do 83º passo, quando começa a disputa entre as duas melhoresconfigurações candidatas, indicada pela área hachurada na Figura 5.2. Com alguma análise dosresultados obtidos por ambas as configurações finais até então, pode-se decidir qual delas atendemelhor ao problema que se busca tratar.

Por fim, pudemos comparar alguns valores de parâmetros da configuração vencedoracom a configuração realizada manualmente. Sabemos que a análise é limitada pela correlaçãoentre os parâmetros e pela ocasião das combinações formadas durante a amostragem. Apontamospossíveis aspectos que podem ter influenciado o bom desempenho da configuração final:

� A combinação de uma política e-greedy por ação com uma predição inicial maisalta remete ao caso de otimismo de valores iniciais (BARTO, 1998), onde estima-tivas maiores induzem à exploração de novas regras inicialmente, com benefíciosposteriores no desempenho.

� A taxa de aprendizagem decrescente pode complementar a situação anterior, ondeo foco inicial é a exploração de novas regras, e que ao longo do tempo vai sendo

5.1. F-RACE 63

direcionado para a busca pelo melhor desempenho.

� A seleção por torneio na configuração vencedora apresenta o dobro do tamanhoencontrado pela configuração realizada manualmente, o que pode nos indicar maiorpressão por candidatos mais aptos.

� A atualização com reforço antecipado mostrou adoção pela configuração vencedora,compatível em parte com a escolha pouco conservadora da ordem de atualização,na qual, sendo a predição atualizada antes que o erro de uma regra, a regra tende aaprender mais rápido problemas simples (BUTZ; WILSON, 2001).

� Menores taxas de ativação do algoritmo genético, de ativação do cruzamento e demutação por alelo parecem favorecer o usufruto das regras conhecidas.

5.1.4 Dificuldades de Implementação

A fim de otimizar o tempo de simulação no F-Race, buscamos realizar simulaçõessimultâneas e desativar a reprodução gráfica do simulador, que tende a ter mais tempo reservadoque outras partes do sistema por quadro no jogo. Entretanto, constatamos que parte da lógicaenvolvida no controle da tela está encapsulada em uma biblioteca binária, a cujo código nãotemos acesso.

A alternativa encontrada foi projetar o sistema de simulação do F-Race em uma arquite-tura cliente-servidor, de forma a paralelizar a execução da corrida. Enquanto múltiplos clientesprocessavam requisições de avaliação de configurações candidatas, o servidor foi responsávelpor todas as demais atividades. Algumas das atividades do servidor são: preparar instâncias,gerenciar a situação das configurações candidatas, realizar requisições avaliação para os clientes,processar os resultados dessas avaliações, gerar ranks, executar testes de hipótese, e monitorar acondição de término da corrida. Além disso, devido às restrições de disponibilidade da infra-estrutura, a arquitetura precisou ser construída de forma a alocar avaliações dinamicamente, comclientes sendo adicionados e removidos durante a corrida, e a tratar situações técnicas de erro nocliente ou de conexão. Para isso, o servidor precisou manter salvo com frequência o estado dacorrida, para carregá-lo quando preciso.

O tempo total para a realização da corrida em uma só máquina é estimado em 3215 horas,quase 134 dias ininterruptos. Porém, devido à paralelização obtida pela arquitetura desenvolvida,a corrida custou 246 horas, ou pouco mais de 10 dias consecutivos. Foram utilizadas de 5a 40 computadores de mesa básicos, simultaneamente, de acordo com a disponibilidade dealocação. Levando em conta os horários de disponibilidade das máquinas, correção de bugs ea necessidade de refazer alguns passos em certos momentos, a etapa de parametrização com oF-Race prolongou-se na prática por um mês.

5.1. F-RACE 64

5.1.5 Experimento Preliminar

Realizamos um experimento de verificação logo após a corrida com a configuraçãovencedora. A fim de diferenciar as versões do algoritmo proposto, denominamos o agenteque a implementa de XCSPlayer v.2. Dessa vez, o experimento além de checar inicialmentea capacidade do agente em adquirir competência, serve indiretamente como investigação doimpacto causado pela utilização da técnica F-Race.

Este experimento seguiu o mesmo delineamento daquele apresentado na Seção 4.5.1. Elesegue a mesma estrutura e quantidade de séries, ciclos e partidas de treinamento e teste. Tambémacontecem com a mesma inicialização de conhecimento dos agentes, condição de aprendizagemdurante as lutas, e imposição ao agente proposto de atuar no melhor nível ao longo das partidasde teste.

Os gráficos das Figuras 5.3 e 5.4 mostram a comparação do agente proposto parame-trizado automaticamente com o agente de referência. Também é realizada a comparação dedesempenho entre as versões do agente proposto, nas Figuras 5.5 e 5.6.


RLTPlayer

Na Figura 5.3, é possível avaliar o agente XCSPlayer v.2 em três períodos. Primeiro,o agente proposto possui um desempenho inferior ao agente rival RLTPlayer, mas tende adiminuir a diferença ao aumentar o desempenho médio, aproximando aos poucos do nível doconcorrente. Depois, o agente proposto apresenta uma queda expressiva de desempenho, quaseque duplicando a diferença com o agente rival. Em um terceiro momento, o agente XCSPlayer

v.2 volta a aumentar seu desempenho, ao passo que o agente rival mantém aproximadamente o

5.1. F-RACE 65

desempenho médio. O comportamento do agente proposto como apresentado nesses períodosindica tendência de aprendizagem, ainda que não tão rápida a do rival, em um ambiente ruidosocomo este. Acreditamos que com mais tempo, o agente proposto poderia alcançar o nível deatuação do agente RLTPlayer.


RLTPlayer

Contra o agente previsível, a situação inverteu-se. O agente XCSPlayer v.2 obteve ótimodesempenho, chegando a convergir. Esse resultado evidencia o fato de ele ter aprendido aidentificar as falhas de comportamento do agente previsível. O agente soube explorar o fato doagente SMPlayer não se aproximar enquanto seu oponente pula, para intercalar momentos deataque (quando o agente proposto estava em vantagem) com momentos de pulo (quando o agenteprevisível estava em vantagem).

Ao comparar o desempenho da primeira versão com a segunda versão contra o agenteimprevisível, na Figura 5.5, não há diferença óbvia de desempenho. Porém, a variação de desem-penho mostrou-se menor em partidas consecutivas, indicando um grau maior de estabilidade.Além disso, é possível identificar mais claramente tendências de evolução e regressão na curva,possibilitando a interpretação de um agente que explora estratégias (mais gerais), e não apenastáticas (mais específicas). Ciclos adicionais para este experimento seriam necessários paraconfirmar ou não esta hipótese.

O desempenho do agente XCSPlayer v.2 mostrou-se claramente superior na Figura 5.6.O agente proposto parametrizado manualmente não conseguiu apresentar uma política de açãoconsistente contra o agente previsível, ao contrário daquele parametrizado automaticamente.Essa diferença é o resultado mais expressivo do impacto causado pela utilização da técnica

5.2. CONCLUSÃO 66


XCSPlayer v.2

F-Race.A ideia geral que assimilamos deste experimento é a de que a configuração encontrada

nesta etapa de parametrização é melhor contra comportamento previsível, e no mínimo tão boae menos instável contra comportamento imprevisível, comparada à configuração encontradamanualmente. A partir de então, aprofundamos a investigação sobre o potencial do agenteproposto com a realização de mais experimentos, descritos no próximo capítulo.

5.2 Conclusão

Neste capítulo, discutimos a etapa de parametrização automática, com a explicação datécnica utilizada, F-Race. Explicamos o funcionamento da técnica, com os conceitos gerais, asinformações relativas à avaliação, os testes de hipóteses utilizados e exemplos de condição deparada.

Em seguida, comentamos sobre a configuração e utilização da técnica. Explicamos omodo como foi realizada a amostragem de configurações candidatas, a especificação de avaliação,e detalhes dos testes de hipóteses utilizados. Analisamos tanto os resultados de operação dacorrida, quanto a configuração resultante, que serviu para a construção de uma segunda versãodo agente proposto. Abordamos ainda a dificuldade relativa ao custo computacional envolvidopara a execução da corrida no contexto da aplicação, agravado por detalhes técnicos, resultandona criação de uma plataforma de corrida distribuída. Com o novo agente, realizamos umexperimento aos moldes daquele visto na Seção 4.5.1, possibilitando vislumbrar o resultado

5.2. CONCLUSÃO 67


XCSPlayer v.2

desta etapa.O próximo capítulo concentra experimentos mais específicos, investigando a escolha de

agentes treinadores, a elaboração de problemas mais longos e um teste de balanceamento. Combase nesses experimentos, é possível avaliar ainda mais o potencial de sistemas classificadores eo impacto da parametrização automática utilizada.

686868

6Experimentos entre Agentes

Esse capítulo trata dos experimentos entre as duas versões parametrizadas do agenteproposto com os demais agentes comentados da Seção 4.4. A primeira seção define os detalhesde metodologia comuns a todos os experimentos. A segunda discute a busca pelo agente treinadorque melhor prepara o agente proposto. A terceira seção desenvolve melhor o experimento deavaliação de competência das versões do agente. Por fim, busca-se demonstrar a integração deuma abordagem baseada em balanceamento dinâmico ao agente proposto.

6.1 Metodologia Geral

Os experimentos deste capítulo possuem três objetivos. O primeiro consiste em descobriro melhor agente professor para treinar o agente XCSPlayer v.2 no modo offline, e fazê-lo adquiriruma base mínima de regras de utilidade para o experimento seguinte. O segundo objetivo é o deexplorar a capacidade de competência e comparar os desempenhos das duas versões do agenteXCSPlayer, em relação ao agente RLTPlayer, utilizando os agentes RDPlayer e SMPlayer paraavaliá-los. O último objetivo consiste em verificar a integração do agente proposto ao sistema debalanceamento proposto por ANDRADE et al. (2005).

Todos os experimentos deste capítulo são realizados como sequências de partidas de lutaentre agentes. Por sua vez, cada partida é composta por ciclos de processamento, nos quais ospersonagens podem tomar uma decisão, divididos entre ciclos de exploração e de usufruto. Nosciclos exploratórios, ocorre a principal etapa na aprendizagem do agente: a criação e o teste dehipóteses sobre o ambiente, permitindo assim formular novas estratégias. Nos ciclos de usufruto,o agente busca executar as ações mais recompensadoras dentro da experiência que acumulou.

Partidas nas quais os agentes que aprendem são livres para realizar ciclos de exploraçãoou usufruto, conforme a política de ação que implementam, são definidas como partidas detreinamento. Partidas de teste são compostas apenas por ciclos de usufruto, para avaliação doagente. Ainda que os agentes não explorem novas regras durante as partidas de teste (como algoritmo genético desativado no agente XCSPlayer), a parte da aprendizagem relativa àatualização de valores é mantida ativada nos agentes aprendizes, em modo online. No caso

6.2. TREINAMENTO OFFLINE 69

de sistemas classificadores, essa medida é necessária para evitar a estagnação do agente emsequências repetitivas de ações (WILSON, 1995).

Quando o treinamento ocorre separado do teste, em modo offline, a intenção é a de queo agente possa adquirir competência inicial mínima, a fim de prepará-lo contra o adversário.Nesse tipo de treinamento, o adversário do agente utilizado nas partidas de treinamento não énecessariamente o mesmo adversário utilizado nas partidas de teste. Por outro lado, boa partedos experimentos deste capítulo possui avaliação intercalada ao processo de treinamento. Arealização dessa abordagem visa avaliar a evolução da aprendizagem do agente com os testesperiódicos. Nos experimentos deste capítulo realizados dessa forma, considerou-se os mesmosadversários em partidas de treinamento e de teste, salvo indicação explícita contrária.

Cada partida nos experimentos possui o limite máximo de tempo de 60 segundos, comcondições de atributos e características dos lutadores iguais para ambos os agentes. Ambos osagentes seguem a mesma interface definida na Seção 4.3 e possuem acesso à mesma consultade permissão sobre ação ao sistema do jogo. Nos experimentos que não possuam treinamentooffline explícito, deve ser considerado que os agentes aprendizes são iniciados sem conhecimentoinicial.

Os agentes possuem todos os parâmetros definidos nessa fase conforme mostram aTabela 4.1 e a Tabela 4.2. A única variável independente das lutas são as sementes utilizadaspelos geradores de número aleatório de cada agente, que por sua vez são geradas pelo Mersenne

Twister com base no tempo de execução (SAITO; MATSUMOTO, 2008). A principal variáveldependente considerada é a pontuação das partidas, definida como a diferença de pontuaçãoentre os lutadores.

6.2 Treinamento Offline

Esta seção trata do processo de preparação do treinamento offline a ser aplicado noexperimento da próxima seção. O treinamento cumpre a função de auxiliar o agente a alcançar umnível de competência geral básico, acelerando o processo de aprendizagem inicial e permitindouma adaptação mais eficiente ao adversário. A utilidade do conhecimento aprendido duranteo treinamento é tão maior quão flexível for sua aplicação, o que compreende em uma base deconhecimento mais diversa. A diversidade do conhecimento adquirido depende principalmentedo agente utilizado como treinador, o qual propicia as situações a serem exploradas. Assim, oprincipal objetivo do experimento executado nesta seção é a busca pelo professor mais adequadoao agente proposto XCSPlayer.

6.2.1 Metodologia Específica

Para o primeiro experimento, um conjunto de agentes candidatos a professor é utilizadopara treinar um mesmo agente, o aluno, o qual é posto em seguida para lutar contra um conjunto


de agentes avaliadores. Existem duas possibilidades básicas de treinamento: uma consiste emapresentar situações aleatórias ao agente aluno, sem viés comportamental, a outra consiste emcolocar o agente aluno para aprender contra si próprio, conhecida como autoaprendizagem (self-

learning). Os candidatos a professor que implementam essas abordagens são, respectivamente,os agentes RDPlayer e XCSPlayer v.2. O aluno, agente a ser treinado, é o agente propostoXCSPlayer v.2. O conjunto de avaliadores é formado pelos agentes RDPlayer, SMPlayer eXCSPlayer v.2. Os agentes são configurados e inicializados como descrito na Seção 6.1.

Cada agente avaliador representa um tipo de comportamento. O agente RDPlayer

possui um comportamento imprevisível, pois proporciona ao oponente situações livres dequalquer viés próprio e, portanto, tende a repetir sequências de ações com menos frequência.O agente SMPlayer, construído como uma máquina de estados, representa um comportamentoprevisível, com sequências de ações mais comuns e mais limitadas. O agente XCSPlayer v.2,sendo um agente que aprende, representa um comportamento dinâmico, que varia conformea experiência que adquire, podendo executar novas sequências de ações e repeti-las quandoapropriado. Supomos que o grau de dificuldade para um agente que aprende esteja relacionadoà frequência de repetições de sequências de ações necessária à adequada aprendizagem doagente. Assim, agentes que apresentam comportamento mais previsível tendem a ter seus pontosfracos mais rapidamente explorados, enquanto aqueles que apresentam alguma mudança decomportamento exigem uma adaptação mais rápida do oponente que aprende, resultando assimem uma dificuldade maior em sua aprendizagem.

Cada combinação de par professor-avaliador é colocada para treinar e testar o agentealuno em 4 séries diferentes de 100 ciclos, cada ciclo com uma partida de treinamento e umapartida de avaliação. A avaliação intercalada ao treinamento permite capturar uma estimativa daqualidade do mesmo ao longo de sua execução.

A aprendizagem do aluno procede durante as partidas de treinamento e teste. Enquantoem uma partida de treinamento o agente atualiza e descobre regras sem restrições, a aprendizagemdurante uma partida de teste difere apenas por não ativar o algoritmo genético. Essa condiçãobusca estabilizar mais o algoritmo durante a fase de desempenho (WILSON, 1995).

6.2.2 Resultados do Experimento

O gráfico da Figura 6.1 mostra a média das avaliações das séries para cada par professor-avaliador. Os três grupos de barras mais à esquerda apresentam, cada um, as médias por avaliador.O agente imprevisível RDPlayer, no primeiro grupo, mostrou-se o mais difícil de enfrentar,derrotando o aluno treinado por ambos os professores. Na extremidade oposta de dificuldade,o agente previsível SMPlayer, no segundo grupo, perdeu por grande diferença para o alunotreinado pelos dois professores. Por último, o agente avaliador proposto, do terceiro grupo,manteve-se aproximadamente no nível do aluno treinado tanto pelo professor RDPlayer (compequena desvantagem sobre ele) quanto pela autoaprendizagem (com pequena vantagem).


Figura 6.1: Desempenho médio dos treinamentos realizados pelos professores contra ostrês avaliadores.

O gráfico confirma a hipótese de que a dificuldade de aprendizagem está associada àimprevisibilidade do oponente. No geral, o professor RDPlayer rendeu ao aluno desempenhosum pouco inferiores contra os dois primeiros agentes, comparado ao outro professor, superandocom pouca diferença o desempenho contra o avaliador XCSPlayer v.2. As médias gerais para aqualidade de treinamento dos professores não apresentaram diferença expressiva, o que nos fezadotar um critério adicional para a seleção do melhor.

Nas séries de avaliações entre o avaliador XCSPlayer v.2 e o agente treinado por autoa-prendizagem, observamos a ocorrência de partidas nas quais os agentes mantiveram-se estáticos,contribuindo com empates artificiais para a média das avaliações. Do ponto de vista de aprovei-tamento das oportunidades, o professor XCSPlayer v.2 deixou de tomar comportamentos queestimulassem a aprendizagem diversificada do aluno, mantendo-se estagnado por períodos. Otreinamento com o professor imprevisível, por outro lado, evita tendência de comportamento noprofessor, que possa prejudicar a experiência do aluno. Assim, considerando essa característica ea pouca diferença de pontuação na média geral, optamos pelo professor RDPlayer.

Existem outros agentes professores possíveis, como por exemplo agentes que adotem umcomportamento ora aleatório, ora composto por sequência estruturada de ações; como tambémformas diferentes de montar o experimento para definir qual professor escolher, como poderiaacontecer em um torneio, ou mesmo se utilizar novamente do algoritmo F-Race para tal tarefa.Acreditamos que as escolhas aqui realizadas são suficientes, dentro da proposta de gerar umconhecimento residual mínimo para os agentes do próximo experimento. Assumimos que aconclusão possa ser extrapolada de forma que o mesmo professor seja utilizado para a primeiraversão do agente proposto XCSPlayer v.1 e para o agente de referência RLTPlayer.

6.3. AVALIAÇÃO DE COMPETÊNCIA ADQUIRIDA 72

6.3 Avaliação de Competência Adquirida

Nas Seções 4.5.1 e 5.1.5, realizamos os primeiros experimentos para avaliação dacompetência do agente proposto. Os resultados preliminares revelaram a capacidade do agenteproposto enfrentar bem um adversário previsível. Porém, não foi possível chegar à conclusãosegura sobre o potencial do agente proposto contra o agente de comportamento aleatório. AFigura 5.5 apontou o comportamento mais instável dos agentes XCSPlayer v.1 e XCSPlayer v.2,bem como o desempenho pouco expressivo. Porém, o gráfico na figura revelou uma possibilidadede comportamento de exploração por parte do segundo agente, levantando a questão do tempode aprendizagem exigido para convergência. Fatores como o grau de ruído do ambiente e apossível necessidade de formar longas cadeias de ação frente a dificuldade do algoritmo emaprendê-las (problema comentado na Seção 4.5) podem ter impactado no desempenho dosagentes. Esta seção tem por objetivo avaliar a competência do agente proposto em experimentomais prolongado, de modo a extrair informações que possam esclarecer mais sobre o processode aprendizagem do agente XCSPlayer, principalmente em situações como as oferecidas peloagente RDPlayer.


São consideradas para o grupo de avaliação as duas versões do agente proposto XCS-Player v.1 e XCSPlayer v.2, além do agente de referência RLTPlayer. Os agentes utilizados comoadversários são novamente o agente RDPlayer e o agente SMPlayer. O experimento consiste narealização de cinco séries de 1100 ciclos de partidas de luta para cada combinação de agenteavaliado e adversário. Cada ciclo é composto por uma partida de treinamento e uma partidade avaliação, ambas com os mesmos agentes. As partidas e os agentes são configurados comoexplica a Seção 6.1. Tanto os agentes propostos quanto o agente de referência são restritos ajogar em seu melhor nível durante as partidas de teste, reservando a exploração apenas às detreinamento.

A fim de acelerar a fase inicial de aprendizagem, foi realizado o treinamento com oagente professor definido na Seção 6.2. O treinamento permite a avaliação de competência emfases mais tardias de aprendizagem, buscando assim explorar mais o problema de convergência.Cada agente avaliado, inicialmente sem conhecimento, enfrenta o agente professor RDPlayer

durante 100 ciclos, compostos por uma partida de treinamento e uma partida de teste, em modode alternância similar ao de exploração e usufruto utilizado por WILSON (1995).

Para facilitar o acompanhamento da evolução dos agentes, as Figuras 6.2 e 6.3 apresentamas médias das 4 séries calculadas em intervalos de 50 partidas. Além da constatação visual, sãorealizados testes de hipóteses para cada par de agente avaliado quanto à diferença de desempenhomédio geral e em três intervalos: o primeiro, logo após o treinamento online; o 10º intervalo,em estágio mais avançado; e as últimas 50 partidas. O teste de hipótese utilizado é o teste de


Wilcoxon para amostras independentes, com nível de significância α = 5%. A hipótese nula H0

é a de que os dois agentes avaliados apresentam diferença de desempenho nula, i.e. possuemmesmo desempenho. A hipótese alternativa H1 afirma que um dos agentes comparados apresentadesempenho maior que o outro. O teste de hipótese calcula o valor-p, de modo que se p < 0,05(valor relativo ao nível de significância), então há evidência estatística para se rejeitar a hipótesenula e considerar a hipótese alternativa. Caso contrário, não há evidência forte que rejeite ahipótese nula.

Adicionalmente, testamos uma série de 360 ciclos de 1 partida de treino e 1 partida deteste entre o agente XCSPlayer v.2 e o agente RLTPlayer, a fim de observar o comportamento deambos. Os agentes são configurados e inicializados do mesmo modo que para as outras séries doexperimento.

6.3.2 Resultados do Experimento

Figura 6.2: 1100 ciclos de 1 partida de treino e 1 partida de teste contra RDPlayer

A Figura 6.2 mostra o desempenho dos agentes avaliados contra o agente de comporta-mento imprevisível. Nela, a primeira versão do agente proposto apresentou ligeira melhora dedesempenho em poucos intervalos, mantendo-se próxima à sua média geral, em relação ao testepreliminar realizado na Seção 4.5.1. Como visto antes, o agente XCSPlayer v.1 apresentou omenor nível de dispersão das médias das séries por intervalo.

Intervalo 1 10 22

RLTPlayer 27,67 18,77 20,58

XCSPlayer v.1 38,11 38,22 42,46

XCSPlayer v.2 16,37 -4,68 0,46Tabela 6.1: Médias dos agentes avaliados contra RDPlayer - dados da Figura 6.2


Intervalo 1 10 22

RLTPlayer 5,14 22,38 5,31

XCSPlayer v.1 4,52 5,54 4,74

XCSPlayer v.2 16,08 16,53 18,63Tabela 6.2: Desvio padrão dos agentes avaliados contra RDPlayer - dados da Figura 6.2

O agente XCSPlayer v.2 revelou considerável queda em seu desempenho, sendo o únicodos avaliados a apresentar média geral negativa. Além disso, ele apresentou a maior das variaçõesnas médias dos intervalos. Assim, torna-se evidente a diferença entre os agentes propostos,questionada na Seção 5.1.5, resultado das parametrizações.

Intervalo 1 10 22

RLTPlayer - XCSPlayer v.1 0,0159 0,2222 0,0079

XCSPlayer v.1 - XCSPlayer v.2 0,0317 0,0079 0,0079

RLTPlayer - XCSPlayer v.2 0,4206 0,2222 0,0556Tabela 6.3: Valores-p do teste de Wilcoxon para amostras independentes em lutas contra

RDPlayer - dados da Figura 6.2

Por sua vez, é possível observar que o agente de referência RLTPlayer não manteve onível de competitividade visto na Seção 4.5.1, perdendo em desempenho médio para a primeiraversão do agente proposto, e contendo razoável dispersão nos intervalos. A explicação maisprovável para essa diferença se deve à ausência de exploração durante as partidas de teste, umavez que é obrigado a escolher a melhor estratégia nelas. Desse modo, é possível inferir que,dentro das condições do experimento, o agente de referência possui maior dependência porexploração constante, ao lidar com situações de treinamento e teste diferentes, comparado aoagente XCSPlayer v.1.

Figura 6.3: 1100 ciclos de 1 partida de treino e 1 partida de teste contra SMPlayer


Já a Figura 6.3 expõe a evolução das médias por intervalo dos agentes avaliados contrao agente previsível. O desempenho do agente RLTPlayer mostrou-se comparável ao nívelapresentado durante os testes preliminares, com algumas variações maiores de médias em algunsintervalos. Isso reflete a menor dependência do agente por exploração, uma vez que as situaçõesem fase de treino e de teste tendem ser semelhantes.

Intervalo 1 10 22

RLTPlayer 70,42 62,72 62,80

XCSPlayer v.1 56,46 63,66 61,40

XCSPlayer v.2 91,39 93,58 97,38Tabela 6.4: Médias dos agentes avaliados contra SMPlayer - dados da Figura 6.3

Intervalo 1 10 22

RLTPlayer 4,09 11,93 2,23

XCSPlayer v.1 4,45 5,69 6,94

XCSPlayer v.2 4,86 3,28 3,34Tabela 6.5: Desvio padrão dos agentes avaliados contra SMPlayer - dados da Figura 6.3

Contra o agente previsível, o agente XCSPlayer v.1 demonstrou sua maior diferença dedesempenho entre o experimento realizado, quase que duplicando a média geral do experimentopreliminar, comparável ao desempenho do agente de referência. Possíveis causas para esseresultado são o treinamento offline com o professor de comportamento aleatório, combinadocom a aprendizagem online que ocorre com o agente previsível usado para avaliação. O agenteapresentou também uma variação menor, com exceção de alguns intervalos, comparado aoexperimento comentado na Seção 4.5.1.

Intervalo 1 10 22

RLTPlayer - XCSPlayer v.1 0,0079 1,0000 0,6905

XCSPlayer v.1 - XCSPlayer v.2 0,0079 0,0079 0,0079

RLTPlayer - XCSPlayer v.2 0,0079 0,0079 0,0079Tabela 6.6: Valores-p do teste de Wilcoxon para amostras independentes em lutas contra

SMPlayer - dados da Figura 6.3

O agente XCSPlayer v.2 atuou como esperado, seguindo o padrão demonstrado naSeção 5.1.5. A segunda versão do agente proposto manteve-se com o maior desempenho e amenor variação entre os agentes avaliados, contra o agente previsível.

A série de partidas entre o agente XCSPlayer v.2 e o agente RLTPlayer produziu resultadocurioso: das 360 partidas de avaliação, apenas 4 resultaram diferentes de zero, sendo eles -10,


-20, -10 e -10 para as partidas de número 72, 85, 88 e 124, respectivamente. Todas as partidasterminaram por limite de tempo (60 segundos), e nas partidas com pontuação nula, os personagensnão desferiram golpes, limitando-se a permanecer parados, agachados ou defendendo.

6.3.3 Análise de Resultados

Quanto ao agente parametrizado manualmente, foi possível observar a dificuldade paramelhorar o desempenho contra o agente RDPlayer. Nas condições em que este experimento foimontado, não foi possível responder a hipótese comentada na Seção 5.1.5 quanto à convergênciado algoritmo contra o agente de comportamento aleatório. O agente aumentou poucos pontos dedesempenho a um alto custo de execução.

Por outro lado, a primeira versão do agente proposto obteve grande vantagem com otreinamento offline realizado, ao enfrentar o agente de comportamento previsível. Com algunsintervalos de exceção, apresentou média de desempenho comparável ao agente RLTPlayer, comvariação menor ao longo das séries. Dados os resultados, o agente XCSPlayer v.1 mostrou-secapaz de adquirir a competência necessária para enfrentar ambos os agentes no mínimo tãosatisfatoriamente bem quanto o agente de referência, dentro das especificações deste experimento.

Comparando os resultados do agente XCSPlayer v.2 no experimento desta seção, épossível inferir que, na maneira como foi conduzida, a parametrização especializou o seucomportamento para identificar sequências de ações bem definidas, ao passo que retirou-lhe acapacidade de generalização, diante de uma estratégia pouco definida do oponente. O modo deavaliação realizado pode ter levado a esses resultados, como também o conjunto de instânciasutilizadas pode não ter sido suficientemente adequado.

Em relação ao agente RLTPlayer, o dado mais significativo observado no experimento foio impacto causado pela ausência de exploração nas partidas de teste contra o agente de compor-tamento imprevisível. Essa condição está relacionada à necessidade contínua de exploração doespaço de pares estado-ação para a garantia de convergência (WATKINS; DAYAN, 1992). Umapossível explicação para o desempenho inferior à primeira versão do agente proposto, sob mesmaregra restrição de exploração a partidas de treinamento, é a falta de mecanismos adicionais queguiem melhor a busca no espaço de soluções, como são os componentes do sistema de descobertade sistemas classificadores (LANZI, 2008).

Entretanto, esse efeito foi observado apenas contra o agente imprevisível, de situaçõesmuito instáveis, e que introduz muito ruído à aprendizagem. O agente de referência foi capazde aprender o comportamento do adversário previsível na configuração de partidas intercaladasutilizada, destacando-se do agente XCSPlayer v.1 em alguns intervalos, ainda que possuindo amaior variação de desempenho entre os três agentes avaliados.

Por fim, a situação ocorrida na série de partidas entre a segunda versão do agenteproposto e o agente de referência remete ao fato ocorrido na Seção 6.2, no qual o agente propostotreinado por autoaprendizagem e o oponente baseado no mesmo agente adotaram o mesmo

6.4. AVALIAÇÃO DE AJUSTE DINÂMICO DE DIFICULDADE 77

comportamento. Interpretamos que, no modelo de problema considerado, os agentes tendem areforçar táticas mais passivas, deixando a iniciativa ao oponente, quando então outros conjuntosde regras são ativados.

6.4 Avaliação de Ajuste Dinâmico de Dificuldade

Testada a capacidade de aquisição de competência do agente proposto, é possível avaliá-los quanto ao contexto de DDA. O experimento desta seção tem o objetivo de demonstrara integração do balanceamento dinâmico ao agente XCSPlayer. Testamos a abordagem debalanceamento dinâmico baseada em desafio proposto, como visto na Seção 3.3.1.


O experimento avalia as duas versões de agentes propostos, XCSPlayer v.1 e XCSPlayer

v.2, modificados para o balanceamento dinâmico. Essas modificações consistem apenas naimplementação de um mecanismo que realiza a avaliação do nível de dificuldade percebida pelooponente e o ajuste na política de seleção, assim como é apresentado na Seção 3.3.1. Os agentesadversários deste experimento são mais uma vez os agentes SMPlayer e RDPlayer.

Os agentes avaliados são colocados para enfrentar cada agente adversário em 1 sériede 5 ciclos. Os ciclos são compostos por 20 partidas de treinamento e 30 partidas de teste. Aexecução das partidas ocorre conforme descrito na Seção 6.1, bem como a configuração dosagentes e a inicialização sem treinamento offline. Apenas durante a etapa de testes, a política deseleção de ação dos agentes avaliados é alterada para atuar no nível de dificuldade percebidopelo oponente, como explicado na Seção 3.3.1.

Os resultados do experimento são analisados por ciclo, através de gráficos boxplot

acrescentados de médias representadas por cruzes centrais, que agrupam os resultados departidas encadeadas em um mesmo ciclo O intuito dessa representação é a de fornecer uma ideiada dispersão dos dados colhidos e medidas de centralidade visuais, ao longo das séries. Sãoutilizados testes de hipóteses entre as médias dos ciclos e a média nula, a qual consideramoscomo o nível de desafio acirrado (com pouca diferença de pontuação). O teste de hipóteseutilizado é o teste Normal, com nível de significância α = 5%. A hipótese nula H0 é a de quea média dos resultados obtidos é aproximadamente nula, i.e. o agente atua no mesmo nível dedesempenho do oponente. A hipótese alternativa H1 afirma que a média dos resultados obtidosé significativamente diferente de zero, e, por consequência, que um dos agentes possui melhordesempenho que o outro. Assim, se o valor-p calculado for menor que o nível de significância,então há evidência estatística para se rejeitar a hipótese nula e considerar a hipótese alternativa.Senão, é preciso uma evidência mais forte para poder rejeitar a hipótese nula.


6.4.2 Resultados dos Experimento

Figura 6.4: 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.1 eRDPlayer

Intervalo 1 2 3 4 5Média -0,300 12,967 0,833 -3,067 0,933Valor-p 0,717 0,128 0,228 0,580 0,484

Tabela 6.7: Médias do agente XCSPlayer v.1 contra RDPlayer por intervalo e respectivosvalores-p do teste de Wilcoxon para amostras independentes em relação à média nula -

dados da Figura 6.4

Figura 6.5: 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.1 eSMPlayer


Intervalo 1 2 3 4 5Média -0,533 3,300 10,100 6,667 -2,867Valor-p 0,885 0,820 0,685 0,172 0,625

Tabela 6.8: Médias do agente XCSPlayer v.1 contra SMPlayer por intervalo e respectivosvalores-p do teste de Wilcoxon para amostras independentes em relação à média nula -

dados da Figura 6.5

Figura 6.6: 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.2 eRDPlayer

Intervalo 1 2 3 4 5Média 2,867 3,867 9,967 4,233 2,467Valor-p 0,533 0,751 0,376 0,427 0,655

Tabela 6.9: Médias do agente XCSPlayer v.2 contra RDPlayer por intervalo e respectivosvalores-p do teste de Wilcoxon para amostras independentes em relação à média nula -

dados da Figura 6.6

Intervalo 1 2 3 4 5Média 10,333 6,533 2,300 -10,867 -6,433Valor-p 0,600 0,201 0,934 0,183 0,841

Tabela 6.10: Médias do agente XCSPlayer v.2 contra SMPlayer por intervalo erespectivos valores-p do teste de Wilcoxon para amostras independentes em relação à

média nula - dados da Figura 6.7

É possível observar nas Figuras 6.4 e 6.5 que o agente XCSPlayer v.1 conseguiu manter-se próximo ao nível do jogador, como confirmado pelo teste de hipótese. Entretanto, sua atuaçãopossui um grande nível de variabilidade: a distância interquartil (a altura das caixas nas figuras)de alguns conjuntos possui variação de quase 30 pontos, e as alças em cada boxplot cobremquase metade do intervalo possível de resultados. Ainda assim, o agente consegue a longo prazomanter o nível de competitividade próximo ao do adversário.


Figura 6.7: 5 ciclos de 20 partidas de treino e 30 partidas de teste entre XCSPlayer v.2 eSMPlayer

Nas Figuras 6.6 e 6.7, o agente XCSPlayer v.2 apresenta atuação similar, mesmo nocaso do agente previsível, contra o qual se destacou anteriormente. Ele apresenta o melhordesempenho em conjunto de partidas do experimento desta seção, no segundo intervalo contra oagente previsível. É o boxplot com média mais próxima de zero e distribuição dos resultadosmais comprimidos ao centro do espaço possível de resultados. Esse agente também consegueatuar competitivamente a longo prazo, de acordo com os resultados dos testes de hipótese.

6.4.3 Análise de Resultados

Como é possível observar, os resultados obtidos variam bastante. Uma análise possívelpode ser realizada ao associar esses resultados à variação encontrada anteriormente, nos experi-mentos preliminares, nas Seções 4.5.1 e 5.1.5, ao interpretar essa variação como a combinaçãoda instabilidade em atuar no melhor nível com a dificuldade em acompanhar o nível do oponente.Nas quatro séries, não há tendência de diminuição dessa variação ao longo dos 5 intervalos.

Contudo, isoladamente, os dados não são indicativos da qualidade das lutas, uma vez quenão mostram a evolução interna dos agentes. Todas as séries mostraram médias próximas a zero,confirmadas por testes de hipótese. A variação pode vir, por exemplo, do próprio adversário,como é o caso do agente imprevisível. Nesse caso, ela é justificável, por acontecer mesmo sem oprocesso de balanceamento.

Além disso, é interessante apontar o fato do agente parametrizado automaticamente terconseguido diminuir seu nível de atuação do patamar de melhor desempenho observado naFigura 5.4 (extremidade superior) para o centro do intervalo de resultados possíveis. Esse podeser uma demonstração mais clara do resultado na utilização da abordagem de balanceamento nosagentes propostos.

A ressalva que a variação representa é a necessidade de uma investigação mais cuidadosa

6.5. CONCLUSÃO 81

sobre os processos que concorrem durante a adaptação do agente proposto, para que possa seraplicado em uma situação real. O agente pode ser competitivo a longo prazo, mas também podeexecutar sequência de ações pouco críveis em alguns trechos das partidas, por exemplo.

6.5 Conclusão

Este capítulo tratou da realização dos experimentos entre agentes a fim de responderalgumas perguntas de pesquisa. Primeiro, foi investigado qual o agente treinador mais adequadopara a realização de um treinamento offline mais efetivo pros agentes propostos. Os resultadosapontaram um empate técnico, decidido por características dos agentes observadas duranteas lutas. Segundo, foram realizados experimentos para saber a capacidade de aquisição decompetência dos agentes propostos, em comparação ao agente de referência RLTPlayer. Osresultados revelaram também o impacto que a exploração tem para o agente de referência empartidas de teste contra o agente imprevisível. Além disso, foi possível observar a falta deiniciativa nos agentes XCSPlayer v.2 e RLTPlayer, quando postos para confrontar entre si. Porúltimo, séries de partidas foram executadas para demonstrar a possibilidade de integração de umaabordagem de balanceamento dinâmico aos agentes propostos. Ainda que houvesse variaçãosignificativa nos resultados, tanto o agente XCSPlayer v.1 quanto o agente XCSPlayer v.2 foramconsiderados competitivos a longo prazo pelos testes de hipótese realizados.

828282

7Experimento entre agentes e humanos

Com os resultados dos experimentos realizados no capítulo anterior, o próximo passode nossa investigação tratou de uma aplicação mais próxima do real para o agente construído.Este capítulo tem por foco o experimento feito entre o agente proposto XCSPlayer v.2 e o agentede referência RLTPlayer contra jogadores humanos. Primeiramente, é dado o delineamento doexperimento, detalhando as considerações tomadas e as etapas realizadas. Também são definidosquais dados são coletados e como é o procedimento de coleta. Em seguida, são apresentadosos resultados tanto quantitativos - similar aos experimentos anteriores - quanto qualitativos,acompanhados de algumas observações. Por último, o capítulo traz uma análise dos dados queforam obtidos, relacionando-os com evidências relatadas anteriormente.

7.1 Metodologia

O experimento realizado neste capítulo tem por objetivo avaliar a capacidade de aquisiçãode competência dos agentes XCSPlayer v.2 e RLTPlayer contra jogadores humanos. O grau deantecipação e de adaptação comportamental de um oponente humano são verdadeiros desafios àscapacidades dos agentes avaliados, de modo que esse experimento permite observar a evoluçãode tais agentes em situações reais, sob a exploração contínua de suas falhas e habilidades porparte dos jogadores.

Entre as duas versões do agente XCSPlayer, escolhemos a segunda, parametrizada peloF-Race, por ter obtido na Seção 6.3 resultados melhores contra um comportamento que apresentapadrão de ações, no caso do agente previsível SMPlayer. É aceitável que o comportamentohumano seja imprevisível até certo ponto, porém achamos que o oponente humano tende aapresentar padrões de comportamento mais constantes, variando conforme os desafios aumentam.

Dividimos o experimento em duas etapas: uma de treinamento e outra de avaliação. Cadaetapa está associada a uma fase da evolução do jogador e busca atender a objetivos diferentes.

A primeira etapa corresponde à fase da evolução do jogador de aprendizagem inicial(ANDRADE et al., 2005), em que ele ainda não domina o controle do personagem, nem estáconfortável com a mecânica do jogo. Por conta disso, esta fase apresenta maior variação de

7.1. METODOLOGIA 83

habilidade, interferindo negativamente no desempenho do jogador. Adicionalmente a essasituação, os participantes apresentam variado nível de experiência inicial, desde jogadores que jáconhecem o gênero de jogos de luta àqueles que não possuem qualquer experiência prévia. Essascircunstâncias não são desejáveis para a realização das lutas contra os agentes de avaliação. Essaetapa é definida então para garantir um conhecimento mínimo aos jogadores humanos sobre ojogo e engajá-los a continuarem com o experimento.

A segunda etapa corresponde à fase mais estável da evolução do jogador, em que elejá está acostumado ao jogo e os resultados das partidas sofrem interferência mínima de fatoresnão relacionados ao desafio proposto pelo oponente, e.g. dificuldade no controle do lutador,desconhecimento de regras do jogo. Essa etapa é adequada para que ocorram as partidas contraos agentes a serem avaliados.

O experimento é conduzido sob a narrativa de um lutador representando sua academiaem uma competição para definir a melhor academia de artes marciais da cidade. Essa abordagemfacilita o entendimento da mecânica e o engajamento do participante no experimento.

Os diferentes lutadores encontrados ao longo do experimento tiveram os valores deseus atributos igualados, para uma análise mais adequada. Todas as partidas desse experimentoobedecem às mesmas regras apresentadas na Seção 3.5, com duração máxima de 60 segundos.

Previamente ao início do experimento, são explicadas algumas informações ao partici-pante: a finalidade do trabalho, apresentação do jogo Knock’em, instruções sobre a interface decontrole e da tela do jogo, ações possíveis do lutador, objetivos na partida e condições de vitória.Em seguida, são informadas as etapas que compõem o experimento e em que elas consistem.

7.1.1 Etapa de Treinamento

A etapa de treinamento é composta por uma sequência de partidas entre o jogador hu-mano e o agente treinador, baseado em uma modificação do agente SMPlayer, que proporcionalum desafio mais acessível e maior liberdade de exploração por parte do jogador. O comporta-mento desse agente, encontrado no projeto do jogo Knock’em, é descrito simplificadamente empseudocódigo no Algoritmo 5.

A duração da etapa de treinamento não deve ser tão curta que o jogador apresentedificuldades em interagir com o jogo e entendê-lo, nem tão longa que ele se especialize contraos oponentes enfrentados. Nesse experimento, cada participante é posto para lutar contrao agente treinador durante 5 partidas, podendo antecipar o fim da etapa ao obter 3 vitóriasconsecutivas. Acreditamos que a duração escolhida é suficiente para que um jogador possaaprender a movimentar o personagem, testar golpes de ataque básicos e especial, tentar pulos edefesas, acostumar-se com as informações dos lutadores na tela e com a jogabilidade em geral, eter uma primeira experiência em compreender o padrão comportamental do oponente.

7.1. METODOLOGIA 84

Algoritmo 5 Tomada de Decisão do Agente Treinadorrequer pulo ≥ 0

1: função TomarDecisão(estado)2: pulo← pulo + 13: se (Distância(estado) = perto) e (Oponente(estado) = atacando) então4: retorna ação← pularParaTrásAtacando5: fim6: se BolaDeFogo(estado) = perto então7: retorna ação← bloquear8: fim9: se Oponente(estado) = agachado então

10: retorna ação← pularParado11: fim12: se (Distânciaestado = média) e (MúltiploDe30(pulo) = verdadeiro) então13: retorna ação← pularParaTrás14: senão se Distância(estado) = perto então15: i← SortearNúmeroAleatório(0,3)16: se (i = 0) então17: retorna ação← socoForte18: senão se (i = 1) então19: retorna ação← socoRápido20: senão se (i = 2) então21: retorna ação← chuteForte22: senão23: retorna ação← chuteRápido24: fim25: fim26: se (Distância(estado) = média) ou (Distância(estado) = longe) então27: se Oponente(estado) = atacando então28: retorna ação← andarParaFrente29: senão30: retorna ação← pularParaFrente31: fim32: fim33: fim

7.1. METODOLOGIA 85

7.1.2 Etapa de Avaliação

A etapa de avaliação consiste em um conjunto de lutas em que o participante, uma veztreinado na etapa anterior, é posto para enfrentar o agente proposto XCSPlayer v.2 e o agente dereferência RLTPlayer. O número de partidas contra cada agente deve ser escolhido de formaque seja possível obter resultados suficientes para a análise, mas ao mesmo tempo não exija aatenção dos participantes por tempo demasiadamente prolongado.

Um outro aspecto a se observar é a disposição das partidas. É interessante que as partidassejam apresentadas de forma equilibrada, para controlar o efeito que a evolução do jogadorpode causar nos resultados. No caso de uma longa série de partidas subsequente a outra, podehaver a chance de que a habilidade do jogador tenha melhorado significativamente entre asséries, oferecendo relativa vantagem ao agente que enfrentou primeiro o jogador, até entãomenos experiente. A fim de mitigar o efeito da evolução do participante, definimos então aetapa de avaliação como sendo composta por 3 rodadas, cada qual com uma série de 3 partidasconsecutivas contra cada um dos agentes de avaliação. Essa estruturação da etapa permitetambém a avaliação por estágios diferentes de experiência tanto dos participantes quanto dosagentes.

A opção por séries intercaladas abre uma possibilidade de enviesamento na atuação doparticipante. Após enfrentar os agentes em algumas séries, o participante pode formar umaopinião sobre cada agente que influencie seu comportamento em séries subsequentes. A soluçãoque encontramos foi a de apresentar os agentes de avaliação como personagens diferentes aolongo das rodadas, sem conhecimento dos participantes, de modo que a experiência com asprimeiras séries não interfira no julgamento da experiência com as últimas séries. Entretanto,adotamos o gênero dos personagens como característica que distingue facilmente os dois agentesao longo da etapa, a fim de que seja possível uma avaliação geral das partidas por agente avaliado,também sem conhecimento por parte do participante.

Dada a dificuldade dos agentes em acompanhar o nível de jogadores humanos, comodescrito na Seção 3.4. Os agentes avaliados são treinados offline contra agente de comportamentoaleatório em uma série de 1200 ciclos de 1 partida de treino e 1 partida de teste, resultante doexperimento da Seção 6.3. Além disso, os agentes possuem aprendizagem ativada continuamentedurante as partidas e acumulam experiência ao longo das rodadas.

Em todas as partidas dessa etapa, os agentes que aprendem possuem liberdade em relaçãoà escolha da política de ação, podendo tanto ocorrer ciclos de exploração quanto de usufruto. Osagentes são configurados conforme os parâmetros definidos na Tabela 4.2 e na Tabela 4.1, sendoa única alteração por parte do agente RLTPlayer o uso da política de seleção e-greedy com taxade exploração igual a 10%.

Novamente, os agentes seguem a mesma interface e as mesmas condições definidasna Seção 4.3. Os agentes avaliados utilizam mais uma vez o gerador de números aleatóriosMersenne Twister, com semente individual por agente e por luta gerada também pelo mesmo

7.2. RESULTADOS DO EXPERIMENTO 86

gerador a partir do tempo de execução (SAITO; MATSUMOTO, 2008).

7.1.3 Dados Coletados

Assim como nos experimentos do Capítulo 6, a avaliação dos agentes é baseada nosresultados das partidas, especificamente os placares finais. As médias de cada agente de avaliaçãopor rodada são agrupadas, em um gráfico boxplot, de modo a oferecer uma perspectiva sobre aevolução de desempenho médio dos agentes contra os jogadores.

Com os dados agrupados por rodada, extraídos em pares de cada participante, é possívelrealizar testes de hipóteses para amostras pareadas. Nesse caso, utilizamos o teste de Wilcoxonpareado, com nível de significância α = 5%. Lembrando que esse teste de hipótese calcula ovalor-p, de modo que se p < α , então há evidência estatística para rejeitar a hipótese de que osagentes avaliados possuem o mesmo desempenho, sendo considerada a hipótese de que um dosagentes apresenta desempenho maior que o outro.

A análise do experimento é complementada pela percepção dos jogadores, traduzidaem respostas obtidas de questionários aplicados aos participantes. Dessa maneira, é possíveldesenvolver uma melhor compreensão quanto ao nível de desafio oferecido pelos agentes e quantoa detalhes que escapam da quantificação dos placares, como a dinâmica da luta e possíveis falhasde comportamento dos agentes.

Foram utilizados quatro tipos de questionários ao longo do experimento. O questionárioinicial, aplicado antes da etapa de treinamento, busca auxiliar categorização dos participantes e aentender seu nível de habilidade. Os participantes responderam ao segundo questionário ao fimda etapa de treinamento. O objetivo desse segundo questionário é, de modo geral, identificar aexperiência obtida nessa etapa, apontando possíveis dificuldades de interação com o jogo aindaexistentes. Ao final de cada rodada os participantes respondem um terceiro tipo de questionário.Nele, os participantes comparam a diferença de dificuldade e diversão entre os agentes da rodada,e entre cada agente da rodada e o agente treinador. O último questionário é apresentado após aconclusão da etapa de avaliação. Os participantes informam qual sobre a dificuldade e a diversãopercebido de acordo com o gênero dos personagens (definindo assim por agente avaliado), bemcomo a experiência geral do jogo.

7.2 Resultados do Experimento

O experimento contou com a participação de 10 pessoas, na faixa etária entre 10 e 35anos, das quais 7 são do sexo masculino. Sete dos participantes informaram usar o computador,em média, por duas horas ou mais, e, quanto à experiência com jogos de ação ou luta, cincodeles reportou ter pouca experiência e quatro reportaram experiência intermediária.

Questionados quanto à etapa de treinamento, sete dos participantes acharam fácil oumuito fácil, enquanto que os demais acharam as lutas contra o agente treinador em um nível


médio de dificuldade. Todos os participantes afirmaram não ter tido problemas com o controleno jogo, porém quatro deles não aprenderam bem a aplicar o golpe especial dentro do intervalodas lutas de treino.

Na primeira rodada, quanto à dificuldade percebida pelos participantes, nove delesacharam o agente RLTPlayer mais difícil que o XCSPlayer v.2 e um pensou o inverso. Emrelação ao agente treinador, cinco pessoas responderam que o agente proposto é mais fácil, aopasso que quatro pessoas acharam o contrário, e nove opinaram que o agente de referência émais difícil, enquanto um pensou o contrário. Quanto à diversão, seis participantes acreditaramser o agente proposto mais divertido que o de referência, com quatro votos contrários; cincoopinaram que o agente proposto é mais divertido que o treinador, com três votos contrários; ecinco pessoas avaliaram o agente de referência como mais divertido, com dois votos contrários.

Em relação à segunda rodada, o cenário de dificuldade inverteu, de modo que oitopessoas votaram a favor do agente proposto parecer mais difícil que o agente de referência eduas votaram contra. A mesma proporção de votos favoráveis e contrários ocorreu em relação àafirmação do do agente proposto parecer mais difícil que o treinador, enquanto que sete pessoasopinaram a favor do agente de referência parecer mais difícil que o treinador, com dois votoscontrários. Entre os agentes avaliados, sete pessoas acharam o agente proposto mais divertido,e duas opinaram o inverso. O agente proposto foi considerado mais divertido que o treinadorpor sete pessoas, e menos divertido por uma. Já quanto ao fato do agente de referência ser maisdivertido que o treinador, ocorreram quatro votos a favor e quatro votos indiferentes.

Na última rodada, o agente de referência foi considerado mais difícil que o proposto por7 votos a 3, e ambos os agentes avaliados foram tidos como mais difíceis que o treinador por6 votos a 4. A opinião sobre o agente avaliado visto como mais divertido ficou dividida meioa meio. O agente proposto pareceu mais divertido que o treinador para seis pessoas, enquantoduas não perceberam diferença; já o agente de referência pareceu mais divertido que o treinadorpara sete pessoas, contra duas que não perceberam diferença.

Ao final do experimento, os participantes concluíram que, na média, o agente RLTPlayer

foi mais difícil que o agente XCSPlayer v.2 para oito pessoas, contra uma que concluiu o inverso.Na média das rodadas, o agente considerado mais divertido foi o agente proposto, com seis votosa favor e dois contrários. Por último, todos os participantes afirmaram que a experiência geralcom o jogo foi boa ou muito boa.

Rodada 1 2 3Oponente RLTPlayer XCSPlayer v.2 RLTPlayer XCSPlayer v.2 RLTPlayer XCSPlayer v.2Média -36,8 3,4 -17,367 -22,067 26,567 29,267Valor-p 0,002 0,770 0,432

Tabela 7.1: Médias gerais dos participantes em cada série de lutas e valores-p do teste deWilcoxon pareado - dados da Figura 7.1

A Figura 7.1 apresenta a distribuição das pontuações obtidas pelos participantes ao longodas séries de partidas que compõem o experimento. É possível observar que, na média, todos


Figura 7.1: Pontuação média dos participantes por série de partidas, na ordem deocorrência: na etapa de treinamento (1), nas três rodadas de avaliação contra agente

RLTPlayer (2,4,6) e agente XCSPlayer v.2 (3,5,7); pontuação negativa indica vantagem doagente sobre o participante; cruzes representam a média do conjunto.

os participantes obtiveram ótimos resultados contra o agente treinador, mesmo sendo essa umafase em que eles ainda se acostumavam com o jogo. Essa situação condiz com as informaçõesobtidas do questionário inicial sobre a experiência de uso com o computador e sobre algumconhecimento prévio de jogos de ação ou luta, como também reforça a ausência de relatos quantoa dificuldades encontradas durante a etapa obtidos pelo questionário.

A maior diferença de desempenho é percebida na primeira rodada de avaliação, quandoos participantes enfrentam pela primeira vez os agentes XCSPlayer v.2 e RLTPlayer, capazesde aprender e previamente treinados. As pontuações médias dos participantes nessa rodada sãona maioria negativas, indicando derrota para os agentes, incluindo nocautes. Nessa rodada épercebida também a maior diferença de desempenho médio entre os agentes, com maior desafiooferecido pelo agente de referência, como também constatado nas respostas do questionárioassociado à rodada. O fato do agente proposto ter uma proporção maior de vitórias que o agentetreinador parece não influenciar diretamente na percepção de dificuldade dos participantes, dosquais metade acreditam que o treinador foi um oponente mais difícil. Uma possível causa paraesses resultados é alguma variação de comportamento durante o combate, ou um comportamentoque represente pouca ameaça, e.g. oponente frequentemente distante ou esquivo.

Na segunda rodada de avaliação, inverteu-se a posição de agente mais desafiador. En-quanto o agente de referência apresentou diminuição de desempenho, passando a perder maispartidas para o jogador, o agente proposto melhorou sua atuação contra os jogadores, a suamelhor em todo o experimento. Ainda que o nível dos dois agentes tenha se aproximado, comoindica o respectivo da Tabela 7.1, a percepção de oito dos participantes é de que o agente propostofoi mais difícil que o agente de referência e que o agente treinador. Essa mudança na opiniãopode ser novamente explicada a nível comportamental, sem necessariamente ser sofisticada. Um

7.3. ANÁLISE DOS RESULTADOS 89

exemplo observado foi a utilização pelo agente proposto de golpes especiais seguidos, dentro dopermitido, o que passou para alguns uma conotação de agressividade.

A última rodada de avaliação revelou participantes um pouco mais experientes, capazesde aproveitar melhor as falhas dos agentes, gerando resultados positivos mais próximos daquelesobtidos contra o agente treinador. A pequena diferença de desempenho médio do agente dereferência em relação ao agente proposto é acompanhada da opinião emitida por sete participantesde que o agente de referência pareceu mais difícil. Esses resultados representam o menordesempenho geral de ambos agentes e indicam uma possível tendência dada a evolução dosjogadores.

7.3 Análise dos Resultados

A primeira conclusão que é possível tomar a partir dos resultados quantitativos e qualitati-vos obtidos é a de que, dentro da configuração executada do experimento, o agente de referência,RLTPlayer, representa um desafio maior ao participante que o agente proposto, XCSPlayer v.2.Isso se deve não só pelas médias de pontuação alcançadas, mas também pela menor variaçãoexistente nas rodadas.

É possível afirmar também que o agente de referência se beneficia mais da atuaçãocom aprendizagem online, ao se observar os experimentos das Seções 5.1.5 e 6.3. O agente dereferência não só apresentou um melhor desempenho inicial, decorrente de uma adaptação maisrápida, como também um decaimento de desempenho mais constante ao longo do experimento.Por sua vez, o agente proposto possui uma oscilação na evolução de seu desempenho, comomostra a Figura 7.1, o que indica uma possível adaptação mais lenta, vindo a alcançar o nível doagente de referência com uma rodada de atraso. Essa é uma característica que, em problemasdinâmicos como o tratado neste trabalho, resulta em maior instabilidade inicial, como pode serobservada na variação dos resultados obtidos pelo agente proposto.

Uma observação importante é a diferença de desempenho obtida entre o experimentodeste capítulo e o experimento do trabalho citado na Seção 3.4 (ANDRADE et al., 2005). Nestetrabalho, observamos resultados melhores, com agentes superando o nível de desempenho doshumanos, pelo menos inicialmente. Em nossa opinião, isso se deve principalmente ao número departidas realizadas durante o treinamento offline, acima de 1000 adicionais, as quais podem terpermitido cada agente descobrir e reforçar regras mais úteis ao problema.

Entretanto, mesmo com essa melhora nos resultados, é notável a maior capacidadede adaptação dos jogadores humanos e como conseguem superar o desafio apresentado pelosagentes em poucas partidas. Considerando suficientemente representativas as modelagens doambiente e da função objetivo adotadas, acreditamos que a construção de um agente no contextode DDA, capaz de acompanhar o nível de atuação de uma pessoa, necessite de investigações maisaprofundadas quanto à capacidade de formular novas táticas (conjunto de regras) em problemasdinâmicos.

7.4. CONCLUSÃO 90

7.4 Conclusão

A aplicação prática do agente proposto, mais especificamente contra jogadores humanos,foi o tema deste capítulo Foi definida a configuração do experimento, quais etapas existentes eseus objetivos. Além da diferença de pontos de vida dos personagens, utilizada como pontuaçãonos experimentos entre agentes, foram construídos questionários a fim de capturar a percepçãodos participantes quanto ao desempenho dos agentes. Devido às dificuldades obtidas em testesiniciais quanto à exploração do controle e ambiente do jogo, foi utilizada uma versão modificadado agente SMPlayer descrito na Seção 4.4, de forma a equilibrar mais as partidas de treinamento.O capítulo mostrou também os resultados obtidos do experimento, revelando melhor desempenhopor parte do agente de referência, apontando partidas com vitórias dos agentes e a opinião dosparticipantes sobre o desafio imposto pelos agentes ao longo do experimento. A partir dosresultados, foram discutidas características relacionadas aos agentes, como a velocidade deadaptação e estabilidade, além de relacionar os resultados obtidos com outros observados emexperimentos prévios. Concluímos que o agente proposto mostrou potencial para competir contraum humano, mas que são necessárias mais investigações.

919191

8Conclusão

Este trabalho investigou a aplicação de sistemas classificadores baseados em precisão nocontexto de ajuste dinâmico de dificuldade (DDA) em jogos de luta. Inicialmente, analisamosquais as soluções existentes na área de DDA. As soluções envolvem ajuste de parâmetros, defases e, principalmente, de comportamento de NPCs.

Quanto ao ajuste de comportamento de personagens, as soluções propostas baseiam-seem técnicas heurísticas e de aprendizagem de máquina, construídas como agentes adaptativos,como algoritmos genéticos, aprendizagem por reforço, sistemas de regras, sistemas baseados emplanejamento. Esses agentes possuem a capacidade de variar o seu nível de atuação, conformea experiência com o oponente. Entretanto, as soluções de aprendizagem existentes possuemdificuldade contra jogadores mais experientes.

Analisamos algumas das propostas de aprendizagem online, identificando suas vantagens,e encontramos uma técnica que compartilha de algumas de suas características. Essa técnica é osistema classificador, que tem aplicações em outras áreas, mas pouca aplicação no contexto dejogos, e especificamente não encontramos aplicação quanto ao problema de DDA.

Os sistemas classificadores agregam a simplicidade dos sistemas de regras, com a capa-cidade de aprendizagem por reforço similar à do Q-Learning, e a capacidade de generalizaçãopropiciada com o uso de um algoritmo genético. Como sabemos da possibilidade de adaptaçãoda técnica para obter desempenho subótimo, focamos então na investigação da capacidade deaquisição de competência do agente. Para isso, implementamos o agente XCSPlayer para aplataforma de jogo de luta Knock’em, e realizamos testes preliminares, que nos apresentou adificuldade em parametrizar o agente.

Recorremos à técnica de parametrização F-Race, que resultou em uma nova configuração.O agente que utiliza esse segundo conjunto de parâmetros apresentou ótimo desempenho contraagentes de comportamento previsível, mas ainda não foi capaz de enfrentar satisfatoriamenteagentes de comportamento imprevisível.

Realizamos então uma nova rodada de experimentos, mais prolongados, a fim de avaliara capacidade de aprendizagem do agente. Obtivemos um bom desempenho do agente parame-trizado à mão contra o agente previsível, devido ao uso de treinamento offline, e comparável

8.1. CONTRIBUIÇÕES 92

ao agente baseado em Q-Learning contra o agente imprevisível. O agente parametrizado au-tomaticamente revelou a ocorrência de especialização durante o processo de otimização dosparâmetros, possuindo excelente desempenho contra agente de comportamento previsível, efraco desempenho contra agente de comportamento previsível.

A segunda versão do agente XCSPlayer foi posta para enfrentar diretamente contra oagente RLTPlayer. Os agentes realizaram exploração nas partidas de treino, mas permaneceramsem iniciativa, estagnados, em 99% das partidas de avaliação.

Outro experimento foi realizado, a fim de confirmar a possibilidade de integração de umaabordagem de balanceamento dinâmico baseada em desafio à arquitetura do agente proposto.As duas versões do agente proposto conseguiram atuar no nível dos oponentes SMPlayer eRDPlayer, mostrando a capacidade do agente atuar no contexto de DDA. Porém, a grandevariação nos resultados indica instabilidade por parte dos agentes, cuja solução exige maisinvestigações.

Por último, o agente proposto XCSPlayer v.2 e o de referência RLTPlayer foram avaliadoscontra oponentes humanos. Esse tipo de oponente é considerado o mais difícil, pela capacidadede aprender o comportamento do adversário, formular novas estratégias, colocá-las em prática eadaptá-las assim que se tornam ineficientes, em tempo consideravelmente menor que os agentes.Ainda que o agente de referência tenha obtido melhor desempenho e o agente proposto tenhaobtido resultados iniciais positivos, as pontuações positivas de ambos agentes não resistiram àcompetitividade humana, indicando a necessidade de mais investigações.

8.1 Contribuições

Este trabalho contribuiu com a investigação de uma técnica pouco explorada na áreade jogos, chamada de sistema classificador, no contexto de ajuste dinâmico de dificuldade,especificamente na aquisição de competência. Primeiramente, buscamos responder às perguntasformuladas na Seção 1.2, aqui repetidas e seguidas de nossas conclusões:

"Dado que há espaço para melhoria no problema de ajuste dinâmico de dificuldade,

a aplicação de sistemas classificadores é viável como solução para aquisição de

competência em jogos de luta de tempo real?"

Com base nas execuções documentadas nos Capítulos 4, 5, 6 e 7, é possível afirmarque um agente baseado em sistemas classificadores é viável computacionalmente para aquisi-ção de competência em jogos de luta de tempo real, desde que implementado e configuradoadequadamente.

"Sistemas classificadores apresentam bom desempenho comparados a outra aborda-

gem da literatura para o mesmo problema?"

8.1. CONTRIBUIÇÕES 93

Foram observados bons resultados por parte do agente baseado em sistemas classifica-dores contra outros agentes, registrados na Seção 6.3, e em algumas partidas contra humanos,relatadas no Capítulo 7. Entretanto, comparando as evoluções de desempenho entre o agenteproposto e o agente baseado em Q-Learning nesses experimentos, respondemos que o agentebaseado em sistemas classificadores apresenta desempenho melhor que o da literatura contraoutros agentes avaliados, e quase tão bons contra humanos. Vale ressaltar que o desempenho doalgoritmo é bastante influenciado pela sua parametrização, e que, mesmo obtendo resultadosiniciais positivos contra humanos, o agente proposto não acompanhou a competitividade dosparticipantes do experimento.

"A abordagem baseada em sistemas classificadores é adequada para a adaptação

da dificuldade ao nível do oponente no problema tratado?"

A integração de uma abordagem de DDA a um agente baseado em sistemas classifica-dores é adequada, considerando o experimento da Seção 6.4, em que um agente baseado emsistemas classificadores conseguiu atuar, em média, no nível de outros agentes. Porém, a variaçãoobservada nos resultados desse experimento indica instabilidade na execução do agente.

Além dessas questões, abordamos outros pontos em nossa pesquisa. Neste trabalho, foimostrada a complexidade em se implementar um agente baseado em sistemas classificadores,como também a dificuldade em parametrizá-lo. Valores de parâmetros correspondentes emtécnicas relacionadas não foram suficientemente adequados, e o ajuste manual de parâmetrosmostrou-se impeditivo.

Esse problema serviu de oportunidade para explorarmos uma técnica de otimizaçãoautomática de parâmetros, chamada F-Race, o que nos permitiu a análise do impacto gerado pelaparametrização na aprendizagem de comportamento de um agente inteligente. No Capítulo 5,foi possível observar o custo para executar a técnica e o cuidado necessário na modelagemdas avaliações consideradas para a corrida, principalmente em problemas de aprendizagem desequências de ações, para não haver especialização contra um tipo de oponente. A forma como émodelado o processo de parametrização impacta diretamente na atuação do agente.

Este trabalho revelou a possibilidade de estagnação de agentes em treinamentos porautoaprendizagem, da mesma forma que pode ocorrer entre agentes aprendizes treinados. Pen-samos que a condição de estagnação pode ser evitada de acordo com a definição da função derecompensa, capaz de enviesar o comportamento do agente.

O experimento relativo à aquisição de competência na Seção 6.3 mostrou aumentono nível de desempenho do agente e a possível ocorrência de especialização causada pelaparametrização automática. Comparando esse experimento com testes preliminares, percebeu-sea necessidade do agente baseado em Q-Learning de operar com aprendizagem em modo online

para alcançar melhores resultados.Demonstramos exemplos de uso do agente baseado sistemas classificadores no contexto

de DDA. O agente mostrou-se aplicável, ao manter uma média próxima a zero, considerada no

8.2. TRABALHOS FUTUROS 94

nível do jogador. Porém deixou evidente sua grande variação de comportamento.A avaliação dos agentes XCSPlayer v.2 e RLTPlayer contra jogadores humanos é outra

contribuição deste trabalho. Ainda que superados pelos participantes humanos ao final doexperimento, os agentes obtiveram partidas iniciais vitoriosas. Isso destacou a importância dotreinamento offline mais cuidadoso e a necessidade por mais estudos para a construção de agentespáreos aos jogadores.

Neste trabalho ainda, identificamos uma possibilidade de antecipação na utilização doreforço pelo agente, implementada de forma parametrizável no agente proposto. O aparecimentodesse modo de atualização em vez do modo tradicional na melhor configuração encontradapelo F-Race e o bom desempenho encontrado nos experimentos anteriores apontam o impactopositivo do modo de reforço, abrindo espaço para mais modificações ao algoritmo básico.

Também é relatada a questão da instabilidade no desempenho do agente baseado emsistemas classificadores. Tanto nos testes preliminares, quanto em parte dos experimentos entreagentes, quanto no experimento com humanos, o agente proposto apresentou maior grau devariação. Acreditamos que isso seja efeito das interações decorrentes da configuração do agente,cujo entendimento é dificultado pela complexidade da arquitetura e de como suas partes seintegram.

Por último, apontamos algumas diferenças entre as técnicas avaliadas neste trabalho. Aprincipal característica do Q-Learning comparado ao algoritmo XCS é a menor complexidadede implementação, com uma arquitetura mais enxuta e, assim, com menos parâmetros. Nesseaspecto, a parametrização manual de um agente baseado em Q-Learning não é problemática.Outro ponto positivo é a maior estabilidade de operação observada, possível consequência datécnica ser mais simples. Ainda quanto ao Q-Learning, bons resultados foram encontrados semmuito esforço de implementação.

Por sua vez, o algoritmo XCS trabalha com regras generalizáveis. Essa característica per-mite uma representação mais compacta do problema por parte do agente, reduzindo a exigênciade memória para problemas com muitos estados e ações, ao contrário da representação tabulardo Q-Learning. Além disso, esse tipo de representação permite uma melhor interpretação doconhecimento gerado, uma vez que as regras são do tipo condição-ação. O algoritmo XCS nãoexige regras iniciais, sendo capaz de gerar regras a partir das situações que encontra, mas tambémpermite a inicialização com um conjunto pré-definido de regras, permitindo a um especialista (e.g.game designer) construir uma base de conhecimento a partir da qual deve ocorrer a adaptação doagente.

8.2 Trabalhos Futuros

Os desafios enfrentados durante o desenvolvimento deste trabalho oferecem oportunida-des de investigação. No contexto geral de agentes adaptativos, seria desejável pesquisar outrasmaneiras de desenvolver a habilidade de um lutador. Uma primeira ideia seria o desenvolvimento

8.2. TRABALHOS FUTUROS 95

de funções de recompensa mais sofisticadas, que representem melhor as nuances de comporta-mento, e.g. recompensando mais defesas e esquivas bem executadas e punindo agente paradoquando há desvantagem de pontuação. Outra possibilidade é a busca por uma aprendizagemresidual maior a partir de simulações sistemáticas com troca de agentes treinadores, cada qualcom um estilo de luta diferente ou com um comportamento específico contra o qual o agentedeve formular uma estratégia.

Especificamente em relação aos sistemas classificadores, é possível citar alguns pro-blemas ainda em aberto, como a aprendizagem de longas cadeias de ações (BARRY, 2002),instabilidade de adaptação, aprendizagem lenta, parametrização complicada. O aprofundamentoteórico e prático em qualquer desses pontos beneficiaria o problema tratado por este trabalho.

A hierarquização de regras poderia ser explorada, de forma a permitir explicitamenteconjuntos de regra prioritárias. Essa abordagem teria por paralelo, em um nível maior deabstração, a formação de táticas e estratégias alternantes e bem definidas.

Suspeitamos que a complexidade do algoritmo colabore para a baixa aplicação em jogosna prática. A simplificação é uma alternativa que tanto promove o sistema classificador quantoreduz o problema com os parâmetros.

O sucesso e a popularização recente de técnicas como Árvores de Comportamentos(CHAMPANDARD, 2007) abre espaço para o desenvolvimento de sistemas que utilizem outrasrepresentações no lugar das regras, tornando-se mais atrativa ao entendimento e utilização porparte do desenvolvedor. Além disso, seria possível explorar as características de árvores, porexemplo, para aprimorar o problema de aprendizagem de longas sequências de ações.

Como há uma família de sistemas classificadores, seria interessante explorar a aplicaçãode outras arquiteturas. Uma opção interessante é a de sistema classificador antecipatório (ACS)(STOLZMANN, 1998), que constrói um modelo de transição de um problema de aprendizagempor reforço.

Por último, seria interessante a integração de um mecanismo de adaptação automáticados parâmetros ao agente. Isso diminuiria o esforço com o processo de parametrização doalgoritmo.

969696

Referências

ANDRADE, G. et al. Extending reinforcement learning to provide dynamic game balancing. In:WORKSHOP ON REASONING, REPRESENTATION, AND LEARNING IN COMPUTERGAMES, 19TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIALINTELLIGENCE (IJCAI), Edinburgh, Scotland. Proceedings. . . [S.l.: s.n.], 2005. p.7–12.

BARRY, A. M. The stability of long action chains in XCS. Soft Computing, [S.l.], v.6, n.3-4,p.183–199, 2002.

BARTO, A. G. Reinforcement learning: an introduction. [S.l.]: MIT press, 1998.

BAUCKHAGE, C.; THURAU, C.; SAGERER, G. Learning human-like opponent behavior forinteractive computer games. In: Pattern Recognition. [S.l.]: Springer, 2003. p.148–155.

BIRATTARI, M. et al. A racing algorithm for configuring metaheuristics. In: THE GENETICAND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO). Anais. . . [S.l.: s.n.],2002. v.2, p.11–18.

BIRATTARI, M. et al. F-Race and iterated F-Race: an overview. In: Experimental methodsfor the analysis of optimization algorithms. [S.l.]: Springer, 2010. p.311–336.

BOCHKANOV, S.; BYSTRITSKY, V. ALGLIB. 2014. Disponível em: <www.alglib.net>.Acesso em: 03 ago. 2014.

BOOKER, L. B.; GOLDBERG, D. E.; HOLLAND, J. H. Classifier systems and geneticalgorithms. Artificial intelligence, [S.l.], v.40, n.1, p.235–282, 1989.

BOX, G. E.; HUNTER, J. S.; HUNTER, W. G. Statistics for experimenters: design,innovation, and discovery. [S.l.]: Wiley-Interscience, 2005.

BULL, L.; KOVACS, T. Foundations of learning classifier systems: an introduction. In: BULL,L.; KOVACS, T. (Ed.). Foundations of Learning Classifier Systems. [S.l.]: Springer BerlinHeidelberg, 2005. p.1–17. (Studies in Fuzziness and Soft Computing, v.183).

BUTZ, M. V. Rule-based evolutionary online learning systems: a principled approach to lcsanalysis and design. [S.l.]: Springer, 2005. v.191.

BUTZ, M. V.; GOLDBERG, D. E.; LANZI, P. L. Gradient descent methods in learning classifiersystems: improving xcs performance in multistep problems. Evolutionary Computation,IEEE Transactions on, [S.l.], v.9, n.5, p.452–473, 2005.

BUTZ, M. V.; WILSON, S. W. An algorithmic description of XCS. In: Advances in LearningClassifier Systems. [S.l.]: Springer, 2001. p.253–272.

CHAMPANDARD, A. Behavior trees for next-gen game AI. In: GAME DEVELOPERSCONFERENCE, AUDIO LECTURE. Anais. . . [S.l.: s.n.], 2007.

CHOMSKY, N. Aspects of the theory of syntax. MIT Press, [S.l.], 1965.

CONOVER, W. Practical nonparametric statistics. [S.l.]: Wiley, 1999. (Wiley series inprobability and statistics: Applied probability and statistics).

REFERÊNCIAS 97

CSIKSZENTMIHALYI, M. Flow: the psychology of optimal experience. [S.l.]: Harper & Row,1990.

DEMASI, P.; OLIVEIRA CRUZ, A. J. de. Evolução de agentes em tempo real para jogoseletrônicos de ação. In: II WORKSHOP BRASILEIRO DE JOGOS E ENTRETENIMENTODIGITAL. Anais. . . [S.l.: s.n.], 2003.

EIBEN, A. E.; SMITH, J. E. Introduction to evolutionary computing. [S.l.]: springer, 2003.

FARIAS, D. L. de. Estudo sobre balanceamento dinâmico de jogos baseado em sistemasclassificadores. 50f. Monografia (Bacharelado) - Centro de Informática, Universidade Federalde Pernambuco, Recife, 2011. Disponível em: <http://www.cin.ufpe.br/ tg/2011-2/dlf2.pdf>.Acesso em: 26 dez. 2013.

FOG, A. Pseudo random number generators. 2014. Disponível em:<http://www.agner.org/random>. Acesso em: 03 ago. 2014.

GENERATION5. [Interview with Jeff Hannan]. Disponível em:<http://www.generation5.org/content/2001/hannan.asp>. Acesso em: 26 dez. 2013.

GRAEPEL, T.; HERBRICH, R.; GOLD, J. Learning to fight. In: INTERNATIONALCONFERENCE ON COMPUTER GAMES: ARTIFICIAL INTELLIGENCE, DESIGN ANDEDUCATION. Proceedings. . . [S.l.: s.n.], 2004. p.193–200.

HART, P.; NILSSON, N.; RAPHAEL, B. A formal basis for the heuristic determination ofminimum cost paths. Systems Science and Cybernetics, IEEE Transactions on, [S.l.], v.4,n.2, p.100–107, July 1968.

HASTINGS, E. J.; GUHA, R. K.; STANLEY, K. O. Automatic content generation in thegalactic arms race video game. Computational Intelligence and AI in Games, IEEETransactions on, [S.l.], v.1, n.4, p.245–263, 2009.

HOLLAND, J. H.; REITMAN, J. S. Cognitive systems based on adaptive algorithms. ACMSIGART Bulletin, [S.l.], n.63, p.49–49, 1977.

HUNICKE, R.; CHAPMAN, V. AI for dynamic difficulty adjustment in games. In:CHALLENGES IN GAME ARTIFICIAL INTELLIGENCE AAAI WORKSHOP. Anais. . .[S.l.: s.n.], 2004. p.91–96.

JUUL, J. The game, the player, the world: looking for a heart of gameness. In: DIGITALGAMES RESEARCH ASSOCIATION (DIGRA) CONFERENCE. Anais. . . [S.l.: s.n.], 2003.

KOSTER, R. A Theory of Fun for Game Design. 1.ed. [S.l.]: Paraglyph Press, 2004.

LANZI, P. L. Learning classifier systems: then and now. Evolutionary Intelligence, [S.l.], v.1,n.1, p.63–82, 2008.

LOYALL, A. B. Believable agents: building interactive personalities. 1997. Tese (Doutoradoem Ciência da Computação) — Stanford University.

MANSLOW, J. Learning and adaptation. In: RABIN, S. (Ed.). AI Game ProgrammingWisdom. [S.l.]: Charles River Media, 2002. p.557–566.

REFERÊNCIAS 98

MARON, O.; MOORE, A. W. Hoeffding races: accelerating model selection search forclassification and function approximation. Robotics Institute, [S.l.], p.263, 1993.

MARON, O.; MOORE, A. W. The racing algorithm: model selection for lazy learners. In: Lazylearning. [S.l.]: Springer, 1997. p.193–225.

MATARIC, M. J. Reward functions for accelerated learning. In: ICML. Anais. . . [S.l.: s.n.],1994. v.94, p.181–189.

MATEAS, M.; STERN, A. Façade: an experiment in building a fully-realized interactive drama.In: GAME DEVELOPERS CONFERENCE. Anais. . . [S.l.: s.n.], 2003. p.4–8.

MCPARTLAND, M.; GALLAGHER, M. Reinforcement learning in first person shooter games.Computational Intelligence and AI in Games, IEEE Transactions on, [S.l.], v.3, n.1,p.43–56, 2011.

MILLINGTON, I.; FUNGE, J. Artificial intelligence for games. [S.l.]: CRC Press, 2009.

MOIOLI, R. C.; VARGAS, P. A.; VON ZUBEN, F. J. Analysing learning classifier systems inreactive and non-reactive robotic tasks. In: Learning Classifier Systems. [S.l.]: Springer, 2008.p.286–305.

NACKE, L. E. et al. Playability and player experience research. In: DIGITAL GAMESRESEARCH ASSOCIATION (DIGRA). Proceedings. . . [S.l.: s.n.], 2009.

NETO, F. et al. Knock’em: um estudo de caso de processamento gráfico e inteligência artificialpara jogos de luta. In: II WORKSHOP DE JOGOS E ENTRETENIMENTO DIGITAL. Anais. . .[S.l.: s.n.], 2003. p.105–112.

NIDORF, D. G.; BARONE, L.; FRENCH, T. A comparative study of NEAT and XCS inRobocode. In: EVOLUTIONARY COMPUTATION (CEC), 2010 IEEE CONGRESS ON.Anais. . . [S.l.: s.n.], 2010. p.1–8.

PEDERSEN, C.; TOGELIUS, J.; YANNAKAKIS, G. N. Modeling player experience in supermario bros. In: COMPUTATIONAL INTELLIGENCE AND GAMES, 2009. CIG 2009. IEEESYMPOSIUM ON. Anais. . . [S.l.: s.n.], 2009. p.132–139.

PONSEN, M.; SPRONCK, I. P. H. M. Improving adaptive game AI with evolutionary learning.In: UNIVERSITY OF WOLVERHAMPTON. Anais. . . [S.l.: s.n.], 2004. p.389–396.

REYNOLDS, C. Steering nehaviors for autonomous characters. In: GAME DEVELOPERSCONFERENCE 1999, San Francisco, California. Anais. . . Miller Freeman Game Group, 1999.p.763–782.

RIEDL, M.; THUE, D.; BULITKO, V. Game AI as storytelling. In: Artificial Intelligence forComputer Games. [S.l.]: Springer, 2011. p.125–150.

SAITO, M.; MATSUMOTO, M. SIMD-oriented fast Mersenne Twister: a 128-bitpseudorandom number generator. In: Monte Carlo and Quasi-Monte Carlo Methods 2006.[S.l.]: Springer, 2008. p.607–622.

SATO, Y.; KANNO, T. Event-driven hybrid learning classifier systems for online soccer games.In: EVOLUTIONARY COMPUTATION, 2005. THE 2005 IEEE CONGRESS ON. Anais. . .[S.l.: s.n.], 2005. v.3, p.2091–2098.

REFERÊNCIAS 99

SCHELL, J. The art of game design: a book of lenses. [S.l.]: CRC Press, 2008.

SMALL, R.; CONGDON, C. B. Agent Smith: towards an evolutionary rule-based agent forinteractive dynamic games. In: EVOLUTIONARY COMPUTATION, 2009. CEC’09. IEEECONGRESS ON. Anais. . . [S.l.: s.n.], 2009. p.660–666.

SPRONCK, P. et al. Adaptive game AI with dynamic scripting. Machine Learning, [S.l.], v.63,n.3, p.217–248, 2006.

SPRONCK, P.; SPRINKHUIZEN-KUYPER, I.; POSTMA, E. Online adaptation of gameopponent AI in simulation and in practice. Proceedings of the 4th International Conferenceon Intelligent Games and Simulation, [S.l.], p.93–100, 2003.

SPRONCK, P.; SPRINKHUIZEN-KUYPER, I.; POSTMA, E. Difficulty scaling of game AI. In:INTERNATIONAL CONFERENCE ON INTELLIGENT GAMES AND SIMULATION(GAME-ON 2004), 5. Proceedings. . . [S.l.: s.n.], 2004. p.33–37.

STOLZMANN, W. Anticipatory classifier systems. Genetic Programming, [S.l.], v.98,p.658–664, 1998.

SUTTON, R. S.; BARTO, A. G. Introduction to reinforcement learning. [S.l.]: MIT Press,1998.

TOGELIUS, J. et al. Assessing believability. In: Believable Bots. [S.l.]: Springer, 2012.p.215–230.

TOZOUR, P. Influence mapping. In: DELOURA, M. (Ed.). Game Programming Gems 2.[S.l.]: Charles River Media, 2001. p.287–297.

TUKEY, J. W. Exploratory data analysis. Addison-Wesley series in behavioral science:quantitative methods. 23 cm. 688 p, [S.l.], 1977.

VERMA, M. A.; MCOWAN, P. W. An adaptive methodology for synthesising mobile phonegames using genetic algorithms. In: EVOLUTIONARY COMPUTATION, 2005. THE 2005IEEE CONGRESS ON. Anais. . . [S.l.: s.n.], 2005. v.1, p.864–871.

VIEIRA, H. et al. Improved efficient, nearly orthogonal, nearly balanced mixed designs. In:SIMULATION CONFERENCE (WSC), PROCEEDINGS OF THE 2011 WINTER. Anais. . .[S.l.: s.n.], 2011. p.3600–3611.

WATKINS, C. J.; DAYAN, P. Q-learning. Machine learning, [S.l.], v.8, n.3-4, p.279–292, 1992.

WIDROW, B. Adaptive switching circuits. In: IRE WESCON CONVENTION RECORD.Anais. . . [S.l.: s.n.], 1960. p.96–104.

WIEGAND, R. P.; LILES, W. C.; DE JONG, K. A. Analyzing cooperative coevolution withevolutionary game theory. In: EVOLUTIONARY COMPUTATION, 2002. CEC’02.PROCEEDINGS OF THE 2002 CONGRESS ON. Anais. . . [S.l.: s.n.], 2002. v.2, p.1600–1605.

WILSON, S. W. Knowledge growth in an artificial animal. In: Adaptive and LearningSystems. [S.l.]: Springer, 1986. p.255–264.

WILSON, S. W. ZCS: a zeroth level classifier system. Evolutionary computation, [S.l.], v.2,n.1, p.1–18, 1994.

REFERÊNCIAS 100

WILSON, S. W. Classifier fitness based on accuracy. Evolutionary computation, [S.l.], v.3,n.2, p.149–175, 1995.

WILSON, S. W.; GOLDBERG, D. E. A critical review of classifier systems. In: GENETICALGORITHMS. Proceedings. . . [S.l.: s.n.], 1989. p.244–255.

YANNAKAKIS, G. N. How to model and augment player satisfaction: a review. In:WORKSHOP ON CHILD COMPUTER INTERACTION (WOCCI). Anais. . . [S.l.: s.n.], 2008.p.21.

YANNAKAKIS, G. N. Game AI revisited. In: COMPUTING FRONTIERS, 9. Proceedings. . .[S.l.: s.n.], 2012. p.285–292.

YANNAKAKIS, G.; TOGELIUS, J. A panorama of artificial and computational intelligence ingames. Computational Intelligence and AI in Games, IEEE Transactions on, [S.l.], v.PP,n.99, p.1–1, 2014.

YILDIRIM, S.; STENE, S. B. A survey on the need and use of AI in game agents. In: SPRINGSIMULATION MULTICONFERENCE, 2008. Proceedings. . . [S.l.: s.n.], 2008. p.124–131.

Documents

Avaliação de aprendizagem de agentes baseados em sistemas ...‡… · Catalogação na fonte Bibliotecária Jane Souto Maior, CRB4 -571 F224a Farias , Denys Lins de Avaliação