Instituto Superior Técnico
Licenciatura em Engenharia Informática e de Computadores
Procura e Planeamento
1o¯
Projecto
Semestre de 2004/2005
O objectivo deste projecto é desenvolver um programa que resolva problemas de uma
versão modificada do Shisen-Sho recorrendo a várias técnicas de procura, efectuando
uma comparação entre o seu funcionamento e desempenho.
Apresentação do jogo
O Shisen-Sho 1 (Figura 1) é um jogo do estilo Mahjongg cujo objectivo é remover
todas as peças do tabuleiro. Duas peças só podem ser removidas se estiverem reunidas
duas condições:
1. As peças são iguais;
2. As peças podem ser ligadas com até três linhas (formando ângulos de 90o entre
elas) que não se sobreponham a outras peças.
Através da observação da Figura 1 verifica-se que alguns dos movimentos permitidos
são a remoção dos char6 na última linha (primeira e terceira colunas) ou dos char8
na terceira linha. Exemplos de movimentos não permitidos são a remoção dos char7
na primeira coluna e na primeira linha (são necessárias 4 linhas para unir as duas
peças) ou a remoção dos circle2 na quinta coluna (não existe um caminho livre
entre as peças). Os alunos são aconselhados a experimentarem o jogo Shisen-Sho de
modo a familiarizarem-se com esta regra e adquirir conhecimento heurı́stico para o
trabalho.
À semelhança do que acontece por exemplo com as cartas, as peças do Shisen-Sho
pertencem a determinados naipes. Assim, vão ser considerados os seguintes naipes:
Characters, Bamboos, Circles, Dragons, Seasons e Flowers 2 . A Tabela 1 mostra as
peças que devem ser consideradas no jogo e os seus respectivos naipes. Um jogo não
tem necessariamente que conter todas as peças.
1
Os screenshots apresentados foram retirados do jogo Shisen-Sho 1.5.0 da distribuição de Linux
Fedora Core 2.
2
Há ainda quem considere um naipe adicional, designado Winds.
2
Figura 1: Um tabuleiro de Shisen-Sho.
Naipe
Characters
Bamboos
Circles
Dragons
Seasons
Flowers
Peças
char1, char2, char3, char4, char5,
char6, char7, char8, char9
bamboo1, bamboo2, bamboo3, bamboo4, bamboo5,
bamboo6, bamboo7, bamboo8, bamboo9
circle1, circle2, circle3, circle4, circle5,
circle6, circle7, circle8, circle9
red-dragon, white-dragon, green-dragon
autumn-tree, spring-tree
mum, orchid, bamboo, plum
Tabela 1: Lista de naipes e peças do Shisen-Sho
3
A versão do Shisen-Sho que vamos considerar usa um sistema de pontuação em que a
eliminação de um par de peças resulta na atribuição de pontos. O número de pontos
obtidos com a remoção de um par corresponde ao produto do peso do naipe pelo
número de pares que faltam remover. Os pesos de cada naipe podem ser consultados
na Tabela 2.
P ontuacaoi = P eso(N aipe(P eca)) ∗ N umeroP aresF altaRemoveri
(1)
Por exemplo, se tivermos um tabuleiro de dimensão 14x6 (ou seja com 42 pares) e na
primeira jogada eliminarmos um par de cı́rculos, obtemos uma pontuação de 2*41=82
na jogada corrente.
Naipe
Character
Circle
Bamboo
Dragon
Flowers
Seasons
Peso
1
2
3
4
5
6
Tabela 2: Pesos de cada naipe a considerar
Para além da pontuação que se vai acumulando à medida que os pares de peças vão
sendo removidos, há ainda a considerar o bónus no caso de se conseguir remover
todas as peças do tabuleiro. Nestas condições a pontuação corrente é multiplicada
por 2. Neste problema, a escolha da ordem com que se eliminam os pares de peças é
fundamental para a obtenção de uma solução de qualidade.
Trabalho a desenvolver
O projecto deve ser feito por grupos de dois alunos. Não se aceitam, sob nenhum
pretexto, grupos de três ou mais alunos. Para os alunos com avaliação em regime M,
o projecto é individual.
O projecto é constituı́do por três partes:
1. Escolha e implementação das estruturas de dados relevantes para a representação do domı́nio apresentado
2. Implementação de heurı́sticas e estratégias que permitam a resolução de problemas de Shisen-Sho.
3. Comparação das várias estratégias de procura utilizadas para resolver os problemas.
4
Código Lisp fornecido
Para a realização deste projecto devem ser utilizados os algoritmos de procura,
desenvolvidos em ANSI Common Lisp, disponı́veis no site da cadeira. O código
fornecido encontra-se no ficheiro procura.lisp. Este contém a implementação de
vários algoritmos de procura. O funcionamento dos mesmos encontra-se descrito em
procura.txt. O mais importante é compreender para que servem, não perceber
exactamente como é que as funções estão definidas.
É ainda fornecido código (ficheiro freecode.lisp) que permite testar, dado um tabuleiro e duas posições, se existe um caminho livre entre elas usando no máximo três linhas ou não. A descrição do modo de uso deste código está no ficheiro freecode.txt.
Implementação
A implementação do algoritmo deve ser efectuada na linguagem LISP (ou CLOS).
A função seguinte deve, obrigatoriamente, ser definida com o nome, lista de argumentos e valor de retorno aqui especificados:
• solve-shisen: Esta função recebe um tabuleiro no formato descrito em seguida
e retorna os seguintes valores:
– A lista com as peças removidas do tabuleiro pela ordem mais adequada
(formato descrito em seguida);
– A configuração final do tabuleiro;
– O tempo gasto na procura;
– O número de nós gerados;
– O número de nós expandidos.
Formato do Tabuleiro
A função solve-shisen recebe, como argumento, a configuração do tabuleiro a resolver. Esse argumento deve ser um array bi-dimensional de dimensão arbitrária em
que uma casa não ocupada no tabuleiro é representada por nil. Uma casa que corresponde a uma peça é representada pelo sı́mbolo de keyword :<nome da peça>. Os
nomes das peças são aqueles que estão indicados na coluna Peças da Tabela 1. Por
exemplo, :char1, :char2, :bamboo7, :autumn-tree, :circle5, etc.
Um exemplo de um tabuleiro muito simples, é o seguinte:
(defconstant prob1
#2A((:char1 :bamboo1 :plum :plum)
(:char2 :bamboo2 :char1 :mum)
(:mum :char2 :bamboo1 :bamboo2)))
5
Representação dos Resultados
A lista de remoção das peças que será retornada pela função solve será constituı́da
por listas de dois elementos em que cada elemento tem as coordenadas de uma das
peças do par removido. As coordenadas de uma peça são uma lista de 2 inteiros não
negativos que representam respectivamente a linha e a coluna da peça (à primeira
linha/coluna corresponde o valor 0). A seguinte lista resolve o problema prob1:
(((0
((0
((0
((1
((1
((2
2)
0)
1)
1)
0)
0)
(0
(1
(2
(2
(2
(1
3))
2))
2))
3))
1))
3)))
O primeiro par removido é o plum na primeira linha.
O programa entregue deve estar devidamente testado e compilar e correr sem necessidade de alterações no interpretador CMUCL em UNIX/LINUX (por exemplo, no
MEGA). Toda e qualquer alteração necessária para que o programa funcione será
penalizada com um valor.
Análise de Resultados
Devem ser testadas todas as técnicas de procura fornecidas no ficheiro “procura.lisp”.
Adicionalmente, novas estratégias que facilitem a resolução dos problemas podem ser
desenvolvidas. Estas podem incluir variações aos algoritmos básicos de procura, novos algoritmos de procura, estratégias hı́bridas, macro-operadores, sub-objectivos,
etc. A análise do problema e dos primeiros resultados obtidos deverá fornecer indicadores quanto a abordagens válidas. Os alunos deverão desenvolver pelo menos uma
abordagem distinta das que estão implementadas no ficheiro procura.lisp. Esta
abordagem até pode apenas consistir em modificações do ficheiro procura.lisp, desde
que devidamente justificadas e analisadas.
Para as técnicas de procura informadas, são necessárias heurı́sticas. Devem ser apresentadas pelo menos três heurı́sticas de desempenho relevante. Essas heurı́sticas
devem, tanto quanto possı́vel, basear-se em ideias distintas (heurı́sticas que variam
apenas em constantes, por exemplo, são consideradas a mesma heurı́stica).
O desempenho dos vários algoritmos de procura utilizados, bem como das heurı́sticas
e das estratégias desenvolvidas deve ser discutido no relatório, fazendo uma comparação dos resultados obtidos para alguns problemas de Shisen-Sho. Não é necessária nem desejável a apresentação exaustiva no corpo do relatório dos resultados
para todos os problemas considerados. A discussão deve limitar-se a problemas que
6
salientem caracterı́sticas ou limitações relevantes do trabalho desenvolvido. Os alunos são encorajados a criar novos problemas, para além dos fornecidos como exemplo,
que sejam adequadas para ilustrar aspectos interessantes da discussão.
O relatório do projecto deve incluir ainda:
• A descrição das estruturas de dados desenvolvidas e as razões subjacentes ao
seu desenvolvimento;
• A descrição das heurı́sticas desenvolvidas e as razões subjacentes ao seu desenvolvimento;
• A descrição das estratégias implementadas e as razões subjacentes ao seu desenvolvimento;
• As opções tomadas durante o desenvolvimento do projecto;
• Uma discussão sobre a forma de conseguir obter melhores resultados, indicando
genericamente o tipo de heurı́sticas/estratégias a desenvolver para isso.
Ainda quanto ao relatório, convém salientar que a legibilidade do mesmo (para a qual
contribuem não só o layout como a correcção ortográfica a construção das frases e
a fluidez do discurso) é de importância capital para a correcta compreensão do seu
conteúdo. Devem evitar-se frases complexas (a utilização da voz passiva, de duplas
negativas, etc.). Todas as figuras e gráficos apresentados devem ser legı́veis e estar
adequadamente legendados.
Alunos com avaliação em regime M
Os alunos com avaliação em regime M devem efectuar o projecto individualmente.
Alternativamente, podem apresentar ao corpo docente da cadeira a descrição de um
novo domı́nio para o projecto. Este será aprovado se considerado de complexidade
e relevância suficientes. A apresentação de propostas pode ser efectuada até uma
semana após a data de disponibilização do presente enunciado.
Entrega dos Projectos e Prazos
Entrega Intercalar
A entrega intercalar será feita no dia 27 de Novembro até às 15h. Esta entrega deve
incluir um relatório muito simples em formato texto (uma página A4, no máximo)
que descreva o trabalho realizado até ao momento. Para além do ficheiro txt com o
relatório, deve ser enviado por e-mail para [email protected] o código desenvolvido.
7
Nesta entrega intercalar deverão estar a funcionar as procuras não informadas, bem
como as procuras informadas do ficheiro procura.lisp. Nesta fase basta existir apenas
uma heurı́stica implementada. A entrega intercalar terá um peso de 20% na nota
final do projecto.
Entrega Final
O projecto deve ser entregue até às 15 horas do dia 11 de Dezembro de 2004 na
portaria do INESC-ID e deverá constar do seguinte:
• Uma versão do projecto entregue on-line. O código desenvolvido em cada projecto será executado para verificação da sua correcção. Por este motivo, é
extremamente importante que a função pedida neste enunciado exista e siga a
interface definida. Não é necessário entregar o ficheiro procura.lisp se este
não tiver sofrido alterações.
Oportunamente, serão dadas mais indicações sobre a forma de entrega dos
projectos por via electrónica.
• Uma listagem completa do código do projecto devidamente comentada e paragrafada (Nota: o tipo de letra utilizado na listagem deve ser monospace, como,
por exemplo, Courier ou Monaco);
• Um relatório do projecto, cujo formato será oportunamente fornecido pelo corpo
docente da cadeira.
A listagem e o relatório do projecto devem ser entregues dentro de uma capa ou
encadernados, apresentando visivelmente o grupo, número e nome dos alunos a que
corresponde. Projectos que não sejam entregues nestas condições serão penalizados
com três valores.
Projectos iguais, ou muito semelhantes, serão classificados com 0 (zero) valores. O
corpo docente da cadeira será o único juiz do que se considera ou não copiar num
projecto.
Critérios de avaliação
Os factores mais importantes para a classificação do projecto são:
• Execução correcta e elegância do programa.
• Eficiência das estruturas de dados escolhidas para a representação do problema.
• Qualidade das heurı́sticas e estratégias desenvolvidas.
• Qualidade do relatório descrevendo o trabalho desenvolvido e os resultados e
conclusões obtidos.
8
Novidades do Projecto
No caso de haver novidades relativas ao projecto, estas serão afixadas na página da
cadeira, pelo que esta página deve ser visitada com frequência.