Jogos Educativos Computadorizados utilizando a Abordagem de Algoritmos Genéticos

Sidnei Renato Silveira
Dante Augusto Couto Barone
e-mail: sidnei@inf.ufrgs.br
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Curso de Pós-Graduação em Ciência da Computação
Caixa Postal 15064 - CEP 91501-970 - Porto Alegre - RS
Fax: (051) 336-5576


Este trabalho aborda a utilização de algoritmos genéticos na implementação de jogos educativos computadorizados. São abordados alguns aspectos gerais quanto à utilização de jogos educativos computadorizados e a abordagem de algoritmos genéticos, além de demonstrar uma proposta de utilização destes algortimos na construção de jogos educativos.
 


1 Introdução

O objetivo do presente artigo é o de apresentar uma das formas de utilização da informática na educação: os jogos educativos computadorizados e abordar a possibilidade da utilização de algoritmos genéticos para o desenvolvimento destes jogos. Através de um algoritmo genético, o jogador pode, por exemplo, traçar caminhos por onde um objeto do jogo deve "caminhar". Este caminho pode ser determinado por um algoritmo genético. Inicialmente, aborda-se a utilização dos jogos educativos computadorizados como uma das formas de aplicação da informática na educação. Posteriormente, apresenta-se um breve estudo sobre os algoritmos genéticos, relatando também um exemplo de jogo implementado: o Jogo do Pingüim e da Abelha. Finalizando, tenta-se trazer uma proposta de aplicação dos algoritmos genéticos no desenvolvimento de jogos educativos computadorizados.
 

2 Jogos Educativos Computadorizados

Os jogos educativos computadorizados possuem, como uma de suas principais vantagens, um grande potencial para o processo de ensino e aprendizagem, por despertarem naturalmente o interesse dos alunos.
 
 

"Os jogos podem ser empregados em uma variedade de propósitos dentro do contexto de aprendizado. Um dos usos básicos e muito importante é a possibilidade de construir-se a autoconfiança. Outro, é o incremento da motivação. (...) um método eficaz que possibilita uma prática significativa daquilo que está sendo aprendido. Até mesmo o mais simplório dos jogos pode ser empregado para proporcionar informações factuais e praticar habilidades, conferindo destreza e competência" [FER 95, p. 02].   Os jogos desempenham um papel importante no desenvolvimento da criança. O jogo representa esforço e conquista, é uma necessidade vital. O jogo possibilita o equilíbrio entre o mundo interno e o externo, canalizando as energias das crianças e transformando em prazer suas angústias [ARA 92] [ROD 92].

Segundo Grossi [GRO s.d.], o jogo estimula a vida e representa, efetivamente, uma contribuição na aprendizagem da criança, por ser uma atividade rica e desafiadora, contribuindo para o crescimento intelectual e afetivo.

Os jogos educativos podem despertar no aluno: motivação, estímulo, curiosidade, interesse em aprender e cabe ao professor aproveitar-se destas características como estratégias pedagógicas. O aluno "constrói" seu conhecimento de maneira lúdica e prazerosa [CAM 95].

A influência do brinquedo no desenvolvimento da criança é muito grande. Através deste, a criança aprende a agir cognitivamente, sendo livre para determinar suas ações. O brinquedo estimula a curiosidade, a iniciativa e a autoconfiança, proporcionando o desenvolvimento da linguagem, do pensamento e da concentração da atenção [VYG 89].
 
 

"Desde muito cedo o jogo na vida da criança é de fundamental importância, pois quando ela brinca, explora e manuseia tudo aquilo que está à sua volta, através de esforços físicos e mentais..." [ARA 92, p.14].   Segundo Piaget, (Piaget apud [ARA 92]), o jogo tem uma relação estreita com a construção da inteligência e possui uma efetiva influência como instrumento incentivador e motivador no processo de ensino e aprendizagem.

