Description

Segundo Projecto
Jogo do Moinho
Neste segundo projecto de Fundamentos da Programac¸˜ao os alunos ira˜o desenvolver as fun¸co˜es de forma a implementar um programa em Python que permita a um jogador humano jogar o Jogo do Moinho contra o computador.
1 Descri¸c˜ao do jogo
O jogo do moinho ´e um antigo jogo tradicional de tabuleiro para dois jogadores com uma multitude de variantes dependendo do nu´mero de pe¸cas dispon´ıveis para cada jogador e a disposi¸c˜ao do tabuleiro .
1.1 O tabuleiro de jogo
O tabuleiro de jogo considerado ´e uma estrutura rectangular de tamanho 3×3. Cada posi¸c˜ao do tabuleiro ´e indexada pela coluna e a linha que ocupa. Num tabuleiro, uma posi¸ca˜o pode estar livre ou ocupada pela pe¸ca de um jogador. O exemplo da Figura 1 mostra um tabuleiro com duas pec¸as diferentes nas posi¸co˜es a1 e b2.
a b c
1 [X]-[ ]-[ ]
| | / |
2 [ ]-[O]-[ ]
| / | |
3 [ ]-[ ]-[ ]
Figura 1: Tabuleiro do jogo do moinho com pec¸as diferentes nas posic¸˜oes a1 e b2.
A ordem de leitura das posi¸co˜es do tabuleiro ´e definida da esquerda para a direita seguida de cima para baixo.
1.2 Regras do jogo
Na variante do jogo do moinho considerada, cada jogador tem trˆes pe¸cas e o vencedor ´e o primeiro jogador a alinhar suas trˆes pe¸cas numa linha vertical ou horizontal. O jogo desenvolve-se em duas fases: coloca¸c˜ao e movimento.
• Na fase de coloca¸c˜ao, tal como no jogo do galo, o tabuleiro come¸ca inicialmente vazio e os jogadores colocam de forma alternada uma das suas pec¸as no tabuleiro. Apo´s ter colocado todas as pe¸cas, e se nenhum jogador conseguiu ganhar entretanto, come¸ca a fase de movimento.
• Durante a fase de movimento, os jogadores continuam a alternar turnos, neste caso podendo movimentar qualquer uma das pe¸cas pr´oprias a qualquer um dos espac¸os livres imediatamente adjacentes conectados por uma linha horizontal, vertical ou diagonal.
O jogo continua at´e que um dos jogadores consegue ganhar.
1.3 Estrat´egia de jogo autom´atico
Neste projecto consideraremos estrat´egias de jogo diferentes dependendo da fase de jogo.
1.3.1 Fase de coloca¸c˜ao
Na fase de coloca¸c˜ao, o jogador computador escolhera´ a primeira ac¸ca˜o dispon´ıvel da lista a seguir:
1. Vit´oria:
Se o jogador tiver duas das suas pe¸cas em linha e uma posic¸˜ao livre ent˜ao deve marcar na posi¸ca˜o livre (ganhando o jogo);
2. Bloqueio:
Se o adversa´rio tiver duas das suas pe¸cas em linha e uma posi¸ca˜o livre ent˜ao deve marcar na posi¸ca˜o livre (para bloquear o advers´ario);
3. Centro:
Se a posic¸˜ao central estiver livre ent˜ao jogar na posi¸ca˜o central;
4. Canto vazio:
Se um canto for uma posi¸ca˜o livre ent˜ao jogar nesse canto;
5. Lateral vazio:
Se uma posi¸c˜ao lateral (que nem ´e o centro, nem um canto) for livre ent˜ao jogar nesse lateral.
1.3.2 Fase de movimento
Na fase de movimento, o jogador computador utilizara´ o algoritmo minimax para escolher o seu seguinte movimento. O minimax ´e um algoritmo recursivo muito utilizado em teoria de jogos que pode sumarizar-se como a escolha do melhor movimento para um pro´prio assumindo que o advers´ario ira´ a escolher o pior poss´ıvel.
Na pra´tica, o algoritmo minimax pode ser implementado como uma fun¸ca˜o recursiva que recebe um tabuleiro e o jogador com o turno atual. A func¸˜ao explora todos os movimentos legais desse jogador chamando a` fun¸ca˜o recursiva com o tabuleiro modificado com um dos movimentos e o jogador adversa´rio como novos paraˆmetros. No caso geral, o algoritmo escolhera´/devolvera´ o movimento que mais favore¸ca o jogador do turno atual. A recursa˜o finaliza quando existe um ganhador ou quando se atinge um n´ıvel m´aximo de profundidade da recurs˜ao. O valor que devolve a func¸˜ao ´e o valor do estado do tabuleiro para cada jogador, sendo positivo para estados de tabuleiro que favore¸cam ao jogador ’X’ e negativo se favorecem ao jogador ’O’. No projeto definimos uma func¸˜ao simples para o valor dum tabuleiro: +1 se o ganhador ´e o joqador ’X’, -1 se o ganhador ´e jogador ’O’, ou 0 se n˜ao h´a ganhador. Assim, no caso geral, quando ´e o jogador ’X’ a escolher movimento, escolhera´/devolver´a o primeiro movimento de valor ma´ximo, e quando ´e o jogador ’O’ a escolher movimento, escolhera´/devolvera´ o primeiro movimento de valor m´ınimo. Adicionalmente, a func¸˜ao recursiva pode ter como argumento uma estrutura que ´e utilizada para registar a sequˆencia de movimentos realizados e que ´e atualizada na chamada a` func¸˜ao recursiva. O pseudo-co´digo correspondente ´e descrito no Algoritmo 1.
2 Trabalho a realizar
O objetivo deste segundo projecto ´e definir um conjunto de Tipos Abstratos de Dados (TAD) que devera˜o ser utilizados para representar a informa¸c˜ao necessa´ria, bem como um conjunto de func¸˜oes adicionais que permitira˜o executar corretamente o jogo do moinho.
2.1 Tipos Abstratos de Dados
Aten¸ca˜o:
• Apenas os construtores e as fun¸co˜es para as quais a verifica¸ca˜o da corre¸c˜ao dos argumentos ´e explicitamente pedida devem verificar a validade dos argumentos. • Os modificadores, e as fun¸co˜es de alto n´ıvel que os utilizam, alteram de modo destrutivo o seu argumento.
• Todas as fun¸co˜es de alto n´ıvel (ou seja, que na˜o correspondem a opera¸c˜oes b´asicas) devem respeitar as barreiras de abstra¸c˜ao.

