Projeto: Ligue S

Ligue 4

Ligue 4, também conhecido como Lig 4 (ou Connect Four, Captain's Mistress, Four Up, Plot Four, Find Four, Fourplay, Four in a Row e Four in a Line) é um jogo de dois adversários, em que os jogadores inicialmente escolhem cores diferentes para jogar e, à cada turno, cada um deles despeja um disco colorido no alto de uma grade verticalmente suspensa, contendo sete colunas e seis linhas. As peças caem pela coluna selecionada, ocupando o primeiro espaço disponível ali. O objetivo do jogo é avizinhar quatro discos da mesma cor uns aos outros, dispondo-os vertical, horizontal ou diagonalmente.

O jogador que conseguir formar a sequência primeiro vence o jogo.

Este jogo foi resolvido matematicamente por James Allen e por Victor Allis, em 1988, embora em trabalhos independentes. Logo, é possível se desenhar um jogador perfeito para o jogo Ligue 4 num tabuleiro 7x6.

O projeto.

Para o projeto, o jogo será ligeiramente modificado: não serão necessárias 4 vizinhanças, mas um total de S, sendo S definido no início do jogo. Ao mesmo tempo, o tabuleiro será dimensionado com M linhas e N colunas, sendo M e N também definidos no início do jogo.

De posse dos parâmetros do jogo, o programa deverá saber se lhe cabe iniciar ou ao seu adversário. A partir daí ele deve apresentar suas jogadas como saída para o jogo, e alternadamente receber como entrada as jogadas de seu adversário.

O programa deverá anunciar quando venceu o jogo, ou quando perdeu, ou quando houve um empate. De preferência, ele deve fazer isso esportivamente.

Fair Play é muito importante!

Avaliação

Os estudantes devem formar equipes de no mínimo uma e no máximo três pessoas. 

Estas equipes devem ser formadas e confirmadas por e-mail até o dia 31/03/2013. As pessoas que porventura não estiverem em nenhuma das equipes formadas até então serão colocadas arbitrariamente em equipes, juntamente com outros que eventualmente estejam na mesma situação.

Estas equipes construirão seus programas e participarão de um torneio de Lig S, em que seus algoritmos jogarão uns contra os outros, em jogos cujos parâmetros S, M e N serão definidos apenas no dia. 

Por uma questão de justiça, haverá jogos de ida e volta, e o critério de desempate será a quantidade de peças posicionadas na partida em que se venceu, se houver. Assim, jogando por exemplo as equipes A e B, caso a equipe A vença a primeira partida depositando 12 peças, e a equipe B vença a segunda partida depositando 16 peças, a equipe A será vencedora do confronto, pelo critério de desempate. Se o empate persistir, então o vencedor será definido em sorteio.

Quem vencer a primeira partida pode, naturalmente, jogar pelo empate na partida seguinte.

A equipe que vencer o torneio obterá nota 10 na avaliação deste projeto. As demais equipes serão penalizadas a cada vez que seu algoritmo tomar uma decisão flagrantemente estúpida. 

As equipes deverão apresentar um relatório descrevendo seus algoritmos, bem como seus pontos fortes e fracos. É desejável que seu algoritmo utilize heurísticas, mas também que ele faça alguma prospecção no espaço de estados do problema, a fim de decidir qual a melhor estratégia. Junto com a apresentação do relatório os membros da equipe serão arguídos, a fim de demonstrar domínio sobre o produto desenvolvido.