Segundo Vieira, [VIE 94], os jogos devem possuir as seguintes características básicas: estimular a imaginação infantil, auxiliar no processo de integração grupal, liberar a emoção infantil, facilitar a construção do conhecimento e auxiliar na aquisição da auto-estima. Os jogos, em geral, também devem promover a criatividade, desenvolver a autonomia e favorecer a expressão da personalidade infantil. Os jogos educativos podem explorar diversos aspectos, tais como: 1) explorar a ludicidade: jogos de exercício, simbólicos e de construção; 2) favorecer a aquisição de condutas cognitivas: jogos que apelam para o raciocínio prático, a discriminação e a associação de idéias; 3) ajudar no desenvolvimento de habilidades funcionais: jogos que exploram a aplicação de regras, a localização, a destreza, a rapidez, a força e a concentração; 4) propiciar atividades sociais: a realização das atividades pode ser desde as individuais até as de participação coletiva em busca da socialização; 5) auxiliar na aquisição de condutas afetivas: jogos que ajudam a desenvolver a confiança, a autonomia e a iniciativa [VIE 94].

Segundo Rizzo [RIZ 88], os jogos constituem um poderoso recurso de estimulação do desenvolvimento integral do aluno. Desenvolvem a atenção, disciplina, autocontrole, respeito a regras e habilidades perceptivas e motoras relativas a cada tipo de jogo oferecido. Podem ser jogados de forma individual ou coletiva, sempre com a presença do educador para estimular todo o processo, observar e avaliar o nível de desenvolvimento dos alunos e diagnosticar as dificuldades individuais, para poder produzir estímulos adequados a cada um.
 
 

"Não há momentos próprios para desenvolver a inteligência e outros do aluno já estar inteligente, sempre é possível progredir e aperfeiçoar-se. Os jogos devem estar presentes todos os dias na sala de aula" [RIZ 88, p. 48].   Os jogos educativos computadorizados são elaborados para divertir os alunos e aumentar a chance de aprendizagem de conceitos, conteúdos e habilidades embutidas no jogo. Um jogo educativo pode propiciar ao aluno um ambiente de aprendizagem rico e complexo; estes ambientes são denominados "micromundos", porque fornecem um mundo imaginário a ser explorado e no qual os alunos podem aprender. Cabe à equipe de desenvolvimento de software educativo desenvolver jogos que sejam atrativos e ao menos tempo possuam um cunho educativo [COB 88].
 
  "Um jogo educativo por computador é uma atividade de aprendizagem inovadora na qual as características do ensino apoiado em computador e as estratégias de jogo são integradas para alcançar um objetivo educacional específico" [STA 91, p.18].   Estes jogos tornaram-se intrinsecamente motivadores, devido ao desafio, a fantasia e a curiosidade que despertam nas crianças. Os jogos podem fornecer resultados não previstos, mas tão importantes quanto os previamente determinados, oferecendo oportunidades para que o aluno utilize a lógica, raciocínio e habilidades de organização para resolver problemas de maneira mais interessante, do que seriam expostos em um exercício comum. Um jogo simples pode "ensinar" várias habilidades e conceitos, de maneira sofisticada, para que os alunos não se cansem rapidamente do jogo [COB 88] [STA 91].

Segundo Berger & Carlson, (apud [STA 91]), os jogos educativos são ambientes nos quais o aluno aprende através da descoberta. Estes ambientes de aprendizagem possuem um enfoque heurístico, não fornecendo o conteúdo diretamente ao aluno. O que o aluno vai aprender, as respostas para alcançar o objetivo, não são pré-determinados. Os jogos educativos utilizam-se do cognitivismo, o aluno "aprende" através da busca, da descoberta e do raciocínio.

Os jogos educativos são uma área que pode tornar-se alvo de inúmeras pesquisas, principalmente os computadorizados, por estarem sendo utilizados em diversas escolas, muitas vezes atendendo apenas ao apelo de marketing imposto pelas outras escolas e pelos alunos, mas sem estarem inseridos em um projeto pedagógico, que leve em consideração os aspectos educativos dos software.
 
 

"Se o ensino for lúdico e desafiador, a aprendizagem prolonga-se fora da sala de aula, fora da escola, pelo cotidiano, até as férias, num crescendo muito mais rico do que algumas informações que o aluno decora porque vão cair na prova" [NET 92, p.43].  
 
 
3 Algoritmos Genéticos
 
 

Os algoritmos genéticos têm se mostrado recentemente como uma técnica eficaz de resolução de problemas de otimização. Os algoritmos genéticos imitam o processo de evolução natural para resolver problemas de otimização em uma aproximação Darwiniana de sobrevivência. Em um processo regido por seleção natural, populações competem umas com as outras para converterem-se em progenitores, em função de um valor chamado ajuste. Depois de selecionados os progenitores, aplicam-se uma série de funções denominadas operadores genéticos: mutação, inversão e cruzamento (crossover) [DAV 91].