2.1.1 TAD posicao (1.5 valores)
O TAD posicao ´e usado para representar uma posi¸ca˜o do tabuleiro de jogo. Cada posi¸ca˜o ´e caraterizada pela coluna e linha que ocupa no tabuleiro. As opera¸co˜es ba´sicas

associadas a este TAD sa˜o:
• Construtor
– cria posicao: str ×str 7→ posicao cria posicao(c,l) recebe duas cadeias de carateres correspondentes `a coluna c e a` linha l de uma posi¸ca˜o e devolve a posi¸ca˜o correspondente. O construtor verifica a validade dos seus argumentos, gerando um ValueError com a mensagem ‘cria posicao: argumentos invalidos’ caso os seus argumentos na˜o sejam va´lidos.
– cria copia posicao: posicao 7→ posicao cria copia posicao(p) recebe uma posi¸ca˜o e devolve uma c´opia nova da posic¸˜ao.
• Seletores
– obter pos c: posicao 7→ str obter pos c(p) devolve a componente coluna c da posi¸c˜ao p.
– obter pos l: posicao 7→ str obter pos l(p) devolve a componente linha l da posi¸c˜ao p.
• Reconhecedor
– eh posicao: universal 7→ booleano eh posicao(arg) devolve True caso o seu argumento seja um TAD posicao e False caso contra´rio.
• Teste
– posicoes iguais: posicao ×posicao 7→ booleano posicoes iguais(p1, p2) devolve True apenas se p1 e p2 sa˜o posi¸co˜es e sa˜o iguais.
• Transformador
– posicao para str: posicao 7→ str posicao para str(p) devolve a cadeia de caracteres ‘cl’ que representa o seu argumento, sendo os valores c e l as componentes coluna e linha de p.
As fun¸c˜oes de alto n´ıvel associadas a este TAD sa˜o:

