14
Centro Universitário Positivo - UnicenP
Núcleo de Ciências Exatas e Tecnológicas NCET
Engenharia da Computação
Paula Fernanda Fonseca
Jogo de Damas Embarcado
Curitiba
2005
2
Centro Universitário Positivo - UnicenP
Núcleo de Ciências Exatas e Tecnológicas NCET
Engenharia da Computação
Paula Fernanda Fonseca
Jogo de Damas Embarcado
Monografia apresentada à disciplina de
Projeto Final, como requisito parcial à
conclusão do Curso de Engenharia da
Computação.
Thomé
Curitiba
2005
Orientador:
Profª.
Adriana
3
4
TERMO DE APROVAÇÃO
Paula Fernanda Fonseca
Jogo de Damas Embarcado
Monografia aprovada como requisito parcial à conclusão do curso de Engenharia
da Computação do Centro Universitário Positivo, pela seguinte banca examinatória:
Professora Adriana Thomé - Orientadora
Professor Roberto Selow - Membro
Professor Edson Ferlin - Membro
Curitiba, 12 de Dezembro de 2005.
iv
5
v
6
AGRADECIMENTOS
A meus pais, Norberto José Fonseca e Simone Maciel Fonseca, pela
oportunidade que me ofereceram de cursar uma faculdade, pela confiança em mim
depositada. Muito obrigada pelo carinho, paciência, compreensão, afinal fiquei
estressada algumas vezes. Amo muito vocês.
A meu amor, Charles Stein, não apenas pelo incentivo, paciência, dedicação,
compreensão, durante esse ano, mas durante toda nossa formação acadêmica. Não foi
fácil chegarmos aqui, mas felizmente conseguimos.
A minhas irmãs por agüentarem minha bagunça constante em casa para que
pudesse produzir meu tabuleiro. Por toda ajuda e incentivo durante esse ano.
Agradeço a todos que direta ou indiretamente ajudaram-me a chegar aqui hoje.
Muito obrigada por tudo.
vi
7
vii
8
SUMÁRIO
LISTA DE FIGURAS .................................................................................................................................................. IX
LISTA DE TABELAS ................................................................................................................................................... X
LISTA DE SIGLAS ..................................................................................................................................................... XI
RESUMO .....................................................................................................................................................................XII
ABSTRACT .................................................................................................................................................................XII
1.INTRODUÇÃO..........................................................................................................................................................14
1.1.
1.2.
1.3.
1.4.
INTRODUÇÃO AO TEMA DO PROJETO............................................................................................................14
MOTIVAÇÃO .................................................................................................................................................14
SITUAÇÃO DO PROJETO NO CONTEXTO GERAL EM QUE ESTÁ INSERIDO .......................................................14
METAS A SEREM ALCANÇADAS ....................................................................................................................15
2.DESCRIÇÃO..............................................................................................................................................................15
3.ESTUDO TEÓRICO .................................................................................................................................................16
3.1.
INTELIGÊNCIAS MÚLTIPLAS .........................................................................................................................16
3.1.1. Tipos de inteligências múltiplas.............................................................................................................18
3.2.
JOGO DE DAMAS ...........................................................................................................................................20
3.2.1. História do Jogo .....................................................................................................................................20
3.2.2. Opiniões sobre o jogo.............................................................................................................................22
3.2.3. Regras do Jogo de Damas......................................................................................................................23
3.3.
ALGORITMO MINIMAX ..............................................................................................................................26
3.3.1. Acrescentando cortes alfa-beta..............................................................................................................32
3.4.
MICROCONTROLADOR 8051.........................................................................................................................38
3.5.
REED SWITCH ................................................................................................................................................38
3.6.
LED ...............................................................................................................................................................39
3.7.
DISPLAY LCD ...............................................................................................................................................39
4.ESPECIFICAÇÃO DO HARDWARE....................................................................................................................41
4.1.
4.2.
FUNÇÕES DO HARDWARE.............................................................................................................................41
COMPONENTES UTILIZADOS ........................................................................................................................42
5.ESPECIFICAÇÃO DO SOFTWARE .....................................................................................................................44
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
AMBIENTE E LINGUAGEM DE DESENVOLVIMENTO ......................................................................................44
INTERFACE COM O USUÁRIO .........................................................................................................................44
DIAGRAMA DE CONTEXTO ...........................................................................................................................44
DIAGRAMA DE FLUXO DE DADOS (DFD) ....................................................................................................44
DIAGRAMA DE ESTADOS ..............................................................................................................................44
FLUXOGRAMA ..............................................................................................................................................47
6.ESPECIFICAÇÃO DA VALIDAÇÃO DO PROJETO ........................................................................................49
7.RESULTADOS ..........................................................................................................................................................49
7.1.
7.2.
SOFTWARE .....................................................................................................................................................49
HARDWARE ....................................................................................................................................................54
8.CONCLUSÃO ............................................................................................................................................................56
9.REFERÊNCIAS BIBLIOGRÁFICAS ....................................................................................................................57
ANEXO 1 .......................................................................................................................................................................59
ANEXO 2 .......................................................................................................................................................................60
ANEXO 3 .......................................................................................................................................................................61
ANEXO 4 .......................................................................................................................................................................62
ANEXO 5 .......................................................................................................................................................................63
ANEXO 6 .......................................................................................................................................................................64
viii
9
LISTA DE FIGURAS
FIGURA 2.1
MÓDULOS DO HARDWARE ..........................................................................................................16
FIGURA 3.1
POSIÇÃO INICIAL DAS PEÇAS....................................................................................................23
FIGURA 3.2 - TOMADA .............................................................................................................................................25
FIGURA 3.3 (A) - TOMADA
FIGURA 3.4
FIGURA 3.3 (B) - TOMADA .......................................25
NOTAÇÃO DAS CASAS DO TABULEIRO ..................................................................................26
FIGURA 3.5 ...................................................................................................................................................................27
FONTE: RICH (1994) ..................................................................................................................................................27
FIGURA 3.6
BUSCA DE DUAS JOGADAS ..........................................................................................................28
FONTE: RICH (1994) ..................................................................................................................................................28
FIGURA 3.7 RETORNANDO OS VALORES DE UMA BUSCA EM DUAS JOGADAS ...............................28
FONTE: RICH (1994) ..................................................................................................................................................28
FIGURA 3.8
UM CORTE ALFA.............................................................................................................................33
FONTE: RICH (1994) ..................................................................................................................................................33
FIGURA 3.9
CORTES ALFA E BETA ..................................................................................................................34
FONTE: RICH (1994) ..................................................................................................................................................34
FIGURA 3.10
REED SWITCH .................................................................................................................................39
FIGURA 3.11
LED.....................................................................................................................................................39
FIGURA 3.12
DISPLAY LCD...................................................................................................................................40
FIGURA 4.1
CASA E PEÇA DO TABULEIRO ...................................................................................................42
FIGURA 5.1
TABULEIRO ......................................................................................................................................45
FIGURA 5.2
DIAGRAMA DE CONTEXTO.........................................................................................................45
FIGURA 5.3
DIAGRAMA DE FLUXO DE DADOS............................................................................................46
FIGURA 5.4
DIAGRAMA DE ESTADOS .............................................................................................................47
FIGURA 5.5 - FLUXOGRAMA..................................................................................................................................48
FIGURA 7.1
CRIANÇA REALIZANDO UMA JOGADA ..................................................................................53
FIGURA 7.2 JOGADA DO COMPUTADOR.........................................................................................................53
FIGURA 7.3
PLACA DE CIRCUITO DO TABULEIRO....................................................................................54
FIGURA 7.4
PLACA DE CIRCUITO DE PROCESSAMENTO........................................................................55
FIGURA 7.5
TABULEIRO ......................................................................................................................................55
FIGURA 7.6
TABULEIRO ......................................................................................................................................56
ix
10
LISTA DE TABELAS
TABELA 1
MÓDULOS LCD DISPONÍVEIS .......................................................................................................40
TABELA 2
PINAGEM DOS MÓDULOS LCD.....................................................................................................41
TABELA 3
COMPONENTES UTILIZADOS.......................................................................................................42
TABELA 4
CUSTO DO PROJETO........................................................................................................................43
x
11
LISTA DE SIGLAS
uc
Microcontrolador
QI
Coeficiente de Inteligência
xi
12
RESUMO
Este trabalho tem como objetivo o desenvolvimento de um tabuleiro de jogo de
damas. O software é baseado no algoritmo Minimax e utiliza uma função de heurística
posicional. O tabuleiro é composto por 64 casas, 24 peças, 12 brancas e 12 pretas, e
um display LCD. Todo o processamento do sistema é realizado no próprio tabuleiro,
através do microcontrolador da Philips.
xii
13
ABSTRACT
This work has as objective the development of a checkers. The software is based
on the Minimax algorithm, using the position heuristic function. The board is composed
by 64 squares, 24 pieces, 12 whites and 12 black, and a display LCD. All the system
processing is carried out in the tray, through the Philips microcontroller.
xiii
14
1. INTRODUÇÃO
1.1. Introdução ao tema do Projeto
O êxito de um bom desempenho escolar é resultado do aprimoramento de
algumas funções cerebrais importantes como: atenção, memória, percepção,
raciocínio, concentração. Isso pode ser conseguido por intermédio de metodologias
adequadas como, por exemplo: os jogos lúdicos, projetos de trabalho e a *caixa de
trabalho. Essas técnicas têm como objetivo estimular a criança a desenvolver, diante
de situações problemas, sua capacidades e habilidades intelectuais, sua criatividade e
iniciativa em busca de soluções. No entanto, sabemos que esse processo torna-se
viável quando apresentado de forma prazerosa, principalmente lúdica para essa
criança.
1.2. Motivação
A realização deste projeto originou-se da análise dessa realidade escolar. E,
dentro desse contexto pensou-se o desenvolvimento de um sistema computacional, a
criação de um jogo de damas, para auxiliar no aperfeiçoamento dessas estruturas
cerebrais, mais especificamente: concentração, percepção e raciocínio.
1.3. Situação do projeto no contexto geral em que está inserido
A inserção do jogo de damas, no âmbito educacional possibilita o
desenvolvimento de dois tipos de inteligência: a espacial e lógico
matemática,
destacando habilidades latentes e inerentes da criança. Sendo assim, é apropriado o
seu uso nessa área de atuação, pois ressalta de forma lúdica seu interesse.
Caixa de Trabalho - Visca idealizou a caixa de trabalho para se trabalhar com as dificuldades de aprendizagem e, para
isso, inspirou-se na caixa individual utilizada pelos terapeutas analista na Psicanálise de crianças. Ela seria composta de
brinquedos e materiais escolhidos para representarem o mundo interno das crianças, suas fantasias inconscientes frente
ao mundo (BARBOSA, 2000, p. 35).
15
1.4. Metas a serem alcançadas
Desenvolvimento de um tabuleiro de jogo de damas com 64 casas e 24 peças,
12 brancas e 12 pretas.
Cada casa preta deve conter um reed switch e um led. Cada peça, tanto as
brancas como as pretas, devem ter embutidas em sua base um imã, este será o
responsável pela ativação dos reed switch. Em um display aparecem as jogadas que o
computador deseja que a criança realize para ele e é mostra também quando uma
jogada foi realizada de forma errada.
2. DESCRIÇÃO
O sistema computacional em questão é composto por um tabuleiro com 64
casas e 24 peças, sendo 12 peças brancas e 12 peças pretas.
O processamento é realizado no tabuleiro através de um microcontrolador. O
hardware é composto por 3 módulos, como ilustra a figura 2.1:
Módulo de Entrada (Jogador 1) - onde o usuário movimenta as peças. A
movimentação de uma peça faz com que os reed switches mudem de estado,
permitindo saber qual delas foi movida;
Módulo de Processamento
Recebendo a saída proveniente do módulo de
entrada, o microcontrolador (uC P89C51) processa os dados e executa o
algoritmo MINIMAX gerando a saída para o próximo módulo;
Módulo de Saída (Jogador 2)
representa a jogada do computador. A casa da
qual o computador deseja mover a peça fica piscando e a casa para onde a
peça será movida também piscará até que o jogador realize esta jogada para
ele.
16
Figura 2.1
Módulos do Hardware
3. ESTUDO TEÓRICO
3.1. Inteligências Múltiplas
A Teoria das Inteligências Múltiplas, de Howard Gardner (1985) é uma alternativa
para o conceito de inteligência como uma capacidade inata, geral e única, que permite
aos indivíduos um desempenho, maior ou menor, em qualquer área de atuação. Sua
insatisfação com a idéia de QI e com visões unitárias de inteligência, que focalizam,
sobretudo, as habilidades importantes para o sucesso escolar, levou Gardner a
redefinir inteligência à luz das origens biológicas da habilidade para resolver
problemas. Através da avaliação das atuações de diferentes profissionais em diversas
culturas, e do repertório de habilidades dos seres humanos na busca de soluções,
culturalmente apropriadas, para os seus problemas, Gardner trabalhou no sentido
inverso ao desenvolvimento, retroagindo para eventualmente chegar às inteligências
que deram origem a tais realizações. Na sua pesquisa, Gardner estudou também:
(a) o desenvolvimento de diferentes habilidades em crianças normais e crianças
superdotadas;
(b) adultos com lesões cerebrais e como estes não perdem a intensidade de sua
produção intelectual, mas sim uma ou algumas habilidades, sem que outras
habilidades sejam sequer atingidas;
"Idiot savants" são idiotas incapazes de pensar racionalmente que, entretanto, têm memórias
prodigiosas que guardam tudo, completamente divorciadas da sua inteligência.
17
(c) populações ditas excepcionais, tais como *idiot-savants e autistas, e como os
primeiros podem dispor de apenas uma competência, sendo bastante
incapazes nas demais funções cerebrais, enquanto as crianças autistas
apresentam ausências nas suas habilidades intelectuais;
(d) como realizou o desenvolvimento cognitivo através dos milênios.
Psicólogo construtivista muito influenciado por Jean Piaget, Gardner distingue-se
dele na medida em que Piaget acreditava que todos os aspectos da simbolização
partem de uma mesma função semiótica, enquanto que ele acredita que processos
psicológicos independentes são empregados quando o indivíduo lida com símbolos
lingüísticos, numéricos gestuais ou outros. Segundo Gardner uma criança pode ter um
desempenho precoce em uma área (o que Piaget chamaria de pensamento formal) e
estar na média ou mesmo abaixo da média em outra (o equivalente, por exemplo, ao
estágio sensório-motor).
Gardner descreve o desenvolvimento cognitivo como uma capacidade cada vez
maior de entender e expressar significado em vários sistemas simbólicos utilizados
num contexto cultural, e sugere que não há uma ligação necessária entre a capacidade
ou estágio de desenvolvimento em uma área de desempenho e capacidades ou
estágios em outras áreas ou domínios. Num plano de análise psicológico, afirma
Gardner (1982), cada área ou domínio tem seu sistema simbólico próprio; num plano
sociológico de estudo, cada domínio se caracteriza pelo desenvolvimento de
competências valorizadas em culturas específicas.
Gardner sugere, ainda, que as habilidades humanas não são organizadas de forma
horizontal; ele propõe que se pense nessas habilidades como organizadas
verticalmente, e que, ao invés de haver uma faculdade mental geral, como a memória,
talvez existam formas independentes de percepção, memória e aprendizado, em cada
área
ou
domínio,
com
possíveis
semelhanças
entre
necessariamente com uma relação direta. (GAMA, 1998)
as
áreas,
mas
não
18
3.1.1. Tipos de inteligências múltiplas
Gardner identificou as inteligências lingüística, lógico-matemática, espacial,
musical, cinestésica, interpessoal e intrapessoal. Postula que essas competências
intelectuais são relativamente independentes, têm sua origem e limites genéticos
próprios e substratos neuroanatômicos específicos e dispõem de processos cognitivos
próprios. Segundo ele, os seres humanos dispõem de graus variados de cada uma das
inteligências e maneiras diferentes com que elas se combinam e organizam e se
utilizam dessas capacidades intelectuais para resolver problemas e criar produtos.
Gardner
ressalta
que,
embora
estas
inteligências
sejam,
até
certo
ponto,
independentes uma das outras, elas raramente funcionam isoladamente. Embora
algumas ocupações exemplifiquem uma inteligência, na maioria dos casos as
ocupações ilustram bem a necessidade de uma combinação de inteligências. Por
exemplo, um cirurgião necessita da acuidade da inteligência espacial combinada com a
destreza da cinestésica. A seguir, os tipos de inteligências são detalhados (GAMA,
1998):
Inteligência lingüística - Os componentes centrais da inteligência lingüística
são uma sensibilidade para os sons, ritmos e significados das palavras, além de uma
especial percepção das diferentes funções da linguagem. É a habilidade para usar a
linguagem para convencer, agradar, estimular ou transmitir idéias. Gardner indica que é
a habilidade exibida na sua maior intensidade pelos poetas. Em crianças, esta
habilidade se manifesta através da capacidade para contar histórias originais ou para
relatar, com precisão, experiências vividas.
Inteligência musical - Esta inteligência se manifesta através de uma habilidade
para apreciar, compor ou reproduzir uma peça musical. Inclui discriminação de sons,
habilidade para perceber temas musicais, sensibilidade para ritmos, texturas e timbre, e
habilidade para produzir e/ou reproduzir música. A criança pequena com habilidade
musical especial percebe desde cedo diferentes sons no seu ambiente e,
freqüentemente, canta para si mesma.
Inteligência lógico-matemática - Os componentes centrais desta inteligência
são descritos por Gardner como uma sensibilidade para padrões, ordem e
sistematização. É a habilidade para explorar relações, categorias e padrões, através da
19
manipulação de objetos ou símbolos, e para experimentar de forma controlada; é a
habilidade para lidar com séries de raciocínios, para reconhecer problemas e resolvêlos. É a inteligência característica de matemáticos e cientistas Gardner, porém, explica
que, embora o talento cientifico e o talento matemático possam estar presentes num
mesmo indivíduo, os motivos que movem as ações dos cientistas e dos matemáticos
não são os mesmos. Enquanto os matemáticos desejam criar um mundo abstrato
consistente, os cientistas pretendem explicar a natureza. A criança com especial
aptidão nesta inteligência demonstra facilidade para contar e fazer cálculos
matemáticos e para criar notações práticas de seu raciocínio.
Inteligência espacial - Gardner descreve a inteligência espacial como a
capacidade para perceber o mundo visual e espacial de forma precisa. É a habilidade
para manipular formas ou objetos mentalmente e, a partir das percepções iniciais, criar
tensão, equilíbrio e composição, numa representação visual ou espacial. É a
inteligência dos artistas plásticos, dos engenheiros e dos arquitetos. Em crianças
pequenas, o potencial especial nessa inteligência é percebido através da habilidade
para quebra-cabeças e outros jogos espaciais e a atenção a detalhes visuais.
Inteligência cinestésica - Esta inteligência se refere à habilidade para resolver
problemas ou criar produtos através do uso de parte ou de todo o corpo. É a habilidade
para usar a coordenação grossa ou fina em esportes, artes cênicas ou plásticas no
controle dos movimentos do corpo e na manipulação de objetos com destreza. A
criança especialmente dotada na inteligência cinestésica se move com graça e
expressão a partir de estímulos musicais ou verbais demonstra uma grande habilidade
atlética ou uma coordenação fina apurada.
Inteligência interpessoal - Esta inteligência pode ser descrita como uma
habilidade pare entender e responder adequadamente a humores, temperamentos
motivações e desejos de outras pessoas. Ela é melhor apreciada na observação de
psicoterapeutas, professores, políticos e vendedores bem sucedidos. Na sua forma
mais primitiva, a inteligência interpessoal se manifesta em crianças pequenas como a
habilidade para distinguir pessoas, e na sua forma mais avançada, como a habilidade
para perceber intenções e desejos de outras pessoas e para reagir apropriadamente a
partir dessa percepção. Crianças especialmente dotadas demonstram muito cedo uma
20
habilidade para liderar outras crianças, uma vez que são extremamente sensíveis às
necessidades e sentimentos de outros.
Inteligência intrapessoal - Esta inteligência é o correlativo interno da
inteligência interpessoal, isto é, a habilidade para ter acesso aos próprios sentimentos,
sonhos e idéias, para discriminá-los e lançar mão deles na solução de problemas
pessoais. É o reconhecimento de habilidades, necessidades, desejos e inteligências
próprias, a capacidade para formular uma imagem precisa de si próprio e a habilidade
para usar essa imagem para funcionar de forma efetiva. Como esta inteligência é a
mais pessoal de todas, ela só é observável através dos sistemas simbólicos das outras
inteligências, ou seja, através de manifestações lingüísticas, musicais ou cinestésicas.
3.2. Jogo de Damas
3.2.1. História do Jogo
A origem do Jogo de Damas perde-se na bruma dos tempos. Sabe-se que é
conhecido, desde os tempos imemoriais, no Extremo Oriente.
Nas escavações feitas no Vale do Rio Nilo, foram encontradas incrustações com
desenhos do tabuleiro e algumas pedras soltas, pelo que se pode afirmar que ele era
jogado no antigo Egito.
Assegura-se que o Jogo de Damas era conhecido no Egito desde a época de
Osortasen I, pois que nas paredes do palácio de Ramsés Meiamoun, Medineth-Habou,
existe um desenho que representa este Faraó jogando as Damas com uma de suas
mulheres.
Também, nos mausoléus de Saggarah, no Egito, se vêem tabuleiros de Damas.
Dois destes, que são da época dos Faraós, existem no Museu do Louvre, em Paris.
No British Museum, de Londres, conserva-se uma antiga caricatura, que
representa um leão e uma cabra, jogando as Damas.
21
Os gregos referindo-se aos tempos fabulosos, e apoiados em alguns dados de
Platão, ou talvez em sua exagerada fantasia, afirmavam que Mercúrio foi o inventor do
Jogo de Damas.
Homero, na Odisséia, apresenta dois pretendentes de Penélope jogando à porta
do palácio de Ulisses, o Pessoi (vocábulo grego que significa: jogo de cálculo), que é
parecido com o Jogo de Damas.
Posteriormente, jogou-se na Grécia o DIAGRISMA. Mais tarde aparece em
Roma o LUDUS
LATRUNCULORUM, modificação do DIAGRISMA dos gregos, pois
no jogo romano já se moviam as pedras, e, quando uma delas chegava a 1ª fila do
adversário, convertia-se em rainha ou pedra coroada (como no jogo moderno),
podendo se mover em todas as direções.
Supõe-se, portanto, que o Jogo de Damas clássicas é o mais antigo de todos
que
atualmente
se
praticam
no
mundo,
descendendo
do
LUDUS
LATRUNCULORUM, dos romanos.
Durante a Idade Média, o Jogo de Damas gozou de uma popularidade imensa
em quase toda a Europa.
Quanto ao nome pelo qual é conhecido atualmente, supõe-se que foi por muitos
séculos o passatempo predileto das Damas da nobreza, que o tinham por seu jogo
favorito, chegando este a familiarizar-se tanto com o belo sexo, que adquiriu o título de
Jogo de Damas.
A história bibliográfica do Jogo de Damas principia na Espanha, com o livro de
Antom Torquemana, intitulado: EL INGÉNIO Ó JUEGO DE MARRO DE PUNTA Ó
DAMAS
Valência, 1547.
Por esta razão os historiógrafos consideram este jogo como auxiliar
indispensável para a reconstrução e interpretação do jogo romano LUDUS
LATRUNCULORUM. (LANDIM)
22
3.2.2. Opiniões sobre o jogo
Existem inúmeras opiniões de escritores, professores, psicólogos, etc., a
respeito do Jogo de Damas. A seguir são apresentadas algumas delas:
A Baliza (Artigo publicado na BALIZA, Jornal Desportivo, Lisboa, 1946): "É
considerado, geralmente, o Jogo de Damas um desporto para distrair o espírito dos
aborrecimentos da vida. Alguns também o cultivam por gosto e para desenvolvimento
da mentalidade no exercício do cálculo. É uma maneira de ocupar o tempo e o espírito,
desviando-o doutras distrações, às vezes nocivas e sempre, mais ou menos
dispendiosas, sobretudo nos inertes e calamitosos tempos que vivemos".
Professor Doutor Carlos Sirtori (Médico e Director do Instituto Gaslini,
Génova, e Presidente da Fundação Carlos Erba, de Milão - ITÁLIA): "As crianças
devem jogar às Damas. Está demonstrado cientificamente que aos 5 ou 6 anos
qualquer criança, normalmente desenvolvida, está apta a conhecer as Regas do Jogo
de Damas. Este Jogo permite-lhe desenvolver plenamente a sua personalidade e dá,
além disso, aos seus Pais a possibilidade de julgar a inteligência e o caráter dos seus
filhos. É um jogo que ela aceita e depois deseja, porque lhe dá, também, o sentido das
primeiras competições mentais, das primeiras vitórias, dos primeiros contactos com o
velho tema de ganhar qualquer coisa aos outros, e de vencer, de se tornar forte,
autoritário. Em suma, um JOGO cheio de gratificações, porque antigo, mais antigo que
o xadrez, jogado até pelos faraós e conhecido de Homero e Platão. Por conseguinte,
temos um meio simples e seguro para analisar as nossas crianças, uma espécie de
teste global que as mães poderão aplicar largamente durante as férias".
Professor Doutor Marlon Tinsley (Professor catedrático de Matemática na
Universidade da Florida - Estados Unidos - e Campeão Americano do Jogo de Damas):
"As Regras do Jogo de Damas são tão simples que uma mente inculta julga,
naturalmente, que o Jogo de Damas é também muito simples. Mas é como na
Matemática: sistemas numéricos com as regras muito simples tornam-se nos mais
complexos cálculos. É por isso que quem não conheça o Jogo de Damas o considere
como um jogo de crianças e de velhos; mas a esses o professor de matemática sorri e
diz-lhes que muitas vezes uma grande parte da complexidade está escondida nas
coisas que à primeira vista parecem ser tranqüilas, modestas e simples".
23
Professor Richard Schmidt (Professor de Matemática e Director da Dublin
School - Escócia): "Para estimular e aguçar a inteligência nada há melhor que um bom
problema de Damas; é, por esse motivo, que obrigo os alunos do curso Secundário a
resolver diariamente problemas do Jogo de Damas".
3.2.3. Regras do Jogo de Damas
3.2.3.1.
Definições e objetivo
a) O Jogo de Damas se pratica entre dois parceiros, em tabuleiro quadrado, de
64 casas alternadamente claras e escuras, dispondo de 12 pedras brancas e 12 pretas.
b) O objetivo é capturar ou imobilizar as peças do adversário. O parceiro que o
conseguir ganha a partida.
3.2.3.2.
Do tabuleiro de damas
O tabuleiro deve ser colocado de modo que a casa angular à esquerda de cada
parceiro seja escura.
3.2.3.3.
Da posição das pedras
No início da partida, as pedras devem ser colocadas no tabuleiro sobre as casas
escuras, da seguinte forma: nas três primeiras filas horizontais, as pedras brancas; e,
nas três últimas, as pedras pretas, como mostra a figura 3.1.
Figura 3.1
Posição Inicial das Peças
24
3.2.3.4.
Da marcha da pedra
a) A pedra movimenta-se em diagonal, sobre as casas escuras, para frente, e
uma casa de cada vez.
b) A pedra que atingir a oitava casa adversária, parando ali, será promovida a
"dama", peça de movimento mais amplos que a simples pedra. Assinala-se a dama
sobrepondo-se, à pedra promovida, outra da mesma cor.
3.2.3.5.
Da marcha da dama
A dama pode mover-se de determinada casa para qualquer outra, não obstruída,
situada na mesma diagonal. A diagonal está obstruída, para a dama, quando nela
houver uma ou mais peças da mesma cor, ou duas ou mais peças adversárias em
casas contíguas.
3.2.3.6.
Da tomada
a) Quando na casa contígua a uma pedra houver uma peça adversária, com
uma casa imediata vaga, na mesma diagonal, a pedra toma-la-á passando para a
citada casa vaga. Assim, a pedra toma para frente e para trás, sendo este o único
movimento retrógrado da pedra. Se, após a tomada de uma pedra, a circunstância se
repetir, a pedra continuará a tomada no mesmo lance, chamando-se a este movimento
"tomada em cadeia". Como ilustrado na figura 3.2.
b) Se, as diagonais da casa de partida da dama, houver uma peça adversária
cuja casa imediata esteja vaga, a dama toma-la-á passando para qualquer casa vaga
após a peça tomada. A dama também toma em cadeia.
c) A tomada é obrigatória. A pedra e a dama têm o mesmo valor para tomar ou
ser tomada. Se, no mesmo lance houver mais de um modo para tomar, é obrigatório
executar o lance que tome o maior número de peças (Lei da maioria), como mostram
as figuras 3.3(a) e 3.3(b).
25
Figura 3.2 - Tomada
Figura 3.3 (a) - Tomada
3.2.3.7.
Figura 3.3 (b) - Tomada
Da saída
As brancas têm sempre a saída, isto é, o primeiro lance da partida. Determina-se
por sorteio ou convenção, para a primeira partida; nas seguintes, as brancas cabem
alternadamente aos dois parceiros.
3.2.3.8.
Da execução dos lances
a) O lance é executado quando se leva diretamente à nova casa a peça tocada;
a peça deve ser imediatamente solta.
b) O lance está completo quando a mão do jogador tiver largado a peça, ao
movê-la de uma casa para outra.
26
3.2.3.9.
Da notação
a) As oito colunas verticais, da esquerda para a direita, para as brancas, são
designadas pelas letras: a, b, c, d, e, f, g, h. Ver figura 3.4.
Figura 3.4
Notação das Casas do tabuleiro
b) As oito travessas horizontais são numeradas de 1 a 8, a contar da base das
brancas.
c) O lance será indicado pela casa de saída da peça e a casa de chegada.
3.3. Algoritmo MINIMAX
O procedimento de busca minimax é um procedimento de busca de
profundidade, de profundidade limitada. A idéia é iniciar na posição corrente e usar o
gerador de movimentos plausíveis para gerar o conjunto de possíveis posições
sucessoras. Agora pode-se aplicar a função de avaliação estática a essas posições e
simplesmente escolher a melhor. Depois disso, pode-se retornar esse valor à posição
inicial para representar a avaliação que foi feita dela. A posição inicial é tão boa para o
jogador 1 quanto a posição gerada pelo melhor movimento que se pode executar a
seguir. Aqui assumi-se que a função de avaliação estática retorna valores altos para
indicar situações boas para o jogador 1, portanto a meta é maximizar o valor da função
de avaliação estática na próxima posição do tabuleiro.
Um exemplo dessa operação é mostrado na figura 3.5 . Ela assume uma função
de avaliação estática que retorna valores que variam de 10 a 10, sendo que 10 indica
vitória para jogador 1, -10, uma vitória do oponente, e 0, um empate. Como o objetivo é
27
maximizar o valor da função heurística, escolhe-se mover para B. Retornando o valor
de B para A, concluí-se que o valor de A é 8, sabe-se que pode-se mover para uma
posição cujo valor seja 8.
A
B
C
D
(8)
(3)
(-2)
Figura 3.5
Fonte: RICH (1994)
Mas, como também sabe-se que a função de avaliação estática não é totalmente
precisa, gostaria-se de levar a busca para além de uma jogada. Isso pode ser muito
importante, por exemplo, em um jogo de xadrez, durante uma troca de peças. Depois
do movimento do jogador 1, a situação pode parecer muito boa, mas, analisando um
movimento à frente, vê-se que uma das peças também será capturada e, portanto, a
situação não é tão favorável quanto parecia. Então é útil olhar-se à frente para ver o
que acontecerá com cada uma das novas posições no próximo movimento a ser feito
pelo oponente. Em vez de aplicar a função de avaliação estática a cada uma das
posições que acabou-se de gerar, aplica-se o gerador de movimentos plausíveis,
gerando um conjunto de posições sucessoras para cada posição do tabuleiro. Se
parasse aqui, depois de ter analisado duas jogadas à frente, poderia-se aplicar a
função de avaliação estática a cada uma dessas posições, conforme mostra a figura
3.6.
Agora é necessário levar em conta que o oponente escolherá quais movimentos
sucessores serão feitos e, assim, qual valor terminal deverá ser retornado ao nível
seguinte. Suponha que tenha-se feito o movimento B. Então o oponente terá de
escolher entre os movimentos E, F e G. O objetivo do oponente é minimizar o valor da
função de avaliação, então podemos esperar que ele escolha o movimento F. Isto
significa que, se for feito o movimento B, a posição real em que o jogador 1 estará um
movimento mais tarde será ruim. Isto se aplica apesar da possível configuração
representada pelo nó E, que é boa para o jogador 1. Mas, como esse nível não é sua
28
vez de jogar, ele não poderá escolher aquele movimento. A figura 3.7 mostra o
resultado da propagação dos novos valores da árvore acima. No nível que representa a
escolha do oponente, o valor mínimo foi escolhido e retornado. No nível que representa
a escolha do jogador 1, o valor máximo foi escolhido.
A
B
C
D
E
F
G
H
I
J
K
(9)
(-6)
(0)
(0)
(-2)
(-4)
(-3)
Figura 3.6 Busca de duas jogadas
Fonte: RICH (1994)
A
B
Jogada de
maximização
C
Jogada de
minimização
D
E
F
G
H
I
J
K
(9)
(-6)
(0)
(0)
(-2)
(-4)
(-3)
Figura 3.7 Retornando os valores de uma busca em duas jogadas
Fonte: RICH (1994)
Uma vez retornados os valores da segunda jogada, fica claro que o movimento
correto para o jogador 1 nesse primeiro nível, dadas as informações que tem-se
disponíveis, é C, já que não há nada que o oponente possa fazer para produzir um
valor pior que
2. Esse processo pode ser repetido para quantas jogadas o tempo
permitir, e as avaliações mais precisas podem ser usadas para escolher o movimento
correto no primeiro nível. O revezamento entre maximização e minimização em jogadas
29
alternadas quando as avaliações estão sendo devolvidas corresponde às estratégias
opostas de dois jogadores, e dá a esse método o nome de minimax.
Depois de descrever informalmente a operação do procedimento minimax, ele
será agora descrito com precisão. Ele é um procedimento recursivo direto, que toma
por base dois procedimentos auxiliares, específicos do jogo que está sendo jogado:
1. GERMOV (Posição, Jogador)
O gerador de movimentos plausíveis, o
qual retorna uma lista de nós que representam os movimentos que podem
ser feitos por Jogador em Posição. Chamamos os dois jogadores de
JOGADOR-UM e JOGADOR-DOIS; em um programa de xadrez,
podemos usar nomes BRANCAS e PRETAS.
2. ESTÁTICA (Posição, Jogador)
A função de avaliação estática, que
retorna um número que representa a qualidade de Posição do ponto de
vista de jogador.
Como em qualquer programa recursivo, um problema crítico com relação ao
projeto de procedimento MINIMAX é quando parar a recursão e simplesmente chamar
a função de avaliação estática. Há vários fatores que podem influenciar essa decisão.
Eles incluem:
Um lado ganhou?
Quantas jogadas já explorarmos?
Quão promissor é esse caminho?
Quanto tempo ainda temos?
Qual o grau de estabilidade dessa configuração?
No procedimento MINIMAX genérico discutido aqui, apela-se a uma função,
PROFUNDO-O-SUFICIENTE, que assume avaliar todos esses fatores e retornar
VERDADEIRO se a busca tiver de ser interrompida no nível corrente, ou FALSO, nos
casos contrários. A simples implementação que será dada à função PROFUNDO-OSUFICIENTE assumirá dois parâmetros: Posição e Profundidade. Ela ignorará o
parâmetro Posição e simplesmente retornará VERDADEIRO caso o parâmetro
Profundidade exceder o valor da constante de interrupção.
30
Um problema que surge na definição de MINIMAX como procedimento recursivo
é que ele precisa retornar não um, mais dois resultados:
O valor do caminho escolhido.
O caminho em si. Retorna-se o caminho inteiro, embora provavelmente
apenas o primeiro elemento, que representa o melhor movimento a partir
da posição atual, seja realmente necessário.
Assume-se que MINIMAX retorna uma estrutura que contém ambos os
resultados e que temos duas funções, VALOR e CAMINHO, que extraem os
componentes separados.
Já que definiu-se o procedimento MINIMAX como função recursiva, precisa-se
também especificar como ele deverá ser chamado inicialmente. O movimento precisa
de três parâmetros, uma posição de tabuleiro, a atual profundidade da busca e o
jogador. Portanto, a chamada inicial para computar o melhor movimento a partir da
posição CORRENTE deverá ser MINIMAX (CORRENTE, 0, JOGADOR-UM) caso seja
a vez do JOGADOR-UM, ou MINIMAX (CORRENTE, 0, JOGADOR-DOIS) caso seja a
vez do JOGADOR-DOIS.
Algoritmo: MINIMAX (Posição, Profundidade, Jogador)
1. Se PROFUNDO-O-SUFICIENTE (Posição, Profundidade), então retorne a
estrutura
VALOR = ESTÁTICA (Posição, Jogador)
CAMINHO = nil
Isto indica que não há nenhum caminho saindo desse nó e que seu valor
é aquele determinado pela função de avaliação estática.
2. Caso contrário, gere mais uma camada da árvore chamando a função
GERMOV (Posição, Jogador) e atribuindo a SUCESSORES a lista que
ela retorna.
31
3. Se SUCESSORES estiver vazio, então não há nenhum movimento a
fazer. Retorne a mesma estrutura que terá sido retornada se
PROFUNDO-O-SUFICIENTE retornasse VERDADEIRO.
4. Se SUCESSORES não estiver vazio, então examine cada elemento e
mantenha registro do melhor. Isto é feito assim:
Inicialize MELHOR-CONTAGEM com o valor mínimo que ESTÁTICA
consiga retornar. Ele será utilizado para refletir o melhor placar que pode
ser atingido por qualquer elemento de SUCESSORES.
Para cada elemento SUC de SUCESSORES, faça o seguinte:
(a) Atribua a RESULTADO-SUC
MINIMAX (SUC, Profundidade + 1, OPOSTO (Jogador))3
Esta chamada recursiva na verdade executará a exploração de SUC.
(b) Atribua a NOVO-VALOR
VALOR (RESULTADO-SUC). Isto
reflitirá os méritos da posição do ponto de vista oposto ao do
próximo nível mais baixo.
(c) Se NOVO-VALOR > MELHOR-CONTAGEM, então encontramos
um sucessor melhor que qualquer outro já tenha sido examinado
até o momento. Registre este fato:
I. Atribua a MELHOR-PLACAR NOVO-VALOR.
II. O melhor caminho conhecido agora é de CORRENTE para
SUC e depois para o caminho apropriado abaixo de SUC,
conforme
determinado
pela
MINIMAX.
Portanto,
atribua
chamada
recursiva
MELHOR-CAMINHO
de
o
resultado da inclusão de SUC à frente de CAMINHO
(RESULTADO-SUC).
32
5. Agora que todos os sucessores foram examinados, sabemos o valor de
Posição e também do caminho que deve ser seguido para chegar a esse
parâmetro. Então retorne a estrutura
VALOR = MELHOR-CONTAGEM
CAMINHO = MELHOR-CAMINHO
Quando a primeira chamada de MINIMAX retorna, o melhor movimento de
CORRENTE é o primeiro elemento de CAMINHO. Para ver como esse procedimento
funciona, você deve acompanhar uma execução na árvore de jogo mostrada na figura
3.6.
O procedimento MINIMAX que foi descrito é muito simples. Porém seu
desempenho pode ser significativamente melhorado com certos refinamentos, como
ilustrado no item a seguir.
3.3.1. Acrescentando cortes alfa-beta
O procedimento minimax é um processo em profundidade. Um caminho é
explorado durante o tempo permitido, a função de avaliação estática é aplicada às
posições do jogo na última etapa do caminho, e o valor pode então ser passado
caminho acima, um nível de cada vez. Uma das boas coisas dos procedimentos em
profundidade é que é sempre possível melhorar sua eficiência usando técnicas
ramificar-e-podar, em que soluções parciais claramente piores do que soluções
conhecidas podem ser logo abandonadas. Essa estratégia é chamada de poda alfabeta. Ela requer a manutenção de dois valores-limite, um representando um limite
inferior para o valor que pode, em última análise, ser atribuído a um nó de maximização
(este valor é chamado alfa) e outro representando um limite superior para outro valor
que pode ser atribuído a um nó de minimização (este valor é chamado de beta).
Para ver como funciona o procedimento alfa-beta, considere o exemplo
mostrado na figura 3.8. Depois de examinar o nó F, sabe-se que o oponente tem
garantida uma contagem de 5 ou menos em C (já que o oponente é o jogador de
minimização). Mas sabe-se também que tem-se garantida uma contagem de 3 ou mais
no nó A, que pode-se atingir movendo-se para B. Qualquer outro movimento que
33
produza uma contagem menor que 3 é pior do que o movimento para B, e pode-se
ignora-lo. Depois de examinar apenas F, tem-se certeza de que um movimento para C
é pior (ele será menor ou igual a 5) independentemente da contagem do nó G. Assim,
não precisa preocupar-se em explorar G. É claro que a eliminação de um nó pode
parecer não justificar o acompanhamento dos limites e sua verificação, mas,
explorando-se essa árvore até seis jogadas, então poderia-se eliminar não um único
nó, mas toda uma árvore com três jogadas de profundidade.
A
Jogada de maximização
B
(3)
C
( < -5)
Jogada de minimização
D
E
F
(3)
(5)
(-5)
G
Figura 3.8 Um corte alfa
Fonte: RICH (1994)
Para ver como os dois limites, alfa e beta, podem ser usados, considere o
exemplo mostrado na figura 3.9. Durante a busca dessa árvore, toda subárvore
encabeçada por B é procurada e descobre-se que em A pode-se esperar uma
contagem de pelo menos 3. Quando esse valor de alfa é passado para F, ele permite
ignorar a exploração de L, por quê? Depois que K é examinado, vê-se que I tem
garantido uma contagem máxima de 0, o que significa que F tem garantido um mínimo
de 0. Mas esse valor é menor que o valor de alfa, e, portanto, mais nenhuma
ramificação de I precisa ser considerada. O jogador de maximização já sabe que não
deve escolher mover para C e depois par I porque, com esses movimentos, a
contagem resultante não será melhor que 0, e com um movimento para B ele pode
alcançar uma contagem de 3. Agora será visto como o valor de beta pode ser usado.
Depois de impedir a continuidade da exploração de I, J é examinado, produzindo um
valor de 5, que é designado como valor de F (já que ele é o máximo entre 5 e 0). Esse
valor torna-se o valor de beta no nó C. Ele indica que C tem garantida uma contagem
de 5 ou menos. Agora precisa-se expandir G. Primeiro M é examinado. Seu valor, 7, é
34
passado de volta para G como valor experimental. Mas agora 7 é comparado a beta
(5). Ele é maior e o jogador com vez de jogar no nó C está tentando minimizar. Então
esse jogador não vai escolher G, porque a contagem obtida seria pelo menos 7, e há
um movimento alternativo para F, que levará a uma contagem de 5. Desse modo não é
necessário explorar nenhuma outra ramificação de G.
A
Jogada de maximização
Jogada de
minimização
C
B
D
E
(3)
(5)
H
G
F
(4)
Jogada de maximização
I
J
M
N
(5)
(7)
(8)
Jogada de minimização
K
L
(0)
(7)
Figura 3.9 Cortes alfa e beta
Fonte: RICH (1994)
Com este exemplo, vê-se que, nos níveis de maximização, pode-se descartar
em movimento logo cedo se ficar claro que seu valor será menor do que o limite atual,
enquanto, nos níveis de minimização, a busca terminará se forem descobertos valores
maiores que o limite atual. Mas descartar um movimento possível através de um
jogador de maximização na verdade significa interromper a busca em um nível de
minimização. Olhe novamente o exemplo da figura 3.8. Uma vez determinado que C é
um mau movimento a partir de A, não pode-se pensar em explorar G, nem nenhum
outro caminho, no nível de minimização abaixo de C. Então alfa e beta são realmente
usados para encerrar uma busca num nível de minimização quando um valor menor
que alfa for encontrado, e no nível de maximização quando um valor maior que beta for
35
encontrado. Interromper a busca em um nível de maximização quando um valor alto é
encontrado pode parecer, a princípio, um contra-senso, mas, se você tiver em mente
que só quer-se chegar em um determinado nó de um nível de maximização se o
jogador de minimização no nível acima escolher aquele nó, então todo o processo
passa a fazer sentido.
Depois de ilustrar a operação da poda alfa-beta, pode-se agora explorar como o
procedimento MINIMAX pode ser modificado para explorar essa técnica. Observe que,
nos níveis de maximização, apenas beta é usado para determinar onde a busca deve
ser interrompida, e, nos níveis de minimização, apenas alfa é usado. Mas, nos níveis
de maximização, também precisamos saber o valor de alfa porque, quando MINIMAX é
chamado recursivamente, um nível de minimização é criado e ele precisa ter acesso a
alfa. Conseqüentemente, nos níveis de maximização, alfa precisa ser conhecido não
apenas para poder ser usado, mas também para poder ser passado árvore abaixo. O
mesmo se aplica aos níveis de minimização com relação a beta. Cada nível precisa
receber ambos valores, um para ser usado e outro para ser passado para o próximo
nível usar.
O procedimento MINIMAX, como está, não precisa tratar os níveis de
maximização e minimização diferentemente, porque ele simplesmente inverte o sinal
das avaliações toda vez que os níveis mudam. Seria bom se uma técnica semelhante
pudesse ser encontrada para não ter que escrever procedimentos separados para os
dois jogadores. Isto é fácil. Em vez de fazer referência a alfa e beta, o MINIMAX usa
dois valores, USAR-LIMITE e PASSAR-LIMITE. USAR-LIMITE é usado para calcular
cortes. PASSAR-LIMITE é meramente passado para o próximo nível como USARLIMITE. É claro que USAR-LIMITE também precisa ser passado para o próximo nível,
mas ele será passado como PASSAR-LIMITE, e então pode ser passado para o
terceiro nível abaixo, novamente como USAR-LIMITE, e assim por diante. Assim como
os valores precisam ter seus sinais invertidos toda vez que eram passados de um nível
para outro, também os limites precisam ter seus sinais invertidos. Isto é necessário
para que, independentemente do nível da busca, um teste maior que determine se um
limite foi ou não cruzado. Agora ainda é preciso que não haja diferença entre código
exigido nos níveis de maximização e aquele exigido nos níveis de minimização.
36
Acabou-se de descrever como os valores alfa e beta são passados árvores
abaixo. Além disso, precisa-se decidir como eles devem ser atribuídos. Para ver como,
vamos voltar primeiro ao exemplo simples da figura 3.8. Em um nível de maximização,
como o do nó A, alfa é definido como sendo o valor do melhor sucessor já encontrado.
(Observe que, embora nos níveis de maximização beta seja usado para determinar
cortes, é alfa que tem seu valor calculado. Desse modo, em qualquer nível USARLIMITE será verificado para cortes e PASSAR-LIMITE será utilizado para poder ser
usado mais tarde). Mas, se o nó de maximização não estiver no topo da árvore,
precisa-se considerar também o valor de alfa vindo de um nó mais alto. Para ver como
isto funciona, olhe novamente a figura 3.9 e considere o que acontece no nó F. Atribuise o valor 0 ao nó I com base no exame do nó K. Este é, até o momento, o melhor
sucessor de F. mas, numa exploração anterior da subárvore encabeçada por B, alfa
recebeu o valor 3, e foi passado árvore abaixo de A até F. Alfa não deve receber 0,
com base no nó I. Ele deve ser mantido com o valor 3, para refletir o melhor movimento
encontrado até então em toda a árvore. Assim, vê-se que, em um nível de
maximização, alfa deve receber o valor que tinha no próximo nível mais alto de
maximização ou o melhor valor encontrado nesse nível, o que quer que seja maior.
Declaração correspondente pode ser feita sobre beta em níveis de minimização. De
fato, o que queremos dizer é que, em qualquer nível, PASSAR-LIMITE deve sempre
ser o máximo entre o valor herdado de cima e o melhor movimento encontrado em seu
nível Se PASSAR-LIMITE for atualizado, o novo valor deve ser propagado tanto para
os níveis inferiores quanto para os níveis superiores, de forma a sempre refletir o
melhor movimento encontrado na árvore.
Neste ponto, nota-se que é feito, para calcular PASSAR-LIMITE, a mesma coisa
que foi feito em MINIMAX para calcular MELHOR-CONTAGEM. Poderíamos também
eliminar MELHOR-CONTAGEM e deixar PASSAR-LIMITE atuando em seu lugar.
Com essas observações, pode-se descrever a operação da função MINIMAX-AB, que requer quatro argumentos. Posição, Profundidade, Usar-Limite e Passar-Limite.
A chamada inicial, para escolher um movimento para JOGADOR-UM na posição
ATUAL, deve ser MINIMAX-A-B (CORRENTE, 0, JOGADOR-UM, valor máximo que
ESTÁTICA pode calcular, valor mínimo que ESTÁTICA pode calcular).
37
Estes valores iniciais de Usar-limite e Passar-Limite representam os piores
valores que cada lado pode atingir.
Algoritmo: MINIMAX-A-B (Profundidade, Jogador, Usar-Limite, PassarLimite)
1. Se PROFUNDO-O-SUFICIENTE (Posição, Profundidade), então retorne a
estrutura
VALOR = ESTÁTICA (Posição, Jogador);
CAMINHO = nil
2. Caso contrário, gere mais uma jogada da árvore chamando a função
GERMOV (posição, Jogador) e atribuindo a SUCESSORES a lista
retornada.
3. Se SUCESSORES estiver vazio, não há movimentos a serem feitos;
retorne a mesma estrutura que seria retornada caso PROFUNDO-OSUFICIENTE tivesse retornado VERDADE.
4. se SUCESSORES não estiver vazio, então examine cada elemento e
acompanhe o melhor deles. Isto é feito da seguinte maneira:
Para cada elemento SUC de SUCESSORES:
(a) Atribua RESULTADO-SUC
MINIMAX-A-B (SUC, Profundidade + 1, OPOSTO(Jogador), - PassarLimite, - Usar-Limite).
(b) Atribua NOVO-VALOR
VALUE (RESULT-SUC).
(c) Se NOVO-VALOR > Passar-Limite, então encontramos um sucessor
melhor que qualquer outro examinado até o momento. Registre o fato
fazendo o seguinte:
I. Atribua Passar-Limite NOVO-VALOR.
38
II. O melhor caminho conhecido é agora de CORRENTE para SUC e
depois para o caminho apropriado, conforme determinado pela
chamada
recursiva
de
MINIMAX-A-B.
Ajuste
MELHOR-
PERCURSO para o resultado da inclusão de SUC á frente de
CAMINHO (RESULTADO-SUC).
(d) Se Passar-Limite (refletindo o melhor valor atual) não for melhor que
Usar-Limite, então deve-se parar de examinar essa ramificação. Mas
tanto os limites quanto os valores foram invertidos. Portanto, se PassarLimite = Usar-Limite, então retorne imediatamente com o valor
VALOR = Passar-Limite
CAMINHO = MELHOR-CAMINHO
5. Retorne a estrutura
VALOR = Passar-Limite
CAMINHO = MELHOR-PERCURSSO
3.4. Microcontrolador 8051
O 8051 é um microcontrolador rápido com clock de 12MHz, sendo que existem
versões de até 30MHz, fornecidas por outros fabricantes, e suas características de
hardware e software permitem usá-lo como um poderoso controlador, sobretudo em
sistemas de lógica seqüencial e combinatória.
Nesse projeto será utilizado o microcontrolador da philips, o P89C51RD2, por
possuir uma capacidade de 64Kbytes de memória flash.
3.5. Reed Switch
É uma pequena ampola de vidro que contém em seu interior duas lâminas de
ferromagnético bem próximas uma da outra. Aproximando-se um imã do reed switch as
lâminas se encostam fechando contato. Como mostrado na figura 3.10.
39
Figura 3.10
Reed Switch
3.6. Led
Led é a sigla de Light-Emitting Diode (diodo emissor de luz). É um semicondutor,
com junção P-N. Quando recebe corrente elétrica o diodo acende. Funciona com baixa
tensão, cerca de 2.5 volts, e corrente, cerca de 10mA. Como mostrado na figura 3.11.
Figura 3.11
Led
3.7. Display LCD
Os
módulos
LCD
são
interfaces
de
saída
muito
útil
em
sistemas
microprocessados. Estes módulos podem ser gráficos e a caracter. A figura 3.12
mostra um display de caracter.
Os módulos LCD gráficos são encontrados com resoluções de 122x32, 128x64,
240x64 e 240x128 dots pixel, e geralmente estão disponíveis com 20 pinos para
conexão. Os LCD comuns (tipo caracter) são especificados em número de linhas por
colunas e são encontrados nas configurações previstas na Tabela 1.
40
Figura 3.12
Tabela 1
Display LCD
Módulos LCD disponíveis
Os módulos podem ser encontrados com LED backlight (com uma iluminação de
fundo) para facilitar as leituras durante a noite. Neste caso, a alimentação deste led fazse normalmente pelos pinos 15 e 16 para os módulos comuns e 19 e 20 para os
módulos gráficos, sendo os pinos 15 e 19 para ligação ao anodo e os pinos 16 e 20
para o catodo. A corrente de alimentação deste led varia de 100 a 200mA, dependendo
do modelo.
Estes módulos utilizam um controlador próprio, permitindo sua interligação com
outras placas através de seus pinos, onde deve ser alimentado o módulo e interligado o
barramento de dados e controle do módulo com a placa do usuário. Naturalmente que
além de alimentar e conectar os pinos do módulo com a placa do usuário deverá haver
41
um protocolo de comunicação entre as partes, que envolve o envio de bytes de
instruções e bytes de dados pelo sistema do usuário.
Assim como em um rádio relógio todo módulo LCD permite um ajuste na
intensidade da luz emitida ou ajuste de contraste, isto é possível variando-se a tensão
no pino 3. A Figura 1 mostra um circuito típico e recomendado pela maioria dos
fabricantes para efetuar este ajuste. Alguns fabricantes recomenda o uso de um
resistor de 4K7
em série com o potenciômetro de 10K .
A Tabela 2 descreve cada pino do módulo ou do display para conexão deste a
outras placas:
Tabela 2
Pinagem dos módulos LCD
4. ESPECIFICAÇÃO DO HARDWARE
4.1. Funções do Hardware
O tabuleiro contém em cada uma de suas casas pretas um reed switch e um led.
Cada peça do jogo, tanto as pretas como as brancas, tem embutida em sua base um
imã. Isso pode ser visualizado na figura 4.1.
42
Figura 4.1
Casa e Peça do tabuleiro
O tabuleiro contém também um display que mostra tanto as jogadas realizadas
pela criança com as do computador.
4.2. Componentes Utilizados
A tabela 1.3 mostra os componentes utilizados para o desenvolvimento do
projeto.
Tabela 3
Componentes utilizados
Componente
Quantidade
Microprocessador da família 8051 (P89C51RD2)
1
Reed Switch
64
Leds
32
Imãs
24
Latch 74HC573
6
Display LCD
1
Decodificador 74LS138
1
Max232
1
Porta lógica 74LS04
1
DM7406
2
74LS14
2
Bateria 6 volts
1
Placa Perfurada
1
Placa Fenolite
1
Diodo 1N4007
32
Demais componentes (resistores, capacitores, chaves, etc)
vários
43
4.3. Tabela de Custos
A tabela 4 mostra o custo do projeto com componentes e mão-de-obra utilizada.
Tabela 4
Custo do Projeto
Descrição
Qtde
Custo Unitário
Total
Microprocessador da família 8051
1
R$ 60,00
R$ 60,00
Reed Switch
64
R$ 1,40
R$ 89,60
Leds
32
R$ 0,15
R$ 4,80
Imãs
24
R$ 1,90
R$ 45,60
Latch 74HC573
6
R$ 0,86
R$ 5,76
Display LCD
1
R$ 19,80
R$ 19,80
Decodificador 74LS138
1
R$ 0,78
R$ 0,78
Max232
1
R$ 2,91
R$ 2,91
Porta lógica 74LS04
1
R$ 0,84
R$ 0,84
DM7406
2
R$ 1,32
R$ 2,64
74LS14
2
R$ 0,56
R$ 1,12
Placa Perfurada
1
R$ 18,00
R$ 18,00
Placa Fenolite
1
R$ 45,12
R$ 45,12
Bateria 6 volts
1
R$ 17,25
R$ 17,25
Diodo 1N4007
32
R$ 0,05
R$ 1,60
(P89C51RD2)
Demais Componentes
Mão-de-Obra (aproximadamente
720 horas
R$ 50,00
R$ 5,00
R$ 3600
TOTAL
3920,22
6 horas por dia, durante 6 meses)
44
5. ESPECIFICAÇÃO DO SOFTWARE
5.1. Ambiente e Linguagem de desenvolvimento
A linguagem utilizada para o desenvolvimento do software foi o C e o ambiente
de desenvolvimento utilizado foi o Keil uVision.
5.2. Interface com o usuário
A interface com o usuário é feita através do tabuleiro, como mostra a figura 5.1.
O usuário realiza sua jogada e fica aguardando o tabuleiro mostrar-lhe, através
do display e dos led s contidos em cada casa, qual é a sua jogada. O usuário deve
então retirar a peça da casa onde o led esta piscando e colocá-la na casa em que o led
acendeu. O jogo só continuará quando o usuário confirmar a jogada que lhe foi
solicitada.
5.3. Diagrama de Contexto
A figura 5.2 mostra o diagrama de contexto do sistema. Esse diagrama mostra o
relacionamento entre as entidades externas e o software.
5.4. Diagrama de Fluxo de Dados (DFD)
A figura 5.3 mostra o diagrama de fluxo de dados do sistema. O DFD é uma
forma gráfica de mostrar as funções que compõem o sistema.
5.5. Diagrama de Estados
A figura 5.4 mostra o diagrama de estados do sistema. Mostra os diferentes
estados de um Objeto durante sua vida, e o estímulo que faz com que o Objeto mude
seu estado.
45
Figura 5.1
Figura 5.2
Tabuleiro
Diagrama de Contexto
46
Figura 5.3
Diagrama de Fluxo de Dados
47
Figura 5.4
Diagrama de Estados
5.6. Fluxograma
A figura 5.5 mostra o fluxograma do sistema. No inicio a criança realiza uma
jogada, então é feita uma leitura do estado do tabuleiro para saber se houve alguma
mudança. Enquanto uma mudança não for detectada o programa ficará preso
realizando sucessivas leituras do tabuleiro. Detectada a mudança verifica se a jogada é
valida, se não for pede para criança jogar novamente, caso contrário verifica se as
peças do computador acabaram. Se acabaram a criança ganha o jogo se não monta-se
a árvore do Minimax para escolher qual é a melhor jogada a ser realizada para o
computador, enviando para o display qual é a linha e coluna da casa origem e a linha e
coluna da casa destino que a criança deve mover. Verifica-se se a criança realizou a
jogada corretamente para o computador se sim verifica se as peças da criança
acabaram para verificar se ele ganhou o jogo, caso contrário manda a criança jogar.
48
Figura 5.5 - Fluxograma
49
6. ESPECIFICAÇÃO DA VALIDAÇÃO DO PROJETO
A validação ocorrerá com crianças das séries iniciais do ensino fundamental. A
fim de, observar as suas reações frente situações-problemas geradas nessa interação.
Diante dessas reações irão demonstrar suas capacidades de raciocínio, habilidades e
destreza procurando alternativas adequadas para solucioná-las.
7. RESULTADOS
7.1. Software
Para o desenvolvimento do software inicialmente pensou-se em fazer uma
implementação dinâmica, pois o MINIMAX é um algoritmo de busca em profundidade
sendo necessário montar uma árvore a cada jogada com uma profundidade préestabelecida, porém por limitação do compilador, que permite apenas 2K de código
hex, isso não foi possível. Testes realizados, utilizando o debuger do próprio
compilador e também fisicamente no tabuleiro, mostraram que o compilador poderia
estar se perdendo na hora de montar o código hex, no debuger do compilador ele
realizava o que era esperado, porém quando gravado no microcontrolador não ocorria
o mesmo resultado. Isso pode ter sido causado devido as inúmeras alocações de
memória que ocorrem durante a montagem da árvore.
A seguir é mostrado o código implementado para a estrutura árvore.
// Inicializa a árvore
void initArvore(Arvore *arvore)
{
arvore->tamanho = 0;
arvore->raiz = NULL;
}
// Destrói a árvore removendo todos os nós
void delArvore(Arvore *arvore)
{
removeNoArvore(arvore, NULL);
}
// remove todos os nós da árvore
// Insere um nó como filho do nós especificado. Se i nó especificado == NULL,
insere a raiz
50
// (somente se a árvore estivar vazia). Retorna 0, se tudo OK, - 1 se erro.
unsigned int insereNo(Arvore *arvore, No *no, unsigned int *conteudo, int peso)
{
No *temp, **posicao;
if (no == NULL)
{
if (arvore->tamanho > 0)
return -1;
posicao = &arvore->raiz;
}
else
{
posicao = &no->filho;
// se tem mais irmãos, posiciona posicao no último
while (*posicao != NULL)
posicao = &(*posicao)->prox;
// pega o proximo
}
if ( (temp = (No*) malloc(sizeof(No)) ) == NULL)
return -1;
temp->cont = (void *)conteudo;
temp->pai = no;
temp->filho = NULL;
temp->prox = NULL;
temp->peso = peso;
*posicao = temp;
arvore->tamanho++;
return 0;
}
// Remove a subárvore enraizada como filha do nó especificado
// Se no == NULL, remove todos os nós da árvore
void removeNoArvore(Arvore *arvore, No *no) reentrant
{
No **posicao;
if (arvore->tamanho == 0)
return;
// Término da recursão
if (no == NULL)
posicao = &arvore->raiz;
else
posicao = &no->filho;
if (*posicao != NULL)
{
removeNoArvore(arvore, *posicao);
removeProxNoArvore(arvore, *posicao);
51
free( (*posicao)->cont );
free(*posicao);
*posicao = NULL;
arvore->tamanho--;
// remove o filho
// mais velho
}
return;
}
void removeProxNoArvore(Arvore *arvore, No *no) reentrant
{
No **p;
p = &no->prox;
if (*p != NULL)
{
removeProxNoArvore(arvore, *p);
free( (*p)->cont );
free(*p);
arvore->tamanho--;
}
}
Pensou-se então em uma outra alternativa para a implementação do algoritmo, a
implementação estática. Esta mostrou-se eficaz não apresentando nenhum problema
para compilar no debug e gravar no microcontrolador para rodar o programa.
Conseguindo-se então realizar jogadas satisfatórias. A seguir um trecho da
implementação estática.
// A partir do tabuleiro raiz verifica quais serão as possiveis jogadas que poderão
ser realizadas pelo computador
void criaJogadas(void)
{
unsigned char data i, data j, data cont;
int data peso;
melhorPeso = -9999;
for (i = 1; i <= 7; i++)
{
if (i % 2 == 0)
j = 1;
else
j = 2;
for (; j <= 8; j+=2)
{
if (getTabuleiro(i, j, tabuleiro) == PeaoPreto)
{
if (j != 1)
52
{
if ((getTabuleiro(i+1,j-1,tabuleiro)==PeaoBranco) &&
(getTabuleiro(i+2, j-2, tabuleiro) == Vazia) )
{
copiaDadosTabuleiro(tabuleiro, raiz);
cont = getTabuleiro(i, j, raiz);
setTabuleiro(i, j, raiz, Vazia);
setTabuleiro(i+1, j-1, raiz, Vazia);
setTabuleiro(i+2, j-2, raiz, cont);
copiaDadosTabuleiro(raiz, melhorTabuleiro);
brancas--;
return;
}
if (getTabuleiro(i+1, j-1, tabuleiro) == Vazia)
{
copiaDadosTabuleiro(tabuleiro, raiz);
cont = getTabuleiro(i, j, raiz);
setTabuleiro(i, j, raiz, Vazia);
setTabuleiro(i+1, j-1, raiz, cont);
peso = calculaPeso();
if (melhorPeso < peso)
{
melhorPeso = peso;
copiaDadosTabuleiro(raiz, melhorTabuleiro);
}
}
}
if (j != 8)
{
if ( (getTabuleiro(i+1, j+1, tabuleiro) == PeaoBranco) &&
(getTabuleiro(i+2, j+2, tabuleiro) == Vazia) )
{
copiaDadosTabuleiro(tabuleiro, raiz);
cont = getTabuleiro(i, j, raiz);
setTabuleiro(i, j, raiz, Vazia);
setTabuleiro(i+1, j+1, raiz, Vazia);
setTabuleiro(i+2, j+2, raiz, cont);
copiaDadosTabuleiro(raiz, melhorTabuleiro);
brancas--;
return;
}
if (getTabuleiro(i+1, j+1, tabuleiro) == Vazia)
{
copiaDadosTabuleiro(tabuleiro, raiz);
cont = getTabuleiro(i, j, raiz);
setTabuleiro(i, j, raiz, Vazia);
setTabuleiro(i+1, j+1, raiz, cont);
peso = calculaPeso();
53
if (melhorPeso < peso)
{
melhorPeso = peso;
copiaDadosTabuleiro(raiz, melhorTabuleiro);
}
}
}
}
}
}
Para verificar o perfeito funcionamento da implementação dinâmica seria preciso
comprar a licença do compilador para realizar os testes necessários e verificar se esse
era o problema.
A figura 7.1 mostra uma jogada realiza da pela criança e figura 7.2 mostra a
jogada que o computador pediu para a criança realizar em resposta a do adversário.
Figura 7.1
Criança realizando uma jogada
Figura 7.2 Jogada do computador
54
7.2. Hardware
Para o desenvolvimento do hardware foi desenvolvida uma placa de circuito
impresso, onde foram colocados os reed switchs, os leds as latchs de controle dos
leds, das colunas e linhas, os open collectors e outros componentes como resistores e
diodos. A figura 7.3 mostra como ficou a placa montada.
Figura 7.3
Placa de circuito do tabuleiro
Para o processamento desenvolveu-se uma placa com o microcontrolador, onde
é possível realizar sua gravação via porta serial, a placa contem também o controle de
contraste do display, um regulador de tensão que converte a tensão da entrada da
bateria de 6, 9 ou 12V para 5V, um decodificador de endereços e os schmitt trigger e
uma porta not. A figura 7.4 mostra a placa montada.
As figuras 7.5 e 7.6 mostram como ficou o tabuleiro montado.
55
Figura 7.4
Placa de circuito de processamento
Figura 7.5
Tabuleiro
56
Figura 7.6
Tabuleiro
8. CONCLUSÃO
Durante o projeto muitos problemas surgiram para o desenvolvimento do
software. A limitação na geração do código hex foi fator primordial, fazendo com que a
estratégia adotada inicialmente para a implementação do MINIMAX fosse alterada no
decorrer do desenvolvimento. Outro ponto que dificultou a implementação do algoritmo
foi a quantidade de memória RAM do microcontrolador que era muito pequena, fazendo
com que fosse implementado somente um nível da árvore. Mesmo diante desses
problemas o software desenvolvido apresentou um bom desempenho quando testado.
O hardware apresentou instabilidade com relação aos reed switches. Isso
dificultou a identificação das peças nas casas. Ora as peças tinham que ser colocadas
no centro da casa para serem detectadas, ora não. Foi sugerida a colocação de mais
um sensor em cada casa para ver se esse problema seria resolvido, porém isso
melhorou para alguns casos outros permaneceram iguais.
57
Muito ainda tem que ser feito para um perfeito funcionamento do tabuleiro:
mudar de microcontrolador ou fazer um banco de memória, comprar a licença do
compilador para que a geração do código hex seja ilimitada, estudar a possibilidade de
acrescentar mais reeds switches por casas ou trocar de sensor.
Apesar
dos
contratempos
e
problemas
ocorridos
no
decorrer
do
desenvolvimento do projeto, este apresentou um desempenho satisfatório, podendo ser
comprovado na visita feita a Instituição de Ensino Positivo Júnior, onde crianças da 2ª e
3ª séries puderam testar o funcionamento e desempenho do jogo.
9. REFERÊNCIAS BIBLIOGRÁFICAS
CARNEIRO, S. Iniciação ao Jogo de Damas. Ed. Presença, 4ª edição, 1994.
RICH, E. Inteligência Artificial. Ed. Makron Books, 2ª edição, 1994.
ANTUNES, C. As Inteligências Múltiplas e seus Estímulos, Ed. Papirus, 8ª edição,
2002.
BARBOSA, Laura Monte Serrat. Caixa de trabalho uma ação psicopedagógica
proposta pela Epistemologia Convergente, in Psicopedagogia e Aprendizagem.
Coletânea de reflexões. Curitiba, 2002.
LUGER, F. Inteligência Artificial. Ed. Bookman, 4ª edição.
RUSSELL, S. Inteligência Artificial. Ed. Campus, tradução da 2ª edição.
Fleury, C. Display LCD. 1996
JÚNIOR, V. P. S. Aplicações Práticas do Microcontrolador 8051. Ed. Érica, 7ª Edição.
Philips
Semiconductors.
04/07/2005
<http://www.semiconductors.philips.com>
Acesso
em:
58
Guilherme,
T.
Federação
Portuguesa
de
Damas:
Opiniões.
Disponível
em
<http://fpdamas.home.sapo.pt/opina.htm>. Acesso em: 20 mar. 2005.
Gama, M. C. S. S. A Teoria das Inteligências Múltiplas e suas implicações para
Educação.
Disponível
em
<http://www.homemdemello.com.br/psicologia/intelmult.html>. Acesso em: 20 mar.
2005.
Laudares, F. Revista Brasileira de Ensino de Física: Usando sensores magnéticos em
um trilho de ar. Disponível em: <http://www.scielo.br/scielo.php > . Acesso em: 8 abr.
2005.