Os algoritmos genéticos são utilizados, geralmente, para buscar uma solução "ótima" para um determinado problema. Pode-se citar, como exemplo de sua aplicação, o mercado de ações. Um algoritmo genético poderia ser utilizado para identificar que ações deveriam ser compradas ou vendidas, quando deveriam ser compradas ou vendidas, e em que quantidade, entre outros problemas. Os algoritmos genéticos criam várias soluções para um determinado problema e estas soluções evoluem, ou seja, o algoritmo genético imita o processo de evolução dos seres vivos.

Nos algoritmos genéticos as variáveis de indivíduos são codificadas em cadeias de longitude finita (formadas normalmente por dígitos binários) as quais são análogas aos cromossomos em um sistema biológico. Os algoritmos genéticos são procedimentos interativos que mantêm uma população de possíveis indivíduos. Cada passo interativo é chamado uma geração. O conjunto de indivíduos inicial, gerado aleatoriamente, é chamado população inicial [DAV 91].
 

Componentes de um Algoritmo Genético:
 

As principais características de um algoritmo genético são: possibilidade de manter uma população de soluções para um determinado problema; possuir um processo de seleção de indivíduos da população, baseado no grau de adaptação de cada indivíduo (fitness) e a existência de operadores genéticos, tais como mutação e crossover.

A população de soluções de um algoritmo genético é composta por cromossomos. Estes cromossomos são avaliados (selecionados) para identificar o grau de adaptação de cada um para encontrar a solução do problema. Esta função é denominada função de avaliação e resulta o fitness de cada cromossomo.

A cada iteração do algoritmo uma nova população é formada através da seleção dos indivíduos mais adaptados (cromossomos com maior fitness). Alguns membros desta nova população sofrem alterações, que são implementadas através da utilização dos operadores genéticos (mutação e crossover).

A mutação gera novos indivíduos (cromossomos) com pequenas modificações, enquanto que o crossover representa uma transformação de mais alta ordem. Após algumas iterações do algoritmo genético espera-se que o melhor indivíduo (o cromossomo com maior fitness) represente uma solução quase ótima, ou seja, o programa converge para uma solução ótima.

A estrutura básica de um algoritmo genético é composta por três módulos: o módulo de avaliação, o módulo de população e o módulo de reprodução. O módulo de avaliação é o que determina o grau de adaptação de cada indivíduo (cromossomo) ao problema que deve ser solucionado. O módulo de população é o responsável, primeiramente, por inicializar os cromossomos, gerando a população inicial de indivíduos. Normalmente, os cromossomos são compostos por strings de bits. O módulo de reprodução é o responsável pela aplicação dos operadores genéticos aos indivíduos da população (mutação e crossover).

3.1 A Utilização dos Algoritmos Genéticos no Desenvolvimento de Jogos: O Jogo do Pingüim e da Abelha
 
 

O Jogo do Pingüim e da Abelha possui a seguinte configuração: uma abelha, um pingüim, cubos de gelo e diversos diamantes. O comportamento da abelha consiste em perseguir o pingüim. A abelha precisa "empurrar" um cubo de gelo sobre o pingüim para vencer o jogo. Já o comportamento do pingüim é um pouco mais complexo: deve fugir da abelha e pegar todos os diamantes. O ambiente do jogo é composto por um quadro (mundo imaginário) e os componentes do jogo (abelha, pingüim, cubos de gelo e diamantes) estão dispostos em posições deste quadro. Tanto o pingüim como a abelha movem-se como se estivessem jogando numa grade, apenas para posições adjacentes às suas (isto no modelo proposto em [AGRE 87]).

No modelo implementado e relatado neste artigo, o pingüim e a abelha passaram a ter uma área de visão maior. Eles podem mover-se até quatro posições na grade. A cada interação, o pingüim dá um passo na grade e a abelha também. Este "passo" pode ser: para cima; para baixo; para a esquerda; para a direita; para a direita, acima, em sentido diagonal; para a esquerda, acima, em sentido diagonal; para a direita, abaixo,em sentido diagonal; para a esquerda, abaixo, em sentido diagonal.