• obter posicoes adjacentes: posicao 7→ tuplo de posicoes obter posicoes adjacentes(p) devolve um tuplo com as posic¸˜oes adjacentes a` posi¸ca˜o p de acordo com a ordem de leitura do tabuleiro.
Exemplos de interac¸ca˜o:
>>> p1 = cria_posicao(’a’, ’4’)
Traceback (most recent call last): <…>
ValueError: cria_posicao: argumentos invalidos
>>> p1 = cria_posicao(’a’, ’2’)
>>> p2 = cria_posicao(’b’, ’3’)
>>> posicoes_iguais(p1, p2)
False
>>> posicao_para_str(p1)
’a2’
>>> tuple(posicao_para_str(p) for p in obter_posicoes_adjacentes(p2))
(’b2’, ’a3’, ’c3’)
2.1.2 TAD peca (1.5 valores)
O TAD peca ´e usado para representar as pe¸cas do jogo. Cada pec¸a ´e caracterizada pelo jogador a quem pertencem, podendo ser pec¸as do jogador ’X’ ou do jogador ’O’. Por conveniˆencia, ´e tamb´em definido o conceito pe¸ca livre, que ´e uma pe¸ca que n˜ao pertence a nenhum jogador. As opera¸co˜es b´asicas associadas a este TAD sa˜o:

• Construtor
– cria peca: str 7→ peca cria peca(s) recebe uma cadeia de carateres correspondente ao identificador de um dos dois jogadores (’X’ ou ’O’) ou a uma pe¸ca livre (’ ’) e devolve a pe¸ca correspondente. O construtor verifica a validade dos seus argumentos, gerando um ValueError com a mensagem ‘cria peca: argumento invalido’ caso o seu argumento na˜o seja va´lido.
– cria copia peca: peca 7→ peca cria copia peca(j) recebe uma pe¸ca e devolve uma c´opia nova da pe¸ca.
• Reconhecedor
– eh peca: universal 7→ booleano eh peca(arg) devolve True caso o seu argumento seja um TAD peca e False caso contra´rio.
• Teste
– pecas iguais: peca ×peca 7→ booleano pecas iguais(j1, j2) devolve True apenas se p1 e p2 s˜ao pe¸cas e sa˜o iguais.
• Transformador
– peca para str: peca 7→ str peca para str(j) devolve a cadeia de caracteres que representa o jogador dono da pe¸ca, isto ´e, ’[X]’, ’[O]’ ou ’[ ]’.
As fun¸c˜oes de alto n´ıvel associadas a este TAD sa˜o:

• peca para inteiro: peca 7→ N peca para inteiro(j) devolve um inteiro valor 1, -1 ou 0, dependendo se a pe¸ca ´e do jogador ’X’, ’O’ ou livre, respetivamente.
Exemplos de interac¸ca˜o:
>>> j1 = cria_peca(’x’)
Traceback (most recent call last): <…>
ValueError: cria_peca: argumento invalido
>>> j1 = cria_peca(’X’)
>>> j2 = cria_peca(’O’)
>>> pecas_iguais(j1, j2)
False
>>> peca_para_str(j1)
’[X]’
>>> peca_para_inteiro(cria_peca(’ ’))
0
2.1.3 TAD tabuleiro (3 valores)
O TAD tabuleiro ´e usado para representar um tabuleiro do jogo do moinho de 3×3 posi¸co˜es e as pe¸cas dos jogadores que nele s˜ao colocadas. As opera¸co˜es b´asicas associadas

a este TAD s˜ao:
• Construtor
– cria tabuleiro: {}7→ tabuleiro cria tabuleiro() devolve um tabuleiro de jogo do moinho de 3×3 sem posi¸co˜es ocupadas por pe¸cas de jogador.
– cria copia tabuleiro: tabuleiro 7→ tabuleiro cria copia tabuleiro(t) recebe um tabuleiro e devolve uma c´opia nova do tabuleiro.
• Seletores
– obter peca: tabuleiro ×posicao 7→ peca obter peca(t, p) devolve a pe¸ca na posi¸ca˜o p do tabuleiro. Se a posi¸ca˜o n˜ao estiver ocupada, devolve uma pe¸ca livre.
– obter vetor: tabuleiro ×str →7 tuplo de pecas obter vetor(t, s) devolve todas as pe¸cas da linha ou coluna especificada pelo seu argumento.
• Modificadores
– coloca peca: tabuleiro ×peca ×posicao 7→ tabuleiro coloca peca(t, j, p) modifica destrutivamente o tabuleiro t colocando a pe¸ca j na posi¸c˜ao p, e devolve o pro´prio tabuleiro.
– remove peca: tabuleiro ×posicao →7 tabuleiro remove peca(t, p) modifica destrutivamente o tabuleiro t removendo a pe¸ca da posi¸c˜ao p, e devolve o pro´prio tabuleiro.
– move peca: tabuleiro ×posicao ×posicao 7→ tabuleiro move peca(t, p1, p2) modifica destrutivamente o tabuleiro t movendo a pe¸ca que se encontra na posi¸ca˜o p1 para a posi¸ca˜o p2, e devolve o pr´oprio tabuleiro.
• Reconhecedor
– eh tabuleiro: universal 7→ booleano eh tabuleiro(arg) devolve True caso o seu argumento seja um TAD tabuleiro e False caso contr´ario. Um tabuleiro v´alido pode ter um ma´ximo de 3 pe¸cas de cada jogador, na˜o pode conter mais de 1 pe¸ca mais de um jogador que do contrario, e apenas pode haver um ganhador em simultaˆneo.
– eh posicao livre: tabuleiro ×posicao 7→ booleano eh posicao livre(t, p) devolve True apenas no caso da posi¸c˜ao p do tabuleiro corresponder a uma posi¸ca˜o livre.
• Teste
– tabuleiros iguais: tabuleiro ×tabuleiro 7→ booleano tabuleiros iguais(t1, t2) devolve True apenas se t1 e t2 sa˜o tabuleiros e sa˜o iguais.
• Transformador
– tabuleiro para str: tabuleiro 7→ str tabuleiro para str(t) devolve a cadeia de caracteres que representa o tabuleiro como mostrado nos exemplos a seguir.
– tuplo para tabuleiro: tuplo 7→ tabuleiro tuplo para tabuleiro(t) devolve o tabuleiro que ´e representado pelo tuplo t com 3 tuplos, cada um deles contendo 3 valores inteiros iguais a 1, -1 ou 0, tal como no primeiro projeto .
As fun¸c˜oes de alto n´ıvel associadas a este TAD sa˜o:

• obter ganhador: tabuleiro 7→ peca obter ganhador(t) devolve uma pe¸ca do jogador que tenha as suas 3 pe¸cas em linha na vertical ou na horizontal no tabuleiro. Se n˜ao existir nenhum ganhador, devolve uma pe¸ca livre.
• obter posicoes livres: tabuleiro 7→ tuplo de posicoes obter posicoes livres(t) devolve um tuplo com as posi¸co˜es na˜o ocupadas pelas pe¸cas de qualquer um dos dois jogadores na ordem de leitura do tabuleiro.
• obter posicoes jogador: tabuleiro ×peca 7→ tuplo de posicoes obter posicoes jogador(t, j) devolve um tuplo com as posi¸c˜oes ocupadas pelas pe¸cas j de um dos dois jogadores na ordem de leitura do tabuleiro.
Exemplos de interac¸ca˜o:
>>> t = cria_tabuleiro()
>>> tabuleiro_para_str(coloca_peca(t, cria_peca(’X’), cria_posicao(’a’,’1’)))
’ a b c 1 [X]-[ ]-[ ] | \ | / |
2 [ ]-[ ]-[ ] | / | \ | 3 [ ]-[ ]-[ ]’
>>> print(tabuleiro_para_str(t)) a b c
1 [X]-[ ]-[ ]
| | / |
2 [ ]-[ ]-[ ]| / | |
3 [ ]-[ ]-[ ]
>>> print(tabuleiro_para_str(coloca_peca(t, cria_peca(’O’), cria_posicao(’b’,’2’)))) a b c
1 [X]-[ ]-[ ]
| | / |
2 [ ]-[O]-[ ]
| / | |
3 [ ]-[ ]-[ ]
>>> print(tabuleiro_para_str(move_peca(t, cria_posicao(’a’,’1’), cria_posicao(’b’,’1’)))) a b c
1 [ ]-[X]-[ ]
| | / |
2 [ ]-[O]-[ ]
| / | |
3 [ ]-[ ]-[ ]
>>> t = tuplo_para_tabuleiro(((0,1,-1),(-0,1,-1),(1,0,-1)))
>>> print(tabuleiro_para_str(t)) a b c
1 [ ]-[X]-[O]
| | / |
2 [ ]-[X]-[O]
| / | |
3 [X]-[ ]-[O]
>>> peca_para_str(obter_ganhador(t))
’[O]’
>>> tuple(posicao_para_str(p) for p in obter_posicoes_livres(t))
(’a1’, ’a2’, ’b3’)
>>> tuple(peca_para_str(peca) for peca in obter_vetor(t, ’a’))
(’[ ]’, ’[ ]’, ’[X]’)
>>> tuple(peca_para_str(peca) for peca in obter_vetor(t, ’2’)) (’[ ]’, ’[X]’, ’[O]’)
2.2 Fun¸c˜oes adicionais
2.2.1 obter movimento manual: tabuleiro ×peca 7→ tuplo de posicoes (1.5
valores)
Fun¸ca˜o auxiliar que recebe um tabuleiro e uma peca de um jogador, e devolve um tuplo com uma ou duas posi¸co˜es que representam uma posi¸c˜ao ou um movimento introduzido manualmente pelo jogador. Na fase de coloca¸ca˜o, o tuplo cont´em apenas a posi¸ca˜o escolhida pelo utilizador onde colocar uma nova pe¸ca. Na fase de movimento, o tuplo cont´em a posi¸ca˜o de origem da pe¸ca que se deseja movimentar e a posi¸ca˜o de destino. Se n˜ao for poss´ıvel movimentar nenhuma pe¸ca por estarem todas bloqueadas, o jogador pode passar turno escolhendo como movimento a posic¸˜ao duma pe¸ca pro´pria seguida da mesma posi¸ca˜o que ocupa. Se o valor introduzido pelo jogador na˜o corresponder a uma posi¸ca˜o ou movimento v´alidos, a fun¸ca˜o deve gerar um erro com a mensagem ’obter movimento manual: escolha invalida’. A fun¸ca˜o deve apresentar a mensagem ’Turno do jogador. Escolha uma posicao: ’ ou ’Turno do jogador. Escolha um movimento: ’, para pedir ao utilizador para introduzir uma posi¸ca˜o ou um movimento.
>>> t = cria_tabuleiro()
m = obter_movimento_manual(t, cria_peca(’X’))
Turno do jogador. Escolha uma posicao: a1
>>> posicao_para_str(m[0])
’a1’
>>> t = tuplo_para_tabuleiro(((0,1,-1),(1,-1,0),(1,-1,0)))
>>> m = obter_movimento_manual(t, cria_peca(’X’))
Turno do jogador. Escolha um movimento: b1a1
>>> posicao_para_str(m[0]), posicao_para_str(m[1])
(’b1’, ’a1’)
>>> m = obter_movimento_manual(t, cria_peca(’O’))
Turno do jogador. Escolha um movimento: a2a1
Traceback (most recent call last): <…>
ValueError: obter_movimento_manual: escolha invalida
2.2.2 obter movimento auto: tabuleiro ×peca ×str →7 tuplo de posicoes (3
valores)
Fun¸ca˜o auxiliar que recebe um tabuleiro, uma peca de um jogador e uma cadeia de carateres representando o n´ıvel de dificuldade do jogo, e devolve um tuplo com uma ou duas posi¸co˜es que representam uma posi¸ca˜o ou um movimento escolhido automaticamente. Na fase de coloca¸ca˜o, o tuplo cont´em apenas a posi¸c˜ao escolhida automaticamente onde colocar uma nova pe¸ca seguindo as regras da sec¸c˜ao 1.3.1. Se na˜o for poss´ıvel movimentar nenhuma pec¸a por estarem todas bloqueadas, a fun¸c˜ao devolve como movimento a posi¸c˜ao da primeira pe¸ca do jogador correspondente seguida da mesma posic¸˜ao que ocupa. Na fase de movimento, o tuplo cont´em a posi¸ca˜o de origem da pec¸a a movimentar e a posi¸ca˜o de destino. A escolha autom´atica do movimento depende do n´ıvel de dificuldade do jogo:
• ’facil’ (1 valor): a pe¸ca a movimentar ´e sempre a que ocupa a primeira posi¸c˜ao em ordem de leitura do tabuleiro que tenha alguma posic¸˜ao adjacente livre. A posi¸ca˜o de destino ´e a primeira posi¸ca˜o adjacente livre.
• ’normal’ (1 valor): o movimento ´e escolhido utilizando o algoritmo descrito na sec¸ca˜o 1.3.2 com n´ıvel de profundidade ma´ximo de recursa˜o igual a 1.
NOTA: Este n´ıvel ´e equivalente a escolher o primeiro movimento poss´ıvel que permita obter uma vit´oria, seguido de bloquear a vito´ria do adversa´rio. Se na˜o existir nenhum movimento de vit´oria ou bloqueio, ent˜ao ´e seguido o mesmo crit´erio de escolha do n´ıvel ’facil’.
• ’dificil’ (1 valor): o movimento ´e escolhido utilizando o algoritmo descrito na sec¸ca˜o 1.3.2 com n´ıvel de profundidade ma´ximo de recursa˜o igual a 5.
>>> t = cria_tabuleiro()
>>> m = obter_movimento_auto(t, cria_peca(’X’), ’facil’)
>>> posicao_para_str(m[0])
’b2’
>>> t = tuplo_para_tabuleiro(((1,0,-1),(0,1,-1),(1,-1,0)))
>>> m = obter_movimento_auto(t, cria_peca(’X’), ’facil’)
>>> posicao_para_str(m[0]), posicao_para_str(m[1])
(’a1’, ’b1’)
>>> m = obter_movimento_auto(t, cria_peca(’X’), ’normal’)
>>> posicao_para_str(m[0]), posicao_para_str(m[1])
(’b2’, ’a2’)
>>> t = tuplo_para_tabuleiro(((1,-1,-1),(-1,1,0),(0,0,1)))
>>> m = obter_movimento_auto(t, cria_peca(’X’), ’normal’)
>>> posicao_para_str(m[0]), posicao_para_str(m[1])
(’b2’, ’c2’)
>>> m = obter_movimento_auto(t, cria_peca(’X’), ’dificil’)
>>> posicao_para_str(m[0]), posicao_para_str(m[1])
(’c3’, ’c2’)
2.2.3 moinho: str ×str 7→ str (1.5 valores)
Fun¸c˜ao principal que permite jogar um jogo completo do jogo do moinho de um jogador contra o computador. A fun¸c˜ao recebe duas cadeias de caracteres e devolve a representa¸c˜ao externa da pe¸ca ganhadora (’[X]’ ou ’[O]’). O primeiro argumento corresponde a representa¸c˜ao externa da pe¸ca com que deseja jogar o jogador humano, e o segundo argumento selecciona o n´ıvel de dificuldade do jogo. Se algum dos argumentos dados forem inva´lidos, a func¸˜ao deve gerar um erro com a mensagem ’moinho: argumentos invalidos’. A fun¸c˜ao deve apresentar a mensagem ’Turno do computador (<nivel>):’, em que <nivel> corresponde `a cadeia de caracteres passada como segundo argumento, quando for o turno do computador.
Exemplo
>>> moinho(’[X]’, ’facil’)
Bem-vindo ao JOGO DO MOINHO. Nivel de dificuldade facil. a b c
1 [ ]-[ ]-[ ]| | / |
2 [ ]-[ ]-[ ]| / | |
3 [ ]-[ ]-[ ]
Turno do jogador. Escolha uma posicao: a2 a b c
1 [ ]-[ ]-[ ]| | / |
2 [X]-[ ]-[ ]
| / | |
3 [ ]-[ ]-[ ]
Turno do computador (facil): a b c
1 [ ]-[ ]-[ ]| | / |
2 [X]-[O]-[ ]
| / | |
3 [ ]-[ ]-[ ]
Turno do jogador. Escolha uma posicao: a1 a b c
1 [X]-[ ]-[ ]
| | / |
2 [X]-[O]-[ ]
| / | |
3 [ ]-[ ]-[ ]
Turno do computador (facil): a b c
1 [X]-[ ]-[ ]
| | / |
2 [X]-[O]-[ ]
| / | |

