xistoso / iaproject Goto Github PK
View Code? Open in Web Editor NEWLe Project for thaz twenties. The 58000 return
Le Project for thaz twenties. The 58000 return
Este selector recebe um tabuleiro
, um inteiro
correspondente ao número da linha e um inteiro
correspondente ao número da coluna, e devolve o valor lógico verdade
se essa posição estiver
preenchida, e falso
caso contrário.
Task of: #5 2.1.2 Tipo tabuleiro
dá jeito como função auxiliar para o codigo ficar legivel.
Este teste recebe dois tabuleiro
, e devolve o valor lógico verdade
se os dois tabuleiro
forem
iguais (i.e. tiverem o mesmo conteúdo), e falso
caso contrário.
Task of: #5 2.1.2
Este construtor recebe um inteiro
correspondente à posição da coluna mais à esquerda a partir
da qual a peça vai ser colocada, e um array
com a configuração da peça a colocar, e devolve uma
nova acção.
Task of: #1
Na parte final do projecto, é obrigatório os alunos compararem as diferentes variantes das procuras,
algoritmos e heurísticas usadas para resolver o jogo do Tetris especificado, e perceberem as diferenças entre elas. Para isso deverão medir vários factores relevantes, e comparar os algoritmos num conjunto significativo de exemplos. Deverão também tentar analisar/justificar o porquê dos resultados obtidos.
Os resultados dos testes efectuados deverão ser usados para escolher as melhores procuras e as
melhores funções de custo/heurísticas a serem usadas. Esta escolha deverá ser devidamente justificada no relatório do projecto.
Nesta fase final é também pretendido que os alunos escrevam um relatório sobre o projecto realizado. Para além dos testes efectuados e da análise correspondente, o relatório do projecto deverá conter também informação acerca da implementação de alguns tipos e funções. Por exemplo, qual a representação escolhida para cada tipo (e porquê), qual a função de utilidade utilizada, como foram implementas as procuras e que optimizações foram efectuadas, quais as funções heurísticas implementadas e como é que foram implementadas, etc. Será disponibilizado um template do relatório
para que os alunos tenham uma ideia melhor do que é necessário incluir no relatório final do projecto.
Esta função recebe um problema
e uma função heurística
, e utiliza o algoritmo de procura A*
em árvore para tentar determinar qual a sequência de acções de modo a maximizar os pontos
obtidos. A função heurística
corresponde a uma função que recebe um estado e devolve um
número, que representa a estimativa do custo/qualidade*
a partir desse estado até ao melhor
estado objectivo. Em caso de empate entre dois nós com igual valor de f na lista deve ser
escolhido o último a ter sido colocado na fronteira. Devem também ter o cuidado do algoritmo
ser independente do problema.
*
Repare que no caso de se usar qualidade, como esta vai corresponder a um valor negativo, o algoritmoA*
vai continuar a seleccionar o nó com menor valor de f.
Este transformador de saída recebe um tabuleiro
e devolve um novo array
com 18 linhas e 10 colunas, que para cada linha e coluna deverá conter o valor lógico correspondente a cada posição do tabuleiro. O array
retornado deverá garantir que qualquer alteração feita ao tabuleiro
original não deve ser repercutida no novo array
e vice-versa.
Task of: #5 2.1.2 Tipo tabuleiro
Este reconhecedor recebe um tabuleiro
, e devolve o valor lógico verdade
se existir alguma
posição na linha do topo do tabuleiro (linha 17) que esteja preenchida, e falso
caso contrário.
Task of: #5 2.1.2 Tipo tabuleiro
Este modificador recebe um tabuleiro
, um inteiro
correspondente ao número linha e um inteiro
correspondente ao número da coluna, e altera o tabuleiro
recebido para na posição correspondente à linha e coluna passar a estar preenchido. Se o número de linha e de coluna recebidos não forem válidos (i.e. não estiverem entre 0 e 17, e 0 e 9), esta função não deverá fazer nada. O valor devolvido por desta função não está definido*
Task of: #5 Tipo tabuleiro
*
Ou seja, não interessa o que é devolvido, mas também não podem usar o valor devolvido quando invocam a função.
Esta função recebe um estado
e uma accao
, e devolve um novo estado
que resulta de aplicar a
accao
recebida no estado original. Atenção, o estado
original não pode ser alterado em situação
alguma. Esta função deve actualizar as listas de peças, colocar a peça especificada pela accao
na
posição correcta do tabuleiro
. Depois de colocada a peça, é verificado se o topo do tabuleiro está preenchido. Se estiver, não se removem linhas e devolve-se o estado. Se não estiver, removem-se as linhas e calculam-se os pontos obtidos.
Task of: #23 2.2.1 Funções do problema de procura
Este modificador recebe um tabuleiro
, um inteiro
correspondente ao número de linha, e altera o tabuleiro recebido removendo essa linha do tabuleiro
, e fazendo com que as linhas por cima da linha removida desçam uma linha. As linhas que estão por baixo da linha removida não podem ser alteradas. O valor devolvido por desta função não está definido.
Task of: #5 2.1.2 Tipo tabuleiro
Este selector recebe um tabuleiro
, um inteiro
correspondente ao número de uma coluna, e devolve a altura de uma coluna, ou seja a posição mais alta que esteja preenchida dessa coluna. Uma coluna que não esteja preenchida deverá ter altura 0.
Task of: #5 2.1.2 Tipo tabuleiro
O tipo estado representa o estado de um jogo de Tetris. Este tipo deverá ser implementado obrigatoriamente como uma estrutura5 em Common Lisp com os seguintes campos:
*
Ver ficheiroutils.lisp
.
Este transformador de entrada recebe um array
com 18 linhas e 10 colunas cujas posições têm o valor lógico T
ou Nil
, e constrói um novo tabuleiro
com o conteúdo do array
recebido. O tabuleiro
devolvido deverá garantir que qualquer alteração feita ao array
original não deve ser repercutida no novo tabuleiro e vice-versa.
Task of: #5 2.1.2 Tipo tabuleiro
Esta função recebe um problema
e usa a procura em profundidade primeiro em árvore para
obter uma solução para resolver o problema. Devolve uma lista de acções que se executada pela
ordem especificada irá levar do estado inicial a um estado objectivo. Deve ser utilizado um
critério de Last In First Out, pelo que o último nó a ser colocado na fronteira deverá ser o
primeiro a ser explorado a seguir. Devem também ter o cuidado do algoritmo ser independente
do problema, ou seja deverá funcionar para este problema do Tetris, mas deverá funcionar
também para qualquer outro problema*
de procura.
*
Portanto, é desaconselhado o uso de variáveis globais e usar/aceder directamente a funções específicas do Tetris. Tudo o que precisarem vai estar dentro do tipo problema recebido
Os algoritmos de procura informada estão concebidos para tentar minimizar o custo de caminho. No entanto, se quisermos maximizar os pontos obtidos, podemos olhar para isto como
um problema de maximização de qualidade. Para podermos usar a qualidade com os algoritmos de procura melhor primeiro, uma solução simples é convertermos a qualidade num valor negativo de custo. Assim sendo, um estado com mais pontos irá ter um valor menor (negativo) e
terá prioridade para o mecanismo de escolha do próximo nó a ser expandido.
Portanto, a função qualidade recebe um estado
e retorna um valor de qualidade inteiro
que
corresponde ao valor negativo dos pontos ganhos até ao momento.
Task of: #23 2.2.1 Funções do problema de procura
O tipo problema representa um problema genérico de procura. Este tipo deverá ser implementado
obrigatoriamente como uma estrutura em Common Lisp
com os seguintes campos:
T
se o estado for uma solução para o problema de procura, e Nil
caso contrário;estado
e devolve uma lista com todas as acções que são possíveis fazer nesse estado;estado
e uma accao
devolve o estado
sucessor que resulta de executar a acção recebida no estado recebido;estado
devolve o custo do caminho desde o estado
inicial até esse estado
.O tipo Acção é utilizado para representar uma acção do jogador. Uma acção é implementada como um par cujo elemento esquerdo é um número de coluna que indica a coluna mais à esquerda escolhida para a peça cair, e cujo elemento direito corresponde a um array
bidimensional com a configuração geométrica da peça depois de rodada*
. A figura seguinte mostra o exemplo de uma acção. O ficheiro utils.lisp
define todas as configurações geométricas possíveis para cada peça**
#2 cria-accao
#3 accao-coluna
#4 accao-peca
*
Um array em que cada posição pode ter o valor T caso essa posição esteja ocupada por uma parte da peça e nil caso contrário. A posição inicial do array (0,0) corresponde sempre à parte da peça mais à esquerda e mais abaixo.**
Guardadas nas constantes peca-i0, peca-i1, peca-j0,etc.
.
Este construtor recebe um tabuleiro
, e devolve um novo tabuleiro
com o mesmo conteúdo do tabuleiro
recebido. O tabuleiro
devolvido deve ser um objecto computacional diferente e deverá garantir que qualquer alteração feita ao tabuleiro
original não deve ser repercutida no novo tabuleiro
e vice-versa.
Task of: #5 2.1.2 Tipo tabuleiro
Esta função recebe um estado
e devolve uma lista de acções correspondendo a todas as acções
válidas que podem ser feitas com a próxima peça a ser colocada. Uma acção é considerada
válida mesmo que faça o jogador perder o jogo (i.e. preencher a linha do topo). Uma acção é
inválida se não for fisicamente possível dentro dos limites laterais do jogo 78. Por exemplo colocar a peça i deitada na última coluna do tabuleiro, ou tentar colocar a peça s com a
orientação inicial na coluna 89, tal como se pode ver na imagem seguinte.
A ordem com que são devolvidas as acções na lista é muito importante. À frente da lista devem estar obrigatoriamente as acções correspondentes à orientação inicial da peça, percorrendo todas as colunas possíveis da esquerda para a direita. Depois é escolhida uma nova orientação, rodando a peça 90º no sentido horário, e volta-se a gerar para todas as colunas possíveis da esquerda para a direita. No entanto, se ao rodar uma peça obter uma configuração geométrica já explorada anteriormente (como por exemplo no caso da peça O em que todas as rotações correspondem à mesma configuração) não devem ser geradas novamente as acções*
Task of: #23 Funções do problema de procura
*
As constantes definidas no ficheiroutils.lisp
já estão ordenadas por esta ordem de rotação, pelo que basta por exemplo no caso da peça t gerarem as colunas possíveis para as peças:peca-t0
,peca-t1
,peca-t2
,peca-t3
As funções descritas nesta subsecção correspondem aos algoritmos de procura a implementar para
determinar a sequência de acções de modo a colocar todas as peças.
É importante ter em conta, que para além destas funções explicitamente definidas (que serão testadas
automaticamente), na 2.ª fase do projecto deverão implementar técnicas adicionais de optimização, várias heurísticas, ou até mesmo funções de custo alternativas, e testá-las. Cabe aos alunos decidir que técnicas/heurísticas adicionais irão precisar para que o vosso algoritmo final procura-best seja o melhor possível.
#30 procura-pp: problema → lista-accoes
#31 procura-A*: problema x heuristica → lista acções
#32 procura-best: array x lista peças → lista acções
Esta função recebe um estado
, e devolve o valor lógico verdade
se o estado recebido corresponder a uma solução, e falso
contrário. Um estado do jogo Tetris é considerado solução se o topo do tabuleiro
não estiver preenchido e se já não existem peças por colocar, ou seja, todas as peças foram colocadas com sucesso (independentemente de terem ou não sido obtidos pontos).
Task of: #23 2.2.1 Funções do problema de procura
Este teste recebe dois estados
, e devolve o valor lógico ´verdade´ se os dois estados
forem iguais
(i.e. tiverem o mesmo conteúdo) e ´falso´ caso contrário.
Task of: #18 Tipo estado
Este reconhecedor recebe um estado
e devolve o valor lógico verdade
se corresponder a um
estado
final onde o jogador já não possa fazer mais jogadas e falso
caso contrário. Um estado
é
considerado final se o tabuleiro
tiver atingido o topo ou se já não existem peças por colocar.
Task of: #18 2.1.3 Tipo estado
Este selector devolve o array
com a configuração geométrica exacta com que vai ser colocada.
Este construtor recebe um inteiro
correspondente à posição da coluna mais à esquerda a partir
da qual a peça vai ser colocada, e um array
com a configuração da peça a colocar, e devolve uma
nova acção.
Task of: #5
Este selector devolve um inteiro
correspondente à coluna mais à esquerda a partir da qual a
peça vai ser colocada.
Task of: #1
Este selector devolve o array
com a configuração geométrica exacta com que vai ser colocada
Task of: #1
Este construtor recebe um estado
e devolve um novo estado
cujo conteúdo deve ser copiado a partir do estado
original. O estado
devolvido deverá garantir que qualquer alteração feita ao estado
original não deve ser repercutida no novo estado
e vice-versa.
Task of: #18 2.1.3 Tipo estado
Uma representação alternativa para um problema de maximização de qualidade, é considerar
que por cada acção podemos potencialmente ganhar um determinado valor, e que o custo é
dado pelo facto de não conseguirmos ter aproveitado ao máximo a oportunidade. Assim sendo
o custo de oportunidade pode ser calculado como a diferença entre o máximo possível e o
efectivamente conseguido. Portanto esta função, dado um estado
, devolve o custo inteiro
de
oportunidade de todas as acções realizadas até ao momento, assumindo que é sempre possível
fazer o máximo de pontos por cada peça colocada*
. Ao usarmos esta função como custo, os
algoritmos de procura irão tentar minimizar o custo de oportunidade.
Task of: #23 2.2.1 Funções do problema de procura
*
Tendo em conta as simplificações usadas no jogo, a pontuação máxima por cada peça é dada por:i – 800
;j –500
,l – 500
,s – 300
,z – 300
,t – 300
,o – 300
.
Este reconhecedor recebe um tabuleiro
, um inteiro
correspondente ao número de uma linha, e
devolve o valor lógico verdade
se todas as posições da linha recebida estiverem preenchidas, e
falso
caso contrário.
Task of: #5 2.1.2 Tipo tabuleiro
Esta função recebe um array
correspondente a um tabuleiro
e uma lista
de peças por colocar,
inicializa o estado
e a estrutura problema
com as funções escolhidas pelo grupo, e irá usar a
melhor procura e a melhor heurística e melhor função custo/qualidade feita pelo grupo para
obter a sequência de acções de modo a conseguir colocar todas as peças no tabuleiro com o
máximo de pontuação. No entanto, tenham em consideração que esta função irá ter um limite
de tempo para retornar um resultado, portanto não vos serve de nada retornar a solução
óptima se excederem o tempo especificado*
. É importante encontrar um compromisso entre a
pontuação obtida e o tempo de execução do algoritmo. Esta função irá ser a função usada para
avaliar a qualidade da vossa versão final. Se assim o entenderem, nesta função já podem usar
implementações e optimizações específicas para o jogo do Tetris.
*
Por exemplo a procura de custo uniforme garante a solução óptima mas irá levar demasiado tempo.
O tipo Tabuleiro
é utilizado para representar o tabuleiro do jogo de Tetris com 18 linhas e 10 colunas, em que cada posição do tabuleiro pode estar preenchida ou não. Cabe aos alunos a escolha da representação mais adequada para este tipo.
#6 cria-tabuleiro
#7 copia-tabuleiro
#9 tabuleiro-preenchido
#10 tabuleiro-altura-coluna
#11 tabuleiro-linha-completa-p
#12 tabuleiro-preenche!
#13 tabuleiro-remove-linha!
#14 tabuleiro-topo-preenchido-p
#15 tabuleiros-iguais-p
#16 tabuleiro->array
#17 array->tabuleiro
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.