O algoritmo genético foi utilizado para definir, a cada passo do jogo, qual a melhor posição de deslocamento da abelha e também do pingüim.

Para o Jogo do Pingüim e da Abelha definiu-se, inicialmente, o seguinte cromossomo, com 7 posições:
 

Onde:

a = Direção para onde o objeto deve se deslocar

b = Direção para onde o objeto está "olhando" (posicionado)

c = Quantas "casas" o objeto pode se mover na grade (a cada passo).
 
 

A direção para onde o objeto deve se deslocar (parte a do cromossomo) segue a lista de "passos" possíveis para o pingüim e/ou abelha, descritas anteriormente.

A direção para onde o objeto está "olhando" (parte b do cromossomo) auxilia na definição do fitness do cromossomo. Por exemplo, se a abelha está olhando para baixo e o pingüim está posicionado abaixo da mesma, este cromossomo terá um fitness mais alto, pois este "passo" da abelha pode fazer com que ela alcance seu objetivo, que é o de "atingir" o pingüim. O cálculo do fitness é feito através da direção para onde o objeto está "olhando" e também do número de "casas" que ele pode "andar", definido na parte c do cromossomo.

O algoritmo genético utilizado possui a seguinte seqüência de passos: 1) inicialização aleatória da população de cromossomos; 2) aplicação da função de avaliação; 3) aplicação da mutação e do crossover criando novos cromossomos; 4) aplicação da função de avaliação e inserção dos novos cromossomos na população.

Função de Avaliação:
 
 

A função de avaliação será definida a partir da posição do objeto. Por exemplo: para o pingüim, a melhor posição, dentre as selecionadas (dentre os cromossomos selecionados) pelo algoritmo genético, é a que possui um diamante ou está mais distante da abelha. Torna-se necessário, aqui, definir o ângulo de visão do pingüim: para onde está olhando e quanto ele consegue "enxergar". A partir disso, tem-se ou não a possibilidade de visualizar algum diamante ou a abelha e avaliar a melhor posição. Seguindo este pensamento, se o ângulo de visão da abelha não permite visualizar o pingüim, a melhor posição para ele deslocar-se é a mais próxima de um diamante, pois o objetivo do pingüim, no jogo descrito, é "pegar" todos os diamantes existentes.

A cada passo do jogo (movimento do pingüim e da abelha), tem-se uma nova população de cromossomos, que serão avaliados (retornando o fitness de cada cromossomo) e também sofrerão mutação e crossover, como descreve-se a seguir. A saída do algoritmo é a posição ótima para onde o objeto deve deslocar-se.
 
 

Mutação
 
  A taxa de mutação é definida pelo usuário, através da interface do jogo (que pode ser vista mais adiante). Geram-se números aleatórios para cada bit do cromossomo. Se este número aleatório for menor que a taxa de mutação estabelecida, este bit é passível de mutação.
 
Crossover
 
  Para a realização do crossover será utilizado o método de cruzamento entre os pais. Este cruzamento poderá ser de um ou dois pontos. O usuário, antes de dar início ao jogo, define se o pingüim e/ou a abelha vão utilizar o crossover de 1 ponto ou o de 2 pontos, através de option buttons dispostos na interface do jogo.

Para a seleção dos pais que irão sofrer o crossover utilizou-se a técnica da roleta. Inicialmente acumula-se o fitness de todos os cromossomos. A partir do fitness acumulado, geram-se números aleatórios no intervalo de zero até este fitness acumulado, para definir que cromossomo está mais próximo, ou dentro do intervalo deste número gerado. A partir disso, organiza-se a população em ordem decrescente do fitness e cruzam-se os pais pela disposição definida após a organização.
 
 

Exemplo de Crossover:

Cromossomo 5

Cromossomo 1

Cromossomo 3

Cromossomo 2
 
 

Exemplo de Crossover de 1 Ponto:

Pai 1: 1011 | 110 Filho 1: 1011001

Pai 2: 0110 | 001 Filho 2: 0110110
 
 

Exemplo de Crossover de 2 Pontos:

Pai 1: 10 |111 | 10 Filho 1: 1010010

Pai 2: 01 |100 | 01 Filho 2: 0111101