3 [O]-[ ]-[ ]
Turno do jogador. Escolha uma posicao: c1 a b c
1 [X]-[ ]-[X]
| | / |
2 [X]-[O]-[ ]
| / | |
3 [O]-[ ]-[ ]
Turno do computador (facil): a b c
1 [X]-[O]-[X]
| | / |
2 [X]-[O]-[ ]
| / | |
3 [O]-[ ]-[ ]
Turno do jogador. Escolha um movimento: c1c2 a b c
1 [X]-[O]-[ ]
| | / |
2 [X]-[O]-[X]
| / | |
3 [O]-[ ]-[ ]
Turno do computador (facil): a b c
1 [X]-[ ]-[O]
| | / |
2 [X]-[O]-[X]
| / | |
3 [O]-[ ]-[ ]
Turno do jogador. Escolha um movimento: a1b1 a b c
1 [ ]-[X]-[O]
| | / |
2 [X]-[O]-[X]
| / | |
3 [O]-[ ]-[ ]
Turno do computador (facil): a b c
1 [O]-[X]-[O]
| | / |
2 [X]-[ ]-[X]
| / | |
3 [O]-[ ]-[ ]
Turno do jogador. Escolha um movimento: b1b2 a b c
1 [O]-[ ]-[O]
| | / |
2 [X]-[X]-[X]
| / | |
3 [O]-[ ]-[ ]
’[X]’
3 Condi¸co˜es de Realiza¸c˜ao e Prazos
• Devera´ submeter um u´nico ficheiro com extensa˜o .py contendo todo o c´odigo do seu projecto. O ficheiro de c´odigo dever´a conter em coment´ario, na primeira linha, o nu´mero e o nome do aluno.
• No seu ficheiro de c´odigo n˜ao devem ser utilizados caracteres acentuados ou qualquer outro cara´cter na˜o pertencente `a tabela ASCII. Todos os testes autom´aticos falhara˜o, mesmo que os caracteres n˜ao ASCII sejam utilizados dentro de comenta´rios ou cadeias de caracteres. Programas que na˜o cumpram este requisito sera˜o penalizados em trˆes valores.
• Na˜o ´e permitida a utilizac¸˜ao de qualquer mo´dulo ou fun¸ca˜o na˜o dispon´ıvel built-in no Python 3, ou seja, n˜ao sa˜o permitidos import, com excec¸˜ao da fun¸ca˜o reduce do functools.
• Pode, ou na˜o, haver uma discussa˜o oral do trabalho e/ou uma demonstra¸ca˜o do funcionamento do programa (ser´a decidido caso a caso).
• Lembre-se que no T´ecnico, a fraude acad´emica ´e levada muito a s´erio e que a co´pia numa prova (projectos inclu´ıdos) leva `a reprova¸ca˜o na disciplina. O corpo docente da cadeira sera´ o u´nico juiz do que se considera ou n˜ao co´pia de um projecto.
4 Submiss˜ao
A submiss˜ao e avalia¸ca˜o da execu¸ca˜o do projecto de FP ´e feita utilizando o sistema Mooshak . Para obter as necessa´rias credenciais de acesso e poder usar o sistema devera´:
• Obter uma password para acesso ao sistema, seguindo as instru¸c˜oes na pa´gina: http://acm.tecnico.ulisboa.pt/~fpshak/cgi-bin/getpass. A password serlhe-a´ enviada para o email que tem configurado no Fenix. Se a password na˜o lhe chegar de imediato, aguarde.
• Apo´s ter recebido a sua password por email, deve efetuar o login no sistema atrav´es da pa´gina: http://acm.tecnico.ulisboa.pt/~fpshak/. Preencha os campos com a informa¸c˜ao fornecida no email.
• Utilize o bot˜ao ”Browse…”, selecione o ficheiro com extens˜ao .py contendo todo o c´odigo do seu projecto. O seu ficheiro .py deve conter a implementa¸ca˜o das fun¸co˜es pedidas no enunciado. De seguida clique no bota˜o ”Submit” para efetuar a submiss˜ao.
Aguarde (20-30 seg) para que o sistema processe a sua submiss˜ao!!!
• Quando a submiss˜ao tiver sido processada, poder´a visualizar na tabela o resultado correspondente. Receber´a no seu email um relato´rio de execu¸ca˜o com os detalhes da avalia¸ca˜o autom´atica do seu projecto podendo ver o nu´mero de testes passados/falhados.
• Para sair do sistema utilize o bota˜o ”Logout”.
Submeta o seu projecto atempadamente, dado que as restri¸c˜oes seguintes podem na˜o lhe permitir fazˆe-lo no u´ltimo momento:
• So´ podera´ efetuar uma nova submissa˜o pelo menos 5 minutos depois da submissa˜o anterior.
• So´ sa˜o permitidas 10 submisso˜es em simultˆaneo no sistema, pelo que uma submissa˜o podera´ ser recusada se este limite for excedido .
• Na˜o pode ter submiss˜oes duplicadas, ou seja, o sistema pode recusar uma submissa˜o caso seja igual a uma das anteriores.
• Sera´ considerada para avalia¸ca˜o a u´ltima submissa˜o (mesmo que tenha pontua¸ca˜o inferior a submisso˜es anteriores). Devera´, portanto, verificar cuidadosamente que a u´ltima entrega realizada corresponde `a vers˜ao do projecto que pretende que seja avaliada. N˜ao h´a excep¸co˜es!
• Cada aluno tem direito a 15 submiss˜oes sem penaliza¸c˜ao no Mooshak. Por cada submissa˜o adicional sera˜o descontados 0.1 valores na componente de avalia¸ca˜o automa´tica.
5 Classifica¸c˜ao
A nota do projecto sera´ baseada nos seguintes aspetos:
1. Execu¸c˜ao correta (60%). A avalia¸ca˜o da correcta execu¸c˜ao sera´ feita atrav´es do sistema Mooshak. O tempo de execu¸c˜ao de cada teste est´a limitado, bem como a mem´oria utilizada.
Existem va´rios casos de teste configurados no sistema: testes pu´blicos (disponibilizados na pa´gina da disciplina) valendo 0 pontos cada e testes privados (na˜o disponibilizados). Como a avalia¸ca˜o automa´tica vale 60% (equivalente a 12 valores) da nota, uma submiss˜ao obt´em a nota m´axima de 1200 pontos.
O facto de um projecto completar com sucesso os testes pu´blicos fornecidos n˜ao implica que esse projecto esteja totalmente correto, pois estes na˜o sa˜o exaustivos. E´ da responsabilidade de cada aluno garantir que o co´digo produzido esta´ de acordo com a especifica¸ca˜o do enunciado, para completar com sucesso os testes privados.
2. Respeito pelas barreiras de abstra¸c˜ao (20%). Esta componente da avalia¸ca˜o ´e feita automaticamente, recorrendo a um conjunto de scripts (na˜o Mooshak) que testam posteriormente o respeito pelas barreiras de abstra¸ca˜o do co´digo desenvolvido pelos alunos.
3. Avalia¸c˜ao manual (20%). Estilo de programa¸ca˜o e facilidade de leitura . Em particular, ser˜ao consideradas as seguintes componentes:
• Boas pr´aticas (1.5 valores): sera˜o considerados entre outros a clareza do co´digo, elementos de programa¸ca˜o funcional, integra¸ca˜o de conhecimento adquirido durante a UC, a criatividade das soluc¸˜oes propostas e a escolha da representa¸ca˜o adotada nos TADs.
• Comenta´rios (1 valor): dever˜ao incluir a assinatura dos TADs (incluindo representac¸˜ao interna adotada e assinatura das operac¸˜oes b´asicas), assim como a assinatura de cada fun¸ca˜o definida, coment´arios para o utilizador (docstring) e comenta´rios para o programador.
• Tamanho de fun¸co˜es, duplicac¸˜ao de c´odigo e abstra¸c˜ao procedimental (1 valor)
• Escolha de nomes (0.5 valores).
6 Recomenda¸c˜oes e aspetos a evitar
As seguintes recomenda¸co˜es e aspetos correspondem a sugest˜oes para evitar maus h´abitos de trabalho (e, consequentemente, m´as notas no projecto): • Leia todo o enunciado, procurando perceber o objetivo das va´rias fun¸co˜es pedidas. Em caso de du´vida de interpreta¸ca˜o, utilize o hora´rio de du´vidas para esclarecer as suas questo˜es.
• No processo de desenvolvimento do projecto, comece por implementar as va´rias fun¸co˜es pela ordem apresentada no enunciado, seguindo as metodologias estudadas na disciplina. Ao desenvolver cada uma das fun¸co˜es pedidas, comece por perceber se pode usar alguma das anteriores.
• Para verificar a funcionalidade das suas fun¸co˜es, utilize os exemplos fornecidos como casos de teste. Tenha o cuidado de reproduzir fielmente as mensagens de erro e restantes outputs, conforme ilustrado nos v´arios exemplos.
• Na˜o pense que o projecto se pode fazer nos u´ltimos dias. Se apenas iniciar o seu trabalho neste per´ıodo ira´ ver a Lei de Murphy em funcionamento (todos os problemas sa˜o mais dif´ıceis do que parecem; tudo demora mais tempo do que n´os pensamos; e se alguma coisa puder correr mal, ela vai correr mal, na pior das alturas poss´ıveis);
• Na˜o duplique c´odigo. Se duas fun¸co˜es s˜ao muito semelhantes ´e natural que estas possam ser fundidas numa u´nica, eventualmente com mais argumentos; • Na˜o se esque¸ca que as fun¸co˜es excessivamente grandes s˜ao penalizadas no que respeita ao estilo de programa¸ca˜o;
• A atitude “vou poˆr agora o programa a correr de qualquer maneira e depois preocupo-me com o estilo” ´e totalmente errada; • Quando o programa gerar um erro, preocupe-se em descobrir qual a causa do erro. As “marteladas” no co´digo tˆem o efeito de distorcer cada vez mais o co´digo.