A implementação do jogo foi realizada através da linguagem Microsoft Visual Basic. Na figura a seguir é demonstrada a modelagem da interface do jogo.
 
 

Figura 1: Tela Principal do Jogo do Pingüim e da Abelha




Funcionamento do Jogo
 

Tanto a abelha quanto o pingüim podem mover-se pela tela (área de movimentação) de maneira aleatória ou através de um algoritmo genético. Isto é definido pelos option buttons existentes no lado direito da tela (conforme mostra a Figura 1). Além disso, o usuário pode definir o tipo de crossover de cada um dos elementos (1 ponto ou 2 pontos) e também a taxa de mutação.

Como informações de saída o usuário recebe o número de movimentos efetuados até que alguém vença o jogo (a abelha vence quando atinge o pingüim com um cubo de gelo; o pingüim, por sua vez, vence quando "pega" todos os diamantes) e também o número de diamantes que o pingüim pegou até o momento.
 
 

4 Uma Proposta de Utilização dos Algoritmos Genéticos no Desenvolvimento de Jogos Educativos Computadorizados
 

No Jogo do Pingüim e da Abelha demonstrado no exemplo anterior, o usuário não tem interação com os objetos do jogo, ou seja, o Pingüim e a Abelha movem-se automaticamente pelo ambiente do jogo, controlados pelo algoritmo genético definido. Torna-se necessário, então, definir um tipo de jogo onde o usuário possa interagir ativamente e que aproveite a abordagem dos algoritmos genéticos no desenvolvimento do mesmo.

Uma proposta que pode ser validada é a criação de um Jogo de Labirinto. Neste jogo, o usuário poderia construir um labirinto e um objeto (por exemplo, um robô), teria que percorrer este labirinto e encontrar a saída do mesmo. O caminho que este robô deve percorrer para encontrar a saída poderia ser controlado por um algoritmo genético. A Figura 2 mostra um exemplo de labirinto que poderia ser construído pelo usuário do jogo. Depois de construí-lo, o algoritmo genético deve controlar o objeto, identificando o caminho correto a ser seguido para alcançar o ponto de chegada.
 
 

Este jogo do labirinto poderia servir como estímulo à criatividade do aluno e também para o fortalecimento da descoberta e refinamento de estratégias de raciocínio, pelo fato de que o usuário deve construir um labirinto com caminhos bastante complexos para que consiga fazer com que o "robô" leve mais tempo para encontrar a saída. Além disso, pode servir também para estimular a noção espacial e desenvolver a coordenação motora através do desenho do labirinto.

Um outro exemplo que pode ser apresentado é a elaboração de um Jogo de Trânsito. Neste jogo, o usuário poderia definir um caminho, incluindo placas de sinalização, semáforos, faixas de pedestres, entre outros sinais de trânsito e o algoritmo genético poderia encontrar o caminho correto a seguir, para chegar a um ponto determinado. A diferença deste jogo para o anterior é que o algoritmo genético deve "respeitar" as leis de trânsito estabelecidas no jogo. Estas leis poderiam ser definidas pelo usuário do jogo. Este jogo, além de desenvolver e estimular o raciocínio também serviria para que o usuário aprendesse e colocasse em prática as leis de trânsito. A Figura 3, na próxima página, mostra um exemplo de caminho que poderia ser construído pelo usuário, no Jogo do Trânsito.

Nestes tipos de jogos, o usuário constrói um ambiente (caminho) pelo qual o "computador" deve seguir. A contribuição destes jogos para a aprendizagem reside no fato de que o usuário constrói mentalmente um ambiente e transfere-o para o computador. A principal vantagem de um jogo computadorizado, como os propostos acima, para a aprendizagem é a possibilidade que o usuário (aluno) tem em construir seu próprio "micromundo", construindo estratégias mentais que o levam a desencadear o raciocínio.
 

A aprendizagem, neste sentido, baseia-se na abordagem cognitivista, onde o professor propõe problemas aos alunos, sem ensinar-lhes as respostas. Uma das metodologias que pode ser empregada na abordagem cognitivista é a utilização de jogos que estimulem o pensamento lógico. Segundo Giraffa [GIR 95], "o aluno aprende, por si próprio, a conquistar as verdades, informações, modelos, etc., através da aquisição de instrumental lógico-racional" (p. 41).
 
 
 

5 Considerações Finais e Trabalhos Futuros
 

A utilização de jogos educativos computadorizados traz inúmeras vantagens à aprendizagem dos alunos, principalmente pelo fato de que os alunos "aprendem brincando". Cabe aos professores tirar proveito destes jogos como ferramenta de apoio ao processo de ensino e aprendizagem, tornando o aprendizado uma experiência mais agradável.
 
 

"... alguns programas são tidos como repetitivos e enfadonhos, cumpre estudar o caminho para se utilizar o grande potencial dos programas de lazer (joguinhos eletrônicos), também vinculados por este meio, em programas educacionais" [ADU 83, p. 52].   Os jogos podem apenas estimular a criatividade, atenção, memória, entre outras habilidades, como também "ensinar" conteúdos embutidos no jogo, como no caso do Jogo do Trânsito. Neste tipo de jogo, o aluno ganha com o aperfeiçoamento de suas estratégias de raciocínio e no entendimento do conteúdo, que no caso são as leis de trânsito. Segundo Piaget (apud [GRO s.d.]), através do jogo a criança sente uma razão intrínseca para exercitar sua inteligência e capacidade. As crianças podem reforçar conteúdos vistos em aula de uma maneira atraente e gratificante.

Como proposta de trabalhos futuros, destaca-se a implementação de um dos jogos propostos neste artigo, para realmente validar a utilização dos algoritmos genéticos na elaboração de jogos educativos computadorizados.
 
 

Referências
 

[ADU 83] ADUAN, Wanda Engel. O Computador na Educação: Herói ou bandido? Tecnologia Educacional, Rio de Janeiro: n. 52, p. 47-53, mai./jun. 1983.

[AGRE 87] AGRE, P. E.; CHAPMAN, D. Pengi: an implementation of a theory of activity. In: AAAI’87.

[ARA 92] ARAÚJO, Vania Carvalho de. O jogo no contexto da educação psicomotora. São Paulo: Cortez, 1992. 106p.

[CAM 95] CAMPOS, Márcia de Borba et alii. Hiperhistórias na Educação: Um meio de educação/reeducação psicomotora. VI Simpósio Brasileiro de Informática na Educação. Anais. Florianópolis: SBC-UFSC, 1995.

[COB 88] COBURN, Peter et alii. Informática na educação. Rio de Janeiro: Livros Técnicos e Científicos Editora, 1988. 298p.

[DAV 91] DAVIS, Lawrence. Handbook of genetic algorithms. New York: Van Nostrand Reinhold, 1991.

[FER 95] FERNANDES, Lúcio Dutra et alii. Jogos no Computador e a Formação de Recursos Humanos na Indústria. VI Simpósio Brasileiro de Informática na Educação. Anais. Florianópolis: SBC-UFSC, 1995.

[GIR 95] GIRAFFA, Lucia Maria Martins. Fundamentos de Teorias de Ensino-Aprendizagem e sua Aplicação em Sistemas Tutores Inteligentes. Porto Alegre: CPGCC-UFRGS, 1995. Trabalho Individual
.
[GRO s.d.] GROSSI, Esther Pillar (Org.). Escolas Infantis: Leitura e escrita. Erechim: Edelbra, s.d., 92p.

[NET 92] NETO, Ernesto Rosa. Laboratório de matemática. In: Didática da Matemática. São Paulo: Ática, 1992. 200p. p. 44-84.

[RIZ 88] RIZZO, Gilda. O Método Natural de Alfabetização. In: Alfabetização Natural. Rio de Janeiro: Francisco Alvez, 1988. p. 33-129.

[ROD 92] RODRIGUES, Maria. O desenvolvimento do pré-escolar e o jogo. São Paulo: Ícone, 1992. 70p.

[STA 91] STAHL, Marimar M. Ambientes de ensino-aprendizagem computadorizados: da sala de aula convencional ao mundo da fantasia. Rio de Janeiro: COPPE-UFRJ, 1991.

[VIE 94] VIEIRA, Clarice V. et alii. Brinquedo. Porto Alegre: Faculdade Porto-Alegrense de Educação Ciências e Letras, set. 1994. 12p.

[VYG 89] VYGOTSKY, L. S. O papel do brinquedo no desenvolvimento. In: A formação social da mente. São Paulo: Martins Fontes, 1989. 168p. p.106-118.